Partiel de mathématiques discrètes, semestre 2, decembre 2008. Durée : 3 heures.

Couchot, J.-F

Les supports de TDs et de TP sont autorisés ; la calculatrice est interdite. Cette épreuve contient trois parties distinctes : un qcm, quelques démonstrations syntaxiques, et quelques programmes Prolog.

1 QCM (1h45)

Q. 1. On considère la base de connaissance suivante :

parent(pam,bob).
parent(tom,bob).
parent(tom,liz).
parent(bob,ann).
parent(bob,pat).
parent(pat,jim).
ancetre(X,Z) :- parent(X,Z).
ancetre(X,Z) :- parent(X,Y),ancetre(Y,Z).

On soumet la requête :

?- ancetre(pam,X).

Prolog donne 4 réponses distinctes et échoue. L’assertion proposée est vraie ou fausse ? Q. 2. Une formule propositionnelle F a pour conséquence logique une tautologie. L’affirmation suivante

est-elle vraie : « F est donc une tautologie » ?

Q. 3. Si j’étudie, je n’échoue pas en maths, si je ne joue pas au basket-ball, alors j’étudie, mais j’ai échoué en mathématiques. Donc, j’ai joué au basket-ball. Le raisonnement proposé est-il incorrect ?

Q. 4. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d’individus humains.

Prédicats Sens
aime(x, y) x aime y
maries(x, y) x et y sont mariés
femme(x) x est une femme
homme(x) x est un homme
fidele(x) x est fidèle
honete(x) x dit la vérité
a Alice
b Bob
c Clinton
∃x . (∀y . homme(x) ∧ (femme(y) ⇒ aime(x, y))

peut se traduire en « certains hommes sont aimés de toutes les femmes ». L’assertion proposée est vraie ou fausse ?

Q. 5. Soit p, q, r trois variables propostionnelles. L’énoncé suivant est-il une tautologie ? (p ∨ q) ∧ r ⇐ (p ∨ r) ∧ (q ∨ r).

Q. 6. Soit x et y des entiers naturels. ∀x . (∃y . x + y ≥ x + 1) est vraie. L’assertion est-elle vraie ? Q. 7. Une base de connaissance Prolog est un ensemble de faits, de règles et de requêtes. L’assertion

proposée est vraie ou fausse ?

Q. 8. Soit p et q les variables propositionnelles correspondant respectivement à « il est grand » et « il est beau ». « Il n’est ni grand, ni beau » peut-elle s’écrire ¬(p ∧ q) ?

Q. 9. Soit p, q, r trois variables propostionnelles. La relation {p ⇒ ¬q, q} ⊧ ¬p est-elle vraie ? Q. 10. « B seulement si A » peut-elle être représentée par ¬A ⇒ B? Q. 11. Soit p, q, r trois variables propostionnelles. L’énoncé suivant est-il une tautologie ? (p ⇒ q) ∨

p ∨ r ⇒ q ∨ r.

Q. 12. Soit p, q les variables propositionnelles correspondant respectivement à « il est grand » et « il est beau ». De plus, « il est petit » signifie qu’il n’est pas grand et « il est moche » signifie qu’il n’est pas beau. « il est faux qu’il est petit ou moche » peut-elle s’écrire ¬(¬p ∨ ¬p) ?

Q. 13. La formule ∀x . x > 0 ⇒ (∃y . e^{y} = x) est vraie sur l’univers ℕ. L’assertion est-elle vraie ? Q. 14. Une formule F a pour conséquence logique une antilogie. On ne peut donc rien dire de F. Q. 15. Les termes p(X, f(a, Y), X) et p(f(U, U), Z, Z) sont-ils unifiables ? Q. 16. Soit p et q les variables propositionnelles correspondant respectivement à « il est grand » et « il

est beau ». Sachant que « il est petit » signifie qu’il n’est pas grand, « il est grand ou il est petit et beau » peut-elle s’écrire p ∨ q?

Q. 17. Dans la formule P (a) ⇒ Q(a) la variable a n’est pas liée. L’assertion est-elle vraie ? Q. 18. La formule ∀x . x > 0 ⇒ (∃y . e^{y} = x) est-elle vraie sur l’univers ℝ? Q. 19. Soit p, q, r trois variables propostionnelles. La relation {r} ⊧ p ∧ q ⇒ r est-elle vraie ? Q. 20. « Il est faux qu’il ne fait pas froid ou qu’il pleut » est-elle équivalente à « il fait froid mais il ne

pleut pas » ?

Q. 21. Soit la démonstration syntaxique suivante : Démonstration

1. ¬B ⇒ ¬A H_{1}
2. A  H_{2}

3. 4.

5. ¬¬B  réduction de l’absurde entre 4. et 1.
6. ¬¬B ⇒ B Axiome 9.
7. B  mp entre 5. et 6.

Si elle était correcte et complète, cette démonstration permetrait-elle de démontrer le théorème de la contraposée ?

Q. 22. Soit la démonstration syntaxique suivante : Démonstration

1. ¬B ⇒ ¬A H_{1}
2. A  H_{2}

3. 4.

5. ¬¬B  réduction de l’absurde entre 4. et 1.
6. ¬¬B ⇒ B Axiome 9.
7. B  mp entre 5. et 6.

La démonstration est-elle correcte et complète si en 3. et 4. on a : 3. ¬¬A ⇒ ¬¬B théoreme de la contraposé sur 1. 4. ¬¬A ⇒ A Axiome 9 ?

Q. 23. On considère la base de connaissance suivante

a_une_baguette(harry).
joueur_de_Quidditch(harry).
sorcier(ron).
sorcier(X) :- a_un_balai(X), a_une_baguette(X).
a_un_balai(X) :- joueur_de_Quidditch(X).

Lorsqu’on soumet successivement les requêtes suivantes

?- sorcier(ron).
?- sorciere(ron).
?- sorcier(hermione).
?- sorciere(hermione).
?- sorcier(harry).

Prolog répond trois fois faux. L’assertion proposée est vraie ou fausse ? Q. 24. La relation {P, Q} ⊢ R se lit-elle « R est une conséquence logique de l’ensemble {P, Q} » ? Q. 25. Dans les clauses

pere_de(Y,Z) :- homme(Y),a_pour_fils(Y,Z).
pere_de(Y,Z) :- homme(Y),a_pour_fille(Y,Z).

La première clause se traduit-elle en ∀y, z . pere(y, z) ⇔ homme(y) ∧ a pour fils(y, z) ?

Q. 26. Soit p et q les variables propositionnelles correspondant respectivement à « il est grand » et « il est beau ». « Il est grand mais il n’est pas beau » peut-elle se traduire par p ∨ ¬q?

Q. 27. Soit p, q, r trois variables propostionnelles. L’énoncé suivant est-il une tautologie ? (p ∨ q) ∧ r ⇒ (p ∨ r) ∧ (q ∨ r).

Q. 28. « B seulement si A » peut-elle être représentée par A ⇒ B? Q. 29. En logique des propositions, il est possible de déduire que P est vraie chaque fois que H_{1}, …, H_{n}

le sont par la méthode des tables de vérités sans qu’il n’existe nécessairement de démonstration syntaxique permettant d’établir P à partir des hypothèses H_{1}, …, H_{n}. L’assertion est-elle vraie ?

Q. 30. Dans la formule (∀x . x ≥ 5) ∧ (∃y; y ≥ x) la variable x est-elle liée ? Q. 31. Soit p, q les variables propositionnelles correspondant respectivement à « il est grand » et « il est

beau ». De plus, « il est petit » signifie qu’il n’est pas grand et « il est moche » signifie qu’il n’est pas beau. « il est faux qu’il est petit ou moche » peut-elle s’écrire p ∧ q.

Q. 32. Soit p et q, deux variables propostionnelles. L’énoncé (p ∧ (p ∨ q)) ⇔ p est-il une tautologie ? Q. 33. On considère les prédicats parent(X,Y), qui est vrai si X est le père ou la mère de Y et

femme(X), qui est vrai si X est est une femme. L’assertion « X est la fille de Y » se traduit-elle en prolog

par fille(X,Y) :- parent(X,Y), femme(X). ?

Q. 34. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d’individus humains.

Prédicat Sens
aime(x, y) x aime y
maries(x, y) x et y sont mariés
femme(x) x est une femme
homme(x) x est un homme
fidele(x) x est fidèle
honete(x) x dit la vérité
a Alice
b Bob
c Clinton

Le prédicat ∃x, y . (maries(x, y) ∧ ¬aime(x, y) ∧ ¬aime(y, x)) traduit-il que « dans certains couples, un conjoint n’aime pas l’autre ».

Q. 35. Soit p, q, r trois variables propostionnelles. L’énoncé suivant est-il une tautologie ? p ∨ (q ∧ r) ⇒ (p ∨ q) ∧ (p ∨ r).

Q. 36. Une formule propositionnelle F a pour conséquence logique une antilogie. L’affirmation suivante est-elle vraie : « F est donc une tautologie » ?

Q. 37. En logique des propositions, P se déduit syntaxiquement de H_{1}, …, H_{n} si et seulement si P est une conséquence logique de H_{1}, …, H_{n}. L’assertion est-elle vraie ?

Q. 38. Soit p, q, r trois variables propostionnelles. L’énoncé suivant est-il une tautologie ? (p ⇒ q) ∧ (p ∨ r) ⇒ q ∨ r.

Q. 39. Soit la démonstration syntaxique suivante :

Démonstration

1. ¬B ⇒ ¬A H_{1}
2. A  H_{2}

3. 4.

5. ¬¬B  réduction de l’absurde entre 4. et 1.
6. ¬¬B ⇒ B Axiome 9.
7. B  mp entre 5. et 6.

La démonstration est-elle correcte et complète si en 3. et 4. on a

3. A ⇒ (¬B ⇒ A) Axiome 1. 4. ¬B ⇒ A modus ponens entre 2. et 3. ?

Q. 40. Soit p et q, deux variables propostionnelles. L’énoncé suivant est-il une tautologie ? (p ⇒ q) ⇒ ((q ⇒ p) ⇒ (q ⇔ p)).

2 Programmation Prolog (0h30)

2.1 Voyages

voiture(auckland,hamilton).
voiture(hamilton,raglan).
voiture(valmont,saarbruecken).
voiture(valmont,metz).
train(metz,frankfurt).
train(saarbruecken,frankfurt).
train(metz,paris).
train(saarbruecken,paris).
avion(frankfurt,bangkok).
avion(frankfurt,singapore).
avion(paris,losAngeles).
avion(bangkok,auckland).
avion(losAngeles,auckland).

Ecrire un prédicat voyage(X,Y) qui détermine s’il est possible de voyager d’un endroit à l’autre en empruntant des voitures, des trains ou des avions. Par exemple votre programme doit répondre yes à la

requête voyage(valmont, raglan).

2.2 Codage des entiers naturels

Les entiers naturels peuvent être codés à l’aide de 0, du successeur de 0 (qui vaut 1), puis du sucesseur du successeur de 0 (qui vaut 2) et ainsi de suite… Le predicat entier est alors défini à l’aide de la constante 0 et du symbol fonctionnel succ selon les clauses suivantes :

entier(0).
entier(X):- X=succ(Y), entier(Y).

1. Définir le predicat somme(X,Y,Z) qui est vrai si l’entier Z est la somme de X et de Y, ces trois entiers étant codés dans cette logique.

2. Définir le predicat plus_grand_que(X,Y) qui est vrai si l’entier X est plus grand que l’entier Y, ces deux entiers étant codés dans cette logique.

3 Démonstration syntaxique (45min)

Dans le système « PR » et en se servant éventuellement des théorèmes déjà démontrés dans le cours, démontrer syntaxiquement les deux formules propositionnelles suivantes :

1. (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C))

2. (A ∨ (B ∧ C)) ⇒ ((A ∨ B) ∧ (A ∨ C))

Nom : Prénom :

Numéro V F Numéro V F Numéro V F
Q. 1  Q. 2  Q. 3
Q. 4  Q. 5  Q. 6
Q. 7  Q. 8  Q. 9
Q. 10  Q. 11  Q. 12
Q. 13  Q. 14  Q. 15
Q. 16  Q. 17  Q. 18
Q. 19  Q. 20  Q. 21
Q. 22  Q. 23  Q. 24
Q. 25  Q. 26  Q. 27
Q. 28  Q. 29  Q. 30
Q. 31  Q. 32  Q. 33
Q. 34  Q. 35  Q. 36
Q. 37  Q. 38  Q. 39

Q. 40