+1 Daumen
2,2k Aufrufe

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 (b1, .., bn) ∈ |Bn haben, für das wir die Ordnungsrelation einführen

(b1, .., bn) ≤ (c1, .., cn) genau dann, wenn bi ≤ ci 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 (b1, .., bn) ≤ (c1, .., cn) folgt, dass ƒ(b1, .., bn) ≤ ƒ(c1, .., cn).

 

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

 für Disjunktionfür Implikationfür Äquivalenz
(0,0) ≤ (0,0)  0 ≤ 0, wahr1 ≤ 1, wahr1 ≤ 1, wahr
(0,0) ≤ (0,1)  0 ≤ 1, wahr1 ≤ 1, wahr1 ≤ 0, falsch
(0,0) ≤ (1,0)  0 ≤ 1, wahr1 ≤ 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?

Avatar von
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 t1 und t2 gegeben die beide monotone boolesche Funktionen sind. Wie kann ich hier zeigen, dass dann auch s=t1 ∨ t und t=t1∧  t2  monotone boolesche Funktionen darstellen? Mir fehlt leider jeder Ansatz dafür einen sinnvollen Beweis zu finden. Wäre für jede Hilfe dankbar.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community