• Home
• Source
• Print

TD 8 – Théorie de la preuve

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)$.

Déduction naturelle

Dans cette partie, nous allons utiliser les règles de la déduction naturelle, que nous rappelons ci-dessous.

Hypothèse	$\dfrac{}{p\vdash p}H$	Affaiblissement	$\dfrac{\Gamma\vdash p }{\Gamma, q \vdash p }W$
Tiers exclus	$\dfrac{}{\Gamma\vdash p \vee\neg p }T$	Double négation	$\dfrac{}{\neg\neg p\vdash p}D_\neg$
Preuve par l’absurde	$\dfrac{\Gamma,p\vdash q \wedge\neg q }{\Gamma\vdash\neg p }A$
Introduction du et	$\dfrac{\Gamma\vdash p \qquad \Gamma\vdash q }{\Gamma\vdash p \wedge q } I_\wedge$	Élimination du et	$\dfrac{\Gamma\vdash p \wedge q }{\Gamma\vdash p }L_\wedge$	$\dfrac{\Gamma\vdash p \wedge q }{\Gamma\vdash q }R_\wedge$
Introduction du ou	$\dfrac{\Gamma\vdash p }{\Gamma\vdash p \vee q }L_\vee$	$\dfrac{\Gamma\vdash q }{\Gamma\vdash p \vee q }R_\vee$	Élimination du ou	$\dfrac{\Gamma\vdash p \vee q \qquad \Gamma \vdash p \to r \quad \Gamma\vdash q \to r}{\Gamma\vdash r}E_\vee$
Modus ponens	$\dfrac{\Gamma\vdash p \qquad \Gamma\vdash p \to q }{\Gamma\vdash q }M$	Déduction	$\dfrac{\Gamma,p\vdash q }{\Gamma\vdash p \to q }D$

1. Écrire les preuves formelles des affirmations suivantes.

   • $p\wedge q \vdash p$,
   • $p\vdash p\vee q$,
   • $\vdash (p\wedge q) \to p$,
   • $p\to q, p \vdash q$,
   • $p \vdash q \to p$ (suggestion: considérer l’affaiblissement),
   • $p \vdash \neg\neg p$ (suggestion: utiliser l’absurde),
   • $\vdash p \to (q \to p)$,
   • $p,\neg p \vdash \neg q$,
   • $p,\neg p \vdash q$ (suggestion: utiliser la double négation et le modus ponens),
   • $\vdash (p\to q) \to (\neg q \to \neg p)$ (très dur, l’absurde est la clef).

2. En vous appuyant sur les preuves formelles prouvées auparavant, démontrer les affirmations suivantes**

   • Si $n$ est strictement positif, alors $n\ne 0$.
   • $n=3m$ implique que $n$ est pair, mais $n$ est impair alors $3m\ne n$.