Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Logik (http://www.informatikerboard.de/board/board.php?boardid=16)
----- wahrheitstabelle in knf. WARUM geht der algorithmus? (http://www.informatikerboard.de/board/thread.php?threadid=2617)
Geschrieben von Ersti111 am 24.11.2015 um 22:07:
wahrheitstabelle in knf. WARUM geht der algorithmus?
Meine Frage:
Hallo zusammen.
Ich weiß wie man aus einer wahrheitstabelle eine knf bilden kann.
(schauen in welchen zeilen formel=0, dann da eine klausel bilden mit den jeweiligen variablen (a,b,c....). Hierbei werden diejenigen variablen bei denen eine 1 eingesetzt wurde verneint.)
Meine frage ist, warum geht das ?
Meine Ideen:
Ich verstehe wie man die dnf abließt und ich weiß auch, dass
bei einer knf alle klauseln erfüllt sein müssen um die formel wahr zu machen. ...
Geschrieben von Karlito am 24.11.2015 um 23:46:
Hallo Ersti111,
Ich kann es mir gerade nur so erklären: Die KNF ist nichts weiter als die negierte DNF aller Zeilen, in der der Wahrheitswert 0 wird.
Beispiel;
![[latex]<br />
\begin{array}{c|c||c} a & b & x<br />
\hline \hline 0 & 0 & 1<br />
\hline 0 & 1 & 0<br />
\hline 1 & 0 & 0<br />
\hline 1 & 1 & 1<br />
\end{array}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\begin{array}{c|c||c} a & b & x<br />
\hline \hline 0 & 0 & 1<br />
\hline 0 & 1 & 0<br />
\hline 1 & 0 & 0<br />
\hline 1 & 1 & 1<br />
\end{array}<br />
)
Wir erhalten also:
![[latex] <br />
x & = & \overline{(\overline{a} \wedge b) \vee (a \wedge \overline{b})}<br />
& \stackrel{De Morgan}{=} & \overline{(\overline{a} \wedge b)} \wedge \overline{(a \wedge \overline{b})}<br />
& \stackrel{De Morgan}{=} & (a \vee \overline{b}) \wedge (\overline{a} \vee b)<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php? <br />
x & = & \overline{(\overline{a} \wedge b) \vee (a \wedge \overline{b})}<br />
& \stackrel{De Morgan}{=} & \overline{(\overline{a} \wedge b)} \wedge \overline{(a \wedge \overline{b})}<br />
& \stackrel{De Morgan}{=} & (a \vee \overline{b}) \wedge (\overline{a} \vee b)<br />
)
Gruß,
Kalito
Geschrieben von Ersti1111 am 24.11.2015 um 23:56:
Stimmt, das ist ein guter Ansatz, zur Begründung.
Danke
P.S: ich bin Ersti111 darf den Namen aber gerade nicht verwenden
Forensoftware: Burning Board, entwickelt von WoltLab GmbH