DNF/KNf < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | In der Aussagenlogik können Sie jede beliebige Formel in eine äquivalente Formel in DNF überführen. Wie viele unterschiedliche Terme (und-verknüpfte Literale) kann eine solche Formel maximal enthalten? |
Hallo,
habe bei obiger Aufgabe nicht wirklich eine Idee. Meine Gedanken bisher:
Bei n Variablen habe ich quasi 2n Literale, da ich ja auch immer die Negation der Variable nehmen kann. Die maximale Anzahl an Termen ist nun die max. Anzahl der Kombinationen, wie ich die Dinger zu Konjunktionen zusammenbasteln kann. Im Falle von drei Varibalen also bspw. die Anzahl aller möglichen 3er-Kombinationen, 2er-Kombinationen und "1er-Kombinationen, sprich:
[mm] \bruch{(2n)!}{(2n-3)!}+\bruch{(2n)!}{(2n-2)!}+\bruch{(2n)!}{(2n-1)!}
[/mm]
Allgemein also: [mm] \summe_{i=1}^{n}\bruch{(2n)!}{(2n-i)!}
[/mm]
Allerdings habe ich so das Gefühl, als ob diese Lösung ziemlich falsch wäre. Daher wollte ich mal hier nach der richtigen Lösung fragen.
Diese Frage wurde in keinen anderen Foren gestellt.
|
|
| |
|
Hallo,
du hast bei n Variablen [mm] 2^n [/mm] mögliche Kombinationen von Einganszuständen. (z.B. n=3: www - wwf - wfw....). Du hast also ebenso [mm] 2^n [/mm] Ausgangszustände, nämlich für jede Eingansbelegung genau eine! Da die Terme in der DNF aus den Belegungen für Ausgang = wahr gebildet werden, hast du maximal [mm] 2^n [/mm] unterschiedliche Terme (in denen kommen alle n Eingangsvariablen vor, wenn du vereinfachen kannst, werden es ja nur weniger)
Gruss Christian
|
|
|
| |
|
Sind das aber nicht (viel) zu wenige?
Wenn ich bspw. folgende DNF mit drei Variablen habe:
[mm] (a\vee b\vee c)\wedge(a\vee b\vee\neg c)\wedge(a\vee\neg b\vee c)\wedge(a\vee\neg b\vee\neg c)\wedge(\neg a\vee b\vee c)\wedge(\neg a\vee b\vee\neg c)\wedge(\neg a\vee\neg b\vee c)\wedge(\neg a\vee\neg b\vee\neg c)\wedge(a\vee b)\wedge(a\vee\neg b)\wedge(\neg a\vee b)\wedge(\neg a\vee\neg b)_{}
[/mm]
Dabei handelt es sich ja um eine DNF und diese hat 12 unterschiedliche Terme. Aber laut [mm] 2^{3} [/mm] dürfte sie ja nur acht haben. Und 12 ist ja noch immer nicht das Maximum, es gibt ja immer noch weitere....
|
|
|
| |
|
> Sind das aber nicht (viel) zu wenige?
>
> Wenn ich bspw. folgende DNF mit drei Variablen habe:
>
> [mm](a\vee b\vee c)\wedge(a\vee b\vee\neg c)\wedge(a\vee\neg b\vee c)\wedge(a\vee\neg b\vee\neg c)\wedge(\neg a\vee b\vee c)\wedge(\neg a\vee b\vee\neg c)\wedge(\neg a\vee\neg b\vee c)\wedge(\neg a\vee\neg b\vee\neg c)\wedge(a\vee b)\wedge(a\vee\neg b)\wedge(\neg a\vee b)\wedge(\neg a\vee\neg b)_{}[/mm]
>
> Dabei handelt es sich ja um eine DNF und diese hat 12
> unterschiedliche Terme. Aber laut [mm]2^{3}[/mm] dürfte sie ja nur
> acht haben. Und 12 ist ja noch immer nicht das Maximum, es
> gibt ja immer noch weitere....
die obige DF ist ja noch weiter kürzbar.. und dann kommst du auch auf höchstens 8..
du kannst ja auch noch unendlich viele [mm] \wedge [/mm] 1 [mm] \wedge [/mm] 1 [mm] \wedge [/mm] 1
drankleben bis zur unendlichkeit, nur sinn macht das genauso wenig, wie die ungekürzte oben!
gruß tee
|
|
|
| |
|
Hm, also das mit den unendlich vielen [mm] \vee1 [/mm] kommt ja nicht in Frage, da ja nach der Anzahl der "unterschiedliche Terme" gefragt ist.
Wenn man aber so argumentiert, dass man nur die maximale Anzahl der Terme zählt, nachdem man die DNF maximal vereinfacht hat, dann könnte es bei 3 Variablen doch auch keine 8 Terme geben. Denn
[mm] (a\vee b\vee c)\wedge(a\vee b\vee\neg c)\wedge(a\vee\neg b\vee c)\wedge(a\vee\neg b\vee\neg c)\wedge(\neg a\vee b\vee c)\wedge(\neg a\vee b\vee\neg c)\wedge(\neg a\vee\neg b\vee c)\wedge(\neg a\vee\neg b\vee\neg c)_{}
[/mm]
Kann man ja vereinfachen zu einer simplen 1.
|
|
|
| |
|
Hallo nochmal,
Was du da hast ist eine KNF , tut der Sache aber keinen Abbruch, läuft ja analog. Man müsste also erstmal klären, wie die Frage zu verstehen ist.
So wie du das darstellst, möchtest du alle möglichen Kombinationen aus den n Variablen bilden. Dabei möchtest du auch die (für die DNF) nicht sinnvollen Kombinationen wie [mm] a\overline{a} [/mm] berücksichtigen? Das ist ja eine mögliche Kombination der beiden Literale. Weiterhin: sind [mm] a\overline{b} [/mm] und [mm] \overline{b}a [/mm] zwei unterschiedliche Kombinationen, d.h. berücksichtigst du das Kommutativgesetz? Fragen über Fragen....
Ich würde vom logischen und praktischen Gesichtspunkt feststellen, die DNF kann maximal [mm] 2^n [/mm] unterschiedliche Terme enthalten, diese ergeben sich aus der Wahrheitstabelle, fertig.
Wenn du wissen willst wie gross die Menge der möglichen Terme ist, ist das natürlich eine andere Frage
Gruss Christian
|
|
|
| |
|
Okay, dann akzeptiere ich das mal so. Danke. :)
|
|
|
|
