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

Couchot, J.-F.

Les supports de TDs et de TP sont autorisés ; téléphones et calculatrices sont interdits.

1 QCM (1h45)

Q. 1. L’affirmation « il fait beau aujourd’hui donc il ne pleuvra pas dans dix jours » est-elle une proposition ? Q. 2. 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 correcte si en 3. et 4. on a :

3. ¬¬A ⇒ ¬¬B théoreme de la contraposée sur 1.
4. ¬¬A ⇒ A  Axiome 9.

Q. 3. « Si la paix survient, alors il y aura une crise économique à moins que le pays se dote d’armes nouvelles ou bien exécute un large programme d’investissement intérieur dans les secteurs de l’enseignement, de la santé et de la lutte contre la pauvreté. Il n’est pas possible de se mettre d’accord sur les objectifs que peut se donner un large programme d’investissement intérieur. Donc si la paix survient et qu’il n’y a pas de crise économique, le pays doit se doter d’armes nouvelles. » Le raisonnement proposé est-il correct ?

Q. 4. La relation {P, Q} ⊢ R se lit-elle « R est une conséquence logique de l’ensemble {P, Q} » ? Q. 5. Soit p, q, r trois variables propostionnelles. L’énoncé suivant est-il une tautologie ? (p ∨ q) ∧ (p ∨ r) ⇒

p ∨ (q ∧ r).

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

Q. 7. La formule ∀x . x > 0 ⇒ (∃y . e^{y} = x) est vraie sur l’univers ℝ. L’assertion proposée est vraie ou fausse ?

Q. 8. « A à moins que B » peut-elle être représentée par ¬A ⇒ B? Q. 9. Soit x et y des entiers naturels. ∃x . (∀y . y ≠ x ⇒ x < 1) est vraie. L’assertion proposée est vraie ou

fausse ?

Q. 10. Soit f, g des symboles de fonctions binaire, R un symbole de relation binaire. Soit A la formule

(∀z . R(x, z) ∧ R(z, y)) ⇒ (∃z . R(z, y) ∨ R(x, z)) .

Soit u, v les termes définis par u = f(z, x) et v = g(x, z)

Alors on a

A(v/y)(u/x) ≡ A(u/x)(v(u/x)/y)

L’assertion proposée est vraie ou fausse ?

Q. 11. Soit p, q, r trois variables propostionnelles. La relation {p ⇒ ¬q, q} ⊧ ¬p est-elle vraie ? Q. 12. 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 en

∀y, z . pere(y, z) ⇔ homme(y) ∧ a pour fils(y, z).

L’assertion proposée est vraie ou fausse ?

Q. 13. « A à moins que B » peut-elle être représentée par ¬B ∨ A? Q. 14. Soit p et q, deux variables propostionnelles. L’énoncé suivant est-il une tautologie ? ((p ⇒ q) ⇒ (q ⇒ p)) ⇒

(q ⇔ p).

Q. 15. On considère les prédicats Prolog 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.

« X est la soeur de Y » se traduit en prolog par

est_la_soeur_de(X,Y) :- parent(Z,X), parent(Z,Y), femme(X).

L’assertion proposée est vraie ou fausse ? Q. 16. « Il est faux que sa mère est anglaise ou que son père est français » est-elle suffisante pour affirmer que

« sa mère est anglaise ou son père n’est pas français » ?

Q. 17. On considère les prédicats Prolog 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.

« X est la fille de Y » se traduit en prolog par

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

L’assertion proposée est vraie ou fausse ? Q. 18. Dans la formule (∀x . x ≥ 5) ∧ (∃y . y ≥ x) la variable x est liée. L’assertion proposée est vraie ou

fausse ?

Q. 19. On note A la proposition « les chiens aboient » et P la proposition « la caravane passe ». La proposition « les chiens aboient à moins que la caravane ne passe » peut-elle être représentée par ¬P ⇒ A?

Q. 20. Soit p, q, r trois variables propostionnelles. La relation {r} ⊧ p ∧ q ⇒ r est-elle vraie ? Q. 21. Soit a et b des symboles de constante, f un symbole de fonction unaire, g un symbole de fonction

binaire et S un symbole de relation binaire. On donne les expressions suivantes :

1. g(a, f(b))

2. S(f(a), g(x, f(y))) L’expression 1 contient 1 seul terme L’assertion proposée est vraie ou fausse ? Q. 22. 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

« L’époux qui aime son épouse lui est fidèle »peut se traduire en

∀x, y . homme(x) ∧ femme(y) ∧ maries(x, y) ∧ aime(x, y) ∧ aime(y, x)

L’assertion proposée est vraie ou fausse ? Q. 23. 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

« Les femmes aiment toujours les hommes fidèles et qui disent la vérité »peut se traduire en

∀x, y . (homme(x) ∧ femme(y) ∧ fidele(x) ∧ honete(x)) ⇒ aime(y, x)

L’assertion proposée est vraie ou fausse ? Q. 24. 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
∃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. 25. L’affirmation « le Vesuve a ravagé la ville de Pompei en 1999 » est-elle une proposition ? Q. 26. Soit dodec le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, cube le prédicat unaire qui

est vrai si son paramètre est un cube, petit le prédicat unaire qui est vrai si son paramètre est petit, entre le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième et devant le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre.

« si un cube a quelque chose devant lui alors il est petit » peut-elle se traduire en

∀x . (∃y . cube(x) ∧ devant(x, y)) ⇒ petit(x)

L’assertion proposée est vraie ou fausse ?

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

Q. 28. Soit dodec le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, cube le prédicat unaire qui est vrai si son paramètre est un cube, petit le prédicat unaire qui est vrai si son paramètre est petit, entre le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième et devant le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre. Dans la formule suivante toutes les occurences de x sont liées.

∀x . dodec(x) ∨ devant(x, y) ⇒ ((∃y . cube(y) ∧ ¬devant(x, y)) ∧ entre(u, y, x))

L’assertion proposée est vraie ou fausse ?

Q. 29. Soit p, q, r trois variables propostionnelles. L’ensemble {p ∧ q} a-t-il pour conséquence logique p ∨ q? Q. 30. « B est une condition nécessaire pour A » peut-elle être représentée par ¬B ⇒ ¬A?

Q. 31. « B seulement si A » peut-elle être représentée par ¬A ⇒ B? Q. 32. 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 proposée est vraie ou fausse ?

Q. 33. « B seulement si A » peut-elle être représentée par A ∨ ¬B? Q. 34. 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 complète cela permetrait démontrer syntax-

iquement le théorème de la contraposée. Vrai ou faux ?

Q. 35. Soit p, q, r trois variables propostionnelles. La relation {p ⇒ q ∨ r, ¬q} ⊧ p ∨ r est-elle vraie ? Q. 36. On considère la base de connaissances 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. 37. « Il est faux que sa mère est anglaise ou que son père est français » est-elle équivalente à « sa mère est

anglaise ou son père n’est pas français » ?

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

Q. 39. « B seulement si A » peut-elle être représentée par A ⇒ B? Q. 40. « A à moins que B » peut-elle être représentée par B ∨ A? Q. 41. La négation de « ce triangle est rectangle donc ce triangle possède un angle droit » est-elle « ce triangle

ne possède pas un angle droit et pourtant il est rectangle »

Q. 42. Soit dodec le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, cube le prédicat unaire qui est vrai si son paramètre est un cube, petit le prédicat unaire qui est vrai si son paramètre est petit, entre le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième et devant le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre.

Les formules

∃x . dodec(x) ∧ petit(x) et ∃x . dodec(x) ⇒ petit(x)

n’ont jamais la même valeur de vérité. L’assertion proposée est vraie ou fausse ?

Q. 43. Dans la formule P (a) ⇒ Q(a) la variable a n’est pas liée. L’assertion proposée est vraie ou fausse ? Q. 44. Soit p, q, r trois variables propostionnelles. L’ensemble p ∧ q est-elle une conséquence logique de

{p, q}?

Q. 45. 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).

L’ensemble des deux clauses se traduit en

∀y, z . pere(y, z) ⇐ (homme(y) ∧ a pour fils(y, z)) ∨ (homme(y) ∧ a pour fille(y, z))

L’assertion proposée est vraie ou fausse ?

Q. 46. 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).

Au requètes successives :

?- parent(jim,X).
?- parent(X,jim).
?- parent(pam,X), parent(X,pat).
?- parent(pam,X), parent(X,Y), parent(Y,jim).

Prolog répond au moins deux fois faux L’assertion proposée est vraie ou fausse ? Q. 47. Soit a et b des symboles de constante, f un symbole de fonction unaire, g un symbole de fonction

binaire et S un symbole de relation binaire. On donne les expressions suivantes :

1. g(a, f(b))

2. S(f(a), g(x, f(y))) L’expression 2 est un terme complexe. L’assertion proposée est vraie ou fausse ? Q. 48. 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. 49. 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
∀x . femme(x) ⇒ (aime(x, b) ∨ aime(x, c))

peut se traduire en « Si une femme n’aime pas Clinton, alors elle aime Bob ». L’assertion proposée est vraie ou fausse ? Q. 50. Soit a et b des symboles de constante, f un symbole de fonction unaire, g un symbole de fonction

binaire et S un symbole de relation binaire. On donne les expressions suivantes :

1. g(a, f(b))

2. S(f(a), g(x, f(y))) L’expression 1 contient quatre termes L’assertion proposée est vraie ou fausse ? Q. 51. Soit f, g des symboles de fonctions binaire, R un symbole de relation binaire. Soit A la formule

(∀z . R(x, z) ∧ R(z, y)) ⇒ (∃z . R(z, y) ∨ R(x, z)) .

Soit u, v les termes définis par u = f(z, x) et v = g(x, z)

Alors on a

A(u/x)(v/y) ≡ A(v/y)(u(v/y)/x)

L’assertion proposée est vraie ou fausse ?

Q. 52. Si je travaille, je ne peux pas étudier ; Soit je travaille, soit je suis reçu en mathématiques ; j’ai été reçu en mathématiques. Donc j’ai étudié. Le raisonnement proposé est-il incorrect ?

Q. 53. Soit dodec le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, cube le prédicat unaire qui est vrai si son paramètre est un cube, petit le prédicat unaire qui est vrai si son paramètre est petit, entre le

Fig. 1 – Graphe à modéliser en Prolog

prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième et devant le prédicat unaire qui est vrai si son premier paramètre est devant son second paramètre. Dans la formule suivante y et u ont des occurences libres

∀x . dodec(x) ∨ devant(x, y) ⇒ ((∃y . cube(y) ∧ ¬devant(x, y)) ∧ entre(u, y, x))

L’assertion proposée est vraie ou fausse ?

Q. 54. « A à moins que B » peut-elle être représentée par B ⇒ A?

Q. 55. L’affirmation « le Vesuve ferra une irruption en 2010 » est-elle une proposition ?

Q. 56. « Il est faux qu’il ne fait pas froid ou qu’il pleut » est-elle équivalente à « il fait froid mais il ne pleut pas » ?

2 Raisonnements écrits (1h15)

2.1 Calcul des prédicats

Dans la série suivante, chaque formule est logiquement équivalente à une et une seule autre. Retrouver les paires équivalentes et justifier.

∀x . ¬p(x) ∧ q(x)  (1)
¬(∀x . p(x) ⇒ q(x))  (2)
∃x . ¬p(x) ∨ ¬q(x)  (3)
∃x . ¬p(x) ∨ q(x)  (4)
(∃x . ¬p(x)) ∨ (∃x . q(x))  (5)
(∃x . ¬p(x)) ∨ ¬(∃x . ¬q(x))  (6)
¬(∃x . p(x)) ∧ (∀x . q(x))  (7)
∃x . p(x) ⇒ ¬q(x)  (8)
¬(∀x . p(x)) ∨ (∀x . q(x))  (9)
∃x . p(x) ∧ ¬q(x)  (10)

2.2 Prolog

2.2.1 Graphe

On considère le graphe donné à la figure 1.

1. Modéliser ce graphe à l’aide du prédicat arc(X, Y) qui est vrai s’il existe un arc depuis le noeud X vers le noeud Y.

2. Construire le prédicat chemin(X, Y) qui est vrai s’il existe un chemin, c’est à dire une suite continue et éventuellement vide d’arcs entre les noeuds X et Y du graphe.

3. Quelle requête Prolog effectueriez-vous pour obtenir tous les noeuds accessibles à partir du noeud a.

2.2.2 Liste d’entiers naturels 1. Définir un prédicat pair(X) qui est vrai si X est un nombre pair.

2. Définir un prédicat membres pairs(L, Lp) qui est vrai si la liste Lp est composée des éléments pairs de la liste L et dans le même ordre.

3. On considère le prédicat Prolog append(L1, L2, L3) qui est est vrai si L3 est la concaténation des listes L1 et L2. Définir le prédicat inverse(L, Lp) qui est vrai si Lp est la liste L retournée.

2.3 Déduction syntaxique

Dans ce qui suit, A, B, C et D sont quatre variables propositionnelles.

1. Démontrer le théorème suivant par déduction syntaxique :

(A ⇒ (B ∧ C)) ⇒ (A ⇒ B) ∧ (A ⇒ C)

On pourra utiliser le théorème de transitivité de l’implication.

2. Effectuer la démonstration sous hypothèse suivante :

{C ⇒ ¬B, C ∨ D, D ⇒ ¬B, A ⇒ B} ⊢ ¬A

On pourra utiliser le théorème de la contraposée et la règle de disjonction des cas.

Réponses au QCM

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  Q. 41  Q. 42
Q. 43  Q. 44  Q. 45
Q. 46  Q. 47  Q. 48
Q. 49  Q. 50  Q. 51
Q. 52  Q. 53  Q. 54
Q. 55  Q. 56