Proposition 1Logique du premier ordre

Tautologies et complétude fonctionnelle

Énoncé

Une valuation booléenne est une application $v$ des lettres propositionnelles dans $\{0, 1\}$ . Elle se prolonge de manière unique en une application $\bar v$ définie sur toutes les formules propositionnelles et compatible avec les tables de vérité : $\bar v(\neg\varphi) = 1 - \bar v(\varphi)$ , et $\bar v(\to \varphi\, \psi) = 0$ si et seulement si $\bar v(\varphi) = 1$ et $\bar v(\psi) = 0$ .

Une tautologie est une formule $\varphi$ telle que $\bar v(\varphi) = 1$ pour toute valuation $v$ .

Complétude fonctionnelle. Pour tout entier $n \geqslant 1$ et toute fonction $F : \{0,1\}^n \to \{0,1\}$ , il existe une formule $\varphi$ écrite avec les lettres $P_1, \dots, P_n$ et les seuls connecteurs $\neg$ et $\to$ , telle que $\bar v(\varphi) = F(v(P_1), \dots, v(P_n))$ pour toute valuation $v$ .

Démonstration

Le prolongement $\bar v$ est bien défini par récurrence sur les formules, grâce à la lecture unique, qui garantit que chaque formule non réduite à une lettre s'écrit d'une seule façon $\neg\varphi$ ou $\to \varphi\, \psi$ .

Pour la complétude fonctionnelle, notons, pour $\varepsilon \in \{0,1\}^n$ , $C_\varepsilon$ la conjonction des littéraux $P_i$ si $\varepsilon_i = 1$ et $\neg P_i$ si $\varepsilon_i = 0$ : par les tables de $\wedge$ et de $\neg$ , $\bar v(C_\varepsilon) = 1$ si et seulement si $v(P_i) = \varepsilon_i$ pour tout $i$ .

Si $F$ est identiquement nulle, la formule $P_1 \wedge \neg P_1$ convient. Sinon, la disjonction des $C_\varepsilon$ pour les $\varepsilon$ tels que $F(\varepsilon) = 1$ vaut $1$ exactement aux points où $F$ vaut $1$ . Comme $\wedge$ et $\vee$ sont des abréviations, cette formule s'écrit avec $\neg$ et $\to$ seuls.

□

Remarque

Savoir si une formule à $n$ lettres est une tautologie est un calcul fini : il suffit d'examiner les $2^n$ lignes de sa table. Par exemple, $\varphi \to (\psi \to \varphi)$ ne peut valoir $0$ que si $\varphi$ vaut $1$ et $\psi \to \varphi$ vaut $0$ , ce qui exige $\varphi = 0$ : c'est impossible, la formule est une tautologie.

Arbre de lecture de

\varphi \to (\psi \to \varphi)

, écrite

\to \varphi \to \psi\, \varphi

; chaque valeur entourée est imposée par la recherche d'une valuation qui donne

0

à la racine, la table de

\to

n'ayant qu'une ligne de valeur

0

. Les deux occurrences de

\varphi

reçoivent alors

1

0

, en rouge : aucune valuation ne convient.

Remarque

Au premier ordre, il n'existe en général plus de tel procédé : l'ensemble des énoncés universellement valides n'est pas décidable (Church, 1936 ; Turing, 1936), et il ne l'est déjà plus pour une signature qui contient un symbole de relation binaire. La notion de procédé décidable sera précisée par la théorie de la calculabilité.

Repose sur

Syntaxe du premier ordre

Sert à

Démonstrations formelles