| PeterPanter |
Beweis Abhängigkeit Boolesche Funktionen
Hi!
Soll folgende Aufgabe Lösen:
f sei eine n-Stellige Funktion. Die Anzahl der n-Tupel an denen f den Wert 1 annimmt sei ungerade. Beweisen sie, dass f dann wesentlich von all ihren Variablen abhängt.
Ich hätte jetzt so Argumentiert, dass die Anzahl der wahren n-Tupel gerade sein muss, weil der "Rauswurf" einer Variablen aus der Funktion nur dann möglich ist, wenn die fragliche Variable keinen Einfluss auf den Wahrheitswert der Funktion hat. Da es nur zwei Zustände gibt muss also zwei mal "wahr" herauskommen, einmal mit (nennen wir die fragliche Variable x) x=1 und ein mal mit x=0. x ist dann überflüssig, weil sein Wert offenbar keinen Einfluss auf das Endergebnis hat.
Ist die Anzahl der wahren Tupel jedoch ungerade, funktioniert das ganze nicht, denn es kommt nicht in beiden Fällen (x=1 und x=0) das gleiche Ergebnis heraus, der Wert von x ist also am Endergebnis beteiligt.
Ist die Überlegung richtig? Wie schreibt man sowas adäquat/ allgemein auf? |
