REPUBLIQUE TUNISIENNE
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université de Carthage
Institut National des Sciences Appliquées et de Technologie
Logique Informatique
TD1
RT3 Olfa MOSBAHI ([email protected])
Exercice 1 :
1. Une relation est une relation d’équivalence si et seulement si elle est réflexive, symétrique et
transitive.
Relation d’équivalence : R
Relation Réflexive : R1
Relation Symétrique : R2
Relation Transitive : R3
R R1 R2 R3
2. Nous avons besoin de courage pour pouvoir aller dans les montagnes.
Courage : P1
Pouvoir aller dans les montagnes : P2
P2 P1
3. Si c’est une personne qui travaille dure alors probablement elle sera élue.
Personne qui travaille dure : P1
Personne élue : P2
P2 P1
Exercice 2 :
Construisez les tables de vérité pour chacune des formules suivantes :
1) A= (p v ⌐q) → q
p q ⌐q p v ⌐q A
0 0 1 1 0
0 1 0 0 1
1 0 1 1 0
1 1 0 1 1
2) B= (p q) ((p q))
p q p q p v q p q (p q) B
0 0 1 1 1 0 1 1
0 1 1 0 1 0 1 1
1 0 0 1 0 1 0 0
1 1 0 0 1 0 1 1
3) C= (p → q) (p → q)
p q p p→q p → q C
0 0 1 1 0 0
0 1 1 1 1 1
1 0 0 0 1 0
1 1 0 1 1 1
4) D= (p q) (p q)
p q p p q p q D
0 0 1 1 0 1
0 1 1 0 1 1
1 0 0 0 1 1
1 1 0 1 0 1
REPUBLIQUE TUNISIENNE
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université de Carthage
Institut National des Sciences Appliquées et de Technologie
Exercice 3 :
Pour chacune des formules suivantes, déterminer si elle est valide, invalide, inconsistante ou
consistante.
1) (p) → p p → P (valide et consistante)
2) p → (p q) = p v (p q)
= (p v p) (p v q)
= T (p v q)
p q p p v q
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
Formule Consistante et invalide
3) F = (p q) q = (p q) v q
P q p q F
0 0 1 1
0 1 0 0
1 0 0 1
1 1 0 0
Formule Consistante et invalide
4) G = (p q) → p
p q pq G
0 0 0 1
0 1 1 0
1 0 1 1
1 1 1 1
Formule Consistante et invalide
5) H = (p → q) → (q → p)
p q p q p→q (q → p H
0 0 1 1 1 1 1
0 1 1 0 1 1 1
1 0 0 1 0 0 1
1 1 0 0 1 1 1
Formule Consistante et valide
Exercice 4 :
a- Transformer les formules suivantes en des formes normales disjonctives (FND).
1) (p q) → r = (p q) r
= p q r
2) p → ((q r) → s) = p ((q r) → s)
= p ((q r) s)
= p (q r s)
= p q r s
REPUBLIQUE TUNISIENNE
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université de Carthage
Institut National des Sciences Appliquées et de Technologie
3) (p q) (s → t) = (p q) (s t)
= (p q s) (p q t)
4) (p → q) → r = (p q) r
= (p q) r
b- Transformer les formules suivantes en des formes normales conjonctives (FNC)
1) p (p q r) = (p p) (p q) (p r)
= T (p q) (p r)
= (p q) (p r)
2) (p → q) (p q) = (p q) (p q)
= (p q) (p q)
= (p q q) (p q p)
= T (p q) = (p q)
3) (p → q) → r = (p q) r
= (p q) r
= (p r) (q r)
4) (p q) (p q) = (p p) (p q) (q p) (q q)
= (p q) (q p)
Exercice 5 :
1) Prouver que (q → p) est une conséquence logique de (p → q).
(p → q) |= (q → p) ?
une conséquence logique I/ I(p → q) = T alors I(q → p) = T
(p → q) → (q → p) = (p q) (q p)
= (p q) (q p)
= (q p q) (q p p) = T ( formule valide )
donc (p → q) |= (q → p)
2) F1 : Ali ne peut pas être un bon élève sauf s’il est sage et que son père le supporte.
F2 : Ali est un bon élève uniquement quand son père le supporte.
Vérifier que F2 est une conséquence logique de F1.
P1 : bon élève
P2 : sage
P3 : son père le supporte
F1 : P1 → P2 P3
F2 : P1 → P3
Mq : F1 |= F2 ?
(P1 → P2 P3 ) → (P1 → P3 ) = (P1 (P2 P3) (P1 P3)
= (P1 (P2 P3)) (P1 P3)
= (P1 P3 P1) (P1 P3 P1 P3)
REPUBLIQUE TUNISIENNE
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université de Carthage
Institut National des Sciences Appliquées et de Technologie
= T (formule valide)
Donc F1 |= F2
3) Vérifier que q est une conséquence logique de (p → q) et p.
(p → q), p |= q ?
Méthode 1 : Appliquer le théorème vu en cours
((p → q) p) → q = ((p q) p) q
= ((p q ) p ) q
= (p p ) (p q ) q
= T (p q ) q
= (p q ) q
= (p q q )
= T (formule valide)
Donc (p → q), p |= q
Méthode 2 : Table de vérité
p q p→q
T T T
T F F
F F T
F T T
I / I(p → q) = T et I(p) = T alors I(q) = T
