Logique propositionnelle
Soit $A$, $B$ et $C$ trois propositions en logique propositionnelle. Avec une table de vérité, montrer que $((A \to (B \to C)) \to ((A \to B) \to (A \to C)))$ est une tautologie. Bien indiquer en quoi la table permet d’affirmer que c’est une tautologie.
Existe-t-il trois formules de logique propositionnelle $\phi$, $\psi$ et $\chi$ telles que $((\phi \to (\psi \to \chi)) \to ((\phi \to \psi) \to (\phi \to \chi)))$ n’est pas une tautologie ? Si oui, lesquelles ? Sinon, le prouver.
On nomme $F$ la formule $((A \to (B \to C)) \to ((A \to B) \to (A \to C)))$. On établit la table de vérité comme suit :
| $A$ | $B$ | $C$ | $(B \to C)$ | $(A \to B)$ | $(A \to C)$ | $(A \to (B \to C))$ | $((A \to B) \to (A \to C))$ | $F$ |
|---|---|---|---|---|---|---|---|---|
| ⊥ | ⊥ | ⊥ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ |
| ⊥ | ⊥ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ |
| ⊥ | ⊤ | ⊥ | ⊥ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ |
| ⊥ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ |
| ⊤ | ⊥ | ⊥ | ⊤ | ⊥ | ⊥ | ⊤ | ⊤ | ⊤ |
| ⊤ | ⊥ | ⊤ | ⊤ | ⊥ | ⊤ | ⊤ | ⊤ | ⊤ |
| ⊤ | ⊤ | ⊥ | ⊥ | ⊤ | ⊥ | ⊥ | ⊥ | ⊤ |
| ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ | ⊤ |
La table montre que c’est une tautologie car quelles que soient les valeurs de vérité affectées aux propositions de la formule, la formule globale est interprétée comme vraie. Autrement dit, c’est parce que toutes les lignes ont la valeur $\top$ qu’on peut dire que c’est une tautologie.
Si nous remplacions les propositions $A$, $B$ et $C$ par des sous-formules quelconques et que nous construisions la table de vérité, nous arriverions inexorablement à remplir une portion de table comme suit :
| $\phi$ | $\psi$ | $\chi$ | $(\psi \to \chi)$ | $(\phi \to \psi)$ | $(\phi \to \chi)$ | $(\phi \to (\psi \to \chi))$ | $((\phi \to \psi) \to (\phi \to \chi))$ | $F'$ |
|---|
Puisque les formules $\phi$, $\psi$ et $\chi$ ne peuvent prendre que les valeurs de vérité $\bot$ ou $\top$, la formule finale ne prendra donc que la valeur $\top$ conformément à la première table de vérité ci-dessus. Donc il s’agira d’une tautologie.
On pourrait généraliser le résultat en constatant, par la même approche par table de vérité, que si une formule $F$ ne dépendant que des propositions $A_1, \dots, A_n$ (avec $n$ un entier strictement positif) est une tautologie, alors toute formule construite à partir de $F$ en remplaçant $A_1, \dots, A_n$ par des formules quelconques $\phi_1, \dots, \phi_n$ est aussi une tautologie.
Qu’en est-il d’une formule simplement satisfiable ? Si l’on remplace les propositions composant une telle formule, la formule résultante est-elle aussi simplement satisfiable ?
Le gâteau de mariage des Kennedy a été mangé avant la cérémonie. Smith, Stuart et Peterson sont les seuls à avoir pu s’approcher du gâteau le jour du méfait. On les interroge et ils répondent chacun les phrases suivantes :
- Smith : Je ne l’ai pas mangé. J’ai une intolérance au sucre. Si je l’avais mangé, je serais à l’hôpital.
- Stuart : Je n’ai pas mangé le gâteau. Smith n’arrête pas de se goinfrer de sucreries. C’est sûrement lui.
- Peterson : Je ne mange pas de dessert. Smith et Stuart, eux, sont de grands gourmands. Ils ont dû manger le gâteau tous les deux.
Les analyses médico-légales de la scène du crime révèlent que le gâteau n’a été mangé que par une seule personne. L’enquêteur Holmes décide que seul le coupable a pu mentir et que donc les deux autres récits sont vrais. Modéliser les déclarations des suspects en logique propositionnelle (bien expliquer quelles sont les propositions). En utilisant ce que l’on sait par ailleurs, indiquer qui est le coupable en le démontrant.
Cet exercice était particulièrement délicat car, contrairement aux exercices traités en TD, il laissait libre la manière de répondre à la question. En outre, les énoncés correspondent à des déclarations plausibles incluant des affirmations catégoriques et des supputations. Si l’on considérait que les conjectures des protagonistes étaient des propositions logiques au même titre que les affirmations pures et simples, alors on arrivait à la conclusion que l’exercice était mal posé. L’idée de traiter les conjectures comme des propositions était tout à fait raisonnable compte tenu de tout ce qui avait été vu en cours, mais il fallait se remettre en question si l’on concluait que l’auteur de l’examen se trompe. Voyons donc une manière de traiter l’exercice.
On introduit les propositions suivantes :
- $G_\mathrm{Smith}$ : « Smith a mangé le gâteau »
- $G_\mathrm{Stuart}$ : « Stuart a mangé le gâteau »
- $G_\mathrm{Peterson}$ : « Peterson a mangé le gâteau »
- $S_\mathrm{Smith}$ : « Smith mange des sucreries »
- $S_\mathrm{Stuart}$ : « Stuart mange des sucreries »
- $S_\mathrm{Peterson}$ : « Peterson mange des sucreries »
- $D_\mathrm{Smith}$ : « La déclaration de Smith est vraie »
- $D_\mathrm{Stuart}$ : « La déclaration de Stuart est vraie »
- $D_\mathrm{Peterson}$ : « La déclaration de Peterson est vraie »
La proposition « untel mange des sucreries » est une simplification pour dire que untel est en mesure de manger des choses sucrées.
Nous indiquons ce qu’implique chaque déclaration si elles sont vraies avec les formules suivantes :
- $F_1 = (D_\mathrm{Smith} \to (\neg G_\mathrm{Smith} \wedge \neg S_\mathrm{Smith}))$
- $F_2 = (D_\mathrm{Stuart} \to (\neg G_\mathrm{Stuart} \wedge S_\mathrm{Smith}))$
- $F_3 = (D_\mathrm{Peterson} \to (\neg G_\mathrm{Peterson} \wedge S_\mathrm{Smith} \wedge S_\mathrm{Stuart}))$
Notons qu’ici, on ne considère pas que la phrase « C’est sûrement lui » implique nécessairement que « c’est lui ». En d’autres termes, le fait que Stuart dise la vérité n’implique pas nécessairement que Smith est coupable. Toutefois, on pourrait interpréter « sûrement » d’une autre manière : si c’est sûr, alors il ne peut en être autrement. Mais prétendre que c’est là nécessairement la bonne manière d’interpréter le terme « sûrement » serait une erreur, car on sait que « sûrement » n’est pas nécessairement synonyme de « nécessairement ». « Sûrement » peut simplement indiquer une forte probabilité, donc permettre l’éventualité de ne pas être vraie. De la même façon, il faut être prudent avec l’expression « Ils ont dû manger le gâteau tous les deux ». Encore une fois, même si Peterson dit la vérité, ceci n’implique pas nécessairement que Stuart et Smith ont tous les deux manger le gâteau. « Ils ont dû » est le signe d’une supposition que l’on pense fortement probable. Donc cette assersion permet le doute et donc autorise que la conclusion soit fausse. Malgré tout, écrivons les formules en supposant que les conjectures de Stuart et Peterson ont valeur de propositions logiques puis continuons :
- $F'_2 = (D_\mathrm{Stuart} \to (\neg G_\mathrm{Stuart} \wedge S_\mathrm{Smith} \wedge D_\mathrm{Smith}))$
- $F'_3 = (D_\mathrm{Peterson} \to (\neg G_\mathrm{Peterson} \wedge S_\mathrm{Smith} \wedge S_\mathrm{Stuart} \wedge D_\mathrm{Smith} \wedge D_\mathrm{Stuart}))$
La présence de Smith, Stuart et Peterson, les analyses médico-légales et l’intuition de Holmes assurent que :
- Analyses médico-légales avec présence de Smith, Stuart et Peterson : $$F_4 = ((G_\mathrm{Smith} \wedge \neg G_\mathrm{Stuart} \wedge \neg G_\mathrm{Peterson}) \vee (\neg G_\mathrm{Smith} \wedge G_\mathrm{Stuart} \wedge \neg G_\mathrm{Peterson}) \vee (\neg G_\mathrm{Smith} \wedge \neg G_\mathrm{Stuart} \wedge G_\mathrm{Peterson}))$$
- Intuition de Holmes : $$F_5 = ((D_\mathrm{Smith} \wedge D_\mathrm{Stuart} \wedge \neg D_\mathrm{Peterson}) \vee (D_\mathrm{Smith} \wedge \neg D_\mathrm{Stuart} \wedge D_\mathrm{Peterson}) \vee (\neg D_\mathrm{Smith} \wedge D_\mathrm{Stuart} \wedge D_\mathrm{Peterson}))$$
Les propos de Smith et de Stuart se contredisent (la déclaration de l’un implique $\neg S_\mathrm{Smith}$ tandis que celle de l’autre implique le contraire). Donc, d’après l’intuition de Holmes, soit Smith ment, soit Stuart ment, mais pas les deux, et aussi Peterson dit vrai. La déclaration de Peterson implique que Smith mange des sucreries, tandis que Smith affirme le contraire. Comme Peterson dit vrai, c’est forcément Smith qui ment et c’est lui le coupable.
Dans le cas où on avait utilisé les formules alternatives $F'_2$ et $F'_3$, on aurait conclu qu’il y a une incohérence dans l’énoncé. Peterson ne peut pas dire vrai si les analyses médico-légales sont correctes. Notons que Peterson n’est pas nécessairement au courant des analyses et donc son hypothèse qu’il y ait deux coupables n’est pas une preuve de mensonge.
On aurait aussi pu modéliser le fait que Smith est ou non à l’hôpital. Mais ceci n’aurait servi à rien car cette connaissance n’interagit pas du tout avec le reste. C’est aussi inutile que de savoir qu’il portait une chemise verte ou bleue. En effet, si Smith dit la vérité, alors il n’a pas mangé le gâteau et il a une intolérance au sucre. Il pourrait donc avoir évité d’aller à l’hôpital, mais en fait, on ne sait pas s’il y est ou non. Il pourrait tout aussi bien y être pour d’autres raisons. Si en revanche, Smith ment, alors selon l’intuition de l’enquêteur, il doit être le coupable, et donc savoir s’il est à l’hôpital ou non n’a aucune importance.
Avec une table de vérité, ou bien la méthode des tableaux ou la méthode par résolution, on pourrait arriver à cette même conclusion. On cherche à montrer que $((F_1 \wedge F_2 \wedge F_3 \wedge F_4 \wedge F_5) \to G_\mathrm{Smith})$. Une table de vérité serait catastrophiquement longue à faire à la main. La méthode des tableaux est très fastidieuse car elle mène à de très nombreux embranchements. La méthode par résolution est efficace si on s’y prend bien pour mettre sous forme normale conjonctive. Faisons-le ainsi :
- $((\neg D_\mathrm{Smith} \vee \neg G_\mathrm{Smith}) \wedge (\neg D_\mathrm{Smith} \vee \neg S_\mathrm{Smith}))$
- $((\neg D_\mathrm{Stuart} \vee \neg G_\mathrm{Stuart}) \wedge (\neg D_\mathrm{Stuart} \vee S_\mathrm{Smith}))$
- $((\neg D_\mathrm{Peterson} \vee \neg G_\mathrm{Peterson}) \wedge (\neg D_\mathrm{Peterson} \vee S_\mathrm{Smith}) \wedge (\neg D_\mathrm{Peterson} \vee S_\mathrm{Stuart}))$
- $((\neg G_\mathrm{Smith} \vee \neg G_\mathrm{Stuart}) \wedge (\neg G_\mathrm{Stuart} \vee \neg G_\mathrm{Peterson}) \wedge (\neg G_\mathrm{Smith} \vee \neg G_\mathrm{Peterson}) \wedge (G_\mathrm{Smith} \vee G_\mathrm{Stuart} \vee G_\mathrm{Peterson}))$
- $((D_\mathrm{Smith} \vee D_\mathrm{Stuart}) \wedge (D_\mathrm{Stuart} \vee D_\mathrm{Peterson}) \wedge (D_\mathrm{Smith} \vee D_\mathrm{Peterson}) \wedge (\neg D_\mathrm{Smith} \vee \neg D_\mathrm{Stuart} \vee \neg D_\mathrm{Peterson}))$
- $\neg G_\mathrm{Smith}$
Mise sous forme clausale :
| $(C_1)$ | $\neg D_\mathrm{Smith}$ | $\neg G_\mathrm{Smith}$ | |
| $(C_2)$ | $\neg D_\mathrm{Smith}$ | $\neg S_\mathrm{Smith}$ | |
| $(C_3)$ | $\neg D_\mathrm{Stuart}$ | $\neg G_\mathrm{Stuart}$ | |
| $(C_4)$ | $\neg D_\mathrm{Stuart}$ | $S_\mathrm{Smith}$ | |
| $(C_5)$ | $\neg D_\mathrm{Peterson}$ | $\neg G_\mathrm{Peterson}$ | |
| $(C_6)$ | $\neg D_\mathrm{Peterson}$ | $S_\mathrm{Smith}$ | |
| $(C_7)$ | $\neg D_\mathrm{Peterson}$ | $S_\mathrm{Stuart}$ | |
| $(C_8)$ | $\neg G_\mathrm{Smith}$ | $\neg G_\mathrm{Stuart}$ | |
| $(C_9)$ | $\neg G_\mathrm{Stuart}$ | $\neg G_\mathrm{Peterson}$ | |
| $(C_{10})$ | $\neg G_\mathrm{Smith}$ | $\neg G_\mathrm{Peterson}$ | |
| $(C_{11})$ | $G_\mathrm{Smith}$ | $G_\mathrm{Stuart}$ | $G_\mathrm{Peterson}$ |
| $(C_{12})$ | $D_\mathrm{Smith}$ | $D_\mathrm{Stuart}$ | |
| $(C_{13})$ | $D_\mathrm{Stuart}$ | $D_\mathrm{Peterson}$ | |
| $(C_{14})$ | $D_\mathrm{Smith}$ | $D_\mathrm{Peterson}$ | |
| $(C_{15})$ | $\neg D_\mathrm{Smith}$ | $\neg D_\mathrm{Stuart}$ | $\neg D_\mathrm{Peterson}$ |
| $(C_{16})$ | $\neg G_\mathrm{Smith}$ |
On peut obtenir la clause vide grâce à la suite de clauses obtenues par résolution :
| $(C_{17})$ | $G_\mathrm{Stuart}$ | $G_\mathrm{Peterson}$ | obtenue par la résolution de $C_{11}+C_{16}$ |
| $(C_{18})$ | $\neg D_\mathrm{Stuart}$ | $G_\mathrm{Peterson}$ | obtenue par la résolution de $C_{3}+C_{17}$ |
| $(C_{19})$ | $\neg D_\mathrm{Stuart}$ | $\neg D_\mathrm{Peterson}$ | obtenue par la résolution de $C_{5}+C_{18}$ |
| $(C_{20})$ | $D_\mathrm{Smith}$ | $\neg D_\mathrm{Peterson}$ | obtenue par la résolution de $C_{12}+C_{19}$ |
| $(C_{21})$ | $D_\mathrm{Smith}$ | obtenue par la résolution de $C_{14}+C_{20}$ | |
| $(C_{22})$ | $\neg S_\mathrm{Smith}$ | obtenue par la résolution de $C_{2}+C_{22}$ | |
| $(C_{23})$ | $\neg D_\mathrm{Stuart}$ | obtenue par la résolution de $C_{4}+C_{22}$ | |
| $(C_{24})$ | $D_\mathrm{Peterson}$ | obtenue par la résolution de $C_{13}+C_{23}$ | |
| $(C_{25})$ | $S_\mathrm{Smith}$ | obtenue par la résolution de $C_{6}+C_{24}$ | |
| $(C_{26})$ | $\square$ | obtenue par la résolution de $C_{22}+C_{25}$ |
Logique des prédicats
Avec la méthode de résolution, démontrer qu’à partir des hypothèses $H_1$, $H_2$ et $H_3$, on peut déduire logiquement $C$ :
- $(H_1)$ $\forall x(\exists y R(x, y) \to R(x, f(x)))$
- $(H_2)$ $\forall x\exists y R(x, y)$
- $(H_3)$ $\exists x R(f(f(x)), x)$
- $(C)$ $\exists x\exists y\exists z (R(x, y) \wedge R(y, z) \wedge R(z, x))$
Montrer que $H_1$, $H_2$ et $H_3$ implique logiquement $C$ est équivalent à montrer que $H_1\wedge H_2\wedge H_3\wedge \neg C$ est une contradiction. On applique alors les premières phases de la méthode indépendemment sur chaque formule $H_1$, $H_2$, $H_3$ et $\neg C$.
Mise sous forme prénexe :
- $(H_1)$ $\forall x\forall y (R(x, y) \to R(x, f(x)))$
- $(H_2)$ $\forall x\exists y R(x, y)$
- $(H_3)$ $\exists x R(f(f(x)), x)$
- $(\neg C)$ $\forall x\forall y\forall z \neg (R(x, y) \wedge R(y, z) \wedge R(z, x))$
Mise sous forme de Skolem, avec $c_3$ nouvelle constante et $g_2$ un nouveau symbole de fonction unaire. On se permet de retirer les quantificateurs car, à partir de maintenant, toutes les variables sont quantifiées universellement :
- $(H_1)$ $(R(x, y) \to R(x, f(x)))$
- $(H_2)$ $R(x, g_2(x))$
- $(H_3)$ $R(f(f(c_3)), c_3)$
- $(\neg C)$ $\neg (R(x, y) \wedge R(y, z) \wedge R(z, x))$
Mise sous forme normale conjonctive :
- $(H_1)$ $(\neg R(x, y) \vee R(x, f(x)))$
- $(H_2)$ $R(x, g_2(x))$
- $(H_3)$ $R(f(f(c_3)), c_3)$
- $(\neg C)$ $(\neg R(x, y) \vee \neg R(y, z) \vee \neg R(z, x))$
Mise sous forme clausale en renommant les variables pour éviter des conflits lors de l’unification :
| $(C_1)$ | $\neg R(x_1, y_1)$ | $R(x_1, f(x_1))$ | |
| $(C_2)$ | $R(x_2, g_2(x_2))$ | ||
| $(C_3)$ | $R(f(f(c_3)), c_3)$ | ||
| $(C_4)$ | $\neg R(x_4, y_4)$ | $\neg R(y_4, z_4)$ | $\neg R(z_4, x_4)$ |
On applique alors la résolution de la façon suivante :
| $(C_5)$ | $R(x_2, f(x_2))$ | obtenue par la résolution de $C_1+C_2$ | $[x_1\mapsto x_2, y_1\mapsto g_2(x_2)]$ | |
| $(C_6)$ | $\neg R(c_3, z_4)$ | $\neg R(z_4, f(f(c_3)))$ | obtenue par la résolution de $C_3+C_4$ | $[x_4\mapsto f(f(c_3)), y_4\mapsto c_3]$ |
| $(C_7)$ | $\neg R(c_3, f(c_3))$ | obtenue par la résolution de $C_5+C_6$ | $[x_2\mapsto f(c_3), z_4\mapsto f(c_3)]$ | |
| $(C_8)$ | ◻ | obtenue par la résolution de $C_5+C_7$ | $[x_2\mapsto c_3]$ |
Modéliser les affirmations suivantes en logique des prédicats, en utilisant uniquement les prédicats suggérés, dont l’arité est précisée après le symbol / :
- Toutes les souris sont plus petites que tous les éléphants.
Souris/1,Éléphant/1,plusPetiteQue/2 - Deux êtres humains sont cousins l’un de l’autre si un des parents de l’un est le frère ou la sœur d’un parent de l’autre.
Humain/1,estParentDe/2,estFrèreOuSœurDe/2,estCousinDe/2 - Qui vole un œuf, vole un bœuf.
vole/2,Œuf/1,Bœuf/1 - Un gentleman est un homme qui sait jouer de la cornemuse mais qui n’en joue pas.
Gentleman/1,Homme/1,Cornemuse/1,saitJouer/2,joue/2
- Sur cette question, il n’y avait pas vraiment d’alternative à ceci : $$\forall x \forall y ((\mathtt{Souris}(x)\wedge \mathtt{\'El\'ephant}(y))\to\mathtt{plusPetiteQue}(x,y))$$
- Sur cette question, on pouvait préférer une forme prénexe, mais il n’y avait pas non plus beaucoup de choix possibles. On aurait pu préciser que les parents sont aussi des humains, mais ceci n’est pas mentionné dans l’énoncé. $$\forall x \forall y ((\mathtt{Humain}(x)\wedge \mathtt{Humain}(y)\wedge \mathtt{estCousinDe}(x, y))\to \exists z\exists t (\mathtt{estParentDe}(z, x)\wedge \mathtt{estParentDe}(t, y) \wedge \mathtt{estFr\`ereOuSœurDe}(z,t)))$$
- Ici encore, on pourrait renvoyer tous les quantificateurs au début sans les changer, mais à part ça, il est difficile d’interpréter la phrase autrement que : $$\forall x\forall y ((\mathtt{vole}(x, y)\wedge \mathtt{Œuf}(y))\to \exists z (\mathtt{vole}(x, z)\wedge \mathtt{Bœuf}(z)))$$
- Cette phrase pouvait mener à des alternatives potentielles. Savoir jouer de la cornemuse signifie-t-il que l’on sait jouer de toutes les cornemuses ? Mais s’il s’agit de certaines cornemuses (au moins une), alors n’est-ce que de ces cornemuses-là que le gentleman ne joue pas ? La formule qui suit suppose que savoir jouer de la cornemuse signifie savoir jouer de toutes les cornemuses, et que donc le gentleman ne joue d’aucune cornemuse : $$\forall x(\mathtt{Gentleman}(x)\to (\mathtt{Homme}(x)\wedge \forall y(\mathtt{Cornemuse}(y)\to (\mathtt{saitJouer}(x, y)\wedge \neg\mathtt{joue}(x, y)))))$$