n-stellige Schaltfunktion Kosten

27.08.2016, 19:25

Dr.Java

n-stellige Schaltfunktion Kosten

Hi. Ich arbeite mich inzwischen schon länger in die Technische Informatik ein, leider ist das Buch das ich benutze etwas dürr was seine Beweise betrifft. Deswegen würde ich hier auch grad ein paar Fragen stellen.
Meine Frage wäre zunächst der Beweis dafür ,das für p als vollständig disjunkte Normalform einer n-stelligen Schaltfunktion f,gilt,
L(p)<=n*2^(n+1) , wobei L die Kosten sind(boolesche).
Das Buch sagt dazu im wesentlichen folgendes , jeder Minterm m der vollständigen,disjunkten Normalform von f besteht aus genau n Literalen und n-1 logischen Und Zeichen .
Ebenso das L(m)<=2n-1 ist und p aus #Tr(f) Mintermen besteht. Tr meint hierbei den Träger von f.
Für die Anzahl der Logischen Oder in p gilt dann, #Tr(f)-1 ,falls #Tr(f)>= 2 ist und 0,falls #Tr(f) <= 1.
Wegen #Tr(f)<=# {0,1}^n=2^n soll dann das besagte folgen, L(p)<=n*2^(n+1).
Meine Frage ist nun wie man das daraus konkret schlussfolgern kann/sollte,denn ich werde da nicht schlau draus.

Vielen lieben Dank im voraus und lg

28.08.2016, 07:16

Auf diesen Beitrag antworten »

eulerscheZahl

Wie könnte so ein p überhaupt aussehen?
Setzen wir n=3:
$[latex]p_3 = \underbrace{\overline{x_1}\, \overline{x_2}\,\overline{x_3}}_{m} \lor \overline{x_1}\, \overline{x_2}\,x_3 \lor \overline{x_1}\, x_2\,\overline{x_3} \lor \overline{x_1}\, x_2\,x_3 \lor x_1\, \overline{x_2}\,\overline{x_3} \lor x_1\, \overline{x_2}\,x_3 \lor x_1\, x_2\,\overline{x_3} \lor x_1\, x_2\,x_3[/latex]$

Ein Minterm m hat n-1 UND Verknüpfungen. Dazu kommen bis zu n Negationen.
Also: n-1 <= L(m) <= 2n-1

p hat bis zu 2^n verschiedene Minterme: jede Variable kann sowohl negiert als auch nicht negiert vorkommen. Bei n Variablen und 2 Möglichkeiten je Variable gibt das 2^n.

Hinzu kommen noch die 2^n-1 ODER Verknüpfungen zwischen den einzelnen Mintermen

für 2^n Minterme macht das also: $[latex]L(p) \leq (2n-1) \cdot 2^n + 2^n-1 = 2n\cdot2^n - 2^n = n\cdot 2^{n+1} - 2^n + 2^n-1 = n\cdot 2^{n+1} - 1[/latex]$ .
Man kann jetzt argumentieren, dass nicht in jedem Minterm jede Variable negiert ist (wie in der Rechnung), aber dadurch wird das Ergebnis nur um etwa 3/4 kleiner, bleibt also exponentiell groß.

28.08.2016, 12:01

Auf diesen Beitrag antworten »

Dr.Java

Ah, danke dir,für die ausführliche Lösung.
Ich habe nur noch ein paar Fragen dazu.

Zitat:

Original von eulerscheZahl
für 2^n Minterme macht das also: $[latex]L(p) \leq (2n-1) \cdot 2^n = 2n\cdot2^n - 2^n = n\cdot 2^{n+1} - 2^n < n\cdot 2^{n+1}[/latex]$ .

Kann man das dann einfach so zusammenrechnen, und wie kommt man darauf das man das am Ende so umformen kann, ich meine ich keine die Regeln wegen dem <=,aber wieso grade so?

Und zum anderen, gibt es diese Regel eigentlich in verschiedenen Formen? Ich habe nämlich in einem anderen Buch das ganze in ähnlichen Zusammenhang gefunden und sie meinten es gelte für jede Boolesche Funktion $[latex]L(f)\leq n\cdot 2^{n+1}-1[/latex]$ ,wobei L(f) die minimalen Kosten sind.
Während das ursprüngliche Buch meint
Für jede n-stellige Schaltfunktion f gilt $[latex]L(f)\leq n\cdot 2^{n+1}[/latex]$ ,wobei L(f) die minimalen Kosten sein sollen.

Wäre dann beides richtig,in verschiedenen Zusammenhängen?

Danke und lg

28.08.2016, 14:28

Auf diesen Beitrag antworten »

eulerscheZahl

Ich hatte leider das ODER zwischen den einzelnen Mintermen vergessen. Habe es oben editiert.
Ich kriege auch die -1 von deinem zweiten Buch. Das macht eine großzügigere Abschätzung aber nicht falsch.
Und wie schon angedeutet, kann man die Grenze noch weiter nach unten setzen: Im Erwartungswert ist nur jede zweite Variable negiert. Und da jede mögliche Kombination verwendet wird, kann man hier auch mit dem Erwartungswert statt dem worst case rechnen.
$[latex]L(p) \leq (\underbrace{n-1}_{\text{UND in m}} + \underbrace{\frac{1}{2}n}_{\text{Negation}}) \cdot \underbrace{2^n}_{\text{Anzahl Minterme}} + \underbrace{2^n-1}_{\text{ODER}}[/latex]$

28.08.2016, 20:37

Auf diesen Beitrag antworten »

Dr.Java

Ah danke dir ,so in etwa beweist es auch das Buch. Nur mit n in der Klammer, nicht mit 1/2 *n. Bedeutet das also im Endeffekt das es irrelevant ist ob du die Zahl der Oder .o.ä. weg lässt? Und was hat es in diesem Sinne mit dem Erwartungswert auf sich ,beziehst sich das nur auf den Vorfaktor von der Negation,beziehungsweise also auf die Warscheinlichkeit das es negiert ist?

lg

28.08.2016, 20:54

Auf diesen Beitrag antworten »

eulerscheZahl

Das ODER hatte ich nur vergessen, das gehört da schon hin.

Der Faktor 1/2 ist die Wahrscheinlichkeit, dass eine Variable negiert ist. Für alle Variablen sind es im Erwartungswert n/2 Negationen je Minterm (kannst du für das Beispiel mit 3 Variablen gerne nachzählen).
Insgesamt sind es n/2 * 2^n. Das ist ein exakter Wert für ein p mit maximaler Anzahl an Mintermen, keine Abschätzung.

Aber wenn du es ohne die 1/2 verstanden hast, will ich dich nicht unnötig verwirren. Das sollte nur eine Fußnote sein, dass man dads besser abschätzen kann.

29.08.2016, 12:55

Auf diesen Beitrag antworten »

Dr.Java

Kann man denn trotz dem Oder auf $[latex] n\cdot 2^{n+1}[/latex]$ kommen,durch umformen nehme ich an? Wegen dem Erwartungswert,okay, ich habe das jetzt noch nicht ganz raus,werd mir das vielleicht später nochmal in Ruhe anschauen.

Danke dir und lg

Neue Frage »

Antworten »

n-stellige Schaltfunktion Kosten

Verwandte Themen