Anzahl Klauseln in Formel < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen,
habe folgendes Problem: es sei der Operand [mm] \oplus [/mm] das ausschließende oder. Wenn man jetzt eine Formel [mm] F={A_1 \oplus A_1 \oplus ... \oplus A_n} [/mm] hat, wie kann man dann zeigen, dass äquivalente DNF- bzw. KNF-Darstellungen von F (die mittels Wahrheitstabellen abgeleitet wurden) aus genau [mm] $2^{n-1}$ [/mm] Klauseln bestehen?
Also d.h. ja dann, dass pro A, welches hinzukommt, sich die Anzahl der Klauseln verdoppelt, oder? Habe das mal für $n=2$ und $n=4$ "per Hand" mittelns Wahrheitstabellen ausprobiert und es stimmt.
Aber wie zeige ich das formal/elementar?
Vielen Dank im voraus und liebe Grüße,
Janine
P.S. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Wollte nur sagen, dass sich die Frage erledigt hat. Weiß jetzt, wie es funktioniert.
Liebe Grüße, Janine
|
|
|
| |
|
hi, also ich habe es net gerafft...
kannst du mir bitte das ergebnis vll geben oder nen tipp wie du es gemacht hast! thx
|
|
|
| |
|
Hallo und guten Morgen,
also sein [mm] f(x_1,\ldots [/mm] , [mm] x_n)=x_1\oplus\ldots \oplus x_n.
[/mm]
Bilden wir die KNF:
[mm] f(x_1,\ldots [/mm] , [mm] x_n)=\bigwedge_{a\in\{0,1\}^n,\sum_ia_i\:\: gerade}(x_1^{1-a_1}\vee\ldots \vee x_n^{1-a_n})
[/mm]
Dass diese Darstellung in konjuntiver Normalform exp. gross ist, sieht man sofort.
Eine andere Aufgaben ist es, zu zeigen,. daß jede Darst. in KNF exponentiell gross ist.
Sei [mm] f(x_1,\ldots [/mm] , [mm] x_n)= C_1\wedge \ldots \wedge C_m \:\:\: (\star)
[/mm]
mit Klauseln [mm] C_i. [/mm] Annahme: Es gibt eine Klausel [mm] C_j [/mm] und eine Variable [mm] x_i, [/mm] so dass in [mm] C_j [/mm] weder [mm] x_i [/mm] noch [mm] \neg x_i [/mm] vorkommt.
Dann kann [mm] (\star) [/mm] nicht gelten: Zu jeder Belegung, die [mm] C_j [/mm] falsch macht, kann man [mm] x_i [/mm] frei wählen, und eine der beiden Wahlen macht
stets die Parität zu 1.
Also enthält dann jede Klausel alle Variablen (d.h. zu jeder Variablen genau eines der Literale [mm] x_i,\neg x_i [/mm] (dass nicht beide in [mm] C_j [/mm] vorkommen dürfen,
überlegt man sich nämlich analog).
Nun schliesst also jede der Klauseln genau eine Belegung der Variablen aus, und die Frage ist: Reicht das schon als Beweis, dass es
exponentiell viele Klauseln sein müssen ? Erscheint mir verdächtig einfach.
Viele Gruesse,
Mathias
|
|
|
|
