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

Un article de Wikipédia, l'encyclopédie libre.

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 du calcul des propositions :

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

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 est vérifié, alors l'est également.

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

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[modifier | modifier le code]

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, , , , ... ; on peut les concevoir comme des variables qui peuvent recevoir deux valeurs, pour vrai, et pour faux.

Un modèle est défini par l’attribution de valeurs de vérité, ou , aux propositions atomiques. Par exemple désigne le modèle dans lequel il y a trois propositions atomiques , , et , 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 , et , ou , implique . Ses axiomes sont données par les tables de vérité suivantes :

Les règles relatives à et s'en déduisent en posant :


On peut alors calculer, par exemple, que dans le modèle défini par  :

On en conclut que est vraie dans le modèle . On montre de même qu'elle est aussi vraie dans le modèle et puisqu’elle ne contient que 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[modifier | modifier le code]

Systèmes de déduction[modifier | modifier le code]

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

(identité), (principe du tiers exclu), et (simplification de la double négation ou raisonnement par l'absurde).

si et , alors .

si et , alors (disjonction des hypothèses).

si et , alors (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 , , ... Un modèle initial ou bien valide ou bien ne valide pas , mais ne fait pas les deux. Comme une proposition ne contient qu’un nombre fini de propositions atomiques, notons le plus grand indice parmi ceux des propositions qui ont une occurrence dans . Si est vraie dans tous les modèles initiaux de longueur , alors elle est vraie dans tous les modèles, puisque les propositions n'ont pas d'occurrence dans quand , donc la valeur de vérité de ces propositions atomiques n'a aucune incidence sur la véracité de .

Démonstration d'un résultat liminaire[modifier | modifier le code]

Pour démontrer (i), on va d’abord démontrer (ii) et (iii) ci-dessous. Soit une formule propositionnelle, et un modèle. Notons la conjonction de toutes les formules atomiques telle que est dans et de toutes les négations des formules atomiques telles que est dans .

théorème (ii) —  Si est vraie dans le modèle alors .

théorème (iii) —  Si est fausse dans le modèle alors .


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 , 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 une proposition de complexité 0, c’est-à-dire une proposition atomique. La formule est dérivable, de même que toute formule du type , où est n’importe quelle conjonction de propositions atomiques ou de leurs négations qui contient parmi elles. Si est vraie dans le modèle , contient . (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 à . Soit une proposition de complexité . Deux cas sont possibles.

a) il y a un tel que

  • Si est vraie dans le modèle alors est fausse dans . Comme est de complexité , l’hypothèse d’induction donne, . (ii) est donc démontrée pour dans ce cas.
  • Si est fausse dans le modèle alors est vraie dans . On a donc par induction . Par ailleurs, on sait que . On peut alors déduire que . (iii) est donc démontrée pour dans ce cas.

b) il y a et tels que

  • Si est vraie dans le modèle alors et sont toutes les deux vraies dans . On a alors par induction et . On en déduit que . (ii) est donc démontrée pour dans ce cas.
  • Si est fausse dans le modèle alors l’une au moins de ou de est fausse dans . Supposons que ce soit . On a alors par induction . Or, de , on peut déduire . (iii) est donc démontrée pour dans ce cas.

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

Fin de la démonstration du théorème de complétude[modifier | modifier le code]

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


Prouvons d’abord . Supposons que est vraie dans tous les modèles de longueur 1, c’est-à-dire les deux modèles et . On a alors, d'après (ii) et . Par la règle de disjonction des hypothèses, on en déduit que mais 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 .


Supposons que soit vrai. Soit une proposition vraie dans tous les modèles de longueur . Soit un modèle de longueur . est vraie dans et dans . D'après (ii), on a alors et . Comme ci-dessus, on en déduit que . Comme un modèle quelconque de longueur , l'hypothèse de récurrence permet de conclure que . est donc vérifiée.

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

Voir aussi[modifier | modifier le code]