Contrôle Continu 2

5 Mars 2025

Dans tout cet exercice, F est une formule sous forme normale conjonctive et on note res(C,D) le resolvant de deux clauses.

  1. Vrai ou faux (on justifiera sommairement) :
    1. Si F est satisfiable et que C est une clause de F, alors F \ {C} (la formule obtenu en enlevant C à F) est satisfiable.
    2. Si F est satisfiable, C et D sont deux clauses de F alors F ∧ res(C,D) est satisfiable.
    3. Il existe des formules non satisfiables qui n’ont pas de réfutation en résolution.
  2. Donnez res(C,D) où C ≡ x ∨ y ∨ ¬z et D ≡ x ∨ w ∨ z.
Correction

1.a. Vrai : si τ est un modèle de F, alors il satisfait toutes les clauses de F. En particulier, il satisfait toutes les clauses de F \ {C}. Donc F \ {C} est satisfiable.

1.b. Vrai, res(C,D) est une conséquence logique de F donc si τ ⊨ F, τ ⊨ res(C,D). A fortiori, τ ⊨ F ∧ res(C,D). Donc si F est satisfiable, F ∧ res(C,D) l’est aussi.

1.c. Faux : toutes les formules contradictoire ont une réfutation en résolution, c’est la complétude de la résolution. On l’a prouvé en cours en utilisant la résolution de Davis-Putnam.

Pour chacune des formules suivantes, écrire l’arbre syntaxique et donnez les variables libres.

  1. ∀x(R(x,y)∧∃z(R(x,z)∨T(z,u))).
  2. (∀x∃yR(x,y)) ∧ S(x,y).
  3. ∃x(¬R(x)∨∃y(S(x,y))).
  4. ∀z(R(x)∧¬S(y))
Correction
  1. Les variables libres sont {y, u}.
  2. Les variables libres sont {y}.
  3. Il n’y a pas de variable libre.
  4. Les variables libres sont {x, y}.

Formalisez en logique du premier ordre les énoncés ci-dessous dans le langage du premier ordre n’ayant pas de constante, pas de symbole de constantes et les prédicats suivant (l’arité est donnée entre parenthèse) : Grenouille(1), Mouche(1), Amphibiens(1), Insecte(1), Animal(1), AimeManger(2). Pour chacune des formules que vous avez écrites, donnez un modèle et un contre-modèle.

  1. Toutes les grenouilles sont des amphibiens et toutes les mouches sont des insectes.
  2. Il y a au moins une grenouille qui aime manger des mouches mais aucune mouche n’aime manger de grenouilles.
  3. Il y a des animaux qui ne sont ni des grenouilles, ni des mouches.
  4. Il n’existe pas d’animal qui soit à la fois un amphibien et un insecte.
Correction
  1. ∀x(Grenouille(x)⇒Amphibien(x)) ∧ ∀x(Mouche(x)⇒Insecte(x)).

Un modèle : on considère l’univers U = {G, M}, Grenouille = Amphibien = {G} et Mouche = Insecte = {M}. Remarquons que si on prend Grenouille = Mouche = ∅, ça marche aussi!

Pour un contre modèle, toujours sur l’univers U = {G, M}, on prend Grenouille = {G}, Amphibien = ∅ (et ce qu’on veut pour Mouche et Insecte).

  1. ∃x(Grenouille(x)∧∀y(Mouche(y)⇒AimeManger(x,y))) ∧ ∀y(∀x((Mouche(y)∧Grenouille(x))⇒¬AimeManger(y,x))).

Un modèle : toujours sur l’univers U = {G, M}, Grenouille = {G} et Mouche = {M} et AimeManger = {(G,M)}.

Un contre-modèle : Grenouille = {G} et Mouche = {M} et AimeManger = ∅.

  1. ∃x(Animal(x)∧¬Grenouille(x)∧¬Mouche(x)).

Un modèle : sur l’univers U = {A}, Animal = {A} et Mouche = Grenouille = ∅.

Un contre-modèle : sur l’univers U = {A}, Animal = Grenouille = {A}.

  1. ¬∃x(Animal(x)∧Grenouille(x)∧Mouche(x)).

Un modèle : Animal = {A}, Grenouille = {A}, Mouche = ∅.

Un contre-modèle : Animal = {A}, Grenouille = {A}, Mouche = {A}.

Donnez les formules obtenues après avoir appliqué les substitutions demandées.

  1. F ≡ ∃x(A(x,y)∧B(x,y)). Donnez F[y=f(z)].
  2. F ≡ ∀x(R(x,y)⇒S(y)). Donnez F[y=f(y)].
  3. F ≡ ∃x(R(x,y)∧∃y.S(y)). Donnez F[y=g(x,x)].
  4. F ≡ ∀x(∃z(T(z,y)∨¬R(x,y))). Donnez F[y=g(x,z)].
Correction
  1. ∃x(A(x,f(z))∧B(x,f(z))).
  2. ∀x(R(x,f(y))⇒S(f(y))).
  3. Attention à la capture ! Et on ne renomme pas une variable liée voyons!.

∃u(R(u,g(x,x))∧∃y.S(y)).

  1. ∀u(∃v(T(v,g(x,z))∨¬R(u,g(x,z)))).