Boolesche Funktionen < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 11:10 Di 15.11.2011 | Autor: | Hurba |
Aufgabe | Überlegen Sie, wie viele boolesche Funktionen es im Falle einer n-stelligen Binäreingabe (d.h. einer Schaltung mit n Eingängen und einem Ausgang) gibt und entwickeln Sie ein Verfahren, wie diese systematisch ermittelt werden können. |
Bin total neu in diesem Thema und wäre froh, wenn mir jemand weiterhelfen kann.
Danke!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 11:26 Di 15.11.2011 | Autor: | Stoecki |
hallo,
der beweis geht über eine vollständige induktion. überlege dir, wie viele möglichkeiten es jeweils bei n=1, n=2 und n=3 boolschen variablen gibt, leite eine regel davon ab und beweise diese. als kleinen ansatz: ist n=1 gibt es genau vier mögliche funktionen.
[mm] f_{1} [/mm] (true) = true;
[mm] f_{1} [/mm] (false) = true;
[mm] f_{2} [/mm] (true) = false;
[mm] f_{2} [/mm] (false) = false;
[mm] f_{3} [/mm] (true) = true;
[mm] f_{3} [/mm] (false) = false;
[mm] f_{4} [/mm] (true) = false;
[mm] f_{4} [/mm] (false) = true;
gruß
|
|
|
|
|
Hallo Hurba,
Es geht auch ohne Induktion. Stoecki weist Dir auch dazu den Weg...
Bei n Eingängen sind alle Möglichkeiten von Eingangskombinationen in einer Wertetabelle mit k Einträgen zu erfassen. Wie groß ist k in Abhängigkeit von n?
Nun kann jeder der k Eingangskombinationen als Ausgangswert entweder 0 oder 1 zugeordnet werden. Daher sind m vollständige Wertetabellen (Input+Output) möglich. Wie groß ist m in Abhängigkeit von k?
Das Gesamtergebnis kann man mit nur 3 Zeichen schreiben.
Grüße
reverend
|
|
|
|