Aussagenlogische Formeln in DNF und KNF bringen

02.10.2013, 10:50

un1x

Aussagenlogische Formeln in DNF und KNF bringen

Hi

Ich versuche folgende Formeln in DNF und KNF zu bringen.

$\begin{eqnarray*} p \rightarrow (q \lor (p1 \wedge p2)) \end{eqnarray*}$
$\begin{eqnarray*} \lnot p \lor (q \lor (p1 \wedge p2)) \end{eqnarray*}$

DNF:
$\begin{eqnarray*} \lnot p \lor ((q \lor p1) \wedge (q \lor p2)) \end{eqnarray*}$

KNF:
$\begin{eqnarray*} \lnot p \lor ((q \lor p1) \wedge (q \lor p2)) \end{eqnarray*}$
$\begin{eqnarray*} (\lnot p \lor (q \lor p1)) \wedge (\lnot p \lor (q \lor p2)) \end{eqnarray*}$

Ist das richtig so?

02.10.2013, 12:40

Math1986

Auf diesen Beitrag antworten »

RE: Aussagenlogische Formeln in DNF und KNF bringen

Zitat:

Original von un1x
Hi

Ich versuche folgende Formeln in DNF und KNF zu bringen.

$\begin{eqnarray*} p \rightarrow (q \lor (p1 \wedge p2)) \end{eqnarray*}$
$\begin{eqnarray*} \lnot p \lor (q \lor (p1 \wedge p2)) \end{eqnarray*}$

DNF:
$\begin{eqnarray*} \lnot p \lor ((q \lor p1) \wedge (q \lor p2)) \end{eqnarray*}$

Das ist keine disjunkte Normalform. In den Komponenten einer DNF darf kein $\begin{eqnarray*} \lor \end{eqnarray*}$ vorkommen.

Du hast da was zuviel umgeformt:
$\begin{eqnarray*} p \rightarrow (q \lor (p_1 \land p_2)) \end{eqnarray*}$
Das ist, wie du schon gesehen hast:
$\begin{eqnarray*} \lnot p \lor q \lor \left(p_1 \wedge p_2\right) \end{eqnarray*}$
Ab hier hast du schon eine DNF.

Zitat:

Original von un1x
KNF:
$\begin{eqnarray*} \lnot p \lor ((q \lor p1) \wedge (q \lor p2)) \end{eqnarray*}$
$\begin{eqnarray*} (\lnot p \lor (q \lor p1)) \wedge (\lnot p \lor (q \lor p2)) \end{eqnarray*}$

Ist das richtig so?

Auch das sind keine KNF.

Du solltest dir nochmal anschauen, wie KNF und DNF definiert sind, und diese Definition hier posten.

02.10.2013, 13:05

un1x

Auf diesen Beitrag antworten »

RE: Aussagenlogische Formeln in DNF und KNF bringen

Zitat:

Auch das sind keine KNF.

Du solltest dir nochmal anschauen, wie KNF und DNF definiert sind, und diese Definition hier posten.

Hi

Definition DNF: Und-Bloecke mit Oder verknuepft. Beispiel

$\begin{eqnarray*} (x1 \wedge x2) \lor (x2 \wedge x4) \end{eqnarray*}$

Definition KNF: Oder-Bloecke mit Und verknuepft. Beispiel

$\begin{eqnarray*} (x1 \lor x2) \wedge (x2 \lor x4) \end{eqnarray*}$

Wenn ich mein Beispiel anschaue, sind doch das oder Bloecke mit Und verknuepft?

$\begin{eqnarray*} (\lnot p \lor (q \lor p1)) \wedge (\lnot p \lor (q \lor p2)) \end{eqnarray*}$

02.10.2013, 14:05

Math1986

Auf diesen Beitrag antworten »

RE: Aussagenlogische Formeln in DNF und KNF bringen

Zitat:

Original von un1x
Wenn ich mein Beispiel anschaue, sind doch das oder Bloecke mit Und verknuepft?

$\begin{eqnarray*} (\lnot p \lor (q \lor p1)) \wedge (\lnot p \lor (q \lor p2)) \end{eqnarray*}$

Ja, das zweite stimmt.

PS: Da und bzw oder sowiso kommutativ ist, ist es sinnvoll, die Klammern nur um die Blöcke selbst zu setzen, nicht in den Blöcken. Dadurch erkennt man die "Blöcke" auf einen Blick.

Also:
$\begin{eqnarray*} \left(\lnot p\lor q\lor p_1\right)\wedge\left(\lnot p\lor q\lor p_2\right) \end{eqnarray*}$

02.10.2013, 14:13

un1x

Auf diesen Beitrag antworten »

Ok danke. Dann passts smile

Neue Frage »

Antworten »

Aussagenlogische Formeln in DNF und KNF bringen

Verwandte Themen