Fondement de l’IA
Correction TD2 : Logique des propositions
Exercice 1 :
(1) La musique n’est ni triste ni rythmée.
(2) Il ne baille pas, il est même joyeux.
(3) Quand il écoute de la musique rythmée, il est joyeux et il danse.
(4) Il danse, sauf s’il n’est pas joyeux.
(5) La musique ne le fait pas danser.
(6) S’il danse en baillant, c’est qu’il n’est pas joyeux.
(7) Il écoute de la musique triste sans bailler.
(8) Ou il écoute de la musique et il danse, ou il n’est pas joyeux.
Exercice 2 :
1) A : ¬p → (q ∧ p))
p q ¬p (q ∧ p) A
V V F V V
V F F F V
F V V F F
F F V F F
2)B : ((p ∧ q) ∨ r)
p q r p∧q B
V V V V V
V V F V V
V F V F V
V F F F F
F V V F V
F V F F F
F F V F V
F F F F F
3) C :(p ↔ (q ∧ p))
p q (q ∧ p) C
V V V V
V F F F
F V F V
F F F V
4) D : ¬(p → ¬q)
p q ¬q p → ¬q D
V V F F V
V F V V F
F V F V F
F F V V F
5) E : ((p → q) → (q → p))
p q p→q q→p E
V V V V V
V F F V V
F V V F F
F F V V V
6) F : ((p ∨ ¬q) → r)
p q r ¬q p ∨ ¬q F
V V V F V V
V V F F V F
V F V V V V
V F F V V F
F V V F F V
F V F F F V
F F V V V V
F F F V V F
Exercice 3 :
1) (p ∨ (q ∧ p)) ≡ p
p q q∧p p ∨ (q ∧ p))
V V V V
V F F V
F V F F
F F F F
Dans la dernière colonne, on retrouve les valeurs de p ; donc (p ∨ (q ∧ p)) ≡ p
2) (p → q) ∧(q → p) ≡ (p ↔ q)
p q p→q q→p (p → q) ∧(q → p)
V V V V V
V F F V F
F V V F F
F F V V V
D’où (p → q) ∧(q → p) ≡ (p ↔ q)
3) ((p ∧ q) ∨ (¬p ∧ ¬q)) ≡ (p ↔ q).
p q p∧q ¬p ¬q (¬p ∧ ¬q)) ((p ∧ q) ∨ (¬p ∧ ¬q))
V V V F F F V
V F F F V F F
F V F V F F F
F F F V V V V
D’où ((p ∧ q) ∨ (¬p ∧ ¬q)) ≡ (p ↔ q).
Exercice 4 : Dresser les tables de vérités pour les démontrer.
Rappel :
Une formule est dite satisfiable si elle est au moins vrai pour une interprétation
Une formule est dite valide si elle est vrai pour toute interprétation
1)
p q r ((p ∨ q) → p) ↔ (r → (q
p∨ p ∨ q) → q∧r r → (q ∧ r ) ∧ r))
q p
V V V V V V V V
V V F V V F V V
V F V V V F F F
V F F V V F V V
F V V V F V V F
F V F V F F V F
F F V F V F F F
F F F F V F V V
La formule est satisfiable
2)
P q r p→q q→r (p → q) ∧ p→r ((p → q) ∧
(q → r) (q → r))
→ (p → r)
V V V V V V V V
V V F V F F F V
V F V F V F V V
V F F F V F F V
F V V V V V V V
F V F V F F V V
F F V V V V V V
F F F V V V V V
La formule est valide
Exercice 5 : Dresser les tables de vérités
a)
p q R (p ∧ q) ((p ∧ q) ∧ r) (p ∨ q) (((p ∧ q) ∧
r) → (p ∨
q))
V V V V V V V
V V F V F V V
V F V F F V V
V F F F F V V
F V V F F V V
F V F F F V V
F F V F F F V
F F F F F F V
Tautologie
b)
p q ¬p p→q ((p → q) → (((p → q) → p) ∧ ¬p)
p)
V V F V V F
V F F F V F
F V V V F F
F F V V F F
Contradiction
c)
p q p→q ¬(p → q) ¬q (p ∧ ¬q) ¬(p → q) → (p ∧ ¬q))
V V V F F F V
V F F V V V V
F V V F F F V
F F V F V F V
Tautologie
d)
p q p→q ((p → q) ∧ p) (((p → q) ∧ p) → q)
V V V V V
V F F F V
F V V F V
F F V F V
Tautologie
