SI3 – Informatique théorique (Année 2024/2025)
TD 01 – Logique des propositions
Exercice 1. Tables de vérité
Écrire la table de vérité des formules propositionnelles suivantes :
1. A ⇒ B
A B A⇒B
0 0 1
☞ 0 1 1
1 0 0
1 1 1
2. ¬A ∨ B
A B ¬A ∨ B
0 0 1
☞ 0 1 1
1 0 0
1 1 1
3. ¬(A ∨ B)
A B ¬(A ∨ B)
0 0 1
☞ 0 1 0
1 0 0
1 1 0
4. ¬A ∧ ¬B
A B ¬A ∧ ¬B
0 0 1
☞ 0 1 0
1 0 0
1 1 0
5. A ∧ (B ∨ C)
A B C A ∧ (B ∨ C)
0 0 0 0
0 0 1 0
0 1 0 0
☞ 0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
6. (A ∧ B) ∨ (A ∧ C)
A B C (A ∧ B) ∨ (A ∧ C)
0 0 0 0
0 0 1 0
0 1 0 0
☞ 0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
7. A ⇒ (B ⇒ C)
A B C A ⇒ (B ⇒ C)
0 0 0 1
0 0 1 1
0 1 0 1
☞ 0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
1
8. (A ∧ B) ⇒ C
A B C A ⇒ (B ⇒ C)
0 0 0 1
0 0 1 1
0 1 0 1
☞ 0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
9. Que peut-on dire de :
— ¬A ∨ ¬B et ¬(A ∧ B) ?
— A ∧ (B ∨ C) et (A ∧ B) ∨ (A ∧ C) ?
— A ⇒ (B ⇒ C) et (A ∧ B) ⇒ C ?
☞ Elles sont équivalentes.
Exercice 2. Contraposée
1. Écrire la table de vérité des formules propositionnelles ¬B ⇒ ¬A.
A B ¬B ⇒ ¬A
0 0 1
☞ 0 1 1
1 0 0
1 1 1
2. À quoi cette formule est-elle équivalente ?
☞ À l’implication A ⇒ B.
Exercice 3. NAND
1. Écrire la table de vérité du ∼
∧, c’est-à-dire la table de vérité de la négation du ∧.
A B A∼
∧B
0 0 1
☞ 0 1 1
1 0 1
1 1 0
2. Donner une formule propositionnelle qui n’utilise que ∼
∧ comme connecteur et dont la
table de vérité est celle du ¬.
☞ A∼
∧A
3. Donner une formule propositionnelle qui n’utilise que ∼
∧ comme connecteur et dont la
table de vérité est celle du ⇒.
☞ A ⇒ B a la même table de vérité que ¬A ∨ B donc que ¬(A ∧ ¬B) donc que A ∼
∧ (B ∼
∧ B).
4. Donner une formule propositionnelle qui n’utilise que ∼
∧ comme connecteur et dont la
table de vérité est celle du ∨.
☞ A ∨ B a la même table de vérité que ¬(¬A ∧ ¬B) donc que (A ∼
∧ A) ∼
∧ (B ∼
∧ B).
5. Donner une formule propositionnelle qui n’utilise que ∼
∧ comme connecteur et dont la
table de vérité est celle du ∧.
☞ A ∧ B a la même table de vérité que ¬¬(A ∧ B) donc que ¬(A ∼
∧ B) donc que (A ∼
∧ B) ∼
∧ (A ∼
∧ B).
2
Exercice 4. Formes normales conjonctives (FNC)
Une formule en forme normale conjonctive est une formule de la forme p1 ∧ p2 ∧ p3 ∧ · · · ∧ pn
avec pi de la forme t1 ∨ t2 ∨ t3 ∨ · · · ∨ tm où ti est une variable ou la négation d’une variable.
Passer les formules suivantes en formes normales conjonctives :
1. ¬((((A ⇒ B) ∨ C) ∧ A) ∨ (D ∧ ¬C)) ∧ B ;
☞
Remarque :
((A ⇒ B) ∨ C) est équivalent à ((¬A ∨ B) ∨ C) et donc à (¬A ∨ B ∨ C).
Donc
¬ {[((A ⇒ B) ∨ C) ∧ A] ∨ (D ∧ ¬C)} ∧ B
¬ [(¬A ∨ B ∨ C) ∧ A] ∧ ¬(D ∧ ¬C) ∧ B
[¬ (¬A ∨ B ∨ C) ∨ ¬A] ∧ (¬D ∨ C) ∧ B
[¬ (¬A ∨ B ∨ C) ∨ ¬A] ∧ (¬D ∨ C) ∧ B
[(A ∧ ¬B ∧ ¬C) ∨ ¬A] ∧ (¬D ∨ C) ∧ B
Forme normale conjonctive :
(A ∨ ¬A) ∧ (¬B ∨ ¬A) ∧ (¬C ∨ ¬A) ∧ (¬D ∨ C) ∧ B
Simplifiée (car (A ∨ ¬A) = ⊤) :
(¬B ∨ ¬A) ∧ (¬C ∨ ¬A) ∧ (¬D ∨ C) ∧ B
Puis (car (¬B ∨ ¬A) ∧ B = ¬A ∧ B) :
¬A ∧ (¬C ∨ ¬A) ∧ (¬D ∨ C) ∧ B
Et enfin (car ¬A ∧ (¬C ∨ ¬A) = ¬A) :
¬A ∧ B ∧ (¬D ∨ C)
2. (A ⇔ B) ∨ ¬((C ∧ D) ∨ (¬D ∨ A)).
☞
(A ⇔ B) ∨ ¬ {(C ∧ D) ∨ (¬D ∨ A)}
(A ⇔ B) ∨ {(¬C ∨ ¬D) ∧ (D ∧ ¬A)}
{(A ⇔ B) ∨ (¬C ∨ ¬D)} ∧ {(A ⇔ B) ∨ (D ∧ ¬A)}
{[(A ∨ ¬B) ∧ (¬A ∨ B)] ∨ (¬C ∨ ¬D)} ∧ {[(A ∨ ¬B) ∧ (¬A ∨ B)] ∨ (D ∧ ¬A)}
{[(A ∨ ¬B) ∨ (¬C ∨ ¬D)] ∧ [(¬A ∨ B) ∨ (¬C ∨ ¬D)]} ∧ {[(A ∨ ¬B) ∨ (D ∧ ¬A)] ∧ [(¬A ∨ B) ∨ (D ∧ ¬A)]}
(A ∨ ¬B ∨ ¬C ∨ ¬D) ∧ (¬A ∨ B ∨ ¬C ∨ ¬D) ∧ (A ∨ ¬B ∨ D) ∧ (A ∨ ¬B ∨ ¬A) ∧ (¬A ∨ B ∨ D) ∧ (¬A ∨ B ∨ ¬A)
Exercice 5. Modélisation et tables de Karnaugh
Vous cherchez à former un groupe de musique et vous disposez de 4 musiciens : Fred, Paul,
Diane et Chloé. Mais vous avez les contraintes suivantes :
— Diane ne veut jouer ni avec Chloé ni avec Paul.
— Paul ne veut pas jouer tout seul.
— Si les deux garçons jouent, alors Chloé veut joueur aussi.
1. Modéliser ces conditions sur la composition du groupe par une formule propositionnelle.
☞ F, P, D, C : Fred/Paul/Diane/Chloé fait partie du groupe
— Diane ne veut jouer ni avec Chloé ni avec Paul : ¬(D ∧ C) ∧ ¬(D ∧ P ) .
— Paul ne veut pas jouer tout seul : ¬(¬F ∧ P ∧ ¬D ∧ ¬C).
— Si les deux garçons jouent, alors Chloé veut joueur aussi : (F ∧ P ) ⇒ C.
Au final :
¬(D ∧ C) ∧ ¬(D ∧ P ) ∧ ¬(¬F ∧ P ∧ ¬D ∧ ¬C) ∧ ((F ∧ P ) ⇒ C).
3
2. Par la méthode des tables de Karnaugh, transformer cette formule en FND (forme normale
dijonctive) la plus simple possible.
FP
00 01 11 10
00 1 0 0 1
01 1 1 1 1
DC
11 0 0 0 0
10 1 0 0 1
☞
3. Avec la méthode de votre choix, est-ce-que vous pourriez réécrire le problème avec des
contraintes plus simples ?
FP
00 01 11 10
00 1 0 0 1
01 1 1 1 1
DC
11 0 0 0 0
10 1 0 0 1
☞
— ¬(P ∧ ¬C) : Chloé et Paul ne peuvent pas être ensemble
— ¬(D ∧ ¬C) : Diane et Chloé ne peuvent pas être ensemble
Exercice 6. Argumentation
Parmi les discours suivants, lesquels sont des raisonnements corrects ?
1. Si Lucette a menti, alors Hugo est coupable. Or Hugo n’est pas coupable. Donc Lucette
n’a pas menti.
☞
— L : Lucette a menti
— H : Hugo est coupable
— Prémisse 1 : L ⇒ H (Si Lucette a menti, alors Hugo est coupable.)
— Prémisse 2 : ¬H (Hugo n’est pas coupable.)
— Conclusion : ¬L (Lucette n’a pas menti.)
L H L⇒H ¬H Les prémisses sont vrais La conclusion est vraie
0 0 1 1 1 1
0 1 1 0 0 1
1 0 0 1 0 0
1 1 1 0 0 0
Pour un raisonnement, si dans toutes les lignes du tableau de vérité où les prémisses sont vraies la conclusion l’est, c’est
un raisonnement valide. Ceci est donc un raisonnement valide
2. Si Lucette a menti, alors Hugo est coupable. Or, Lucette n’a pas menti. Donc Hugo n’est
pas coupable.
☞
4
— L : Lucette a menti
— H : Hugo est coupable
— Prémisse 1 : L ⇒ H (Si Lucette a menti, alors Hugo est coupable.)
— Prémisse 2 : ¬L (Lucette n’a pas menti.)
— Conclusion : ¬H (Hugo n’est pas coupable.)
L H L⇒H ¬L Les prémisses sont vrais La conclusion est vraie
0 0 1 1 1 1
0 1 1 1 1 0
1 0 0 0 0 1
1 1 1 0 0 0
Il y a un cas de figure où les deux prémisses sont vraies, mais la conclusion est fausse, le raisonnement n’est donc pas
valide.
Exercice 7. Tautologie et contradictions
Parmis les formules suivantes, lesquelles sont des tautologies (des formules toujours vrai) ou
des contradictions (des formules toujours fausses) ?
1. (A ∧ B) ⇒ A
A B (A ∧ B) ⇒ A
0 0 1
☞ 0 1 1
1 0 0
1 1 1
Tautologie.
2. (A ∧ B) ⇒ (¬A ∧ ¬B)
A B (A ∧ B) ⇒ (¬A ∧ ¬B)
0 0 1
☞ 0 1 1
1 0 1
1 1 0
Ni tautologie, ni contradiction.
3. ¬(A ⇒ (A ∨ B))
A B ¬(A ⇒ (A ∨ B))
0 0 0
☞ 0 1 0
1 0 0
1 1 0
Contradiction.
