Wie viele surjektive boolesche Funktionen f : {0,1}^n → {0,1}^2 gibt es? und andere

Question

Hey, ich komm bei diesen Aufgaben einfach nicht weiter, wär cool wenn mir jemand helfen könnte.

1. Wie viele surjektive boolesche Funktionen f : {0,1}^n → {0,1} gibt es?

2. Wie viele surjektive boolesche Funktionen f : {0,1}^n → {0,1}^2 gibt es?

3. Wie viele boolesche Funktionen f : {0,1}^n → {0,1} mit genau k Nullstellen gibt es?

Comments

1. Wie viele surjektive boolesche Funktionen f : {0,1}ⁿ → {0,1} gibt es?

Prinzipiell gibt es 2^n boolesche Funktionen f : {0,1}ⁿ → {0,1}. Surjektiv sind alle, die beide Werte im Wertebereich 1 und 2 tatsächlich annehmen.

Also alle 2^n ausser zwei nämlich 00000… resp. 11111111…

Deshalb ist meine Antwort bei 1. 2^n - 2

2. Wertebereich hat 4 Elemente 00, 01, 10 und 11

Deshalb prinzipiell 4^n boolsche Funktionen möglich. Jetzt musst du noch systematisch diejenigen abziehen, die zB nur die Werte 01,10 und 11 annehmen, etc, wenn du keinen direkteren Ansatz findest.

3. Ist der Binomialkoeffizient (n tief k)

---

Schau mal in dein DS-Skript, Seite 2 ganz unten, da steht zumindest die 1 schonmal genau so drin ;)

---

danke für die Antwort, hab aber noch ein paar Fragen:

zu 1. Gibt es prinzipiell nicht 2^{2^n} boolesche Funktionen?

zu 3. Wie kommst du darauf?

---

Stell mal bitte Fragen zum neuen DS-Blatt.. brauch Antworten.

Answer 1

3. Wie viele boolesche Funktionen f : {0,1}ⁿ → {0,1} mit genau k Nullstellen gibt es?

Das ist der Binomialkoeffizient (n tief k)

Die Funktion hat n Stellen, an denen ein Funktionswert definiert ist. Die k Stellen, an denen eine 0 steht, kann man auf (n tief k) Arten ausrechnen. Für die übrigen an denen 1 steht, geht das nur noch 1 Mal.

1. und 2. vgl. mein Kommentar zur Frage.