KNF vs. DNF < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:51 So 07.05.2006 | | Autor: | dump_0 |
Hallo liebe Leute!
Ich habe ein kleines Problem mit einer Fragestellung bzgl. Normalformen und zwar geht's um folgendes:
1) Wie sieht eine zu der folgeden, in KNF gegebenen Formel F äquivalente Formel in DNF aus?
[tex]F = (x_1 \vee y_1) \wedge (x_2 \vee y_2) \wedge \ldots (x_n \vee y_n)[/tex]
2) Es dauert i.A. relativ lange die Erfüllbarkeit für ein in KNF gegebene Formel zu zeigen. Ist dies auch für in DNF gegebene Formeln der Fall?
Welche Fragestellungen sind für Formeln, die in DNF gegeben sind, aufwändig zu beantworten?
bei 1) fällt mir leider nicht viel ein, ich weiß wie man konkrete Formeln in NF in eine andere NF umwandelt, aber bei diesem allg. Fall fällt mir leider nichts ein.
2) Ich denke es ist weitaus einfacher eine erfüllende Belegung für eine Formel in DNF zu finden, da man hier ja nur ein Modell für eine Teilformel finden muss (also dass eine Belegung für die Konjunktion der einzelnen Literale gleich 1 ergibt) im Gegensatz zu Formeln in KNF wo man für alle Disjunktionen eine erfüllende Belegung finden müsste.
Bei dem anderen Teil mit der Fragestellung fällt mir leider auch nichts ein :/
Schöne Grüße
[mm] dump_0
[/mm]
|
|
| |
|
Hallo und guten Morgen,
> 1) Wie sieht eine zu der folgeden, in KNF gegebenen Formel
> F äquivalente Formel in DNF aus?
>
> [tex]F = (x_1 \vee y_1) \wedge (x_2 \vee y_2) \wedge \ldots (x_n \vee y_n)[/tex]
Allgemein kann man Boole'sche Funktionen [mm] G\colon\{0,1\}^n\to\{0,1\}
[/mm]
in KNF [mm] G(x_1,\ldots [/mm] , [mm] x_n)=\bigwedge_{a\in\{0,1\}^n, G(a)=0}''x\neq [/mm] a''
mit [mm] ''x\neq [/mm] a''= [mm] (x_1\neq a_1)\vee\ldots (x_n\neq a_n)\:\: =\:\: x_1^{1-a_1}\vee\ldots \vee x_n^{1-a_n}
[/mm]
mit [mm] x_i^b:= x_i [/mm] falls b=1 und [mm] x_i^b=\neg x_i [/mm] sonst
und in DNF
[mm] G(x_1,\ldots [/mm] , [mm] x_n)=\bigvee_{a\in\{0,1\}^n, G(a)=1}''x=a''
[/mm]
mit [mm] ''x=a''=x_1^{a_1}\wedge\ldots\wedge x_n^{a_n}
[/mm]
darstellen.
Hierüber bekommst Du sicherlich F in DNF hin:
F wird wahr gdw für [mm] 1\leq i\leq [/mm] n jeweils mindestens eine der Variablen [mm] x_i,y_i [/mm] den Wert 1 hat, also nicht beide
den Wert 0, d.h.
[mm] F=\bigvee_{a,b\in\{0,1\}^n,\forall 1\leq i\leq n\: a_i+b_i\geq 1} (x_1^{a_1}\wedge \ldots \wedge x_n^{a_n}\wedge y_1^{b_1}\wedge\ldots \wedge y_n^{b_n})
[/mm]
Es geht vielleicht auch geschikcter und kürzer, aber im Zweifel liefert Dir dieses Standard-Verfahren immerhin eine Lösung.
Gruss,
Mathias
>
>
> 2) Es dauert i.A. relativ lange die Erfüllbarkeit für ein
> in KNF gegebene Formel zu zeigen. Ist dies auch für in DNF
> gegebene Formeln der Fall?
>
> Welche Fragestellungen sind für Formeln, die in DNF gegeben
> sind, aufwändig zu beantworten?
>
>
> bei 1) fällt mir leider nicht viel ein, ich weiß wie man
> konkrete Formeln in NF in eine andere NF umwandelt, aber
> bei diesem allg. Fall fällt mir leider nichts ein.
>
> 2) Ich denke es ist weitaus einfacher eine erfüllende
> Belegung für eine Formel in DNF zu finden, da man hier ja
> nur ein Modell für eine Teilformel finden muss (also dass
> eine Belegung für die Konjunktion der einzelnen Literale
> gleich 1 ergibt) im Gegensatz zu Formeln in KNF wo man für
> alle Disjunktionen eine erfüllende Belegung finden müsste.
>
> Bei dem anderen Teil mit der Fragestellung fällt mir leider
> auch nichts ein :/
>
>
> Schöne Grüße
> [mm]dump_0[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:48 So 14.05.2006 | | Autor: | dump_0 |
Danke für deine Antwort.
Nicht ganz einfach wie ich finde, aber beim durchprobieren hat's geklappt.
Von allein wäre ich nicht drauf gekommen :)
Mfg
[mm] dump_0
[/mm]
|
|
|
|
