AMU - L3 Informatique Cours Logique et Calculabilité - 2015
TD no 4
Calcul Propositionnel : Algorithmes, Français, Modélisation
Exercice 1
Calculer une forme clausale (conjonctive) de chacune des formules suivantes :
1. ψ1 = (p ∧ ¬((q ∨ r) ⇒ p)) ∨ s ;
2. ψ2 = (p1 ∧ q1 ) ∨ (p2 ∧ q2 ) ;
3. ψ3 = ¬((p ⇔ q) ⇒ (r ⇒ s)).
Exercice 2 (Algorithme de Quine). Transformez la formule suivante :
ϕ = (p ⇒ ((q ∨ r) ∧ s)) ∧ ¬(q ⇔ (r ∧ (p ∨ s)))
en forme normale conjonctive et appliquez ensuite l’algorithme de Quine pour trouver tous les modèles
de ϕ.
Exercice 3 (Algorithme DPLL). Transformez la formule
ϕ = ¬[(p ⇒ s) ⇒ ((q ⇒ r) ⇒ ((p ∨ q) ⇒ (s ∧ q ∧ r ∧ ¬p)))]
en FNC et appliquez algorithme de DPLL pour trouver un modèle. Répétez ensuite l’exercice avec la
formule de l’exercice 2.
Exercice 4 Montrez que, pour tout n ≥ 1, il existe un ensemble de clauses Cn dont les symboles propo-
sitionnels sont { p1 , . . . , pn } tel que l’arbre construit par l’algorithme de Quine est un arbre complet de
profondeur n (donc, avec 2n noeuds) où, par contre, l’arbre exploré par l’algorithme DPLL est une branche
de longueur n (donc, seulement n + 1 noeuds sont explorés par l’algorithme).
Exercice 5 Utiliser la méthode de la coupure pour prouver ou infirmer les affirmations suivantes.
1. |= p ⇒ p
2. |= ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r)
3. |= ((s ⇒ r) ∧ p ∧ ¬r) ⇒ ¬r ∧ ¬s ∧ p
4. |= [(p ∧ q) ∨ (r ∧ q)] ⇒ (p ∨ r)
5. {q ⇒ (¬q ∨ r), q ⇒ (p ∧ ¬r)} |= q ⇒ r
6. {q ⇒ (¬q ∨ r), q ⇒ (p ∧ ¬r)} |= q ∧ r
7. |= (p ∧ (q ∨ r)) ⇔ ((¬p ⇒ r) ∧ (p ∧ q)).
8. |= (p ∨ (q ∧ r)) ⇔ ((p ⇒ r) ∨ (p ∧ q)).
9. {p ⇒ q, q ⇒ r, p ∨ ¬r} |= p ∧ q ∧ r.
10. {p ⇒ q, q ⇒ r, p ∨ ¬r} |= (p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r).
F RANÇAIS ET LOGIQUE FORMELLE
Exercice 6 Alain, Baru et Carole sont prévenus de fraude fiscale. Ils prêtent serment de la façon suivante :
Alain : « Baru est coupable et Carole est innocente. »
Baru : « Si Alain est coupable alors Carole aussi. »
Carole : « Je suis innocente mais au moins un des deux autres est coupable. »
Exprimer le témoignage de chacun sous forme propositionnelle. Dresser la table de vérité de ces formules.
Les témoignages sont-ils compatibles ? Le témoignage d’un suspect découle de celui d’un autre suspect ?
Lequel ? En supposant que tous sont innocents, qui a fait un faux témoignage ?
Exercice 7 L’association des Informaticiens de AMU est dirigée par trois directions : scientifique, finan-
cière, générale. Le règlement intérieur spécifie que :
— Les membres de la direction générale sont choisis parmi ceux de la direction financière.
— Nul ne peut être membre de la direction générale et de la direction scientifique s’il n’est pas membre
de la direction financière.
— Aucun membre de la direction scientifique ne peut être membre de la direction financière.
1. Donner une spécification logique de ce règlement.
2. Proposer un règlement plus simple équivalent.
M ODÉLISATION
Exercice 8 On cherche à deviner la position d’un certain nombre de bateaux sur une grille de bataille
navale à 2 lignes (a et b) et 3 colonnes (1, 2 et 3). On dispose des informations suivantes :
1. Il y a au moins un bateau sur la ligne b.
2. Il y a au moins un bateau sur la ligne a.
3. Il n’y a pas deux bateaux sur une même colonne.
4. Il n’y a pas de bateau en (b, 1).
5. S’il y a un bateau sur la ligne a, alors il n’y en a pas en (b, 3).
En notant xi l’information « il y a un bateau en position (x, i) » (pour x ∈ {a, b} et i ∈ {1, 2, 3}), mo-
délisez par une formule du calcul propositionnel les cinq affirmations ci-dessus, simplifiez au maximum
l’ensemble des formules obtenues puis dessinez les modèles de cet ensemble.
