Hi. Um eine NNF (Negationsnormalform) in die entsprechende KNF (Konjunktive Normalform) zu konvertieren, bedient man sich meist des Distributiv-, Kommutativ- und Assoziativgesetzes.
Beispiel: NNF \( \rightarrow \) KNF
NNF = \( ((p_1 \land p_2)\lor \neg p_2) \lor p_1 \)
KNF = \( (p_1 \lor \neg p_2 \lor p_1) \land (p_2 \lor \neg p_2 \lor p_1) \)
Herleitung:
$$ \begin{array}{rcl} ((p_1 \land p_2)\lor \neg p_2) \lor p_1 & = & ((p_1 \lor \neg p_2)\land (p_2 \lor \neg p_2)) \lor p_1 \;\;\;\;\text{(Distributivgesetz)}\\ & = & ((p_1 \lor \neg p_2)\lor p_1 ) \land ((p_2 \lor \neg p_2) \lor p_1) \;\;\;\;\text{(Distributivgesetz)}\\ & = & (p_1 \lor (\neg p_2 \lor p_1)) \land (p_2 \lor (\neg p_2 \lor p_1)) \;\;\;\;\text{(Assoziativgesetz)}\\ & = & (p_1 \lor \neg p_2 \lor p_1) \land (p_2 \lor \neg p_2 \lor p_1) \\ \end{array} $$
Ferner kann man den Ausdruck in diesem Beispiel sogar vereinfachen:
$$ \begin{array}{rcl} ((p_1 \land p_2)\lor \neg p_2) \lor p_1 & = & ((p_1 \lor \neg p_2)\land (\underbrace{p_2 \lor \neg p_2}_{= 0})) \lor p_1 \\ & = & (\underbrace{(p_1 \lor \neg p_2)\land 0}_{= 0}) \lor p_1 \\ & = & 0 \lor p_1 \\ & = & p_1 \\ \end{array} $$
Ich hoffe, es hilft.
MfG
