Révisions de Logique 2008

Exercice A : Paradoxe de Russel

Soit un langage formé de la relation binaire d'appartenance ∈ représentant l'appartenance. On cherche à décrire les ensembles de la forme $\left\{y|F[y;p_1;p_2;...;p_n]\right\}$, par exemple $A\cup B$ serait décrit par $\left\{y|y\in A\vee y\in B\right\}$. On propose alors la règle suivante :

$\overline{⊢\exists x\forall y\left(y\in x\iff F[y;p_1;p_2;...;p_n]\right)}$(axiome de compréhension)

1. Soit $G=\forall yy\in x\iff \neg \left(y\in y\right)$. Montrer que $G⊢\perp$ par déduction naturelle.
2. En déduire que cette théorie est contradictoire i.e. $⊢\perp$.
3. Montrer par la méthode de résolution que la théorie est inconsistante

Pour vous entrainer

• Un barbier peut-il raser tous les hommes qui ne se rasent pas eux-mêmes et seulement ceux-là ?
• Peut-il exister un catalogue des catalogues qui ne s'auto-référencent pas ?

Exercice B : Prouvabilité

On considère le langage suivant :

• Un symbole de constante $a$
• Un symbole de fonction unaire $f$
• Un symbole de fonction binaire $g$

Et la théorie suivante :

$\Gamma =\{\begin{array}{c}\forall x\left(gax=x\wedge gxa=x\right)\\ \forall x\left(gx\left(\mathrm{fx}\right)=a\wedge g\left(fx\right)x=a\right)\\ \forall x,y,z(g\left(gxy,z\right)=g\left(x,gyz\right))\end{array}$

Montrer que :

• $\Gamma ⊢\forall x,y\left(gxy=a\Rightarrow y=fx\right)$
• $\Gamma ⊢/\forall x,y\left(gxy=gyx\right)$

Pour vous entrainer

• $\Gamma ⊢\forall y\left(\forall x\left(gxy=x\wedge gyx=x\right)\right)\Rightarrow y=a$
• $\Gamma ⊢\forall x\left(ffx=x\right)$
• $\Gamma ⊢/\exists x,y\neg \left(gxy=gyx\right)$
• $\Gamma ⊢/\exists x\neg \left(x=a\right)$

Exercice C : Algorithme d'unification

Trouver si possible un unificateur des formules suivantes :

1. $\{\begin{array}{c}R(h(gxy,w),s,gat)\\ R(u,fy,g\left(a,gxy\right))\\ R(h\left(t,fz\right),f\left(huv\right),z)\end{array}$

   avec $a$ symbole de constante, $R$ prédicat, $f,g,h$ symboles de fonctions et $x,y,z,t,u,v,w$ des variables.

2. $\{\begin{array}{c}P(fx,fy,gzz,h\left(x,gxa,fy\right))\\ P(f\left(gab\right),f\left(gxa\right),g\left(t,f\left(gxa\right)\right),h\left(gab,y,t\right))\end{array}$

• • Accueil
  • Actualité
  • A propos
  • Infos Logo
  • Infos techniques
  • Proposer article
  • Plan du site
  • Ouvrages
  • Mailing List
  • Imprimer
• • Algèbre
  • Analyse
  • Ensembles
  • Geometrie
  • Graphes
  • Logique
  • Probabilités
  • Recherche Opérationnelle
  • Statistiques

Cette page respecte les recommandations du W3C. Son contenu est sous licence Creative Commons.