Soit $P$, $Q$ et $R$ trois propositions en logique propositionnelle. En utilisant une table de vérité, déterminer si $((P\to\neg Q)\to R)$ est une tautologie, une contradiction ou simplement satisfiable en le justifiant clairement.
Soit $\phi$, $\psi$ et $\chi$ trois formules quelconques de logique propositionnelle. En justifiant brièvement, la formule $((\phi\to\neg\psi)\to\chi)$ peut-elle être une tautologie ? Une contradiction ? Simplement satisfiable ?
On nomme $F$ la formule $((P\to\neg Q)\to R)$. On établit la table de vérité comme suit :
| $P$ | $Q$ | $R$ | $\neg Q$ | $(P\to\neg Q)$ | $F$ |
|---|---|---|---|---|---|
| ⊥ | ⊥ | ⊥ | ⊤ | ⊤ | ⊥ |
| ⊥ | ⊥ | ⊤ | ⊤ | ⊤ | ⊤ |
| ⊥ | ⊤ | ⊥ | ⊥ | ⊤ | ⊥ |
| ⊥ | ⊤ | ⊤ | ⊥ | ⊤ | ⊤ |
| ⊤ | ⊥ | ⊥ | ⊤ | ⊤ | ⊥ |
| ⊤ | ⊥ | ⊤ | ⊤ | ⊤ | ⊤ |
| ⊤ | ⊤ | ⊥ | ⊥ | ⊥ | ⊤ |
| ⊤ | ⊤ | ⊤ | ⊥ | ⊥ | ⊤ |
La table montre que la formule n’est ni une tautologie, ni une contradiction, puisqu’il existe au moins un cas où la formule est satisfaite et au moins un cas où la formule ne l’est pas. La formule est donc simplement satisfiable.
La formule $((\phi\to\neg\psi)\to\chi)$ peut être une tautologie. En effet, si $A$ est une proposition et que $\phi=A$, $\psi=A$ et $\chi=\neg A$ alors la formule est toujours satisfaite. La formule peut aussi être une contradiction dans le cas où $\phi=A$, $\psi=\neg A$ et $\chi=(A\wedge\neg A)$. Enfin, la proposition peut être simplement satisfiable comme dans le cas de la première question.
On veut modéliser le jeu du pierre–feuille–ciseaux (aussi appelé pierre–papier–ciseaux ou chifoumi) en logique propositionnelle. On ne considère qu’un unique duel où deux joueurs ne font en tout qu’un seul geste de la main qui représente soit une pierre (poing fermé), soit une feuille (main tendue), soit des ciseaux (index et majeur formant un « V »). On suppose qu’il y a un joueur numéro 1 et un joueur numéro 2. On introduit les propositions suivantes :
- $P_1$ (respectivement $P_2$) indique que le joueur 1 (resp. joueur 2) a fait le geste de la pierre.
- $F_1$ (respectivement $F_2$) indique que le joueur 1 (resp. joueur 2) a fait le geste de la feuille.
- $C_1$ (respectivement $C_2$) indique que le joueur 1 (resp. joueur 2) a fait le geste des ciseaux.
- $W_1$ (respectivement $W_2$) indique que le joueur 1 (resp. joueur 2) a gagné le duel.
- $L_1$ (respectivement $L_2$) indique que le joueur 1 (resp. joueur 2) a perdu le duel.
- $N$ indique que le duel a abouti à un match nul.
Écrivez, en utilisant les propositions introduites ci-dessus et aucune autre, des formules en logique propositionnelle modélisant les affirmations suivantes :
- Si l’un des deux joueurs gagne, alors il ne perd pas.
- Un des deux joueurs gagne si et seulement si l’autre perd.
- Un joueur ne peut pas faire plusieurs gestes à la fois.
- Si les deux joueurs font le même geste, alors il y a match nul.
- Si un joueur fait une pierre et l’autre une feuille, alors celui qui a fait la feuille gagne.
- Si un joueur fait une feuille et l’autre des ciseaux, alors celui qui a fait les ciseaux gagne.
- Si un joueur fait des ciseaux et l’autre un pierre, alors celui qui a fait la pierre gagne.
- S’il y a match nul, alors aucun des deux joueurs ne gagne.
On peut modéliser les phrases comme suit :
- $((W_1\to\neg L_1)\wedge(W_2\to\neg L_2))$
- $((W_1\leftrightarrow L_2)\wedge(W_2\leftrightarrow L_1))$
- $((P_1\to(\neg F_1\wedge\neg C_1))\wedge(F_1\to(\neg C_1\wedge\neg P_1))\wedge(C_1\to(\neg P_1\wedge\neg F_1))\wedge(P_2\to(\neg F_2\wedge\neg C_2))\wedge(F_2\to(\neg C_2\wedge\neg P_2))\wedge(C_2\to(\neg P_2\wedge\neg F_2)))$
- $(((P_1\wedge P_2)\vee(F_1\wedge F_2)\vee(C_1\wedge C_2))\to N)$
- $(((P_1\wedge F_2)\to W_2)\wedge((P_2\wedge F_1)\to W_1))$
- $(((F_1\wedge C_2)\to W_2)\wedge((F_2\wedge C_1)\to W_1))$
- $(((C_1\wedge P_2)\to W_2)\wedge((C_2\wedge P_1)\to W_1))$
- $(N\to(\neg W_1\wedge\neg W_2))$
Notons que la modélisation précédente n’impose pas que les joueurs aient fait un geste. Dans le cas où l’un des deux joueurs n’a fait aucun geste (c’est-à-dire qu’il y a un $i\in\{1,2\}$ tel que $P_i$, $F_i$ et $C_i$ sont tous interprétés comme vrais), alors il est possible que $W_1$, $W_2$, $L_1$, $L_2$ et $N$ soit tous interprétés comme faux. Cela signifie que faute de geste de l’un des joueurs, l’issue du duel ne peut être déterminé avec certitude. On pourrait ajouter la contrainte qu’un geste parmi les trois possibles doit avoir été effectué par les deux joueurs, mais la modélisation précédente permet de laisser la possibilité aux participants de ne pas jouer ou bien de faire un geste non autorisé.
Soient les formules de logique du premier ordre suivantes :
- $(H_1)$ $\forall x(P(x)\to\neg P(f(x)))$
- $(H_2)$ $\forall y(P(f(y))\to Q(y))$
- $(H_3)$ $\forall z(Q(z)\to(\neg\exists t\neg P(t)\vee \neg\exists u Q(u)))$
- $(C)$ $\forall v\neg P(f(v))$
Montrer, en utilisant le principe de résolution, que $H_1\wedge H_2\wedge H_3$ permet de déduire logiquement $C$. Faites très attention à appliquer et à détailler très rigoureusement chaque étape.
Il faut montrer que $H_1\wedge H_2\wedge H_3\wedge\neg C$ est contradictoire. 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(P(x)\to\neg P(f(x)))$
- $(H_2)$ $\forall y(P(f(y))\to Q(y))$
- $(H′_3)$ $\forall z\forall t\forall u(Q(z)\to(\neg\neg P(t)\vee \neg Q(u)))$
- $(\neg C)$ $\exists v\neg\neg P(f(v))$
Mise sous forme de Skolem, avec $c$ nouvelle constante. On se permet de retirer les quantificateurs car, à partir de maintenant, toutes les variables sont quantifiées universellement :
- $(H′_1)$ $(P(x)\to\neg P(f(x)))$
- $(H′_2)$ $(P(f(y))\to Q(y))$
- $(H″_3)$ $(Q(z)\to(\neg\neg P(t)\vee \neg Q(u)))$
- $(\neg C′)$ $\neg\neg P(f(c))$
Mise sous forme normale conjonctive :
- $(H″_1)$ $(\neg P(x)\vee\neg P(f(x)))$
- $(H″_2)$ $(\neg P(f(y))\vee Q(y))$
- $(H‴_3)$ $(\neg Q(z)\vee P(t)\vee\neg Q(u))$
- $(\neg C″)$ $P(f(c))$
Mise sous forme clausale :
| $(C_1)$ | $\neg P(x)$ | $\neg P(f(x))$ | |
| $(C_2)$ | $\neg P(f(y))$ | Q(y) | |
| $(C_3)$ | $\neg Q(z)$ | P(t) | \neg Q(u) |
| $(C_4)$ | $P(f(c))$ | $\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)$ | $\neg P(c)$ | obtenue par la résolution de $C_1+C_4$ | $[x\mapsto c]$ | |
| $(C_6)$ | $\neg Q(z)$ | $\neg Q(u)$ | obtenue par la résolution de $C_3+C_5$ | $[t\mapsto c]$ |
| $(C_7)$ | $\neg P(f(z))$ | $\neg Q(u) | obtenue par la résolution de $C_2+C_6$ | $[y\mapsto z]$ |
| $(C_8)$ | $\neg Q(u)$ | $ | obtenue par la résolution de $C_4+C_7$ | $[z\mapsto c]$ |
| $(C_9)$ | $\neg P(f(u))$ | $ | obtenue par la résolution de $C_2+C_8$ | $[y\mapsto u]$ |
| $(C_10)$ | ◻ | obtenue par la résolution de $C_4+C_9$ | $[u\mapsto c]$ |
Annexes
Syntaxe
La logique des propositions traite des expressions construites à l’aide d’un vocabulaire 𝓥 constitué de propositions (ou atomes) 𝓟 et d’opérateurs (ou connecteurs) 𝓒 :
- 𝓟 = {p, q, …}
- 𝓒 = {¬, ∧, ∨, →, ↔}
- 𝓥 = 𝓟 ⋃ 𝓒 ⋃ {(, )}
Les symboles de 𝓟 (p, q, etc.) dénotent des affirmations telles que « le moteur est en marche », « la vanne de sécurité est ouverte », « la cuve de liquide radioactif fuit », etc. On remplace ces affirmations par des symboles neutres pour s’affranchir du sens particulier de ces phrases et pour ne se concentrer que sur la cohérence, la validité du raisonnement, et non sur le sens des propositions elles-mêmes.
Nous proposons ici un ensemble de connecteurs parmi d’autres existants, plus ou moins riches — e.g. {¬, ∨}, {¬, ∧}, {¬, ∧, ∨}, etc.
- Expression
- Une expression est une concaténation de termes de 𝓥.
On note 𝓥* l’ensemble de toutes les expressions que l’on peut former avec le vocabulaire 𝓥.
pq(, p→, ¬∧ sont des expressions de 𝓥*.
On construit, sur 𝓥, le langage propositionnel 𝓛0 ⊂ 𝓥* (ou ensemble de formules) comme étant le plus petit sous-ensemble de 𝓥* obtenu par les lois suivantes :
- tout atome appartient à 𝓛0 ;
- si φ ∈ 𝓛0 et ψ ∈ 𝓛0 alors ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) ∈ 𝓛0 ;
- il n’existe pas d’autres façons d’obtenir un élément de 𝓛0.
Seules les expressions formées à partir des règles indiquées sont dites « bien formées ».
- Formule
- On appelle formule ou ebf (expression bien formée) tout élément de 𝓛0.
Sémantique
La sémantique détermine les règles d’interprétations des propositions, et permet ainsi d’attacher des valeurs de vérité à des formules.
- Interprétation
- On appelle interprétation toute application I : 𝓟 ⟶ {⊤, ⊥}. ⊤ (ou Vrai ou 1) et ⊥ (ou Faux ou 0) sont appelées valeurs de vérité.
Une interprétation est une correspondance entre des éléments de 𝓛0 et une image du monde extérieur ; cette correspondance peut être étendue à toutes les formules de 𝓛0 en reprenant les lois de construction de 𝓛0. Soit une formule η ∈ 𝓛0, l’interprétation étendue d’une formule η, notée I[η], est obtenue récursivement de la façon suivante :
- si η est un atome, alors I[η] est obtenue directement par I
- si η est obtenue par la loi (ii), plusieurs cas sont possibles :
- η = ¬φ alors I[η] = ⊤ ssi I[φ] = ⊥
- η = (φ ∧ ψ) alors I[η] = ⊤ ssi I[φ] = I[ψ] = ⊤
- η = (φ ∨ ψ) alors I[η] = ⊤ ssi I[φ] = ⊤ ou I[ψ] = ⊤
- η = (φ → ψ) alors I[η] = ⊤ ssi I[φ] = ⊥ ou I[ψ] = ⊤
- η = (φ ↔ ψ) alors I[η] = ⊤ ssi I[φ] = I[ψ]
Voici quelques définitions et notations essentielles, reposant sur la notion de sémantique et d’interprétation en logique des propositions. Il s’agit ici de qualifier les différentes formules selon leur interprétation.
- Tautologie
- On appelle tautologie toute formule φ telle que I[φ] = ⊤ pour toute interprétation I. On écrit alors : ⊨ φ
- Contradiction
- On appelle contradiction toute formule φ telle que I[φ] = ⊥ pour toute interprétation I.
- Satisfiabilité
- Une formule φ est dite satisfiable s’il existe au moins une interprétation I telle que I[φ] = ⊤.
- Conséquence logique
- On note φ ⊨ ψ (ψ conséquence logique de φ) si pour toute interprétation I telle que I[φ] = ⊤ alors I[ψ] = ⊤.
- Équivalence logique
- On note φ ≡ ψ (ψ équivalent logiquement à φ) ssi φ ⊨ ψ et ψ ⊨ φ.
Principe de résolution
Les étapes de la méthode par résolution sont les suivantes :
- Transformer le problème en une recherche de contradiction.
- Mise sous forme prénexe.
- Mise sous forme de Skolem.
- Mise sous forme normale conjonctive.
- Mise sous forme clausale.
- Application du principe de résolution en indiquant quelles clauses sont utilisées et quelles valeurs sont affectées aux variables pour unifier les littéraux opposés.