Funktionale Vollständigkeit

---

Beispiel - Umschreibung des ausschließenden Oders

Betrachten wir z.B. den mittels ausschließendem Oder verknüpften Satz

• "Der Wumpus befindet sich auf Feld [A,3] oder [B,2]"

Dieser besteht aus den Teilaussagen

• γ: "Der Wumpus befindet sich auf Feld [A,3]"
• δ: "Der Wumpus befindet sich auf Feld [B,2]"

Betrachten wir alle möglichen Kombinationen der relevanten Zustände der Welt, und schreiben wir ° für den Junktor, so ergibt sich folgende Tabelle:

Zustand der Welt / Bewertung von γ	Zustand der Welt / Bewertung von δ	Bewertung von γ ° δ
Wumpus nicht auf Feld [A,3] / falsch	Wumpus nicht auf Feld [B,2] / falsch	falsch
Wumpus nicht auf Feld [A,3] / falsch	Wumpus auf Feld [B,2] / wahr	wahr
Wumpus auf Feld [A,3] / wahr	Wumpus nicht auf Feld [B,2] / falsch	wahr
Wumpus auf Feld [A,3] / wahr	Wumpus auf Feld [B,2] / wahr	nicht möglich, deswegen falsch

---

Dies können wir durch eine Kombination aus Konjunktion, Disjunktion und Negation ausdrücken:

• "Der Wumpus befindet sich auf Feld [A,3] ODER [B,2], UND NICHT auf Feld [A,3] UND [B,2]"

also

• (γ ODER δ) UND NICHT (γ UND δ)

γ	δ	γ°δ	γ ODER δ	γ UND δ	NICHT (γ UND δ)	(γ ODER δ) UND NICHT (γ UND δ)
falsch	falsch	falsch	falsch	falsch	wahr	falsch
falsch	wahr	wahr	wahr	falsch	wahr	wahr
wahr	falsch	wahr	wahr	falsch	wahr	wahr
wahr	wahr	falsch	wahr	wahr	falsch	falsch

---

Das nichtausschließende Oder lässt sich auch durch eine Kombination der Negation und der Äquivalenz ausdrücken:

Eine mittels ausschließendem Oder verknüpfte Aussage ist genau dann wahr, wenn genau eine der beiden Teilaussagen wahr ist. Dies entspricht genau dem Gegenteil der Äquivalenz, die ja genau dann wahr ist, wenn beide Teilaussagen wahr sind.

γ	δ	γ°δ	γ GENAU _DANN_ WENN δ	NICHT (γ GENAU _DANN_ WENN δ)
falsch	falsch	falsch	wahr	falsch
falsch	wahr	wahr	falsch	wahr
wahr	falsch	wahr	falsch	wahr
wahr	wahr	falsch	wahr	falsch

---