• Home
• Source
• Print

Devoir maison

À faire individuellement ou en binôme. La date limite pour rendre le devoir est fixée au 13 janvier au matin.Une seule rédaction par binôme, a rendre

• soit manuscrite et remise en main propre le jour du cours ;
• soit au format pdf, rédigée en LaTeX (pour les débutants en LaTeX il est possible d’utiliser le logiciel LyX), et envoyée par mail ;
• soit au format html, utilisant la technologie MathJax (la même utilisée pour ces pages), envoyée par mail ou hebergée par vos soins.

Word, openoffice et autres logiciels ne permettant pas un rendu correct des mathématiques, s’abstenir.

Sémantique du calcul des propositions (3 points)

On ajoute au calcul des propositions les constantes $\bot$ (faux), $\top$ (vrai), et l’opérateur ternaire $A ? B:C$, ayant la même table de vérité que $(A∧B)∨(¬A∧C)$. Cet opérateur est appelé opérateur conditionnel, par analogie avec l’opérateur du langage C.

• Montrer que les formules $(A ? B:C) ? D:E$ et $A ? (B ? D:E):(C ? D:E)$ sont équivalentes.
• Montrer que les opérateurs $¬$, $∨$, $∧$ et $→$ peuvent être remplacés par l’opérateur conditionnel et les constantes vrai et faux (autrement dit, donner des expressions équivalentes à $¬A$, $A∧B$, etc. qui n’emploient que $\bot,\top$ et l’opérateur conditionnel).

Théorie des modèles (6 points)

1. Considérer les formules

   • $∃x.∀y.R(x,y)$,
   • $∃x.∀y.R(y,x)$,
   • $∀x.∃y.\biggl(R(x,y) ∧ ∀z.\Bigl(R(x,z) → \bigl((z = y) ∨ R(x,y)\bigr)\Bigr)\biggr)$,

   déterminer si elles sont vraies dans les interprétations

   1. $ℕ$ où $R$ est interprété par $<$ ;
   2. $ℚ$ où $R$ est interprété par $<$ ;
   3. $\mathcal{P}(ℕ)$ où $R$ est interprété par $⊂$ ;

   montrer un contre-exemple si elles sont fausses, ou justifier pourquoi elles sont vraies.

2. Pour chacune des formules suivantes, donner une interprétation qui la rend vraie et une qui la rend fausse.

   • $∃x.∃y.R(x) ∧ ¬R(y)$,
   • $∀x.∃y.R(x) → \bigl(R(y) ∧ S(x,y)\bigr)$,
   • $∀x.∀y.∀z.\bigl(S(y,x) ∧ S(z,x)\bigr) → \bigl(S(y,z) ∨ S(z,y)\bigr)$.

Déduction naturelle (6 points)

En utilisant les règles de la déduction naturelles vues aux TDs 8 et 9, donner les preuves formelles des énoncés suivants.

• $\vdash p → \bigl((p → q) → q\bigr)$,

• $\vdash ¬(p → q) → (p ∧ ¬q)$ (il faut utiliser deux fois l’absurde et une fois la double négation),

• $∀x.(p→q) \vdash p→∀x.q$ si $x$ n’est pas libre dans $p$,

Déduction naturelle et fonctions (8 points)

Dans cet exercice on utilise le langage constitué du seul symbole $=$. On va voir que cela suffit a exprimer et prouver par déduction naturelle quelques propriétés élémentaires des fonctions.

1. Soit $f$ un symbole de fonction, écrire formellement les propriétés « $f$ est injective » et « $f$ est surjective ». Dans la suite on notera $I$ et $S$ ces deux formules.

2. Écrire formellement « il existe deux éléments $x$ et $y$ distincts ». Dans la suite on notera $D$ cette formule.

3. Donner une preuve (informelle) du fait que, s’il existe une fonction $f:A→B$ non injective, alors $A$ contient au moins deux éléments distincts.

4. Soit $I'$ la formule $∃x.∃y.(f(x)=f(y)) ∧ ¬(x=y)$. Donner la preuve formelle de $I' \vdash D$.

5. Esquisser la preuve formelle de $¬I \vdash I'$. (Dur ! Il faut utiliser plusieurs fois l’absurde, la double négation, et la preuve de $¬∀x.p\vdash ∃x.¬p$ vue au TD 9)

6. Conclure que $¬I\vdash D$.