Von KNF in DNF < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:03 Di 04.12.2007 | | Autor: | pho3n1x |
| Aufgabe | Sei [mm] n \ge 1 [/mm] und [mm] \varphi_n := \wedge^n_{i=1} (X_i \gdw Y_i) [/mm]. Zeigen Sie das jede zu [mm] \varphi_n [/mm] äquivalente Formel in DNF mindestens [mm] 2^n [/mm] konjunktive Klauseln hat.
Hinweis: Betrachten Sie eine beliebige Formel [mm] \psi_n [/mm], die äquivalent zu [mm] \varphi_n [/mm] ist und in DNF ist. Zeigen Sie, dass es für jede Konjunktion [mm] (\lambda_1 \wedge ... \wedge \lambda_n) [/mm] mit [mm] var(\lambda_i) = X_i [/mm] mindestens eine konjunktive Klausel von [mm] \psi_n [/mm] gibt, die [mm] (\lambda_1 \wedge ... \wedge \lambda_n) [/mm] als Subformel enthält. |
Wollte das ganze über eine vollständige Induktion über n beweisen. Induktionsanfang usw. sind klar. Nur im Induktionsschritt stecke ich fest, weil ich einfach nicht auf die DNF Formel (für ein beliebiges n) komme.
Also das aller Erste was ich versucht hatte, war erstmal die Biimplikation los zu werden. Dann würde sich folgendes ergeben:
(1) [mm] \wedge^n_{i=1} ((\neg X_i \vee Y_i) \wedge (\neg Y_i \vee X_i)) [/mm] (als KNF)
bzw.
(2) [mm] \wedge^n_{i=1} ((\neg X_i \wedge \neg Y_i) \vee (Y_i \wedge X_i)) [/mm]
Mit der letzte Formel hatte ich mir die resultierenden Formel für verschiedene Werte angeguckt (n=1, n=2, n=3) und diese in eine DNF überführt (für konkrete n-Werte war das für mich auch kein Problem gewesen). Das Problem ist jetzt aber, dass ganze allgemein für [mm] \varphi_n [/mm] zu machen, um anschließend im Induktionschritt von n+1 auf n zu kommen. Ich Komme von (1) oder (2) nicht auf eine äquivalente DNF.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:00 Fr 07.12.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
