Théorème de complétude du 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 $\models P$.
• ou bien on montre que cette formule est prouvable ou dérivable en utilisant un système de déduction, et on note $⊢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 $⊢P$ est vérifié, alors $\models 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 $\models P$ est vérifié, le système de déduction doit permettre de prouver qu'on a également $⊢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.

Ce théorème a été prouvé par Paul Bernays en 1926.

Vérité et 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érité ou leur fausseté. On peut représenter les propositions par des lettres, p, q, r, ... et 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 $\neg$, et $\wedge$, ou $\vee$, implique $\to$. Ses axiomes sont données par les tables de vérité suivantes :

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

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

On en conclut que $\neg (p\wedge \neg 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.

Preuve du théorème de complétude

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

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

si $⊢P\to Q$ et $⊢P\to R$, alors $⊢P\to Q\wedge R$.

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

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

Nous allons maintenant prouver que, dans ces systèmes :

(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, donnons-nous un ensemble infini dénombrable, ordonné par les entiers positifs, de propositions atomiques, toutes distinctes, p₁, p₂, p₃... Un modèle initial de longueur n contient ou bien p_i = V ou bien p_i = F, mais pas les deux, pour $1\le i\le n$. Comme une proposition P ne contient qu’un nombre fini de propositions atomiques, notons n le plus grand indice d'une proposition p_n ayant 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 où sa vérité est définie, puisque les propositions p_m n'interviennent pas dans P pour m > n.

Pour prouver (i), on va d’abord prouver (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}$.

(ii) Si P est vraie dans le modèle $\mathcal{M}$ alors $⊢h(\mathcal{M})\to P$.

(iii) Si P est fausse dans le modèle $\mathcal{M}$ alors $⊢h(\mathcal{M})\to \neg P$.

On va prouver (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 $(\neg p)\vee (q\wedge 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 prouvée pour les propositions de complexité 0. La preuve 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=\neg 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, $⊢h(\mathcal{M})\to \neg Q$. (ii) est donc prouvé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 $⊢h(\mathcal{M})\to Q$. Par ailleurs, on sait que $⊢Q\to \neg \neg Q$. On peut alors déduire que $⊢h(\mathcal{M})\to \neg \neg Q$. (iii) est donc prouvée pour P dans ce cas.

b) il y a R et S tels que $P=R\wedge 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 $⊢h(\mathcal{M})\to R$ et $⊢h(\mathcal{M})\to S$. On en déduit que $⊢h(\mathcal{M})\to R\wedge S$. (ii) est donc prouvé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 $⊢h(\mathcal{M})\to \neg R$. Or, de $\neg R$, on peut déduire $\neg (R\wedge S)$. (iii) est donc prouvée pour P dans ce cas.

Cela termine cette preuve de (ii) et (iii).

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₁. Supposons que P est vraie dans tous les modèles de longueur 1, c’est-à-dire les deux modèles p₁ = V et p₁ = F. On a alors, d'après (ii) $⊢p_1\to P$ et $⊢\neg p_1\to P$. Par la règle de disjonction des hypothèses, on en déduit que $⊢(p_1\vee \neg p_1)\to P$ mais $p_1\vee \neg 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 prouver que $⊢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 $⊢(h(\mathcal{M})\wedge p_{n+1})\to P$ et $⊢(h(\mathcal{M})\wedge \neg p_{n+1})\to P$. Comme ci-dessus, on en déduit que $⊢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 $⊢P$. I_{n + 1} est donc vérifiée.

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