Logique (mathématiques)/Exercices/Forme Normale Disjonctive

Partie A

Soit $\phi =\neg (x\land y\land z)\land (x\land y\lor x\land z\lor y\land z)$.

1. Construire la table de vérité de cette fonction
2. Conserver les contextes de cette table où $\phi =1$

Solution

$x$	$y$	$z$	$\neg (x\land y\land z)$	$x\land y$	$x\land z$	$y\land z$	$\phi$
0	0	0	1	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	1	1
1	0	0	1	0	0	0	0
1	0	1	1	0	1	0	1
1	1	0	1	1	0	0	1
1	1	1	0	1	1	1	0

La FND de $\phi$ est $(\neg x\land y\land z)\lor (x\land \neg y\land z)\lor (x\land y\land \neg z)$

 

Partie B

Soit $\psi =(x\iff \neg z)\lor (\neg x\iff y)$.

1. Construire la table de vérité de cette fonction
2. Conserver les contextes de cette table où $\psi =1$

Solution

$x$	$y$	$z$	$x\iff \neg z$	$\neg x\iff y$	$\psi$
0	0	0	0	0	0
0	0	1	1	0	1
0	1	0	0	1	1
0	1	1	1	1	1
1	0	0	1	1	1
1	0	1	0	1	1
1	1	0	1	0	1
1	1	1	0	0	0

La FND de $\psi$ est $(\neg x\land \neg y\land z)\lor (\neg x\land y\land \neg z)\lor (\neg x\land y\land z)\lor (x\land \neg y\land \neg z)\lor (x\land \neg y\land z)\lor (x\land y\land \neg z)$

 

Partie C

Reprendre la formule $\psi$ de la partie B :

• À l'aide de transformations équivalentes successives, retrouver la FND de $\psi$.

Solution

${\begin{aligned}\psi &=(x\iff \neg z)\lor (\neg x\iff y)\\&\equiv (x\Rightarrow \neg z)\land (\neg z\Rightarrow x)\lor (\neg x\Rightarrow y)\land (y\Rightarrow \neg x)\\&\equiv (\neg x\land z)\lor (\neg x\land x)\lor (\neg z\land z)\lor (\neg z\land x)\lor (x\land \neg y)\lor (x\land \neg x)\lor (y\land \neg y)\lor (y\land \neg x)\\&\equiv (\neg x\land z)\lor (\neg z\land x)\lor (x\land \neg y)\lor (y\land \neg x)\\&\equiv (\neg x\land z\land (y\lor \neg y))\lor (\neg z\land x\land (y\lor \neg y))\lor (x\land \neg y\land (z\lor \neg z))\lor (y\land \neg x\land (z\lor \neg z))\\&\equiv (\neg x\land z\land y)\lor (\neg x\land z\land \neg y)\lor (\neg z\land x\land y)\lor (\neg z\land x\land \neg y)\lor (x\land \neg y\land z)\lor (x\land \neg y\land \neg z)\lor (y\land \neg x\land z)\lor (y\land \neg x\land \neg z)\\&\equiv (\neg x\land z\land y)\lor (\neg x\land z\land \neg y)\lor (\neg z\land x\land y)\lor (\neg z\land x\land \neg y)\lor (x\land \neg y\land z)\lor (y\land \neg x\land \neg z)\end{aligned}}$