• Home
• Source
• Print

TD7 – Sémantique du calcul des prédicats

Modèles booléens

1. Parmi les formules suivantes, indiquer lesquelles sont des tautologies, des antilogies, satisfaisables ou falsifiables.

   • $\neg p \vee p$,
   • $\neg p \wedge q$,
   • $\neg p \wedge p$,
   • $(p \to q) \vee (q \to p)$,
   • $p \wedge p$,
   • $(p \to q) \to (\neg q \to \neg q)$,

2. Soient $p$ et $q$ deux formules. Parmi les affirmations suivantes, lesquelles sont vraies (au niveau metalogique)?

   Si l’affirmation est vraie, montrer un exemple à l’aide des tables de vérité et justifier pourquoi c’est vrai dans le cas général. Si l’affirmation est fausse, donner un contre-exemple à l’aide des tables de vérité.

   • $p$ est une tautologie si et seulement si sa négation est une antilogie.
   • Si $p$ et $q$ sont satisfaisables, alors $p\wedge q$ est satisfaisable.
   • Si $p$ et $q$ sont des tautologies, alors $p\wedge q$ est une tautologie.
   • Si $p\vee q$ est une tautologie, alors au moins l’une de $p$ ou $q$ est une tautologie.
   • Si $p\leftrightarrow q$ est une tautologie, alors $p$ et $q$ sont des tautologies.

3. Soient $p$ et $q$ deux formules. Parmi les affirmations suivantes, lesquelles sont vraies (au niveau metalogique, bien sûr)?

   • $p \models p$,
   • $p\wedge q \models p$,
   • $p,q\models p$,
   • $p\vee q \models p$,
   • $p\to q \models p$,
   • $(p \vee \neg p) \to q \models q$,
   • $\neg p \wedge p\models q$.

4. Même exercice qu’avant, mais esquissez seulement les preuves.

   • $p,q\models r$ si et seulement si $(p\wedge q)\models r$,
   • $p\models q$ si et seulement si $p\to q$ est une tautologie,
   • Si $p\models r$, alors $p\wedge q \models r$,
   • Si $p\models r$, alors $p\vee q \models r$,
   • Si $p\models r$ et $q\models r$, alors $p\vee q\models r$,
   • $p\models q$ et $p\models r$ si et seulement si $p\models q\wedge r$,
   • $p\models q$ si et seulement si $p\models q\vee r$,
   • Si $p\models r$ et $\neg p\models r$, alors $r$ est une tautologie,
   • Si $p\models q$ et $p\models \neg q$, alors $\models\neg p$,
   • Si $p\models q$ et $q\models r$, alors $p\models r$,

Modèles du calcul des prédicats

1. On note A1, A2 et A3 les trois formules suivantes :

   A1 : $∀x. ∃y. y = x + 1$ ;

   A2 : $∃x. ∀y. x ≤ y$ ;

   A3 : $∀x. ∀y. \bigl( (x + 1 = y + 1 ) ⇒ x = y \bigr)$.

   • Montrer que ces trois formules sont indépendantes.
   • Donner trois modèles très différents vérifiant ces trois formules.

2. Donner des contre-exemples pour montrer que les formules suivantes ne sont pas toujours vraies :

   • $\bigl(∀x. ∃y. A(x, y)\bigr) ⇒ ∃y. A(y, y)$ ;
   • $\bigl(∃x. ∃y. A(x, y)\bigr) ⇒ ∃y. A(y, y)$ ;
   • $\bigl((∃x. A(x)) ⇔ (∃x. B(x))\bigr) ⇒ ∀x. (A(x) ⇔ B(x))$ ;
   • $\bigl(∃x. A(x) ⇒ B(x)\bigr) ⇒ \bigl((∃x. A(x)) ⇒ (∃x. B(x))\bigr)$.

3. Déterminer si les formules suivantes sont toujours vraies :

   • $\bigl((∃x. A(x)) ⇒ (∃x. B(x))\bigr) ⇒ \bigl(∃x. A(x) ⇒ B(x)\bigr)$ ;
   • $¬\bigl(∃y. ∀x. A(x, y) ⇔ ¬ A(x, x) \bigr)$ ;
   • $\bigl(∀x. ∃y. A(x, y) ⇒ B(x, y) \bigr) ⇔ \bigl(∀x. ∃y. ¬A(x, y) ∨ B(x, y) \bigr)$.