Théorème de complétude (calcul des propositions)

Le calcul des propositions est un calcul logique restreint. On emploie souvent le nom de proposition pour désigner une formule logique non quantifiée. Il existe deux façons de valider une formule $P$ du calcul des propositions :

• ou bien on montre que cette formule est vraie dans tout modèle (voir ci-dessous). On dit alors que $P$ est une tautologie, et on note $\vDash P$.
• ou bien on montre que cette formule est prouvable ou dérivable en utilisant un système de déduction, et on note $\vdash P$.

Un système de déduction correct doit être construit de façon que, à partir de formules vraies (tautologies), on puisse déduire d'autres formules vraies. Dans ce cas, si $\vdash P$ est vérifié, alors $\vDash P$ l'est également.

Le système de déduction sera complet, si inversement, il permet de déduire toute formule vraie. Autrement dit, si $\vDash P$ est vérifié, le système de déduction doit permettre de démontrer qu'on a également $\vdash P$.

Le théorème de complétude du calcul des propositions énonce que les systèmes de déduction, décrits dans les articles calcul des propositions ou déduction naturelle ou calcul des séquents, sont complets. Il y a équivalence entre être une tautologie et être prouvable.

Le théorème de complétude du calcul des propositions classique a été démontré par Paul Bernays en 1926.

Approche classique de la véracité et de la fausseté d'une proposition dans un modèle

Pour le calcul des propositions, il n’est pas nécessaire d’analyser la structure des formules atomiques en prédicats et objets. La seule propriété des propositions atomiques qui compte dans les calculs de la logique classique est leur véracité ou leur fausseté. Si on représente les propositions atomiques par des lettres, $p$, $q$, $r$, ... ; on peut les concevoir comme des variables qui peuvent recevoir deux valeurs, $V$ pour vrai, et $F$ pour faux.

Un modèle est défini par l’attribution de valeurs de vérité, $V$ ou $F$, aux propositions atomiques. Par exemple $(p=V,q=F,r=V)$ désigne le modèle ${\mathcal {M}}$ dans lequel il y a trois propositions atomiques $p$, $q$, et $r$, la seconde étant fausse et les deux autres vraies.

On peut définir un calcul des vérités semblable au calcul des nombres et utilisant les connecteurs logiques non $\lnot$, et $\land$, ou $\lor$, implique $\to$. Ses axiomes sont données par les tables de vérité suivantes :

• $\lnot V=F,\lnot F=V$
• $V\land V=V,V\land F=F\land V=F\land F=F$

Les règles relatives à $\lor$ et $\to$ s'en déduisent en posant :

• $P\lor Q=\lnot (\lnot P\land \lnot Q)$
• $P\to Q=\lnot P\lor Q$

On peut alors calculer, par exemple, que dans le modèle ${\mathcal {M}}$ défini par $p=F$ :

$\lnot (p\land \lnot p)=\lnot (F\land \lnot F)=\lnot (F\land V)=\lnot F=V$

On en conclut que $\lnot (p\land \lnot p)$ est vraie dans le modèle $p=F$. On montre de même qu'elle est aussi vraie dans le modèle $p=V$ et puisqu’elle ne contient que $p$ comme proposition atomique, elle est vraie dans tous les modèles et est donc une tautologie.

Démonstration du théorème de complétude du calcul des propositions classique

Systèmes de déduction

On peut montrer que les systèmes de déduction cités en préambule permettent en particulier d'effectuer les déductions suivantes :

$\vdash P\to P$ (identité), $\vdash \lnot P\lor P$ (principe du tiers exclu), $\vdash P\to \lnot \lnot P$ et $\vdash \lnot \lnot P\to P$ (simplification de la double négation ou raisonnement par l'absurde).

si $\vdash P\to Q$ et $\vdash P\to R$, alors $\vdash P\to Q\land R$.

$\vdash \lnot R\to \lnot (R\land Q)$

si $\vdash P\to R$ et $\vdash Q\to R$, alors $\vdash P\lor Q\to R$ (disjonction des hypothèses).

si $\vdash P$ et $\vdash P\to Q$, alors $\vdash Q$ (modus ponens).

Nous allons maintenant démontrer que, dans ces systèmes :

théorème (i) — Si une proposition est une tautologie alors elle est dérivable.

Il suffit de montrer le théorème pour des modèles finis. En effet, ordonnons linéairement les propositions atomiques, nous obtenons la suite $p_{1}$, $p_{2}$, $p_{3}$... Un modèle initial ou bien valide $p_{i}$ ou bien ne valide pas $p_{i}$, mais ne fait pas les deux. Comme une proposition $P$ ne contient qu’un nombre fini de propositions atomiques, notons $n$ le plus grand indice parmi ceux des propositions $p_{n}$ qui ont une occurrence dans $P$. Si $P$ est vraie dans tous les modèles initiaux de longueur $n$, alors elle est vraie dans tous les modèles, puisque les propositions $p_{m}$ n'ont pas d'occurrence dans $P$ quand $m>n$, donc la valeur de vérité de ces propositions atomiques n'a aucune incidence sur la véracité de $P$.

Démonstration d'un résultat liminaire

Pour démontrer (i), on va d’abord démontrer (ii) et (iii) ci-dessous. Soit $P$ une formule propositionnelle, et ${\mathcal {M}}$ un modèle. Notons $h({\mathcal {M}})$ la conjonction de toutes les formules atomiques $p_{n}$ telle que $p_{n}=V$ est dans ${\mathcal {M}}$ et de toutes les négations des formules atomiques $p_{n}$ telles que $p_{n}=F$ est dans ${\mathcal {M}}$.

théorème (ii) —  Si $P$ est vraie dans le modèle ${\mathcal {M}}$ alors $\vdash h({\mathcal {M}})\to P$.

théorème (iii) —  Si $P$ est fausse dans le modèle ${\mathcal {M}}$ alors $\vdash h({\mathcal {M}})\to \lnot P$.

On va démontrer (ii) par induction sur la complexité des formules. Celle-ci est mesurée par le nombre maximal d’opérateurs emboités. Par exemple dans $(\lnot p)\lor (q\land r)$ , le ou et le non sont emboités l’un dans l’autre. Mais le non et le et ne le sont pas. Cette proposition est de complexité 2 parce qu’elle a au maximum deux opérateurs emboités.

Soit $p_{i}$ une proposition de complexité 0, c’est-à-dire une proposition atomique. La formule $p_{i}\to p_{i}$ est dérivable, de même que toute formule du type $H\to p_{i}$, où $H$ est n’importe quelle conjonction de propositions atomiques ou de leurs négations qui contient $p_{i}$ parmi elles. Si $p_{i}$ est vraie dans le modèle ${\mathcal {M}}$, $h({\mathcal {M}})$ contient $p_{i}$. (ii) est donc démontrée pour les propositions de complexité 0. La démonstration de (iii) est identique.

Supposons que (ii) et (iii) soient vraies pour toutes les propositions de complexité au plus égale à $n$. Soit $P$ une proposition de complexité $n+1$. Deux cas sont possibles.

a) il y a un $Q$ tel que $P=\lnot Q$

• Si $P$ est vraie dans le modèle ${\mathcal {M}}$ alors $Q$ est fausse dans ${\mathcal {M}}$. Comme $Q$ est de complexité $n$, l’hypothèse d’induction donne, $\vdash h({\mathcal {M}})\to \lnot Q$. (ii) est donc démontrée pour $P$ dans ce cas.
• Si $P$ est fausse dans le modèle ${\mathcal {M}}$ alors $Q$ est vraie dans ${\mathcal {M}}$. On a donc par induction $\vdash h({\mathcal {M}})\to Q$. Par ailleurs, on sait que $\vdash Q\to \lnot \lnot Q$. On peut alors déduire que $\vdash h({\mathcal {M}})\to \lnot \lnot Q$. (iii) est donc démontrée pour $P$ dans ce cas.

b) il y a $R$ et $S$ tels que $P=R\land S$

• Si $P$ est vraie dans le modèle ${\mathcal {M}}$ alors $R$ et $S$ sont toutes les deux vraies dans ${\mathcal {M}}$. On a alors par induction $\vdash h({\mathcal {M}})\to R$ et $\vdash h({\mathcal {M}})\to S$. On en déduit que $\vdash h({\mathcal {M}})\to R\land S$. (ii) est donc démontrée pour $P$ dans ce cas.
• Si $P$ est fausse dans le modèle ${\mathcal {M}}$ alors l’une au moins de $R$ ou de $S$ est fausse dans ${\mathcal {M}}$. Supposons que ce soit $R$. On a alors par induction $\vdash h({\mathcal {M}})\to \lnot R$. Or, de $\lnot R$, on peut déduire $\lnot (R\land S)$. (iii) est donc démontrée pour $P$ dans ce cas.

Cela termine cette démonstration de (ii) et (iii).

Fin de la démonstration du théorème de complétude

Prouvons maintenant (i), le théorème de complétude, par induction sur la longueur des modèles. Soit $I_{n}$ l’énoncé : Si $P$ est vraie dans tous les modèles de longueur $n$ alors $P$ est dérivable. Démontrons par récurrence les énoncés $I_{n}$.

Prouvons d’abord $I_{1}$. Supposons que $P$ est vraie dans tous les modèles de longueur 1, c’est-à-dire les deux modèles $p_{1}=V$ et $p_{1}=F$. On a alors, d'après (ii) $\vdash p_{1}\to P$ et $\vdash \lnot p_{1}\to P$. Par la règle de disjonction des hypothèses, on en déduit que $\vdash (p_{1}\lor \lnot p_{1})\to P$ mais $p_{1}\lor \lnot p_{1}$ est elle-même une formule dérivable : c’est le principe du tiers-exclu. La règle du modus ponens suffit alors pour démontrer que $\vdash P$.

Supposons que $I_{n}$ soit vrai. Soit $P$ une proposition vraie dans tous les modèles de longueur $n+1$. Soit ${\mathcal {M}}$ un modèle de longueur $n$. $P$ est vraie dans $({\mathcal {M}},p_{n+1}=V)$ et dans $({\mathcal {M}},p_{n+1}=F)$. D'après (ii), on a alors $\vdash (h({\mathcal {M}})\land p_{n+1})\to P$ et $\vdash (h({\mathcal {M}})\land \lnot p_{n+1})\to P$. Comme ci-dessus, on en déduit que $\vdash h({\mathcal {M}})\to P$. Comme ${\mathcal {M}}$ un modèle quelconque de longueur $n$, l'hypothèse de récurrence $I_{n}$ permet de conclure que $\vdash P$. $I_{n+1}$ est donc vérifiée.

Cela termine cette démonstration du théorème de complétude du calcul des propositions.

Voir aussi

• Théorème de complétude de Gödel
• Théorèmes d'incomplétude de Gödel