Boolesche Algebra Monotonie

Question

Hallo zusammen,

kann mir bitte jmd. bei dieser Aufgabe helfen? Würde mich sehr über einen Lösungsweg freuen :)



Eine Boolesche Funktion f(x₁,...,xn) heißt numerisch monoton, falls für (x₁,...,xn) < (y1,...,yn)2* gilt, dass

f(x₁, ..., xn) ≤ f(y1, ..., yn).

Die Schreibweise (x1, ..., xn)2* bedeutet hierbei die binären Bits x₁,...,xn interpretiert als einstellige binäre Zahl. Es wird also zum Beispiel x₁ = 1, x₂ = 0, x₃ = 1 als die Zahl 5 interpretiert.


Wie viele numerisch monotone Boolesche Funktionen f : Bn → B gibt es?
*2 ist tiefgestellt

Answer 1

Wieviele Stellen gibt es, an denen der Übergang von f(x) = 0 zu f(y) = 1 erfolgen kann?

Comments

Das weiß ich nicht

---

Die Schreibweise (x1, ..., xn)2* bedeutet hierbei die binären Bits x₁,...,xn interpretiert als einstellige binäre Zahl.

Gemeint ist wohl "n-stellige" binäre Zahl.

Das ergibt 2ⁿ verschiedene Eingaben.

Jede dieser Eingaben kann die Stelle sein, an der f erstmals den Wert 1 annimmt.

Außerdem kann es sein, dass f niemals den Wert 1 annimmt.