TP 5 : Introduction à la logique du premier ordre

Systèmes Logiques

Pour chacune des formules suivantes, dessinez un arbre syntaxique et donnez leurs variables libres.

  1. ∃x(A(x,y)∧B(y)).
  2. ∃x(∃y((A(x,y)⇒B(x)))).
  3. ∀x(A(x)) ∧ B(x).
  4. ∀x(A(x)∧B(y)).
  5. ∀x(∃y(∀z(P(x,y,z)))∧R(z))
Correction
  1. {y}
G r ∃x And ∧ r->And A A(x,y) And->A B B(y) And->B
  1. ∅
G e1 ∃x e2 ∃y e1->e2 Imp ⇒ e2->Imp A A(x,y) Imp->A B B(y) Imp->B
  1. {x}, en effet, la portée du ∀x s’arrête après A(x).
G q1 ∀x A A(x) q1->A And ∧ And->q1 B B(x) And->B
  1. {y}
G q1 ∀x And ∧ q1->And A A(x) And->A B B(y) And->B
  1. {z}, la dernière occurrence de z n’est pas liée.
G q1 g∀x And ∧ q1->And q2 ∃y q3 ∀z q2->q3 A P(x,y,z) q3->A And->q2 B R(z) And->B

Essayez de traduire les affirmations suivantes en logique du premier ordre. On prendra soin de définir le langage utilisé.

  1. Il existe des chats qui ont des poils et il existe des chats qui n’ont pas de poils.
  2. Tous les chats ont soit des poils soit pas de poils.
  3. Les grenouilles sont vertes.
  4. Certaines grenouilles sont vertes.
  5. Il existe un humain tel que si cet humain boit, alors tous les humains boivent.
  6. Bob aime tout le monde et tout le monde aime Bob.
  7. Alice aime tous les humains.
  8. Si Alice aime tous les humains alors il n’existe aucun humain qui n’est pas aimé par Alice.
  9. Pour tout humain, les amis des amis de cet humain sont ses amis.
Correction
  1. ∃x(Chat(x)∧Poil(x)) ∧ ∃y(Chat(y)∧¬Poil(y))
  2. ∀x(Chat(x)⇒(Poil(x)∨¬Poil(x)))
  3. ∀x(Grenouille(x)⇒Vert(x)): attention ici, écrire ∀x(Grenouille(x)∧Vert(x)) ne serait pas correct car on sous-entendrait que toutes les x sont des grenouilles aussi.
  4. ∃x(Grenouille(x)∧Vert(x))
  5. ∃x(Humain(x)∧(Bois(x)⇒(∀y(Humain(y)⇒Bois(y)))))
  6. ∀x(Aime(Bob,x)) ∧ ∀x(Aime(x,Bob))
  7. P = ∀x(Humain(x)⇒Aime(Alice,x))
  8. P ⇒ ¬(∃x(Humain(x)∧¬Aime(Alice,x)))
  9. ∀x(Humain(x)⇒(∀y∀z((Ami(x,y)∧Ami(y,z))⇒Ami(x,z))))

Pour chaque affirmation de l’exercice précédent, indiquez si elles vous semblent toujours vraies ou non. Si non, proposez une structure où l’affirmation n’est pas réalisée (un contre-modèle).

Correction
  1. Non, il suffit de prendre une interprétation I où ChatI = ∅.
  2. C’est un théorème de la LPO. Voir le chapitre sur le calcul des séquents pour le prouver.
  3. Non, il suffit de prendre une interprétation I où GrenouilleI = {Crazy} et VertI = ∅.
  4. Non, il suffit de prendre une interprétation I où GrenouilleI = ∅.
  5. C’est un théorème de la LPO connu sous le nom du paradoxe des buveurs.
  6. Non il suffit de prendre une interprétation sur le domaine {A, B}, AimeI = ∅ et BobI = B.
  7. Non, même problème qu’au-dessus. Attention, si on prend un ensemble d’humains vide, cela ne conviendrait pas car dans ce cas, effectivement, Alice aimerait tous les humains (vu qu’il n’y en a pas).
  8. C’est un théorème de la LPO!
  9. On prend HumainI = {A, B, C} et AmiI = {(A,B), (B,C)}. C’est un contre modèle vu qu’on n’a pas (A,C) dans AmiI.