Informatiker Board | Druckvorschau: Umwandlung von DNF in KNF

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)
--- Umwandlung von DNF in KNF (http://www.informatikerboard.de/board/thread.php?threadid=2054)

Geschrieben von Fragesteller am 08.01.2015 um 20:45:

Umwandlung von DNF in KNF

Meine Frage:
Hallo,

ich möchte Wissen wie man A ^ (B v C ) in die KNF bringt.

Meine Ideen:
Habe nun folgendes gemacht : ( A ^ B) v (A ^ C)

Wie geht es nun weiter? Was sind denn die Regeln?

Geschrieben von eulerscheZahl am 08.01.2015 um 21:06:

Damit hast du eigentlich schon eine konjunktive Normalform. Wenn du aber eine kanonische haben willst:
Das einfachste ist, sich eine Wahrheitstabelle zu machen und daraus dann die einzelnen teile abzulesen, wo die Funktion 1 wird und mit einem ODER zu verknüpfen.
$[latex](A\wedge\overline{B}\wedge C) \vee (A\wedge B\wedge \overline{C}) \vee (A\wedge B \wedge C)[/latex]$
algebraische Umformungen sind zwar prinzipiell möglich, aber unnötig kompliziert.

Geschrieben von Fragesteller am 09.01.2015 um 15:54:

Danke, habe jetzt folgende Aussagen zusammen:

1. A v B v C

2. ¬ A v B v C

3. B v ¬ C

4. ¬ B v ¬ C

5. C v ¬ B

Ich muss sie nun mittels Resolution lösen. Wie gehe ich nun am besten vor? Ich weiß, dass ich eine Behauptung aufstellen und diese negieren muss.

Also habe ich

6. ¬ B

......

(1 + 2) 7 : B v C
(7+4) 8: Wiederspruch .... Also sind B und C die Täter?

Hab das mit der Resolution noch nicht so verstanden. Oder ist das richtig?