Logique (mathématiques)/Exercices/Cohérence et formes clausales

Exercices

Voici 2 types d'exercices pour les formes clausales.

Type 1 : À partir de la négation

Soit la conséquence suivante : $\models ((p\rightarrow q)\lor (r\rightarrow s))\rightarrow (p\land r\rightarrow q\lor s)$.

• Est-elle vraie ? Prouvez-le en utilisant la méthode de résolution (appliquée aux formes clausales).

Solution

• Nous simplifions la conséquence en enlevant les implications :

${\begin{aligned}&\models ((p\rightarrow q)\lor (r\rightarrow s))\rightarrow (p\land r\rightarrow q\lor s)\\&\models \neg ((\neg p\lor q)\lor (\neg r\lor s))\lor (\neg (p\land r)\lor q\lor s)\\&\models \neg (\neg p\lor q\lor \neg r\lor s)\lor (\neg p\lor \neg r\lor q\lor s)\\&\models (p\land \neg q\land r\land \neg s)\lor \neg p\lor \neg r\lor q\lor s\\\end{aligned}}$

• Nous prenons la négation de la conséquence, on arrive donc à :

$\models (\neg p\lor q\lor \neg r\lor s)\land p\land r\land \neg q\land \neg s$
Nous avons donc 5 clauses que l’on retrouve du point 1 à 5.
${\begin{aligned}&1.\neg p\lor q\lor \neg r\lor s\\&2.p\\&3.r\\&4.\neg q\\&5.\neg s\\&6.q\lor \neg r\lor s\qquad (1,2)\\&7.\neg r\lor s\qquad (4,6)\\&8.s\qquad (3,7)\\&9.\Box \qquad (5,8)\\\end{aligned}}$
La conséquence est donc vraie.

 

Type 2 : À partir de la contradiction

Soit la conséquence suivante : $\models (a\land b\lor c\land d)\land (a\rightarrow \neg a)\land \neg c$.

• Est-elle vraie ? Prouvez-le en utilisant la méthode de résolution (appliquée aux formes clausales).

Solution

• Nous simplifions la conséquence en enlevant les implications :

${\begin{aligned}&\models (a\land b\lor c\land d)\land (a\rightarrow \neg a)\land \neg c\\&\models (a\lor c\land a\lor d\land b\lor c\land b\lor d)\land (\neg a\lor \neg a)\land \neg c\\&\models (a\lor c\land a\lor d\land b\lor c\land b\lor d)\land \neg a\land \neg c\\\end{aligned}}$

• Nous montrons sa contradiction, donc nous n'avons pas besoin de la négation de la conséquence.

On a donc 6 clauses que l’on retrouve du point 1 à 6.
${\begin{aligned}&1.a\lor c\\&2.a\lor d\\&3.b\lor c\\&4.b\lor d\\&5.\neg a\\&6.\neg c\\&7.c\qquad (1,5)\\&8.\Box \qquad (6,7)\\\end{aligned}}$
La contradiction est vraie, donc la conséquence est fausse.