dijunktive konjunk. Normalform < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:35 Fr 06.01.2006 | | Autor: | JoergL |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
hallo,
kann mir jemand einen allgemeinen term für die
disjunktive und konjunktive Normalform von binären booleschen funktionen geben? sollte auch als Mathe LKler zu verstehen sein,
Vielen Dank
Joerg
|
|
| |
|
Hallo Joerg,
hatte ich nicht eine der beiden schon geschrieben ?
Also, zu [mm] f\colon\{0,1\}^n\to\{0,1\} [/mm] sind
[mm] f(x_1,\ldots [/mm] , [mm] x_n) =\bigvee_{a\in\{0,1\}^n, f(a)=1} (x_1^{a_1}\wedge\ldots \wedge x_n^{a_n})
[/mm]
= [mm] \bigwedge_{a\in\{0,1\}^n, f(a)=0} (x_1^{1-a_1}\vee\ldots\vee x_n^{1-a_n})
[/mm]
mit [mm] x_i^{a_i} [/mm] = [mm] x_i [/mm] falls [mm] a_i [/mm] =1 und = [mm] \neg x_i [/mm] falls [mm] a_i=0.
[/mm]
Erstere heisst disjunktive und zweitere konjunktive Normalform.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:20 Fr 06.01.2006 | | Autor: | JoergL |
Vielen Dank erstmal
meine nachfrage:
gilt die letzte zeile deiner antwort:
mit x,i,ai = x, i falls ai=0 usw.
auch für die konjunktive normalform? dort steht ja immer ein x,i,1-ai
dieses 1-ai irritiert mich?
brauche die formel für meine facharbeit, waer super wenn du das noch mal
bestätigen kannst.
Gruss,
Joerg
|
|
|
| |
|
Hallo Joerg,
ich denke, die Formel fuer die konjunktive Normalform sollte so stimmen:
f(x) [mm] =\bigwedge_{a\in\{0,1\}^n, f(a)=0} (x_1^{1-a_1}\vee\ldots \vee x_n^{1-a_n})
[/mm]
denn es hat ja allgemein [mm] x^a [/mm] den Wert 1 genau dann, wenn x=a gilt, und
man muss, damit der Funktioswert 1 wird, sicherstellen, dass sich x von jeder Nullstelle
von f an mindestens einer Stelle [mm] x_i [/mm] unterscheidet.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:49 Fr 06.01.2006 | | Autor: | JoergL |
Danke
noch eine Frage (-:,
kann ich als Bedingung für die konjuinktive Normalform auch schreiben
mit [mm] x_i^{1- a_i} [/mm] = [mm] x_i [/mm] falls [mm] a_i [/mm] =1 und = [mm] \neg x_i [/mm] falls [mm] a_i=0.
[/mm]
oder stimmen die Bedingungne für beide Normalformen überein?
in der KNF steht schließlich ein [mm] x_i^{1 -a_i} [/mm]
|
|
|
| |
|
Hallo Joerg,
fuer die KNF musst Du schon [mm] x_i^{1-a_i} [/mm] nehmen, was gleich 1 ist, wenn [mm] x_i\neq a_i [/mm]
und 0 , wenn [mm] x_i=a_i. [/mm] Allerdings wird bei der KNF ueber andere [mm] a\in\{0,1\}^n [/mm]
konjugiert, als bei der DNF disjungiert wird: Bei KNF alle a mit f(a)=0
(''ein x mit f(x)=1 muss sich von JEDEM solchen an MINDESTENS einer Stelle
unterscheiden), bei der DNF alle a mit f(a) =1 (x muss mit MINDESTENS einem an
ALLEN Stellen uebereinstimmen).
Alles klar ?
Gruss,
Mathias
> Danke
>
> noch eine Frage (-:,
>
> kann ich als Bedingung für die konjuinktive Normalform auch
> schreiben
>
> mit [mm]x_i^{1- a_i}[/mm] = [mm]x_i[/mm] falls [mm]a_i[/mm] =1 und = [mm]\neg x_i[/mm]
> falls [mm]a_i=0.[/mm]
>
> oder stimmen die Bedingungne für beide Normalformen
> überein?
>
> in der KNF steht schließlich ein [mm]x_i^{1 -a_i}[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 So 15.01.2006 | | Autor: | JoergL |
hui, vielen Dank für die ganzen antworten, war ne schwere Geburt....
Gruss Joerg
|
|
|
|
