Monotone Boolesche Funktionen (Tupel und Ordnungsrelation)

Question

1) Auf der Menge n-Tupel (b₁,....,b_n) ∈ Bⁿ führen wie eine Ordnungsrelation ≤ ein:

    (b₁,.......,b_n) ≤ (c₁,.....,c_n) genau dann wenn b_i ≤ c_i für alle i = 1,.....,n

2) Man nennt eine Boolsche Funktion f: Bⁿ →B monoton wenn für zwei beliebige Tupel aus der Bedingung
(b₁,.......,b_n) ≤ (c₁,.....,c_n)  folgt, dass f(b₁,.......,b_n) ≤ f(c₁,.....,c_n).

 

a) Welche der folgenden Boolschen Funktionen f,g,h: Bⁿ→B sind monoton und welche nicht? Geben sie eine kurze Begründung!

f(b₁, b₂, ..... , b_n) = 1 ⇔ b₁ ≤ b₂ ≤ ... ≤ b_n

Answer 1

Diese Funktion ist nicht monoton.

Ein Gegenbeispiel: Für z.B. n = 3:

(b₁, b₂, b₃) = (0,0,0) ≤ (1, 1, 0) = (c₁, c₂, c₃)

f(b₁, b₂, b₃) = 1, denn 0≤0≤0

f(c₁, c₂, c₃) = 0, denn 1≤1>0

Also gilt zwar (b₁, b₂, b₃) ≤(c₁, c₂, c₃) aber f(b₁, b₂, b₃) > f(c₁, c₂, c₃).