Eine Aussage A kann wahr (w) oder falsch (f) sein. Andere Wahrheitswerte sind nicht zulässig (tertium non datur).
Junktoren sind Verknüpfungen, die in der Menge der Aussagen definiert sind. Mit
Hilfe von Junktoren kann man elementare Aussagen zu komplexeren Aussagen zusammensetzen.
Tautologien sind Aussagen, die immer wahr sind.
Beispiele für Junktoren:
einstelliger Junktor:
¬
Negation
zweistellige Junktoren (Auswahl):
∧
Konjunktion, logisches UND
∨
Disjunktion, logisches ODER
→
Implikation (wenn ... dann)
↔
Äquivalenz (genau dann wenn)
Die Definition der Junktoren kann über eine Wahrheitstafel erfolgen:
A
B
¬A
A ∧ B
A ∨ B
A → B
A ↔ B
W
W
F
W
W
W
W
F
W
W
F
W
W
F
W
F
F
F
W
F
F
F
F
W
F
F
W
W
Beachte: Eine Implikation ist auch wahr, wenn die Voraussetzung (Prämisse) falsch ist, denn aus etwas Falschem kann man alles folgern.
Wie viele zweistellige Junktoren gibt es?
24 = 16
Aufgaben:
1. Bilde geeignete Aussagen und formalisiere:
Wenn Anton kommt, so auch Fridolin.
Ulrike oder Christa, wenigstens eine von beiden kommt.
Entweder es kommt Fridolin oder es kommt Theobald.
Theobald und Christa kommen beide, oder es kommen beide nicht.
Wenn Ulrike kommt, dann kommen auch Christa und Anton.
Gustav kommt nur, wenn Fridolin nicht kommt.
Wer kommt, wenn alle oben genannten Aussagen wahr sind?
Als Abkürzung für die Aussage 'Anton kommt' verwendet man zweckmäßigerweise A, für die anderen Personen entsprechend.
Wenn Anton kommt, so auch Fridolin.
A → F
Ulrike oder Christa, wenigstens eine von beiden kommt.
U ∨ C
Entweder es kommt Fridolin oder es kommt Theobald.
¬(F ↔ T)
Theobald und Christa kommen beide, oder es kommen beide nicht.
T ↔ C
Wenn Ulrike kommt, dann kommen auch Christa und Anton.
U → (C ∧ A)
Gustav kommt nur, wenn Fridolin nicht kommt.
G ∧ ¬F
Für die sechs Personen gibt es insgesamt 26 = 64 Möglichkeiten zu kommen oder eben nicht. Außerdem sollen alle sechs Aussagen gleichzeitig wahr sein. Mit einer Wahrheitstafel
kann diese Situation dargestellt werden. Aufgrund der Äquivalenz von Christa und Theobald (2. Spalte) verkürzt man auf 32 mögliche Konstellationen.Nun geht man nach dem Auschlussverfahren vor. Wenn nur
eine Aussage nicht erfüllt ist, kann die Konstellation verworfen werden. Mit der Konjunktion G ∧ ¬F kann man 24 Konstellationen ausschließen. Dann betrachtet man für die folgenden Aussagen nur noch die noch nicht ausgeschlossenen.
Es kommen demnach Christa, Theobald und Gustav.
2. Durch welche Wahrheitswerte müssen die Aussagen A, B und C
belegt werden, damit die folgenden Aussagen wahr werden:
a) (¬A ∧ ¬B) ↔ ¬(A ∨ B)
b) (¬A ∨ ¬B) ↔ ¬(A ∧ B)
Anmerkung: Die Äquivalenzen in a) und b) heißen
deMorgansche Gesetze.
c) (A → B) ↔ (¬A ∨ B)
d) (A ∧ ¬B ∧ ¬C) ∨ (¬A ∧ ¬B ∧ C)
Welche Aussagen sind Tautologien?
Wahrheitstafel erstellen (exemplarisch für Teilaufgabe a))
A
B
¬A ∧ ¬B
¬(A ∨ B)
(¬A ∧ ¬B) ↔ ¬(A ∨ B)
W
W
F
F
W
F
W
F
F
W
W
F
F
F
W
F
F
W
W
W
Man erhält: a, b und c sind Tautologien, d nicht.
3. Gib die Wahrheitstafel für den dreistelligen Junktor if A then B else C an,
wobei er den Wahrheitswert von B hat, wenn A wahr ist bzw. den Wahrheitswert von C hat, wenn A falsch ist.
Wie viele dreistellige Junktoren gibt es?
A
B
C
if A then B else C
W
W
W
W
W
W
F
W
W
F
W
F
W
F
F
F
F
W
W
W
F
W
F
F
F
F
W
W
F
F
F
F
Es gibt 28 = 256 verschiedene Konstellationen.
Man benötigt aber nicht alle Junktoren, sondern kann aus einigen wenigen die anderen erzeugen: man
spricht von einem Erzeugendensystem. Beispiele für ein Erzeugendensystem für sind E1:(¬, ∧, ∨)
oder E2:(¬, ∧) oder sogar nur E3:(↑,
also nand).
A
B
A ↑ B
W
W
F
F
W
W
W
F
W
F
F
W
Man nennt eine Formel
der Bauart (A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ C) ∨ (¬A ∧ ¬B ∧ C) eine mehrgliedrige Disjunktion, bei der jedes
Disjunktionsglied eine Konjunktion von Variablen und negierten Variablen ist, eine disjunktive Normalform (DNF).
So kann man beispielsweise A ↔ B einfach 'nachbauen', indem man dafür (A ∧ B) ∨ (¬A ∧ ¬B) schreibt.
4. Gib folgende Aussagen in den
jeweiligen Erzeugendensystemen an:
a) A → B
b) A ↔ B
c) A ∨ B
d) Junktoren von E1 durch Junktor von E3 ausdrücken.
Beginnt man mit Teilaufgabe d), erschließen sich die anderen Teilaufgaben.
¬A lässt sich durch (A ↑ A) ersetzen, (A ∧ B) durch (A ↑ B) ↑ (A ↑ B).
(A ∨ B) kann mithilfe der deMorganschen Gesetze umgewandelt werden in ¬(¬A ∧ ¬B).
Weitere beliebige Aussagen lassen sich dann durch disjunktive Normalforman ausdrücken.
5. Formalisiere folgende Aussage: Der See ist nicht
zugefroren, oder der Esel geht nicht auf’s Eis, oder es stimmt
nicht, dass der See nicht zugefroren ist oder es dem Esel zu gut
geht, oder es stimmt nicht, dass der See nicht zugefroren ist oder es
dem Esel nicht zu gut geht oder der Esel auf’s Eis geht.
Überprüfung mit einer Wahrheitstabelle: keine Tautologie.
6. Negiere die folgenden Aussagen. Verwende nur die Junktoren von E1.
a) A → B sowie (¬A ∧ B) ↔ (A ∨ B) .
b) Verbalisiere die Aussagen aus Teilaufgabe a) sowie ihre Negationen mit A:
Die Panze fralt und B: Die Turtel knuselt sowie mit einer
Interpretation deiner Wahl.
Man kann z.B. eine Wahrheitstafel verwenden:
A
B
A→ B
¬(A→ B)
(¬A ∧ B) ↔ (A ∨ B)
¬((¬A ∧ B) ↔ (A ∨ B))
W
W
W
F
F
W
F
W
W
F
W
F
W
F
F
W
F
W
F
F
W
F
W
F
Mit disjunktiven Normalformen lassen sich nun die Aussagen bzw. ihre Negationen mit den Junktoren von E1 ausdrücken.
Zu Teilaufgabe b): Wenn die Panze fralt, dann knuselt die Turtel.
Die Negation: Die Panze fralt und die Turtel knuselt nicht.
Anmerkung: Negationen von (zusammengestzten) Aussagen kann man auch durch 'Es ist nicht der Fall, dass ...' ausdrücken.
2. Aussage: Genau dann fralt die Panze nicht und es knuselt die Turtel, wenn die Panze fralt oder die Turtel knuselt.
Die Negation: Es ist nicht der Fall, dass genau dann die Panze nicht fralt und die Turtel knuselt, wenn die Panze fralt oder die Turtel knuselt.
BEACHTE: Nicht immer sind Verbalisierungen eindeutig. Man muss ggfs sorgfältig formulieren.
7. Beweise: Wenn
der Hahn kräht auf dem Mist, ändert sich das Wetter oder es
bleibt wie es ist.
A: Der Hahn kräht.
B: Das Wetter ändert sich.
Die Formalisierung lautet dann: A → (B ∨ ¬B). Nun wieder eine Wahrheitstafel verwenden.
