Université Mouloud MAMMERI de Tizi-Ouzou

Faculté de génie électrique et informatique

Département d’informatique
Module : Logique Mathématique – L2 – année : 2022/2023

Chapitre II

Calcul Propositionnel Formel

Par : Mr HABET Md-Said

(reprise des notes de cours de Mr KHEMLICHE Salem)

Contenu du chapitre :
II.1/ Introduction
II.2/ Système formel pour le calcul propositionnel
II.3/ Adéquation et complétude du CPF
II.4/ Cohérence
 Chapitre II : Le calcul propositionnel formel

II.1/ Introduction :
La technique des tables de vérité (TV) dans l’étude de la validité d’un argument montre ses limites dès
lors que le nombre de variables propositionnelles (v.p) devient grand (la taille de la TV est de 2n lignes, ce
qui est difficile à utiliser et exploiter, n étant le nombre de v.p).
Une autre approche a été utilisée pour démontrer la validité des formules : c’est la formalisation par les
systèmes formels.
Tout système formel est composé de :
1. un alphabet (ensemble de symboles utilisés) ;
2. un ensemble de suites finies de symboles appelés formules bien formées (fbf) : ce sont les phrases
du langage ;
3. un ensemble fini de formules appelées axiomes ;
4. un ensemble fini de règles d’inférence.

Définition II.1.1 :
Une règle d’inférence est la représentation d’un procédé permettant, à partir d’une ou plusieurs
formules, de dériver d’autres formules.

II.2/ Système formel pour le calcul propositionnel :

Définition II.2.1 :
Le système formel du calcul propositionnel (CPF) est défini par :
1. L’alphabet composé de :
(i) variables propositionnelles (v.p) : a, b, c, …, z
(ii) connecteurs :  , 
(iii) parenthèses : (, )
2. L’ensemble des formules bien formées (fbf) : définies par :
(i) Toute v.p est une fbf.
(ii) Si A et B sont des fbfs alors (A) et (A  B) sont des fbfs.
(iii) Toute fbf est obtenue par l’application d’un nombre fini de fois des clauses (i) et (ii).
3. Les axiomes :
(Ax1) (A  (B  A))
(Ax2) (A  (B  C))  ((A  B)  (A  C))
(Ax3) (B  A)  (A  B)
où A, B et C sont des fbfs quelconques.
4. La règle d’inférence appelée Modus Ponens (MP) :
A, A  B
; où : A et B sont des fbfs quelconques
B
5. Règle de substitution :
À partir d’une formule B contenant la variable x, on peut obtenir la formule : [A/x] B obtenue en
remplaçant toutes les occurrences de x dans B par la formule A.

-2-
 Chapitre II : Le calcul propositionnel formel

La substitution est écrite comme suit :

B
; où : A et B sont des fbfs quelconques, et x variable ayant des occurrences dans B
[A/x] B

Remarque :
Le choix de l’ensemble des axiomes défini le système formel. Il existe plusieurs systèmes formels pour
le calcul propositionnel. Le système présenté dans la définition II.2.1 est le plus étudié dans la littérature.

Définition II.2.2 : (démonstration)

Une démonstration dans le calcul propositionnel formel est une suite finie de fbf A1, A2, …, An telle que
Ai est soit un axiome ou se déduit par Modus Ponens à partir de deux éléments A j et Ak avec j < i et k < i.
On dit que A1, A2, …, An est une démonstration de An.
La formule An est un théorème et on note : ⊢ An.

Remarque :
a) Dans la définition II.2.2, Aj et Ak doivent être de la forme B et (B  Ai) respectivement.
b) Si A1, A2, …, An est une démonstration et k<n alors A1, A2, …, Ak est une démonstration et Ak est un
théorème.

Définition II.2.3 : (déduction)

Soit F un ensemble de fbf. La suite de formules A1, A2, …, An est appelée déduction si pour tout i
(1 ≤ i ≤ n), nous avons l’un des cas suivants :
1. Ai est un axiome du CPF.
2. Ai est un élément de F.
3. Ai est obtenu par application du (MP) aux éléments précédents de la suite.
An est une déduction à partir de F, et on note : F ⊢ An.

Remarques :
• L’écriture : ⊢ A signifie que A est un théorème.
L’écriture : F ⊢ A signifie que A est déductible de F.
• Une démonstration est une déduction sans hypothèses.
• On peut utiliser dans une déduction ou une démonstration un théorème déjà démontré.

Exemple 1 : Montrons : {A, (B  (A  C))} ⊢ (B  C)

1. A hypothèse
2. B  (A  C) hypothèse
3. (B  (A  C))  ((B  A)  (B  C)) Ax2
4. (B  A)  (B  C) MP + 2. + 3.
5. A  (B  A) Ax1
6. B  A MP + 1. + 5.
7. B  C MP + 4. + 6.

-3-
 Chapitre II : Le calcul propositionnel formel

Exemple 2 : Démonstration de : ⊢ (A  A)
1. (A  ((A  A)  A))  ((A  (A  A))  (A  A)) Ax2
2. A  ((A  A)  A) Ax1
3. (A  (A  A))  (A  A) MP + 1. + 2.
4. A  (A  A) Ax1
5. A  A MP + 3. + 4.

Exemple 3 : Déduction de : {B  (B  A)} ⊢ (B  A)

1. B  (B  A) hypothèse
2. (B  (B  A))  ((B  B)  (B  A)) Ax2
3. (B  B)  (B  A) MP + 1. + 2.
4. (B  B) théorème (exemple 2)
5. B  A MP + 3. + 4.
Donc : {B  (B  A)} ⊢ (B  A).
On écrit aussi (de manière plus allégée) : B  (B  A) ⊢ (B  A).

II.2.4/ Théorème de déduction :

Soit Γ un ensemble de fbf et A, B deux fbf.
Si Γ ∪ {A} ⊢ B alors Γ ⊢ (A  B).

Démonstration :
Par récurrence sur la longueur de la déduction de B.
Soit B1, …, Bn = B cette déduction.
Pour n = 1 : B1 = B alors nous avons les trois cas suivants :
Cas 1 : B est un axiome ; la déduction de A  B à partir de Γ est la suivante :
1. B axiome
2. B  (A  B) Ax1
3. A  B MP + 1. + 2.
d’où : Γ ⊢ (A  B).
Cas 2 : B est un élément de Γ ; la déduction de A  B à partir de Γ est la suivante :
1. B hypothèse (élément de Γ)
2. B  (A  B) Ax1
3. A  B MP + 1. + 2.
d’où : B ⊢ (A  B) donc Γ ⊢ (A  B).
Cas 3 : B est A ; (A  B) devient (A  A).
On sait que A  A est un théorème donc Γ ⊢ (A  A) i.e : Γ ⊢ (A  B).

Supposons que la propriété est vraie pour toute longueur n de la déduction de B tel que 1 ≤ n ≤ k
et montrons qu’elle reste vraie pour n = k+1.

-4-
 Chapitre II : Le calcul propositionnel formel

La (k+1)ième formule de la déduction de B est un des cas suivants :

Cas 1 : B est un axiome. C’est un cas identique au cas 1 précédent (n=1), d’où : Γ ⊢ (A  B).
Cas 2 : B ∈ Γ. C’est le même cas que le cas 2 précédent (n=1), d’où : Γ ⊢ (A  B).
Cas 3 : B est A. C’est le même cas que le cas 3 précédent (n=1), d’où : Γ ⊢ (A  B).
Cas 4 : B est obtenue à partir de deux fbf précédentes par application du MP. Ces deux formules doivent
être de la forme : C et C  B, où C est une fbf quelconque. Chacune d’elles est déduite à partir de
Γ ∪ {A} et chacune d’elles a une déduction de longueur ≤ k ; donc par hypothèse de récurrence :
Γ ⊢ (A  C) et Γ ⊢ (A  (C  B)).
La déduction de A  B à partir de Γ est :
1. ⊢…
2. ⊢
.
.
.
i. ⊢ (A  C).
.
.
j. ⊢ A  (C  B)
j+1. ⊢ (A  (C  B))  ((A  C)  (A  B)) Ax2
j+2. ⊢ (A  C)  (A  B) MP + j. + (j+1).
j+3. ⊢ A  B MP + i. + (j+2).
d’où : Γ ⊢ (A  B). CQFD.

Proposition II.2.5 : (Réciproque du théorème de déduction)

Soit Γ un ensemble de fbf et A, B deux fbf.
Si Γ ⊢ (A  B) alors Γ ∪ {A} ⊢ B.

Démonstration :
Soit une déduction de A  B à partir de Γ, notre objectif est de construire une déduction de B à partir
de : Γ ∪ {A}.
1. ⊢
2. ⊢
.
.
.
n. ⊢ A  B
n+1. ⊢ A hypothèse (élément de Γ ∪ {A})
n+2. ⊢ B MP + n. + (n+1).
Donc : Γ ∪ {A} ⊢ B.

-5-
 Chapitre II : Le calcul propositionnel formel

Corollaire II.2.6 : (Syllogisme hypothétique ou transitivité)

Pour toutes fbf A, B et C, nous avons :
(A  B), (B  C) ⊢ (A  C)

Démonstration :
1. ⊢ A  B hypothèse
2. ⊢ B  C hypothèse
3. ⊢ A hypothèse
4. ⊢ B MP + 1. + 3.
5. ⊢ C MP + 2. + 4.
Donc : (A  B), (B  C), A ⊢ C.
En appliquant le théorème de déduction, on aura : (A  B), (B  C) ⊢ (A  C).

Exemple 4 : ⊢ ((A  B)  C)  (B  C) par déduction

1. (A  B)  C hypothèse
2. B  (A  B) Ax1
3. B  C Transitivité + 1. + 2.
Donc : (A  B)  C ⊢ (B  C) ; en appliquant le théorème de déduction, on obtient :
⊢ ((A  B)  C)  (B  C).

Exercice 1 :
Trouver une démonstration de ⊢ ((A  B)  C)  (B  C).

II.3/ Adéquation et complétude du CPF :

II.3.1 Théorème d’adéquation :
Tout théorème du CPF est une tautologie, i.e : ⊢ Φ ⟹ ⊨ Φ.

Démonstration :
Il s’agit de vérifier que tous les axiomes sont des tautologies et montrer ensuite que dans une
démonstration, chaque formule est une tautologie. En effet, chaque formule intermédiaire est soit un
axiome, soit une formule obtenue par Modus Ponens à partir de deux tautologies de la forme B et B  C
donc C est une tautologie.

II.3.2 Théorème de complétude :

Toute tautologie est un théorème, i.e : ⊨ Φ ⟹ ⊢ Φ.

-6-
 Chapitre II : Le calcul propositionnel formel

Lemme :
Soit A une formule à variables parmi {p1, ..., pn}.
pi si pi = 1
On pose p′i = p
i si pi = 0

A si A = 1
et A′ =
A si A = 0

Alors : { p1′ , … , p′n } ⊢ A′

Démonstration du lemme :
Par récurrence sur le nombre n de connecteurs  et  contenus dans A.
Si n = 0 : alors A = pi et pi ⊢ pi et ainsi p1′ ⊢ A′
Supposons que la propriété reste vraie pour un nombre n de connecteurs  et  contenus dans A
avec 0 ≤ n ≤ k ; montrons qu’elle reste vraie pour n = k+1.
- Si A = B :
• si B vaut 0 alors B′ = B = A = A′ donc par hypothèse de récurrence (HR) : { p1′ , … , p′n } ⊢ B′
donc { p1′ , … , p′n } ⊢ A′ .
• si B vaut 1 alors B′ = B et A′ = B. Par (HR) on a : { p1′ , … , p′n } ⊢ B ou bien :
{ p1′ , … , p′n } ⊢ B donc { p1′ , … , p′n } ⊢ A′ .
- Si A = (B  C) :
Par (HR) : { p1′ , … , p′n } ⊢ B′ et { p1′ , … , p′n } ⊢ C′ . Il y a trois cas :
• Si B = 0 alors B′ = B et (B  C) = 1 donc A′ = A
on a : { p1′ , … , p′n } ⊢ B ; en vertu du théorème ⊢ B  (B  C), on déduit :
{ p1′ , … , p′n } ⊢ (B  C), c'est-à-dire : { p1′ , … , p′n } ⊢ A′ .
• Si C = 1 alors A vaut 1 et A′ = A, C′ = C ; donc { p1′ , … , p′n } ⊢ C ;
or ⊢ C  (B  C) Ax1
Par MP on obtient : { p1′ , … , p′n } ⊢ (B  C), c'est-à-dire : { p1′ , … , p′n } ⊢ A′ .
• Si B vaut 1 et C vaut 0 alors B′ = B et C′ = C et A′ = A ;
donc : { p1′ , … , p′n } ⊢ B
{ p1′ , … , p′n } ⊢ C
D’après le théorème : ⊢ B  (C  (B  C)), on obtient : { p1′ , … , p′n } ⊢ (B  C)
i.e : { p1′ , … , p′n } ⊢ A d’où { p1′ , … , p′n } ⊢ A′ .

Démonstration du théorème de complétude :

Soit A une tautologie contenant les variables p1 , … , pk .
D’après le lemme précédent A′ ≡ A et on a : { p1′ , … , p′k } ⊢ A′ .
Si pk prend la valeur 1 alors { p1′ , … , p′k−1 , pk } ⊢ A (1)
Si pk prend la valeur 0 alors { p1′ , … , p′k−1 , pk } ⊢ A (2)
En appliquant le théorème de déduction à (1) on obtient : { p1′ , … , p′k−1 } ⊢ (pk  A) (3)
En l’appliquant à (2), on aura : { p1′ , … , p′k−1 } ⊢ (pk  A) (4)

-7-
 Chapitre II : Le calcul propositionnel formel

De plus, on a le théorème : ⊢ pk  A  ((pk  A)  A) (5)

D’où : (6) { p1′ , … , p′k−1 } ⊢ pk  A  A MP + (5) + (3)
Et : (7) { p1′ , … , p′k−1 } ⊢ A MP + (6) + (4)
On a éliminé p′k .
On recommence le même raisonnement pour éliminer tous les atomes p′k−1 , p′k−2 , . . . , p1′
et on aboutit finalement à : ⊢ A.

II.4/ Cohérence :
Définition II.4.1 :
Une théorie est dite cohérente ou consistante s’il n’existe pas de fbf A telle que A et A soient toutes
les deux des théorèmes. Sinon elle est dite incohérente ou inconsistante.

Corollaire II.4.2 :
Le système de CPF est consistent : il n’existe aucune formule A telle que ⊢ A et ⊢ A.

Preuve :
D’après le théorème d’adéquation, tout théorème A est une tautologie ; par conséquent A n’est pas
une tautologie et d’après le même théorème A n’est pas un théorème.

Exercice :
1) Montrer qu’il existe A tel que ⊢ A et ⊢ A si et seulement si pour toute formule B, on a : ⊢ B.
2) Soit CPF’ le calcul obtenu à partir du CPF en ajoutant comme quatrième axiome la formule
suivante :
(Ax4) ⊢ A  (A  B).
Montrer que CPF’ est inconsistant.

----------=====---------- Fin du chapitre II ----------=====----------

-8-