2020-2021
L OGIQUE F ORMELLE
T.D.N◦ 3
(Logique des prédicats)
Section : LCS1
Enseignante : Yousra Hlaoui
Exercice 1
Formaliser en Calcul des prédicats les phrases suivantes :
1. Les baleines sont des mammifères.
2. Les entiers sont pairs ou impairs.
3. Il existe un entier pair
Exercice 2
Traduire les énoncés suivants en logique des prédicats :
1. Tous les hommes sont méchants.
2. Seulement les hommes sont méchants.
3. Il existe des hommes méchants.
4. Il existe un homme qui n’est pas méchant.
5. Il n’existe pas d’hommes méchants.
6. Il existe un homme qui aime toutes les femmes.
7. Chaque chat connaît un chien qui le déteste.
8. Tous les poissons, sauf les requins, sont gentils avec les enfants.
9. Tous les oiseaux ne peuvent pas voler.
10. N’importe qui peut apprendre la logique s’il travaille assez.
Exercice 3
Soient les deux prédicats P et N d ?arité 1, et les formules suivantes :
1. ∀ x (P (x) ∧ N (x))
2. ∀ x (P (x) ⇒ N (x))
1
3. ∃ x (P (x) ∧ N (x))
4. ∃ x (P (x) ⇒ N (x))
Proposer des domaines D tels que si on interprète dans D, P (x) par le "sens commun" de "x
est un poisson" et N (x) par le "sens commun" de "x sait nager" on ait :
1. un modèle qui satisfait 1 et 2
2. un modèle qui satisfait 2 et pas 1
3. un modèle qui satisfait 3 et 4
4. un modèle qui satisfait 4 et pas 3
Exercice 4
Traduire en français les formules suivantes :
1. ∀ x (E(x) ⇒ (∃ y (C(y) ∧ ∃ z (M (z) ∧ T (x, y, z)))),
avec E(x) : x est étudiant, C(y) : y est un cours, M (z) : z est un mauvais enseignant,
T (x, y, z) : x suit le cours y enseigné par z.
2. ∀ x ∀ y ∀ z (T (x) ⇒ C(y, x) ∧ C(w, x) ∧ D(y, z) ∧ D(y, w)) ⇒ G(f (g(y), g(z)), g(w)),
avec T (x) : x est un triangle, C(x, y) : y est le côté de x, D(x, y) : x est différent de y,
G(x, y) : x est plus grand que y, f (x, y) : somme de x et de y, g(x) : longueur de x.
Exercice 5
Soit le langage des prédicats L = {a, b : constantes, f : symbole fonctionnel, P : symbole de prdicats}
et l’interprétation suivante :
— Le domaine D = {1, 2}
— I(a) = 1, I(b) = 2, f (1) = 2, f (2) = 1, P (2, 1) = 0, P (2, 2) = 0, P (1, 2) = 1, P (1, 1) = 1.
Établir la valeur de vérité des formules suivantes :
1. P (a, f (a)).
2. P (b, f (b)).
3. ∀ x ∀ y P (y, x).
4. ∀ x ∀ y P (y, x) ⇒ P (f (x), f (y)).
Exercice 6
Pour chaque ensemble de formules suivantes : donner le système de Herbrand et dire si
l’ensemble de formules est satisfaisable ou non.
1. {∀x (P (x) ∨ Q(x) ∨ R(x)), ¬P (a), ¬Q(b), ¬R(c)}
2. {∀x P (x), ∀x ¬Q(x), ∀x (¬P (f (x)) ∨ Q(f (x)))}
3. {∀x P (x), ∀x ¬P (f (x)), ∀x P (f (f (x))), ∀x (¬P (f (f (x))) ∨ ¬P (x) ∨ P (f (x)))}
2
Exercice 7
Soit l’ensemble de formules F = {∀x (p(x) ⇒ q(x)), ∀x(q(x) ⇒ r(x))} et la formule
F = ∀x(p(x) ⇒ r(x)). Est-ce que F |= F ? Utiliser la résolution basée sur le théorème de
Herbrand.
