Interprétation (logique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Interprétation.

En logique, une interprétation est une attribution de sens aux symboles d'un langage formel. Les langages formels utilisés en mathématiques, en logique et en informatique théorique ne sont définis dans un premier temps que syntaxiquement; pour en donner une définition complète, il faut expliquer comment ils fonctionnent et en donner une interprétation. Le domaine de la logique qui donne une interprétation aux langages formels s'appelle la sémantique formelle.

Introduction[modifier | modifier le code]

Pour plus de commodité, nous allons nous restreindre aux logiques formelles les plus souvent étudiées, à savoir, la logique propositionnelle, la logique des prédicats et la logique modale. Une interprétation est une fonction qui a pour domaine un langage formel et pour cible un modèle.

Si le modèle contient les booléens, une interprétation affecte à chaque proposition une valeur de vérité. Si pour une interprétation donnée, la fonction affecte la valeur Vrai à une proposition, l'interprétation est appelée la structure de la proposition.

Langages formels[modifier | modifier le code]

Un langage formel est composé d'une collection fixe de propositions (aussi appelés formules, en fonction du contexte), composé d'un ensemble fixe de lettres ou de symboles. L'inventaire de ces lettres sont prises est appelé l'alphabet (en) sur lequel la langue est définie. La caractéristique essentielle d'un langage formel est que sa syntaxe peut être défini sans référence à l'interprétation. Par exemple, nous pouvons déterminer que (P ou Q) est une formule bien formée, même sans savoir si elle est vraie ou fausse.

Exemple[modifier | modifier le code]

Un langage formel peut être défini avec l'alphabet α = { , }, et avec un mot étant en , si elle débute par et est uniquement composée de symboles et .

Une interprétation possible de pourrait être d'affecter le chiffre '1' à  et '0' à . Alors,  désignerait 101 sous l'interprétation de .

Logique constantes[modifier | modifier le code]

Dans le cas de la logique propositionnelle et de la logique des prédicats, les langages formels ont des alphabets qui sont divisés en deux ensembles: les symboles logiques (constantes logiques (en)) et les symboles non-logique. L'idée derrière cette terminologie est que les symboles logiques ont la même signification quel que soit le sujet étudié, tandis que les symboles non-logiques changent de sens selon la zone d'étude.

Les logiques constantes donnent toujours le même sens à chaque interprétation de la norme standard, de sorte que seul le sens des symboles non-logiques sont modifiées. Les logiques constantes incluent les symboles quantificateurs ∀ ("tous") et ∃ ("certains"), les connecteurs logiques ∧ ("et"), ∨ ("ou"), ¬ ("pas"), les parenthèses, et (dans de nombreux traitements) le symbole de l'égalité =.

Propriétés générales des interprétations vérifonctionnels[modifier | modifier le code]

Cette section traite de la logique classique. Pour d'autres approches, voir par exemple Logique intuitionniste.

De nombreuses interprétations couramment étudiées associent chaque proposition dans un langage formel avec une seule valeur de vérité, soit Vrai ou Faux. Ces interprétations sont appelés vérifonctionnelle[Informations douteuses] [?], ils comprennent les interprétations usuelles de la logique propositionnelle et du premier ordre. Les propositions qui sont dites vraie par une affectation particulière sont dit être satisfaite par cette affectation.

Aucune proposition ne peut se voir attribuer à la fois la valeur vrai et faux par la même interprétation[Informations douteuses] [?], mais il est possible que la valeur de vérité d'une même proposition peut différer selon différentes interprétations. Une proposition est cohérente que si elle est vraie dans au moins une interprétation; sinon, elle est incohérente. Une proposition φ est dit être logiquement valide si elle est satisfaite par toutes les interprétations (si φ est satisfaite par toute interprétation qui satisfait ψ alors φ est dit être une conséquence logique de ψ).

Connecteurs logiques[modifier | modifier le code]

Certains symboles logiques d'un langage (autres que les quantificateurs) sont lesconnecteurs logiques qui représentent la fonction de vérité — fonctions qui prennent des valeurs de vérité en tant qu'arguments et retourne les valeurs de vérité en sorties (en d'autres termes, ce sont des opérations faites les valeurs de vérité).

Le connecteur logique permet à des propostions composées à être construit à partir de simples propositions. Les connecteurs sont généralement vus comme des constantes logiques, ce qui signifie que le sens des connecteurs est toujours le même.

Nous définissons les connecteurs logiques de la manière suivante en logique propositionnelle:

  • ¬Φ est Vrai ssi Φ est Faux.
  • (Φ ∧ Ψ) est Vrai ssi Φ est Vrai et Ψ est Vrai.
  • (Φ ∨ Ψ) est Vrai ssi Φ est Vrai ou Ψ est Vrai (ou les deux).
  • (Φ → Ψ) est Vrai ssi Φ est Vrai ou Ψ est Vrai (ou les deux).[Informations douteuses] [?]
  • (Φ ↔ Ψ) est Vrai ssi (Φ → Ψ) est Vrai et (Ψ → Φ) est Vrai.

Donc, en vertu d'une interprétation donnée de toutes les lettres de la proposition Φ et Ψ, nous pouvons déterminer les valeurs de vérité de toutes les formules. Le tableau suivant montre à quoi ce genre de chose ressemble. Les deux premières colonnes montrent les valeurs de vérité des lettres. Les autres colonnes montrent les valeurs de vérité des formules construites à partir de ces lettres.

Connecteurs logiques
Interprétation Φ Ψ ¬Φ (Φ ∧ Ψ) (Φ ∨ Ψ) (Φ → Ψ) (Φ ↔ Ψ)
#1 V V F V V V V
#2 V F F F V F F
#3 F V V F V V F
#4 F F V F F V V

Maintenant, il est plus facile de voir ce qui rend une formule logique valide.

Interprétation d'une théorie[modifier | modifier le code]

Une interprétation d'une théorie est la relation entre une théorie et une matière quand il y a une correspondance entre certains énoncés élémentaires de la théorie, et certains énoncés relatifs à l'objet. Si chaque énoncé élémentaire dans la théorie a un correspondant, elle est appelée une interprétation complète, sinon, elle est appelée une interprétation partielle[1].

Interprétations pour la logique propositionnelle[modifier | modifier le code]

Le langage formel pour la logique propositionnelle se compose de formules construit à partir de symboles propositionnels et de connecteurs logiques. Le seul symbole non-logique dans un langage formel pour la logique propositionnelle sont les symboles propositionnelles, qui sont souvent notée par une lettre majuscule. Pour rendre le langage formel précis, un ensemble spécifique de propositionnelle symboles doit être fixé.

Le genre standard d'interprétation dans ce cadre est une fonction qui associe chaque symbole propositionnel à l'une des valeurs de vérité vrai et faux. Cette fonction est connue comme une assignation de véritéthéorie de la démonstrationthéorie de la démonstration.

Pour une langue avec n variables propositionnelles distinctes, il y a 2n interprétations possibles distinctes. Pour toute variable a, par exemple, il y a 21=2 interprétations possibles: 1) a est affecté V, ou 2) a est affecté F. Pour la paire a, b il y a 22=4 interprétations possibles: 1) les deux sont affectés V, 2) les deux sont affectés F, 3) a est affecté V et b est affecté F, ou 4) a est affecté F et b est affecté V.

Logique du premier ordre[modifier | modifier le code]

Contrairement à la logique propositionnelle, où chaque langage est le même, il y a beaucoup de langages de premier ordre différents. Chaque langage de premier ordre est défini par une signature. Dans le cas des symboles fonctionnels et prédicats, une arité est également attribué. L'alphabet du langage formel se compose de constantes logiques, du symbole de relation de l'égalité =, tous les symboles de la signature, et un ensemble infini de symboles connus comme des variables.

Interprétations d'un langage du premier ordre[modifier | modifier le code]

Pour attribuer un sens à toutes les propositions du langage du premier ordre, les informations suivantes sont nécessaires.

  • Un univers du discours D.
  • Pour chaque symbole, un élément de D en tant qu'interprétation.
  • Pour chaque symbole de fonction n-aire, une fonction n-aire de D à D en tant que son interprétation (qui est une fonction DnD).
  • Pour chaque symbole n-aire, une relation n-aire sur D en tant que son interprétation (qui est un sous-ensemble de Dn).

Un objet portant cette information est connue comme une structure (de la signature σ, ou la structure-σ, ou comme un "modèle".

Les informations spécifiées dans l'interprétation fournit suffisamment d'informations pour donner une valeur de vérité à toute formule atomique, après chacune de ses variables libres. La valeur de vérité d'une proposition arbitraire est alors défini par induction à l'aide du schéma-T, qui est une définition des sémantiques du premier ordre développé par Alfred Tarski. Le schéma-T interprète les connecteurs logiques à l'aide d'unetable de vérité. Ainsi, par exemple, φ & ψ est satisfait si et seulement si φ et ψ sont satisfaits.

Ce qui laisse la question de savoir comment interpréter les formules de la forme x φ(x) et x φ(x). L'idée est que la proposition x φ(x) est vraie en vertu d'une interprétation, où chaque les cas substitution de φ(x), où x est remplacé par un élément du domaine, est satisfait. La formule x φ(x) est satisfaite s'il existe au moins un élément de d du domaine tel que φ(d) est satisfaite.

Certains auteurs admettent aussi des variables propositionnelles dans la logique du premier ordre, qui doit alors aussi être interprétées. Une variable propositionnelle peut se 'tenir debout', comme une formule atomique. L'interprétation d'une variable propositionnelle est l'une des deux valeurs de vérité vrai et faux.

Parce que les interprétations de premier ordre décrites ici sont définies dans la théorie des ensembles, ils n'associent pas chaque symbole de prédicat avec une propriété (ou une relation), mais plutôt avec l'extension de cette propriété (ou relation). En d'autres termes, ces interprétations de premier ordre sont extensionelles, et non intensionnelles.

Exemple d'une interprétation de premier ordre[modifier | modifier le code]

Un exemple d'interprétation du langage L décrit ci-dessus est comme suit.

  • Domaine : Unjeu d'échecs
  • Constantes individuelles : a: Le Roi blanc, b: La Reine noire, c: Le pion du Roi blanc
  • F(x) : x est une pièce
  • G(x) : x est un pion
  • H(x) : x est noir
  • I(x) : x est blanc
  • J(x, y) : x peut prendre y
  • les données suivantes sont vraies : F(a), G(c), H(b), I(a) J(b, c),
  • les suivantes sont fausses : J(a, c), G(a).

Univers non-vide[modifier | modifier le code]

Comme indiqué plus haut, une interprétation de premier ordre est généralement nécessaire pour spécifier un ensemble non-vide comme le univers du discours. La raison de cette exigence est de garantir que les équivalences telles que

,

où x n'est pas une variable libre de φ, sont logiquement valide. Cette équivalence tient dans toutes les interprétations avec un univers non-vide, mais ne tient pas toujours lorsque les univers vides sont autorisés. Par exemple, l'équivalence

échoue dans une structure avec un univers vide. Ainsi, la théorie de la démonstration de la logique du premier ordre devient plus compliqué lorsque les structures vides sont autorisés[2]. théorie de la démonstration

Logique d'ordre supérieur[modifier | modifier le code]

Un langage formel pour la logique d'ordre supérieur ressemble beaucoup au langage formel dédié à la logique du premier ordre. La différence est qu'il y a beaucoup de variables de types différents. Certaines variables correspondent à des éléments de l'univers, comme dans la logique du premier ordre. D'autres variables correspondent à des objets de type supérieur: sous-ensembles de l'univers, fonctions de l'univers, fonctions prennent un sous-ensemble de l'univers et renvoyant une fonction à partir de l'univers des sous-ensembles de l'univers, etc. Tous ces types de variables peuvent être quantifiés.

Exemple[modifier | modifier le code]

Soit un système formel simple (que nous pouvons appeler ) dont l'alphabet α n'est composé que de trois symboles { , , } et dont la règle de formulation est:

'Toute chaîne de symboles de qui est composée d'au moins 6 symboles, et qui n'est pas infiniment longue, est une formule de

Le schéma d'axiome  est:

«  * * » (où « * » est une variable métasyntaxique pour une chaîne finie de «  »)

Une preuve formelle peut être construit comme suit:

(1)
(2)
(3)

Dans cet exemple, le théorème produit «   » peut être interprété comme «Un plus trois égal quatre.» Une interprétation différente serait de lire à l'envers : «Quatre moins trois égal un.»[3][réf. insuffisante]

Autres concepts d'interprétations[modifier | modifier le code]

Il existe d'autres utilisations du terme «interprétation» qui sont couramment utilisés, et qui ne se réfèrent pas à l'attribution de significations envers des langages formels.

Une théorie interprète une autre théorie S s'il y a une extension par des définitions T′ de T tel que S est contenu dans T′.

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) Haskell Curry, Foundations of Mathematical Logic, Mcgraw Hill,
  2. Mates, Benson (1972), Elementary Logic, Second Edition, New York: Oxford University Press, p. 56, (ISBN 0-19-501491-X)
  3. (en) Geoffrey Hunter, Metalogic: An Introduction to the Metatheory of Standard First Order Logic, University of California Press,

théorie de la démonstration

Liens externes[modifier | modifier le code]