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

**Forme Normale Disjonctive**
Leçon : Logique

Exercices n^o1

Exercices de niveau 15.
Exo préc. :	Sommaire
Exo suiv. :	Forme Normale Conjonctive

En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Forme Normale Disjonctive
Logique (mathématiques)/Exercices/Forme Normale Disjonctive », n'a pu être restituée correctement ci-dessus.

Partie A[modifier | modifier le wikicode]

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

Construire la table de vérité de cette fonction
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[modifier | modifier le wikicode]

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

Construire la table de vérité de cette fonction
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[modifier | modifier le wikicode]

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}}$