Monotone Boolesche Funktionen

Question

Ich soll in einer Hausaufgabe zweistellige Boolesche Funktionen für Disjunktion, Implikation und Äquivalenz untersuchen und feststellen ob diese monoton sind. 

Als Hilfestellung ist gegeben, das wir ein n-Tupel (b₁, .., b_n) ∈ |Bⁿ haben, für das wir die Ordnungsrelation einführen

(b₁, .., b_n) ≤ (c₁, .., c_n) genau dann, wenn b_i ≤ c_i für alle i = 1, .. n, wobei sich das ≤ von den Zahlen auf die Wahrheitswerte überträgt.

und

dass man eine boolesche Funktion dann monoton nennt, wenn für zwei beliebige Tupel aus der Bedingung (b₁, .., b_n) ≤ (c₁, .., c_n) folgt, dass ƒ(b₁, .., b_n) ≤ ƒ(c₁, .., c_n).

 

Mein Ansatz ist, dass ich alle Tupel suche, für die die Bedingung gilt und dann die Ergebnisse miteinander vergleiche. Also:

	für Disjunktion	für Implikation	für Äquivalenz
(0,0) ≤ (0,0)	0 ≤ 0, wahr	1 ≤ 1, wahr	1 ≤ 1, wahr
(0,0) ≤ (0,1)	0 ≤ 1, wahr	1 ≤ 1, wahr	1 ≤ 0, falsch
(0,0) ≤ (1,0)	0 ≤ 1, wahr	1 ≤ 0, falsch
(0,0) ≤ (1,1)	0 ≤ 1, wahr
(1,0) ≤ (1,0)	1 ≤ 1, wahr
(1,0) ≤ (1,1)	1 ≤ 1, wahr
(0,1) ≤ (0,1)	1 ≤ 1, wahr
(0,1) ≤ (1,1)	1 ≤ 1, wahr
(1,1) ≤ (1,1)	1 ≤ 1, wahr

Ist diese Lösung so korrekt, wenn ich zu dem Schluss komme, dass die Disjunktion in diesem Sinne monoton ist und die Implikation und die Äquivalenz nicht?

Comments

Disjunktion scheint tatsächlich zu funktionieren, wenn n=2.

Aber was machst du mit
(1,0,0), (1,0,1), (0,1,1) sind die immer alle gegenseitig ≤ und so schlussendlich '='?

Einzige Ausnahme (0,0,0) ist echt kleiner als alle andern?

---

Vorweg: Vielen Dank für deine schnelle Antwort.

Ich bin mir nicht ganz sicher, worauf du hinaus willst Für die Disjunktion sollte es auch mit Tripeln funktionieren, da wirklich nur (0,0,0) echt kleiner ist und alle anderen Tripel immer 1 ergeben sollten.

Gibt es für diese Aufgabe einen formalen Beweis? In der nächsten Aufgabe sind zwei Terme t₁ und t₂ gegeben die beide monotone boolesche Funktionen sind. Wie kann ich hier zeigen, dass dann auch s=t₁ ∨ t₂  und t=t₁∧  t₂  monotone boolesche Funktionen darstellen? Mir fehlt leider jeder Ansatz dafür einen sinnvollen Beweis zu finden. Wäre für jede Hilfe dankbar.