I.
7 Série 2 : Calcul propositionnel : théorie de la démonstration
Correction de la Série 2 : Calcul propositionnel
Correction de l’exercice 1
1. On a ϕ1 |= ϕ3 , c’est à dire, la contrainte ϕ3 est une conséquence logique de la contrainte ϕ1
car, pour toute valuation v,
– v satisfait ϕ1 ssi v(p1 ) = 0 et v(p2 ) = 1,
– v satisfait ϕ3 ssi v(p2 ) = 1 et (v(p1 ) = 0 ou v(p3 ) = 1).
D’où, mod(ϕ1 ) ⊆ mod(ϕ3 ). Soit Γ2 = {ϕ1 , ϕ2 }, on a mod(Γ2 ) = mod(Γ1 ) car
mod(Γ1 ) = mod(ϕ1 ) ∩ mod(ϕ2 ) ∩ mod(ϕ3 ) = mod(ϕ1 ) ∩ mod(ϕ2 ) = mod(Γ2 ).
Donc les conséquences de Γ1 et Γ2 sont les mêmes et on peut alors simplifier Γ1 par Γ2 .
2. Afin de déterminer l’ensemble des modèles de Γ2 , on détermine la table de vérité de ϕ1 et ϕ2
p1 p2 p3 p4 ϕ1 p1 ∨ p4 ϕ2 p3 ∨ ¬p1 ϕ3
1 1 1 1 0 1 1 1 1
1 1 1 0 0 1 1 1 1
1 1 0 1 0 1 1 0 0
1 1 0 0 0 1 1 0 0
1 0 1 1 0 1 1 1 0
1 0 1 0 0 1 1 1 0
1 0 0 1 0 1 1 0 0
1 0 0 0 0 1 1 0 0
0 1 1 1 1 1 1 1 1
0 1 1 0 1 0 0 1 1
0 1 0 1 1 1 1 1 1
0 1 0 0 1 0 1 1 1
0 0 1 1 0 1 1 1 0
0 0 1 0 0 0 0 1 0
0 0 0 1 0 1 1 1 0
0 0 0 0 0 0 1 1 0
L’ensemble M des modèles de Γ2 = {ϕ1 , ϕ2 } est l’intersections des modèles de ϕ1 et ϕ2 :
p1 p2 p3 p4
0 1 1 1
0 1 0 1
0 1 0 0
Remarquons que la table de vérité montre bien que l’ensemble des modèles de Γ2 est le même
que celui de Γ3 .
27
Chapitre I. Logique des propositions
3. Γ2 admet au moins un modèle (il y en a trois), il est donc satisfaisable (ou consistante, ou encore
cohérente et non contradictoire.
4. Les conséquences logiques de Γ2 sont toutes les formules dont l’ensemble des modèles contient
M . On a donc entre autres :
¬p1 , p2 , p1 ⇒ p2 , p1 ∨ p2 , p1 ⇒ p3 , p1 ⇒ p4 , p3 ⇒ p4 , p4 ⇒ p2 .
5. Soit
Γ3 = Γ2 ∪ {p2 ⇒ p3 }.
L’ensemble des modèles de Γ3 est l’intersections des modèles de Γ2 et {p2 ⇒ p3 } :
p1 p2 p3 p4
0 1 1 1
Donc Γ3 admet au moins un modèle (il y en a un seul), il est donc satisfaisable.
Correction de l’exercice 2
1. Soit la formule
G = ¬A ∨ (B ⇒ C) ∧ (A ⇒ B) ∧ A ∧ ¬C.
Après élimination des implications, on obtient une clause conjonctive :
G = (¬A ∨ ¬B ∨ C) ∧ (¬A ∨ B) ∧ A ∧ ¬C.
Cette formule G s’écrit comme l’ensemble de clauses
C = {(¬A ∨ ¬B ∨ C), (¬A ∨ B), A, ¬C}.
En utilisant les règles d’inférence pour la méthode de la coupure, on a
¬A ∨ ¬B ∨ C ¬C Coupure
¬A ∨ ¬B ¬A ∨ B Coupure
¬A ∨ ¬A factorisation
¬A A Coupure
⊥
Puisqu’on arrive à dériver la clause vide, la formule G est contradictoire ou insatisfiable.
2. (a) Soit la formule
F = ((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
Après élimination des implications, on obtient une clause disjonctive :
F = ¬(¬A ∨ B) ∨ ¬(¬B ∨ C) ∨ ¬A ∨ C
28
I.7 Série 2 : Calcul propositionnel : théorie de la démonstration
Ainsi, ¬F est une clause conjonctive qui s’écrit comme suit :
¬F = (¬A ∨ B) ∧ (¬B ∨ C) ∧ A ∧ ¬C
Cette formule ¬F s’écrit comme l’ensemble de clauses
C = {(¬A ∨ B), (¬B ∨ C), A, ¬C}.
En utilisant les règles d’inférence pour la méthode de la coupure, on a
¬A ∨ B A Coupure
B ¬B ∨ C Coupure
C ¬C Coupure
⊥
Puisqu’on arrive à dériver la clause vide, la formule ¬F est contradictoire, et par suite, la
formule F est une tautologie (ou valide).
(b) Soit la formule
K = ((¬A ⇒ B) ∨ C) ⇒ (¬C ⇒ (¬A ⇒ B))
Après élimination des implications, on obtient une clause disjonctive :
K =(A ∨ B ∨ C) ⇒ (C ∨ A ∨ B)
=(¬A ∧ ¬B ∧ ¬C) ∨ C ∨ A ∨ B
Ainsi, ¬K est une clause conjonctive qui s’écrit comme suit :
¬K = (A ∨ B ∨ C) ∧ ¬C ∧ ¬A ∧ ¬B
Cette formule ¬K s’écrit comme l’ensemble de clauses
C = {(A ∨ B ∨ C), ¬A, ¬B, ¬C}.
En utilisant les règles d’inférence pour la méthode de la coupure, on a
A∨B∨C ¬C Coupure
A∨B ¬B Coupure
A ¬A Coupure
⊥
Puisqu’on arrive à dériver la clause vide, la formule ¬K est contradictoire, et par suite, la
formule K est une tautologie.
(c) Soit la formule
L = ¬((¬A) ⇒ (¬((¬B) ∧ ((¬B) ⇒ A))))
29
Chapitre I. Logique des propositions
Après élimination des implications, on obtient une clause conjonctive :
L =¬(A ∨ (¬((¬B) ∧ (B ∨ A))))
=¬A ∧ ¬B ∧ (B ∨ A)
Cette formule L s’écrit comme l’ensemble de clauses
C = {¬A, ¬B, (B ∨ A)}.
En utilisant les règles d’inférence pour la méthode de la coupure, on a
B∨A ¬A Coupure
B ¬B Coupure
⊥
Puisqu’on arrive à dériver la clause vide, la formule L est contradictoire.
(d) Soit la formule
M = ((B ∧ (¬C ∧ D)) ⇒ A) ∨ ¬(E ∧ A)
Après élimination des implications, on obtient une clause disjonctive :
M =(¬(B ∧ (¬C ∧ D)) ∨ A) ∨ ¬(E ∧ A)
=¬B ∨ C ∨ ¬D ∨ A ∨ ¬E ∨ ¬A
Ainsi, ¬M est une clause conjonctive qui s’écrit comme suit :
¬M = B ∧ ¬C ∧ D ∧ ¬A ∧ E ∧ A
Cette formule ¬M s’écrit comme l’ensemble de clauses
C = {A, ¬A, B, ¬C, D, E}.
Comme A ∧ ¬A =⊥, donc la formule ¬M est contradictoire, et par suite, la formule M est
une tautologie.
(e) Soit la formule
N = ((¬B ∧ A) ⇒ ¬C) ⇒ ((A ∧ C) ⇒ B)
Après élimination des implications, on obtient une clause disjonctive :
N =¬(¬(¬B ∧ A) ∨ ¬C) ∨ (¬(A ∧ C) ∨ B)
=(¬B ∧ A ∧ C) ∨ ¬A ∨ ¬C ∨ B
30
I.7 Série 2 : Calcul propositionnel : théorie de la démonstration
Ainsi, ¬N est une clause conjonctive qui s’écrit comme suit :
¬N = (B ∨ ¬A ∨ ¬C) ∧ A ∧ C ∧ ¬B
Cette formule ¬N s’écrit comme l’ensemble de clauses
C = {(¬A ∨ B ∨ ¬C), A, ¬B, C}.
En utilisant les règles d’inférence pour la méthode de la coupure, on a
(¬A ∨ B ∨ ¬C) C Coupure
¬A ∨ B ¬B Coupure
¬A A Coupure
⊥
Puisqu’on arrive à dériver la clause vide, la formule ¬N est contradictoire, et par suite, la
formule N est une tautologie.
Correction de l’exercice 3 On a le système d’axiomes suivant :
A1 : α ⇒ (β ⇒ α);
A2 : (α ⇒ (β ⇒ γ)) ⇒ ((α ⇒ β) ⇒ (α ⇒ γ));
A3 : (¬β ⇒ ¬α) ⇒ (α ⇒ β);
et la règle du Modus Ponens : si ` α et ` α ⇒ β, alors ` β.
1. Montrer que si ` α, alors ` β ⇒ α (qu’on nommera après R1 ).
Preuve :
1, ` α Hypothèse ;
2, α ⇒ (β ⇒ α) A1 ;
3, β ⇒ α Modus Ponens (1,2).
2. Montrer que si ` (α ⇒ β) et ` (β ⇒ γ), alors ` (α ⇒ γ) (qu’on nommera après R2 ).
Preuve :
1, β ⇒ γ Hypothèse ;
2, (α ⇒ (β ⇒ γ)) Application du résultat de la question 1 (R1 ) ;
3, (α ⇒ (β ⇒ γ)) ⇒ ((α ⇒ β) ⇒ (α ⇒ γ)) A2 ;
4, (α ⇒ β) ⇒ (α ⇒ γ) Modus Ponens (3,2) ;
5, α ⇒ β Hypothèse ;
6, α ⇒ γ Modus Ponens (4,5) ;
3. Montrer que si ` (α ⇒ (β ⇒ γ)), alors ` (β ⇒ (α ⇒ γ)).
Preuve :
31