Zeigen Sie, dass {→, 0} ein vollständiges Operatorensystem ist

Question

Hallo, wie schon im Titel erwähnt, muss ich beweisen, dass {→, 0} ein vollständiges Operatorensystem ist.

Was ich schon weiß ist folgendes:

Ein System von Operatoren ist genau dann ein vollständiges Operatorensystem, wenn mit den enthaltenen Operatoren alle booleschen Funktionen dargestellt werden können (Negation, Konjunktion, Disjunktion). (https://www.stacklounge.de/42/vollstandiges-operatorensystem)

Hier (http://www.informatik.uni-leipzig.de/~der/Vorlesungen/DIV/logik.pdf auf Seite 11, bzw. Seite 6 der PDF) sind die gängisten Operatorensysteme schon bewiesen.

Leider bringt mich das alles nicht weiter, ich komme einfach nicht darauf wie ich zB. die Negation durch eine Implikation darstellen könnte. Zudem bereitet mir die 0 Probleme, da ich nicht weiß wie ich diese einsetzen soll.

Würde mich über Tipps freuen.

,

MfG

Comments

Wie wäre es denn !A als A -> 0 darzustellen?

---

Danke das hat es schon mal um einiges klarer gemacht.

Konjunktion wäre dann (a → (b → 0)) →0 oder? Zumindest ist die Wahrheitstabelle identisch mit der von a ∧ b

Answer 1

Durch etwas Herumprobieren oder kennen der üblichen semantischen Äquivalenzen ist die Aufgabe machbar, wie ich finde.

Negation: \(\neg A \: \equiv \: A \rightarrow 0\)

Konjunktion (wie schon bemerkt): \((A \wedge B) \: \equiv \: \neg(A \rightarrow \neg B) \: \equiv \: ((A \rightarrow (B \rightarrow 0)) \rightarrow 0) \)

Disjunktion: \((A \vee B) \: \equiv \: (\neg A \rightarrow B) \: \equiv \: ((A \rightarrow 0) \rightarrow B)\)

Comments

Ja habe es dann auch durch rumprobieren rausbekommen. Bei Disjunktion habe ich (a→b)→b. Das ist aber beides richtig denke ich.

---

Ja, es ist beides möglich.