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.

Answer 1

Antwort mit KI erzeugt:

Analyse der Booleschen Funktionen hinsichtlich Monotonie

Die Untersuchung von Booleschen Funktionen auf ihre Monotonie beinhaltet, dass für jegliche Eingangstupel \( (b_1, ..., b_n) \) und \( (c_1, ..., c_n) \), wenn \( (b_1, ..., b_n) \leq (c_1, ..., c_n) \), dann sollte gelten, dass \( f(b_1, ..., b_n) \leq f(c_1, ..., c_n) \).

Wir werden nun die Disjunktion (\(\vee\)), Implikation (\(\rightarrow\)) und Äquivalenz (\(\leftrightarrow\)) für zweistellige Boolesche Funktionen untersuchen.

Disjunktion (\(\vee\))

Die Disjunktion ist definiert als \( a \vee b \), wobei das Ergebnis wahr ist (\(1\)), wenn mindestens einer der beiden Eingänge wahr ist. Die Disjunktion ist bekannt für ihre Monotonie, weil das Hinzufügen von "wahr" (\(1\)) zu einem der Eingänge das Ergebnis nicht falsch (\(0\)) machen kann.

Beispielergebnisse:
- \(0 \vee 0 = 0\)
- \(0 \vee 1 = 1\)
- \(1 \vee 0 = 1\)
- \(1 \vee 1 = 1\)

Alle Vergleiche in deinem Ansatz für Disjunktion zeigen, dass wenn eine Eingangskombination kleiner oder gleich einer anderen ist, das Ergebnis ebenfalls dieser Bedingung folgt.

Implikation (\(\rightarrow\))

Die Implikation \( a \rightarrow b \) ergibt wahr (\(1\)), es sei denn, \(a\) ist wahr (\(1\)) und \(b\) ist falsch (\(0\)). Dies bedeutet, die Funktion könnte nicht monoton sein, da das Ändern eines Eingangswertes von \(0\) zu \(1\) das Ergebnis von wahr (\(1\)) zu falsch (\(0\)) ändern könnte.

Ein spezifisches Beispiel ist der Übergang von \( (0,1) \rightarrow (1,0) \), was von \(1\) zu \(0\) wechselt, was zeigt, dass die Implikation nicht monoton ist.

Äquivalenz (\(\leftrightarrow\))

Die Äquivalenz ist wahr (\(1\)), wenn beide Eingänge gleich sind, und falsch (\(0\)), wenn sie unterschiedlich sind. Dies bedeutet, dass jede Änderung des Wertes eines der Eingänge, wenn sie nicht gleich geändert werden, das Ergebnis von wahr zu falsch ändern könnte, was die Äquivalenz nicht-monoton macht.

Eine spezifische Verletzung der Monotonie wäre der Übergang von \( (0,0) \) zu \( (0,1) \), wo das Ergebnis von wahr (\(1\)) zu falsch (\(0\)) wechselt.

Schlussfolgerung

Nachdem wir alle Fälle analysiert haben, können wir schlussfolgern:
- Die Disjunktion ist monoton, da keine Eingangsänderungen das Ergebnis von wahr zu falsch ändern.
- Die Implikation und Äquivalenz sind nicht monoton, da gewisse Änderungen der Eingangswerte das Ergebnis von wahr zu falsch verschieben können.

Deine Strategie, alle Tupel zu überprüfen und ihre Ergebnisse zu vergleichen, ist korrekt und hilft, zu dem Schluss zu kommen, dass nur die Disjunktion monoton ist, während Implikation und Äquivalenz es nicht sind.