 Fomelgröße der teuersten Schaltfunktion, Beweise |
Dr.Java 
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
 |
|
| 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
__________________
| Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Dr.Java: 01.09.2016 20:09.
|
|
01.09.2016 20:03 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
| 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.
__________________
| Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
|
02.09.2016 16:25 |
|
|
|
|
| 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]](http://www.matheboard.de/latex2png/latex2png.php?f(X_1,\dots,X_n)=\neg X_n e_0 \lor X_n e_1)
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]](http://www.matheboard.de/latex2png/latex2png.php?\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)})
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]](http://www.matheboard.de/latex2png/latex2png.php?K(n-1) = \frac 5 2 \cdot 2^{n-1}-4) 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]](http://www.matheboard.de/latex2png/latex2png.php?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)
Oh, das ist ja gleich K(n). Damit ist per Induktion dsa Ergebnis bewiesen.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
02.09.2016 17:51 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
| Zitat: |
Original von eulerscheZahl
Wir haben die Gleichung:
Die Kosten verteilen sich wie folgt:
|
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 ein.
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]](http://www.matheboard.de/latex2png/latex2png.php?K(n) \leq 2K(n-1)+4 <br />
\leq 5 \cdot 2^{n-1} - 8+4<br />
= \frac 5 2 \cdot 2^n - 4)
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
__________________
| Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
|
02.09.2016 21:00 |
|
|
|
|
| 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]](http://www.matheboard.de/latex2png/latex2png.php?2^{n-1} = \frac 1 2 \cdot 2^n)
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
02.09.2016 21:04 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
| 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).
|
Ah oh man darauf muss man auch erst kommen,dann ist jetzt alles klar. Danke nochmal vielmals.
lg
__________________
| Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
|
03.09.2016 18:35 |
|
|
|
