Fomelgröße der teuersten Schaltfunktion, Beweise

01.09.2016, 20:03

Dr.Java

Fomelgröße der teuersten Schaltfunktion, Beweise

Hallo.
'Sei f eine beliebige n-stellige Schaltfunktion.Dann gilt
f(X_1,...,X_n)=1 <=> (X_n=0 und f(X_1,...,X_n-1,0)=1) oder
(X_n=1 und f(X_1,...,X_n-1,1)=1)
<=> ¬X_n f(X_1,...,X_n-1,0) V X_n f(X_1,...,X_n-1,1)=1.
Also gilt f(X_1,...X_n)=¬X_n f(X_1,...,X_n-1,0) V X_n f(X_1,...,X_n-1,1)=1.

Für i Element {0,1} sei e_i ein Boolescher Ausdruck mit e_i= f(X_1,...,X_n-1,i) und minimalen Kosten. Es gilt dann L(e_i)=L(f_i)<= K(n-1) Daraus folgt f(X_1,...X_n)=¬X_n e_0 V X_n e_1

Und somit K(n)<=2K(n-1)+4.
Diese Abschätzung gilt für jede n-stellige Schaltfunktion. '

(K(n)= max{L(f)|f:{0,1}^n -> {0,1}},ist also die Formelgröße der teuersten n-stelligen Schaltfunktion)

Meine Frage wäre hierbei, wie kann man daraus K(n)<=2K(n-1)+4 folgern ?

Und zum anderen. Durch K(1)=1 und K(n)<=2K(n-1)+4 soll man anhand von Induktion zeigen das gilt,
K(n)<= (5/2)*(2^n)-4.
Mein wertes Buch zeigt zwar einen Beweis,aber leider wieder sehr sparsam.

Es gilt für n=1, verstehe ich. Für den Schluss rechnet man von n-1 auf n wie folgt(laut Buch) .
K(n) <= 2K(n-1)+4
<= 5*2^(n-1)-8+4
=(5/2)*(2^n)-4 .
Die Schritte verstehe ich leider überhaupt nicht,außer vielleicht der ersten Zeile. Wie kommt man auf diese Umformungen?

Wäre sehr dankbar für Hilfestellungen .

lg

02.09.2016, 06:09

Auf diesen Beitrag antworten »

eulerscheZahl

Dein Buch nutzt Induktion.
Dazu muss man das Ergebnis aber auch erst einmal kennen, um es beweisen zu können.

Den Rest schaue ich mir heute Nachmittag an.

02.09.2016, 16:25

Auf diesen Beitrag antworten »

Dr.Java

Zitat:

Original von eulerscheZahl
Dein Buch nutzt Induktion.
Dazu muss man das Ergebnis aber auch erst einmal kennen, um es beweisen zu können.

Richtig. Sie wollen das mit v.I. lösen ,aber sie geben wie gesagt nur Bruchstücke eines Beweis an. Es soll bewiesen werden das K(n)<= (5/2)*(2^n)-4 gilt.

Zitat:

Original von eulerscheZahl
Den Rest schaue ich mir heute Nachmittag an.

Ich danke dir.

02.09.2016, 17:51

Auf diesen Beitrag antworten »

eulerscheZahl

Zitat:

Meine Frage wäre hierbei, wie kann man daraus K(n)<=2K(n-1)+4 folgern ?

Wir haben die Gleichung: $[latex]f(X_1,\dots,X_n)=\neg X_n e_0 \lor X_n e_1[/latex]$
Die Kosten verteilen sich wie folgt:
$[latex]\underbrace{f(X_1,\dots,X_n)}_{K(n)}=\underbrace{\neg}_{1} X_n \underbrace{\land}_{1} \underbrace{e_0}_{K(n-1)} \underbrace{\lor}_{1} X_n \underbrace{\land}_{1} \underbrace{e_1}_{K(n-1)}[/latex]$

Zur Induktion: wir kennen/vermuten bereits das Ergebnis und beweisen dessen Richtigkeit.
K(n) <= 2K(n-1)+4
Induktionsschritt: setze das bekannte Ergebnis $[latex]K(n-1) = \frac 5 2 \cdot 2^{n-1}-4[/latex]$ ein.
$[latex]2K(n-1)+4 = 2 \cdot \left(\frac 5 2 \cdot 2^{n-1}-4\right) + 4 = \frac 5 2 \cdot 2 \cdot 2^{n-1} - 2\cdot4 + 4 = \frac 5 2 \cdot 2^n - 4[/latex]$
Oh, das ist ja gleich K(n). Damit ist per Induktion dsa Ergebnis bewiesen.

02.09.2016, 21:00

Auf diesen Beitrag antworten »

Dr.Java

Zitat:

Original von eulerscheZahl
Wir haben die Gleichung: $[latex]f(X_1,\dots,X_n)=\neg X_n e_0 \lor X_n e_1[/latex]$
Die Kosten verteilen sich wie folgt:
$[latex]\underbrace{f(X_1,\dots,X_n)}_{K(n)}=\underbrace{\neg}_{1} X_n \underbrace{\land}_{1} \underbrace{e_0}_{K(n-1)} \underbrace{\lor}_{1} X_n \underbrace{\land}_{1} \underbrace{e_1}_{K(n-1)}[/latex]$

Das mit den 2K(n-1) habe ich mir schon gedacht und der Rest der Rechnung, das ich nicht selbst drauf gekommen bin, Kosten sind natürlich Zahl die Zeichen,jetzt ergibt das auch Sinn.

Zitat:

Original von eulerscheZahl
Zur Induktion: wir kennen/vermuten bereits das Ergebnis und beweisen dessen Richtigkeit.
K(n) <= 2K(n-1)+4
Induktionsschritt: setze das bekannte Ergebnis $[latex]K(n-1) = \frac 5 2 \cdot 2^{n-1}-4[/latex]$ ein.
$[latex]2K(n-1)+4 = 2 \cdot \left(\frac 5 2 \cdot 2^{n-1}-4\right) + 4 = \frac 5 2 \cdot 2 \cdot 2^{n-1} - 2\cdot4 + 4 = \frac 5 2 \cdot 2^n - 4[/latex]$
Oh, das ist ja gleich K(n). Damit ist per Induktion dsa Ergebnis bewiesen.

Ach so ist das mit n-1 auf n gemeint, das war mir irgendwie nicht klar,obwohl das ja eigentlich offensichtlich ist. Der Rest der Rechnung ist mir jetzt auch klar, auch wenn ich jetzt glaube das Buch hat einen Druckfehler. Es schreibt ja
$[latex]K(n) \leq 2K(n-1)+4 <br /> \leq 5 \cdot 2^{n-1} - 8+4<br /> = \frac 5 2 \cdot 2^n - 4[/latex]$
Das heißt in der zweiten Zeile fehlen also der Nenner und die zweite 2,oder bringe ich da was durcheinander?

Vielen lieben Dank nochmals und lg

02.09.2016, 21:04

Auf diesen Beitrag antworten »

eulerscheZahl

Zitat:

Das heißt in der zweiten Zeile fehlen also der Nenner und die zweite 2,oder bringe ich da was durcheinander?

Dafür hast du im Exponenten bei der 2 ein (n-1).
$[latex]2^{n-1} = \frac 1 2 \cdot 2^n[/latex]$

03.09.2016, 18:35

Auf diesen Beitrag antworten »

Dr.Java

Zitat:

Original von eulerscheZahl

Zitat:

Das heißt in der zweiten Zeile fehlen also der Nenner und die zweite 2,oder bringe ich da was durcheinander?

Dafür hast du im Exponenten bei der 2 ein (n-1).
$[latex]2^{n-1} = \frac 1 2 \cdot 2^n[/latex]$

Ah oh man darauf muss man auch erst kommen,dann ist jetzt alles klar. Danke nochmal vielmals.

lg

Neue Frage »

Antworten »

Fomelgröße der teuersten Schaltfunktion, Beweise

Verwandte Themen