monotone Boolesche Funktionen?
Hey,
Angenommen die Terme t1 und t2 repräsentieren zwei monotone Boolesche Funktionen. Zeigen Sie, dass dann auch die Terme s = t1 ∨ t2 und t = t1 ∧ t2 monotone Boolesche Funktionen repräsentieren
danke in voraus!
3 Antworten
Es bedeutet, dass die Umkehrung einer monotonen Funktion monoton ist.
s = t1 ∨ t2 Da OR eine monotone Operation ist, folgt, dass s eine monotone Funktion ist. t = t1 ∧ t2 Da AND eine monotone Operation ist, folgt, dass t eine monotone Funktion ist.
In der Mathematik bezeichnet der Begriff "monoton" eine Funktion, die entweder immer steigt oder immer fällt, wenn ihre Eingabewerte zunehmen. In Bezug auf Boolesche Funktionen bedeutet dies, dass eine monotone Boolesche Funktion immer entweder "wahr" oder "falsch" zurückgibt, wenn ihre Eingabewerte zunehmen.
T1 und T2 sind beide monotone Boolesche Funktionen. Wir wollen nun zeigen, dass die Funktionen S = T1 ∨ T2 und T = T1 ∧ T2 ebenfalls monoton sind.
Um dies zu zeigen, betrachten wir zunächst die Funktion S = T1 ∨ T2. Wenn T1 und T2 beide "wahr" sind, wird S ebenfalls "wahr" sein, da "wahr" ∨ "wahr" = "wahr" ist. Wenn T1 "wahr" und T2 "falsch" ist, wird S ebenfalls "wahr" sein, da "wahr" ∨ "falsch" = "wahr" ist. Und wenn T1 "falsch" und T2 "wahr" ist, wird S ebenfalls "wahr" sein, da "falsch" ∨ "wahr" = "wahr" ist. In allen diesen Fällen gibt S immer "wahr" zurück, wenn T1 und T2 zunehmen, also ist S eine monotone Boolesche Funktion.
Jetzt betrachten wir die Funktion T = T1 ∧ T2. Wenn T1 und T2 beide "wahr" sind, wird T ebenfalls "wahr" sein, da "wahr" ∧ "wahr" = "wahr" ist. Wenn T1 "wahr" und T2 "falsch" ist, wird T "falsch" sein, da "wahr" ∧ "falsch" = "falsch" ist. Und wenn T1 "falsch" und T2 "wahr" ist, wird T ebenfalls "falsch" sein, da "falsch" ∧ "wahr" = "falsch" ist. In allen diesen Fällen gibt T immer "falsch" zurück, wenn T1 und T2 zunehmen, also ist T eine monotone Boolesche Funktion.
Da wir gezeigt haben, dass S und T immer entweder "wahr" oder "falsch" zurückgeben, wenn ihre Eingabewerte zunehmen, sind S und T monotone Boolesche Funktionen.