Fomelgröße der teuersten Schaltfunktion, Beweise |
01.09.2016, 20:03 | Auf diesen Beitrag antworten » | ||||
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 |
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.
Ich danke dir. |
||||
02.09.2016, 17:51 | Auf diesen Beitrag antworten » | ||||
eulerscheZahl |
Wir haben die Gleichung: Die Kosten verteilen sich wie folgt: 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. |
||||
Anzeige | |||||
|
|||||
02.09.2016, 21:00 | Auf diesen Beitrag antworten » | ||||
Dr.Java |
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.
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 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 |
Dafür hast du im Exponenten bei der 2 ein (n-1). |
||||
03.09.2016, 18:35 | Auf diesen Beitrag antworten » | ||||
Dr.Java |
Ah oh man darauf muss man auch erst kommen,dann ist jetzt alles klar. Danke nochmal vielmals. lg |
|