wie viele n-stellige Boolsche Funktionen F:

Question

Untersuchen Sie für die folgenden drei Eigenschaften, wie viele n-stellige Boolesche Funktionen f sie jeweils erfüllen und begründen Sie die Antworten.

a) Die Werte von f hängen nicht vom konkreten Tupel (b1, . . . , bn) sondern nur von der Anzahl der Einsen im Tupel ab (z.B. f wird 1 für alle Tupel mit einer oder mit zwei Einsen und 0 sonst).

b) f wird 1 für alle Tupel der Form (b1,...,bn) mit b1 = 0 und kann sich auf Tupeln mit b1 = 1 beliebig verhalten.

c) Für beliebige Tupel (b1,...,bn) hat f die Eigenschaft f(b1,...,bn) = f(¬b1,...,¬bn). d) f hat die Eigenschaften aus b) und c). Hinweis: Folgende Fakten können Sie für zwei beliebige Mengen A mit k und B mit m Elementen verwenden:

1) Die Anzahl der Funktionen f : A → B ist mk.
2) Die Anzahl der Untermengen von A ist 2k und die Anzahl der n-Tupel mit Einträgen aus A ist kn.

Answer 1

Insgesamt gibt es ja 2^(2^n) n-stellige boolsche Funktionen. Wie kommt man darauf? Es gibt einfach 2^n Tupel der Länge n und für jedes Tupel hat man 2 mögliche Funktionswerte.

A) Der Funktionswert hängt nur von der Anzahl der 1en ab, bei Tupeln der Länge n können das 0,1,...,n Einsen sein. Für jeden dieser Fälle können wir 0 oder 1 als Funktionswert wählen, also erhalten wir 2^n solcher Funktionen

B) Falls b1 = 1 muss f = 1 sein sonst egal. Naja jetzt gibt es 2^n Tupel der Länge n, dabei sind 2^(n-1) von der Form (0,...) und die anderen 2^(n-1) von der Form (1,...). Für die erste Gruppe können wir jedem Tupel beleibig 0 oder 1 zuordnen, bei der zweiten Gruppe haben wir keine Wahlmöglichkeit also nur 2^(2^(n-1))

C) Hier stimmt f(x) immer mit f(not x) überein. Jetzt können wir die n-Tupel in 2^(n-1) 2er Paare gruppieren, nämlich immer ein Tupel und das negierte Tupel. Jedem dieser Paare können wir wieder beleibig 0 oder 1 zuordnen: 2^(2^(n-1)) Funktionen

D) Hier ist nur eine Funktion möglich (nämlich die die alles auf 1 schickt) Betrachte nämlich ein beliebiges Tupel b, falls b1 = 1 muss f(b)=1 nach B sein, falls b1 = 0 betrachte aber das Tupel not b, nach C) gilt f(b)=f(not b) aber not b fängt ja jetzt mit einer 1 an muss nach B auf 1 abgebildet werden.