Universit e de Tunis El Manar
Facult e des Sciences
economique et de Gestion de
Tunis
T.D. Logique math ematique
Le calcul propositionnel ou CPO
2015-2016
Section : LFIG2
Exercice 1
Repr esenter les propositions suivantes par des formules :
1. Une relation est une relation d equivalence ssi elle est r eexive, sym etrique et transitive.
2. Il faut de lhabitude et du courage pour escalader cette montagne.
3. Si lhumidit e est tr es elev ee, il pleuvra cet apr`es midi ou ce soir
Exercice 2
Publicité
1. ( p) p
3. (p ( q) ( q
5. (p q) ( q p)
7. p ( (p q)
9. p ( (q p)
11. p ' ( (p q))
13. p p
2. p (p ' q)
4. (p ( q) p
6. (p q) (q p)
8. (p ' (q p)) p
10. (p ' q) ' ( p ( q)
12. p p
Exercice 3
Publicité
Brown, Jones et Smith sont pr evenus de fraude scale et pr etent serment de la fa con suivante :
Brown : Jones est coupable et Smith est innocent.
Jones : Si Brown est coupable alors Smith aussi.
Smith : Je suis innocent mais au moins un des deux autres est coupable.
1. Exprimer le t emoignage de chacun des suspects sous forme propositionnelle.
2. Dresser la table de v erit e de ces formules.
3. Les t emoignages des trois suspects sont-ils compatibles ?
4. Le t emoignage de lun des suspects d ecoule de celui dun autre suspect. Lequel ?
1
5. Le t emoignage de lun des suspects d ecoule de celui des deux autres suspects. Lesquels ?
6. En supposant que tous sont innocents qui a fait un faux t emoignage ?
7. Si tous disent vrai, lequel est coupable ?
8. Si exactement les innocents disent vrai, lequel est coupable ?
Exercice 4
Publicité
Mettre les formules suivantes en forme normale conjonctive puis en forme normale disjonctive :
1. ( p ' q) r
3. (p ( q) ' (s t)
5. (p ' q) ' (p ( q)
7. (p q) ( (p ( q)
9. ( p ' q) ( (p ' q)
2. p ((q ' r) s)
4. (p q) r
6. p ( ( p ' q ' r)
8. (p q)
Exercice 5
V erier que les formules suivantes sont equivalentes en les mettant sous la m eme forme normale :
1. (p q) ' (p r) et p (q ' r)
2. (p q) (p ' q) et ( p q) ' (q p)
Publicité
3. p ' q ' ( p ( q) et p ' q ' (p ( q)
4. p ( (p (p ' q)) et p ( q ( (p ' q)
Exercice 6
Montrer par r esolution linconsistance de lensemble des clauses dans les deux cas suivants :
" S1 = {p ( q ( r, p ( r, q, r}
" S2 = {p ( q, q ( r, p ( q, r}
" S3 = {p ( p, p ( q, q ( q}
" S4 = {p ( q, p ( r, q ( r, p ( q, q ( r, p ( r}
" S5 = {p ( q ( r, q ( r, p ( r, q ( r, q}
Montrer que {p ( q ( r, p ( r, s, p ( q ( s} |= r ' s
2