Boolesche Algebra

Jrgen Reischer
Informationswissenschaft Regensburg

Aussagenlogik

Aussagenlogik:

Teilbereich der (klassischen) Logik, der sich mit

Aussagen und ihren logischen Verknpfungen
(Junktoren, Konnektoren) befasst;
Grndervter sind u. a. Aristoteles, George Boole,
Gottlob Frege und Bertrand Russell.
Eine Anwendung der Aussagenlogik findet sich
z. B. in der Informatik:

2010

Hardware: Konzeption logischer Schaltungen;

Software: Formulierung logischer Bedingungen in
Programmiersprachen.
Jrgen Reischer

Aussagenlogik

Aussagen:

sind wahr (w, true) oder falsch (f, false), d. h. sie

besitzen genau einen von zwei Wahrheitswerten;
sind einfach (elementar) oder komplex, d. h. durch
Junktoren aus elementaren Aussagen zusammengesetzt:

2010

Elementaraussagen kann direkt ein Wahrheitswert

zugeordnet werden: "Die Erde ist rund." ist wahr;
fr komplexe Aussagen kann ein Wahrheitswert aus den
Elementaraussagen berechnet werden (KompositionalittsPrinzip): "Die Erde ist rund und der Mond ist aus grnem
Kse." ist (insgesamt) falsch.

sind negierbar: "Es ist nicht der Fall (unwahr), dass die
Erde eine Scheibe ist." ist wahr.
Jrgen Reischer

Aussagenlogik

Junktoren:

2010

sind zunchst rein logische Verknpfungen wie

"und", "oder", "falls" u. a., die auch eine
umgangssprachliche Interpretation besitzen;
verknpfen die Wahrheitswerte von zwei
Aussagen miteinander und liefern einen neuen
Wahrheitswert fr die Gesamtaussage ("Falls
es regnet, ist die Strae nass." ist wahr);
knnen als Funktionen mit zwei Argumenten
(Eingangswerte) und einem Ergebnis
(Ausgangswert) verstanden werden.
Jrgen Reischer

Aussagenlogik

Beispiele fr Aussagen, die in der Aussagenlogik

behandelt werden knnen:

Beispiele fr Aussagen, die nicht (unmittelbar)

behandelt werden knnen:

2010

"3 ist eine Primzahl." (w);

"3 und 2 ergibt 7." (f);
"Der Mars hat zwei Monde." (w);
"Es gibt Leben im All." (w);
"Einstein war Biologe." (f).

"Alle (diese) Raben sind schwarz." (w oder f);

"Das Quark ist das kleinste Teilchen der Materie." (w oder f);
"Diese Aussage ist falsch." (w und/oder f);
"Der Knig von Frankreich ist kahl." (weder w noch f);
"Die Leiche hat ihr Abitur nachgemacht." (weder w noch f).
Jrgen Reischer

Aussagenlogik

bungsaufgabe:
Welche der folgenden Stze sind Aussagestze, die in
der Aussagenlogik behandelt werden knnen?

2010

"Schwren Sie, dass Sie die Wahrheit sagen!";

"Eine Primzahl ist nur durch 1 und sich selbst teilbar.";
"Wer hat den Kuchen aufgegessen?";
"Reiche mir doch bitte das Salz herber."
"Wer dreimal lgt, dem glaubt man nicht.";
"Albert Einstein ist Albert Einstein.";
"Die Sonne scheint oder (und) sie scheint nicht.";
"Die Erdscheibe ist rund oder (und) sie ist nicht rund.";
"Ich knnte behaupten, dass 1+1=2 ist.";
"Dass die Welt aber auch so schlecht ist!";
"Kein Mensch hat zwei Herzen!".
Jrgen Reischer

Aussagenlogik

Schreibweisen:

Einer (Elementar-)Aussage wie "Die Erde ist rund."

wird eine Aussagenvariable A, B, C, , X, Y, Z
zugeordnet.
Beispiel (Anfhrungsstriche relevant):

Zugleich kann die Variable aber auch fr den

Wahrheitswert der Aussage stehen:

2010

A = "Die Erde ist rund.";

B = "Der Mond ist aus grnem Kse.".

A ist wahr
A"Die Erde ist rund." = w bzw. kurz A = w;

B ist falsch
B"Der Mond ist aus grnem Kse." = f bzw. kurz B = f.
Jrgen Reischer

Aussagenlogik

Die logischen Junktionen (Junktoren) entsprechen den

logischen Operationen (Operatoren) auf Bits:

Es handelt sich hierbei nicht um (Binr-)Ziffern im

Sinne von Bits oder Zahlen, sondern um logische
Wahrheitswerte:

2010

0
falsch, 1
wahr (diese Zuordnung ist letztlich willkrlich

und prinzipiell umkehrbar);
logischer Operator
(aussagen)logischer Junktor.

Wahrheitswerte besitzen keinen Stellenwert wie 20, 21 usw.,

da es sich nicht um Zahlen handelt;
Wahrheitswerte werden stets einzeln verrechnet, nicht als
Ketten von Bits.
Wahrheitswerte sind letztlich bereits Interpretationen von
Bits (genau wie einzelne Bits als Dualziffern).
Jrgen Reischer

Aussagenlogik

Junktoren und ihre Schreibweisen:

Negation: '' (z. B. A)

Konjunktion: '
' (z. B. A B);

Disjunktioninklusiv: '
' (z. B. A B);

Disjunktionexklusiv: '
' (z. B. A B);

Subjunktion: '' (z. B. A B);

Bijunktion: '' (z. B. A B).
 vgl. die logischen Operatoren.

2010

Jrgen Reischer

Aussagenlogik

Definition/Interpretation der Junktoren:

Negation:

Definition:
A ist dann wahr, wenn A falsch ist;

A ist dann falsch, wenn A wahr ist.
 A kann nicht zugleich wahr und falsch sein.
 A und A knnen nicht zugleich zutreffen.

Interpretation:

2010

A = "Es ist nicht der Fall, dass A", "nicht A";

A = "Die Erde ist eckig."  A = "Es ist nicht der Fall,
dass die Erde eckig ist." (daraus folgt nicht zwingend,
dass die Erde rund ist!).
Jrgen Reischer

10

Aussagenlogik

Anmerkungen zur Negation:

Die Negation einer Aussage kann in der Alltagssprache

durch verschiedene Mittel erreicht werden:

"kein"/"niemand"/"nichts" ("nicht ein/einer/etwas"):

"Es ist nicht der Fall, dass ein Wal ein Fisch ist." = "Kein Wal ist ein Fisch.";
"Es ist nicht so, dass jemand (ein Mensch) 2010 auf dem Mars war." =
"Niemand (kein Mensch) war 2010 auf dem Mars.";
"Es ist nicht so, dass etwas Grnes gelb ist." = "Nichts Grnes ist gelb.".

"nicht": "Es ist nicht der Fall, dass Hans Maria kennt." = "Hans
kennt Maria nicht." (Negation des Verbs anstelle des Satzes);
"weder noch": "Es ist nicht der Fall, dass Hans Maria oder
Maria Hans kennt." = "Hans kennt Maria nicht und Maria kennt
Hans nicht." = "Weder kennt Hans Maria noch Maria Hans.";
"un-": "Es ist nicht so, dass Hans schuldig ist." = "Hans ist
unschuldig."

 Negation der ganzen Aussage wird auf Negation eines

Satzteils bertragen (Bedeutungsgleichheit vorausgesetzt).
2010

Jrgen Reischer

11

Aussagenlogik

Konjunktion:

Definition:

Interpretation:

2010

A B ist genau dann wahr, wenn sowohl A als auch B

wahr sind;
A B ist falsch, wenn A oder B oder beide falsch sind.
A B: "A und B (zugleich)", "sowohl A als auch B";
A = "Die Erde ist rund.", B = "Der Mond ist eckig.":

A B  "Die Erde ist rund und der Mond ist eckig." ist
insgesamt falsch.

A B  "Die Erde ist rund und es ist nicht der Fall, dass der
Mond eckig ist." ist insgesamt wahr.
Jrgen Reischer

12

Aussagenlogik

Anmerkungen zur Konjunktion:

Die Konjunktion "und" in der Alltagssprache ist

vieldeutig:

temporal gleichordnend: "den Zug hren und sehen";

temporal nachordnend: "den Zug erst hren und dann
sehen";
kausal nachfolgend: "auf eine Bananenschale treten
und (deshalb) ausrutschen";
mengenbildend: "Hans und Maria zusammen", "1 und 1
gibt (zusammen) 2", "das eine und das andere";
intensivierend: "der Zug kam nher und nher".

 Im logischen Sinne bedeutet "und" am ehesten

"sowohl als auch", "beides zugleich".
2010

Jrgen Reischer

13

Aussagenlogik

Disjunktion (inklusiv):

Definition:

A B ist bereits dann wahr, wenn entweder A oder B

oder auch beide A und B wahr sind;
A B ist nur dann falsch, wenn sowohl A als auch B
falsch sind.

Interpretation:

A B: "A oder B (oder beide)", "A und/oder B";

A = "Die Erde ist rund.", B = "Der Mond ist eckig.":

2010

A B  "Die Erde ist rund oder der Mond ist eckig." ist
insgesamt wahr.
A B  "Es ist nicht der Fall, dass die Erde rund ist, oder der
Mond ist eckig." ist insgesamt falsch.
Jrgen Reischer

14

Aussagenlogik

Disjunktion (exklusiv):

Definition:

A B ist dann wahr, wenn entweder A oder B (aber

nicht A und B zugleich) wahr sind;
A B ist dann falsch, wenn A und B beide falsch oder
beide wahr sind (d. h. wenn A und B gleich sind).

Interpretation:

A B: "entweder A oder B";

A = "Einstein ist tot.", B = "Einstein ist lebendig.":

2010

A B  "Entweder Einstein ist tot oder Einstein ist lebendig."

ist insgesamt wahr.
A B  "Entweder Einstein ist tot oder es ist nicht der Fall,
dass Einstein lebendig ist." ist insgesamt falsch.
Jrgen Reischer

15

Aussagenlogik

Anmerkungen zur Disjunktion:

In der Alltagssprache wird "A oder B" meist als exklusives

"entweder A oder B" verstanden, auch wenn es Beispiele
fr das inklusive Oder gibt:

Alltagssprachliches "oder" kann manchmal auch "und"

bedeuten und umgekehrt:

2010

"Hans fhrt dieses Jahr nach Neuseeland oder Brasilien in

den Urlaub." (nur exklusiv interpretierbar);
"Heute abend gehen wir etwas essen oder etwas trinken."
(auch inklusiv interpretierbar).

"Sprechstunde ist Montag und Mittwoch." (= "Sprechstunde

ist Montag oder Mittwoch.");
"Einstein war nicht Biologe oder Chemiker, sondern
Physiker." (= "Einstein war kein Biologe und kein Chemiker,
sondern Physiker.").
Jrgen Reischer

16

Aussagenlogik

Subjunktion:

Definition:

Interpretation:

2010

A B ist dann wahr, wenn A falsch ist (und B wahr oder

falsch) oder sowohl A als auch B wahr sind;
A B ist nur dann falsch, wenn A wahr und B falsch ist.
A B: "falls/wenn A, dann B", "B, falls A", "gesetzt/fr
den Fall, dass A, dann B" (A Antezendes, B Konsequens);
A = "Die Erde ist eine Kugel.", B = "Die Erde ist rund.":

A B  "Falls die Erde eine Kugel ist, ist die Erde rund." ist wahr;

A B  "Falls die Erde eine Kugel ist, ist es nicht der Fall, dass
die Erde rund ist." ist falsch.
Jrgen Reischer

17

Aussagenlogik

Anmerkungen zur Subjunktion A B:

Aus der Wahrheit von A B folgt:

Logisch gleichwertig mit A B:

2010

Wenn A der Fall (wahr) ist, ist auch B der Fall (wahr).
Wenn A falsch ist (also A der Fall ist), kann ber die
Wahrheit von B keine Aussage gemacht werden, da aus
Falschem Beliebiges folgt ("Ex falso sequitur quodlibet."
oder: "Wenn der Mond aus grnem Kse ist, ist
Beckenbauer der Kaiser von China.").
B A: Wenn B nicht der Fall (falsch) ist, dann ist
auch A nicht der Fall (falsch);
A B (eine umgangssprachliche [Re-]Interpretation fr
A B ist hier weniger sinnvoll).
Jrgen Reischer

18

Aussagenlogik

Bijunktion:

Definition:

A B ist genau dann wahr, wenn A und B wahr oder A

und B falsch sind (d. h. wenn A und B gleich sind);
A B ist dann falsch, wenn A wahr und B falsch ist
oder umgekehrt (d. h. wenn A und B verschieden sind).

Interpretation:

A B: "A genau dann, wenn B", "A nur dann, wenn B";
A = "Die Sonne scheint.", B = "Der Himmel ist blau.":

2010

A B  "Die Sonne scheint genau dann, wenn der Himmel blau

ist." ist wahr;
A B  "Die Sonne scheint genau dann, wenn es nicht der
Fall ist, dass der Himmel blau ist." ist falsch.
Jrgen Reischer

19

Aussagenlogik

Anmerkungen zur Bijunktion A B:

Aus der Wahrheit von A B folgt:

2010

Wenn A der Fall (wahr) ist, ist auch B der Fall (wahr) und
umgekehrt (vgl. 1 unten).
Wenn A nicht der Fall (falsch) ist, dann ist auch B nicht
der Fall (falsch) und umgekehrt (vgl. 2 unten).

Logisch gleichwertig mit A B:

(A B) (B A) = (B A) (A B): A und B sind

gleich, wenn aus der Wahrheit von A die Wahrheit von B
und aus der Wahrheit von B die Wahrheit von A folgt (vgl.
1 oben).

(A B) (A B): Nur wenn A (der Fall ist), ist auch B

der Fall, da bei A entsprechend B folgt (vgl. 2 oben).
Jrgen Reischer

20

Aussagenlogik

Logische Junktionen im berblick/Vergleich:

*

* Fr '' (unrer Operator) wird nur der Wert von A

verwendet, fr alle anderen A und B (binre
Operatoren).
2010

Jrgen Reischer

21

Aussagenlogik

Allgemeine Hinweise:

Es ist zu unterscheiden zwischen den zwei

Ebenen der Objekt- und der Metasprache:

2010

Objektsprache: die Ebene der aussagenlogischen

Ausdrcke (d. h. einfache Elementaraussagen
oder durch Junktoren zusammengesetzte
Aussagen);
Metasprache: die Ebene der Sprache, in der die
aussagenlogischen Ausdrcke interpretiert
werden (hier Dt.; oder auch jede andere
natrliche Sprache).
Jrgen Reischer

22

Aussagenlogik

Die Semantik der Objektsprache ist eine

andere als die der Metasprache, so dass die
Interpretation der Junktoren in der
Metasprache nicht immer gelingt:

2010

Die Semantik der Objektsprache definiert lediglich,

welcher Junktor bei welchen Wahrheitswerten von A
und B welche Ergebnisse liefert.
Ob die jungierten Aussagen A und B dabei auch in
einem sinnvollen inhaltlichen Zusammenhang auf der
Ebene der Metasprache stehen, spielt keine Rolle.
Insbesondere bei der Subjunktion und der Bijunktion
darf "Wenn A, dann B" bzw. "A genau dann, wenn B"
nicht als kausal, temporal oder sonstwie verbunden
interpretiert werden.
Jrgen Reischer

23

Aussagenlogik

Beispiele fr die inhaltliche Unabhngigkeit der

Teilaussagen A und B in A B:

Beispiel 1: A = "2+2=4", B = "Mars ist ein Planet.":

"2+2=4" "Mars ist ein Planet." (formal wahr):

"Wenn 2+2=4 ist, dann ist Mars ein Planet."
(inhaltlich ok).

Beispiel 2: A = "2+2=5", B = "Mars ist ein Planet.":

"2+2=5" "Mars ist ein Planet". (formal wahr);

"Wenn 2+2=5 ist, dann ist Mars ein Planet."
(inhaltlich ko).

 A B ist auch dann wahr, wenn A falsch ist!

Die natrlichsprachigen Bedeutungen der Aussagen
werden auf der Ebene der Aussagenlogik ignoriert.
2010

Jrgen Reischer

24

Aussagenlogik

Letztlich wird versucht, eine bestmgliche

Zuordnung der logischen Junktionen zu
natrlichsprachigen Konnektoren zu finden:
Konnektor der Metasprache (Deutsch)
Syntax
Semantik
"A und/oder B"
'das eine oder das andere,
oder auch beides zugleich'


A/B f/f

f/w w/f w/w

w
w
A
B f
AB
Syntax
Semantik
Junktor der Objektsprache (Aussagenlogik)
2010

Jrgen Reischer

25

Aussagenlogik

Semantik und Syntax aussagenlogischer

Terme ('Aussageformen'):

2010

Bislang haben wir durch Definitionen (vgl.

Wertetabelle oben) nur festgelegt, welche
'Bedeutung' die Junktoren im Hinblick auf die
Verknpfung von Wahrheitswerten haben.
Fr eine vollstndige Bestimmung der
'aussagenlogischen Sprache' muss auch
festgelegt werden, wie aussagenlogische
Terme syntaktisch korrekt konstruiert werden
mssen, um berhaupt interpretierbar zu sein.
Jrgen Reischer

26

Aussagenlogik

Definition der Syntax der aussagenlogischen

Ausdrcke: Aussagenlogische Terme sind per
Definition nur
1) die Wahrheitswerte w und f;
2) die Wahrheitswert-Variablen A, B, C, , X, Y, Z;
3) die Verknpfungen zweier (beliebiger, einfacher oder
schon komplexer) aussagenlogischer Terme und zu

, ;

, , , ;
o (jede andere zweiwertige Junktion, z. B. exklusive
Disjunktion).

4) Nur die in 1) bis 3) erklrten Ausdrcke sind

aussagenlogische Terme.
2010

Jrgen Reischer

27

Aussagenlogik

Operatorenvorrang (strker nach schwcher):

2010

Implizite Operatorenhierarchie:
1)

Negation A;

2)

Konjunktion A B ('Punkt'-Operator);

3)

Disjunktion A B ('Strich'-Operator);

4)

Subjunktion A B ('Pfeil'-Operator);

5)


Bijunktion A B ('Pfeil'-Operator).
Negation bindet strker als Konjunktion, Konjunktion strker
als Disjunktion usw.

Explizite nderung der Operatoren-Hierarchie durch

Klammerung '()' mglich:

geklammerte (Teil-)Ausdrcke werden zuerst berechnet;

Klammer-Hierarchie: '( [ () ] )'.

Jrgen Reischer

28

Aussagenlogik

2010

Beweis fr die logische

Gleichheit von A B,
B A und A B
mittels Wertetabellen:

AB

A B

B A

Jrgen Reischer

29

Aussagenlogik

Beweis fr die logische

Gleichheit von A B,
(A B) (B A) und
(A B) (A B)
mittels Wertetabellen:
A B AB BA

AB

A B A B A B

(A B)
(A B)

f w

f w

w f

w f

w w

w w

2010

(A B)
(B A)

Jrgen Reischer

30

Aussagenlogik

bungsaufgaben:

bersetzen Sie folgende Stze in eine

aussagenlogische Form:

bersetzen Sie folgende Stze in eine

aussagenlogische Form, indem Sie "Wenn A, dann B"
durch A B wiedergeben:

2010

"Berta und Ursula lieben Fritz nicht.";

"Es regnet, aber es ist nicht kalt." ("aber"/"sondern" = "und");
"Fritz fhrt nicht nach Genua oder Pisa, sondern nach Rom.".

"Wenn die Sonne scheint, regnet es nicht, und wenn es

regnet, scheint die Sonne nicht."
"Peter verkauft sein Auto nur, wenn er keinen Verlust
macht."
"Kurt verreist nicht gerne, es sei denn ins Ausland."
Jrgen Reischer

31

Aussagenlogik

Weisen Sie anhand von Wertetabellen nach, dass

folgende Aussagen (stets) wahr sind:

Weisen Sie anhand von Wertetabellen nach, dass

folgende Verknpfungen gleichwertig sind:

2010

A A;
A A;
A (B A);
A B (A B);
(A B) (B A).

(A) = A;
A B = A B;
A B = (A B);
(A B) = A B;
A B = (A B) (A B).
Jrgen Reischer

32

Boolesche Funktionen

Die ein- und zweistelligen Operationen bzw.

Junktionen knnen als Funktionen verstanden werden:

Bislang haben wir eine einstellige und fnf zweistellige

Funktionen kennengelernt.
Es gibt jedoch insgesamt 16 zweistellige Funktionen:

2010

mit ein/zwei Werten als Eingabe (Argumente),

mit einem Wert als Ausgabe (Ergebnis).

Jeder der beiden Eingangswerte kann wahr oder falsch sein,

so dass insgesamt vier Eingangskombinationen mglich sind;
jeder Eingangskombination kann ein eigener Ausgabewert
zugeordnet werden, der das Funktionsergebnis darstellt.

Die 16 mglichen Funktionen im berblick:

Jrgen Reischer

33

Boolesche Funktionen

2010

Funktionen 0 bis 7:
A/B f/f

f/w w/f w/w Bezeichnung

F0

Kontradiktion, 'Null'-Funktion f

F1

Konjunktion

AB

F2

Inhibition von A

A B

F3

Identitt von A

F4

Inhibition von B

A B

F5

Identitt von B

F6

DisjunktionExkl., Antivalenz

AB

F7

DisjunktionInkl., Adjunktion

AB

Jrgen Reischer

Term

34

Boolesche Funktionen

2010

Funktionen 8 bis 15:

A/B f/f

f/w w/f w/w Bezeichnung

Term

F8

Peirce-Funktion, Negatdisj.

(A B)

F9

Bijunktion

AB

F10

Negation von B

F11

Replikation

BA

F12

Negation von A

F13

Subjunktion

AB

F14

Sheffer-Funktion, Negatkonj. (A B)

F15

Tautologie, 'Eins'-Funktion
Jrgen Reischer

w
35

Boolesche Funktionen

Interpretationshilfe fr obige Tabelle:

Jede Zeile kann in eine eigenstndige Wertetabelle
berfhrt werden, die jeweils eine andere logische
Funktion (und damit Junktion) darstellt.
A

F0

F1

F15

Kontradiktion Konjunktion
2010

Jrgen Reischer

Tautologie
36

Boolesche Funktionen

Obige Tautologie und Kontradiktion stehen fr eine

ganze Klasse von Termen (hier logische Ausdrcke),
die schon allein aufgrund ihrer logischen Form stets
wahr oder falsch sind:

Tautologie: Aussageterm, der insgesamt immer wahr ist

(Wahr- oder 'Eins'-Funktion):

Kontradiktion: Aussageterm, der insgesamt immer falsch ist

(Falsch- oder 'Null'-Funktion):

2010

A A, A w, A A;
(A A) B, A (B A);

A A, A f, (A A);
(A A) B, (A A) B;

Tautologien bzw. Kontradiktionen sind bei jeder

mglichen Belegung der Aussagenvariablen mit
Wahrheitswerten wahr bzw. falsch.
Jrgen Reischer

37

Boolesche Funktionen

Die Peirce- und Sheffer-Funktionen haben besondere

Eigenschaften:

Negatdisjunktion: (A B) = A NOR B:

Negatkonjunktion: (A B) = A NAND B:

A = A NOR A, B = B NOR B;
A B = (A NOR B) = (A NOR B) NOR (A NOR B).
A = A NAND A, B = B NAND B;
A B = (A NAND B) = (A NAND B) NAND (A NAND B).

Ferner gelten die Gesetze von de Morgan:

(A B) = A B (= A NOR B);

(A B) = A B (= A NAND B).
 Jede logische Funktion kann allein durch NAND oder NOR
ausgedrckt werden!

2010

Jrgen Reischer

38

Boolesche Funktionen

bungsaufgaben:

Funktionstabellen:

Erstellen Sie eine Schaltung in Form eines logischen

Terms, die folgende Bedingungen erfllen soll:

2010

Erstellen Sie eine Funktionstabelle fr 1 Eingangsvariable

A und benennen Sie die Funktionen.
berlegen Sie, welche Funktionen bei 0 Eingangsvariablen
mglich sind.

Drei Personen A, B, C haben jeweils einen Schalter vor

sich, der an oder aus sein kann;
eine Lampe L soll dann aufleuchten, wenn mindestens
zwei der Personen oder alle drei ihren Schalter gedrckt
haben.
Jrgen Reischer

39

Boolesche Funktionen

Bislang haben wir vorgegebene Terme mittels

Wertetabellen untersucht:

Umgekehrt knnen Wertetabellen auch dazu

genutzt werden, Terme zu erstellen:

2010

zur berprfung der Gleichheit zweier Terme

(gleiche Ausgabewerte = gleiche Funktion);
zur berprfung der ausnahmslosen Wahrheit
eines Terms (alle Ausgaben sind wahr bei jeder
mglichen Kombination der Eingangsvariablen).

in disjunktiver Normalform;
in konjunktiver Normalform.
Jrgen Reischer

40

Boolesche Funktionen

Disjunktive Normalform (DNF):

A
f
f
f
f
w
w
w
w

2010

B
f
f
w
w
f
f
w
w

C
f
w
f
w
f
w
f
w

F
w
w
w
f
w
f
f
f

Minterm
A
B
C
A
B
C
A
B
C

A
B
C

Eine Funktion F soll dann wahr

werden, wenn mindestens zwei
Eingangsvariable falsch sind:
F(A,B,C) =
(A
B
C)
(A
B
C)
(A
B
C)
(A
B
C)

Beispiel: Ein Signal soll ertnen,

wenn mindestens zwei von drei
redundanten Rechnern (z. B. in
einem Flugzeug) ausgefallen sind.

Jrgen Reischer

41

Boolesche Funktionen

Aufstellung einer DNF:

Fr jede Zeile der Wertetabelle, die wahr

werden soll, wird ein so genannter Minterm
erstellt, der mit allen anderen Mintermen der
Tabelle disjungiert wird.
In einem Minterm sind alle Eingangsvariablen so
konjungiert, dass der Minterm selbst wahr wird:

2010

Ist die Eingangsvariable in der entsprechenden Zeile

falsch, muss die Variable negiert in den Minterm
eingehen, damit der Minterm insgesamt wahr werden
kann;
ist die Eingangsvariable schon wahr, wird sie nichtnegiert mit den anderen Variablen konjungiert.
Jrgen Reischer

42

Boolesche Funktionen

Konjunktive Normalform (KNF):

A
f
f
f
f
w
w
w
w

2010

B
f
f
w
w
f
f
w
w

C
f
w
f
w
f
w
f
w

F
w
w
w
f
w
f
f
f

Maxterm

A
B
C

A
B
C
A
B
C
A
B
C

Eine Funktion F soll dann wahr

werden, wenn mindestens zwei
Eingangsvariable falsch sind:
F(A,B,C) =
(A
B
C)
(A
B
C)
(A
B
C)
(A
B
C)

berlegung: Wenn A = B = C = f, dann

werden alle Maxterme wie gewnscht
wahr, d. h. F = w; bei A = f & B = C =
w wird A
B
C = f und damit F = f.

Jrgen Reischer

43

Boolesche Funktionen

Aufstellung einer KNF:

Fr jede Zeile der Wertetabelle, die falsch

werden soll, wird ein so genannter Maxterm
erstellt, der mit allen anderen Maxtermen der
Tabelle konjungiert wird.
In einem Maxterm sind alle Eingangsvariablen so
disjungiert, dass der Maxterm selbst falsch wird:

2010

Ist die Eingangsvariable in der entsprechenden Zeile

wahr, muss die Variable negiert in den Maxterm
eingehen, damit der Maxterm insgesamt falsch werden
kann;
ist die Eingangsvariable schon falsch, wird sie nichtnegiert mit den anderen Variablen disjungiert.
Jrgen Reischer

44

Boolesche Funktionen

bungsaufgabe:
Gegeben sei rechts stehende
Wertetabelle:

2010

Erzeugen Sie jeweils eine DNF

und KNF.
berlegen Sie, welche Funktion
damit realisiert werden kann.
Interpretieren sie hierzu f als 0
und w als 1, wobei A, B und C die
Stellenwerte 22, 21 und 20
aufweisen sollen.
Jrgen Reischer

A
f
f
f
f
w
w
w
w

B
f
f
w
w
f
f
w
w

C
f
w
f
w
f
w
f
w

F
f
f
w
w
f
w
f
w

45

Aussagenlogische Schlsse

Mit Hilfe der Aussagenlogik lassen sich Stze

der Alltagssprache (Metasprache) als Ausdrcke
der logischen Sprache (Objektsprache)
formulieren.
Dies soll aber kein Selbstzweck sein, sondern
aussagenlogische Terme spielen beim logischen
Schlieen eine entscheidende Rolle:
Aus einer oder mehreren Prmissen (vorausgesetzte
Aussagen) wird
ber eine logische Schlussfolgerung

eine Konklusion (erschlossene Aussage) abgeleitet.

2010

Jrgen Reischer

46

Aussagenlogische Schlsse

Ein Schluss ist dann logisch gltig, wenn

Sind eine oder mehrere Prmissen falsch, ist der

Schluss zwar ebenfalls logisch gltig (aus Falschem
folgt Beliebiges), aber

2010

die Konklusion wahr ist unter der Voraussetzung, dass die

Prmissen wahr sind (bzw. aus wahren Prmissen eine wahre
Konklusion folgt), d. h.
bei wahren Prmissen die Konklusion nicht falsch sein kann
(nur in diesem Fall wre der Schluss ungltig).

unbegrndet oder nicht-wohlfundiert (engl. 'unsound');

die wahre Konklusion bei falschen Prmissen folgt nicht aus
den (falschen) Prmissen, sondern ist kontingenterweise aus
anderen Grnden (zuflligerweise) wahr.
Jrgen Reischer

47

Aussagenlogische Schlsse

Obgleich bei logischen Schlssen anders als

bei Junktionen Prmissen und Konklusion
keine neue Aussage bilden, besteht eine
bereinstimmung mit der Subjunktion:

Ist die Subjunktion wahr, ist der Schluss gltig:

2010

sind die Prmissen wahr, ist der Schluss begrndet

('sound');
sind die Prmissen falsch, ist der Schluss unbegrndet
('unsound').

Ist die Subjunktion hingegen falsch, ist der

Schluss ungltig.
Jrgen Reischer

48

Aussagenlogische Schlsse

Eine wahre Subjunktion nennen wir Implikation; sie

beschreibt einen gltigen Schluss. Analog verfahren wir
mit der wahren Bijunktion und nennen sie quivalenz.
A B AB AB

A B AB AB

w w

w f

w f

w w w

w f

w w w

A B:

2010

A impliziert B
A folglich B

w
f

A B: A quivalent B
A gleich//= B

Jrgen Reischer

49

Aussagenlogische Schlsse

Eine Schlussfolgerung (Implikation) wird im Alltag nur

dann als gltig akzeptiert, wenn sie wahr ist:

Subjunktion: "Wenn die Erde eine Kugel ist, dann ist die
Erde eine Scheibe." (w f = f);
Implikation:

Eine quivalenz (Doppelschluss) wird im Alltag nur

dann als gltig akzeptiert, wenn sie wahr ist:

2010

"Wenn die Erde eine Kugel ist, dann ist die Erde rund."
(w w = w oder w w).
"Wenn die Erde keine Kugel ist, dann ist die Erde nicht rund."
(f f = w oder f f).

Bijunktion: "Genau dann, wenn 1+1=2 ist, ist auch 2+24."

(w f = f);
quivalenz: "Genau dann, wenn 1+12 ist, ist auch 2+24."
(f f = w oder f f).
Jrgen Reischer

50

Aussagenlogische Schlsse

Hinweis:

Oftmals wird die Subjunktion bereits als (materiale)

Implikation und die Bijunktion als (materiale) quivalenz
bezeichnet.
Dies ist terminologisch insofern inkorrekt, als hier
objektsprachliche Junktionen mit metasprachlichen
Interpretationen gleichgesetzt werden:

2010

Das Konzept der quivalenz setzt voraus, dass die bijungierten

Werte auch tatschlich gleich, d. h. beide wahr oder falsch
sind. Sind die Werte verschieden, kann man nicht von
quivalenz (Gleichheit) reden, wohl aber von Bijunktion.
Das Konzept der Implikation setzt voraus, dass aus wahren
Prmissen keine falsche Konklusion folgt. Wenn dies der Fall
ist, kann man nicht von Implikation sprechen, wohl aber von
Subjunktion.
Jrgen Reischer

51

Aussagenlogische Schlsse

Die Zurckfhrung der Implikation bzw.

quivalenz auf die wahre Subjunktion bzw.
Bijunktion hat zwei Vorteile:

2010

Es kann rechnerisch festgestellt werden, ob ein

Schluss logisch gltig ist: nmlich genau dann,
wenn die Sub-/Bijunktion eine Tautologie ist (d.
h. bei allen Kombinationen der Eingangsvariablen
A, B, C, nur wahr als Ergebnis herauskommt);
vor allem kann dadurch auch ermittelt werden,
ob ein Schluss logisch ungltig ist.
Jrgen Reischer

52

Aussagenlogische Schlsse

Beispiel:

Es soll die Gltigkeit des Schlusses

(A B) A B nachgewiesen werden:
A
f
f
w
w

B
f
w
f
w

AB
f
w
w
w

A
w
w
f
f

(A B) A
f
w
f
f

[(A B) A] B
w
w
w
w

Da aus allen Belegungen von A und B w resultiert,

handelt es sich um eine Tautologie und damit um
einen gltigen Schluss.
2010

Jrgen Reischer

53

Aussagenlogische Schlsse

Alltagssprachliches Beispiel fr diesen

Schluss:

Aussagen:

A = "Anna ist in der Arbeit.";

B = "Anna ist zu Hause.".

Schluss:
P1 "Anna ist in der Arbeit oder zu Hause."
P2 "Anna ist nicht in der Arbeit."
Q "Anna ist zu Hause."
(P = Prmisse[n], Q = Konklusion)

2010

Jrgen Reischer

AB
A

B
Modus tollendo ponens
54

Aussagenlogische Schlsse

Beispiel:

Es soll die Gltigkeit des Schlusses

(A B) A B nachgewiesen werden:
A
f
f
w
w

B
f
w
f
w

AB A
w
f
w
f
f
w
w
w

(A B) A
f
f
f
w

[(A B) A] B
w
w
w
w

Da aus allen Belegungen von A und B w resultiert,

handelt es sich um eine Tautologie und damit um
einen gltigen Schluss.
2010

Jrgen Reischer

55

Aussagenlogische Schlsse

Alltagssprachliches Beispiel fr diesen

Schluss:

Aussagen:

A = "Anna arbeitet.";
B = "Anna verdient Geld.".

Schluss:
P1 "Wenn Anna arbeitet, verdient sie Geld." A B
P2 "Anna arbeitet."
A
Q "Anna verdient Geld."
(P = Prmisse[n], Q = Konklusion)

2010

Jrgen Reischer

B
Modus ponendo ponens
56

Aussagenlogische Schlsse

Beispiel:

Es soll die Gltigkeit des Schlusses

(A B) B A nachgewiesen werden:
A
f
f
w
w

B
f
w
f
w

A B B
w
w
w
f
f
w
w
f

(A B) B
w
f
f
f

A
w
w
f
f

[(A B) B] A
w
w
w
w

Da aus allen Belegungen von A und B w resultiert,

handelt es sich um eine Tautologie und damit um
einen gltigen Schluss.
2010

Jrgen Reischer

57

Aussagenlogische Schlsse

Alltagssprachliches Beispiel fr diesen

Schluss:

Aussagen:

A = "Anna arbeitet.";
B = "Anna verdient Geld.".

Schluss:
P1 "Wenn Anna arbeitet, verdient sie Geld." A B
P2 "Anna verdient kein Geld."
B
Q "Anna arbeitet nicht."
(P = Prmisse[n], Q = Konklusion)

2010

Jrgen Reischer

A
Modus tollendo tollens
58

Aussagenlogische Schlsse

Beispiel:

Es soll die Gltigkeit des Schlusses

(A B) (B C) (A C) nachgewiesen werden:
A
f
f
f
f
w
w
w
w

B
f
f
w
w
f
f
w
w

C
f
w
f
w
f
w
f
w

AB
w
w
w
w
f
f
w
w

BC
w
w
f
w
w
w
f
w

(A B) (B C) A C
w
w
w
w
f
w
w
w
f
f
f
w
f
f
w
w

[(A B) (B C)] (A C)
w
w
w
w
w
w
w
w

Da aus allen Belegungen von A, B und C w resultiert, handelt es

sich um eine Tautologie und damit um einen gltigen Schluss.
2010

Jrgen Reischer

59

Aussagenlogische Schlsse

Alltagssprachliches Beispiel fr diesen

Schluss:

Aussagen:

A = "Anna arbeitet.";
B = "Anna verdient Geld.";
C = "Anna ist glcklich.".

Schluss:
P1 "Wenn Anna arbeitet, verdient sie Geld."
AB
P2 "Wenn Anna Geld verdient, ist sie glcklich."
BC
Q "Wenn Anna arbeitet, ist sie glcklich."
AC
(P = Prmisse[n], Q = Konklusion)
Modus barbara

2010

Jrgen Reischer

60

Aussagenlogische Schlsse

Gltige Schluss-Schemata sind generell so

konstruiert bzw. zu konstruieren, dass
Folgendes gilt:
Die Prmissen mssen wahr werden knnen; sie
drfen aber durchaus auch falsch sein, ohne dass
der Schluss gleich ungltig wird.

Wenn die Prmissen aber tatschlich wahr sind,
dann muss auch notwendig eine wahre Konklusion
folgen.
 Schlsse wie w f oder (Aw)
(B
B) f
A
B
bzw. f w oder A
A A
A sind damit von
vorneherein ungltig bzw. unsinnig.

2010

Jrgen Reischer

61

Aussagenlogische Schlsse

Die Schluss-Schemata sind wiederum rein formal

definiert, d. h.

2010

es kommt nicht auf die konkreten Aussagen und deren Inhalte

an, die fr A, B, C usw. eingesetzt werden;
sie sind gltig allein aufgrund ihrer formalen Struktur
(logischen Form), das es sich aus aussagenlogischer
Perspektive um Tautologien handelt (so wie A A).

Genau genommen wird auch keine neue Aussage

erschlossen, sondern eine implizit ("implicare") in den
Prmissen eingeschlossene Aussage explizit gemacht
(Tautologien sind uninformativ, d. h. erzeugen keine
neue Information, die nicht schon vorher latent in den
Prmissen vorhanden war).
Jrgen Reischer

62

Aussagenlogische Schlsse

Beispiel fr die inhaltliche Ignoranz eines

formalen Schluss-Schemas und das implizite
Vorhandensein der explizierten Aussage:

Eine Person befindet sich auf einer Party, auf der

hochgelehrte Gesprche stattfinden. Sie stellt die
zwei folgenden berlegungen an:

berlegung 1:
Ich kann mich am Gesprch beteiligen oder nicht.

Wenn ich es tue, wird man mich fr dumm halten.

Wenn ich es nicht tue, hlt man mich fr arrogant.

Folglich werden sie mich fr dumm oder arrogant halten.
 (G G) (G D) (G A) D A.

2010

Jrgen Reischer

63

Aussagenlogische Schlsse

berlegung 2:
Sie halten mich fr dumm oder arrogant (aus
berlegung 1).

Wenn man mich fr dumm hlt, werde ich nicht
wieder eingeladen.

Wenn man mich fr arrogant hlt, werde ich auch
nicht wieder eingeladen.

Also werde ich auf jeden Fall nicht wieder
eingeladen.
 (D A) (D E) (A E) E.

 Formal sind beide Schlsse gltig, aber: Wenn

eine der Prmissen falsch ist, kann auch die
Konklusion falsch sein!
2010

Jrgen Reischer

64

Aussagenlogische Schlsse
 Hierdurch wird zweierlei deutlich:

2010

Der Schluss ist zwar logisch formal zwingend, sobald

jedoch eine der Prmissen falsch ist, kann auch die
Konklusion falsch werden, d. h. die logische Gltigkeit
eines Schlusses ist nicht hinreichend fr seine inhaltliche
Korrektheit (gewhrleistet ist nur, dass aus Wahrem
Wahres folgt).
Stellt die Person fest, dass die Prmissen tatschlich alle
wahr sind, so ist die Konklusion notwendigerweise wahr.
In die Prmissen (D E) (A E) ist aber schon
eingearbeitet, dass die Person in jedem Falle nicht mehr
eingeladen wird, egal was sie tut. Der Schluss muss
ausdrcklich eigentlich gar nicht mehr gezogen werden.
Jrgen Reischer

65

Aussagenlogische Schlsse

bungsaufgaben:

Weisen Sie durch Wertetabellen nach, dass die

folgenden Schlsse ungltig sind:

Versuchen Sie jeweils ein sprachliches Beispiel zu

finden, das den Fehlschluss deutlich macht.
Geben sie zu der/den folgenden Prmisse/n
jeweils gltige Konklusionen an:

2010

(A B) B A;
(A B) A B;

jeweils eine Prmisse: A A; A B; A B; A B;

jeweils zwei Prmissen: A B, B C; A B, B.
Jrgen Reischer

66

Aussagenlogische Schlsse

Prfen Sie die folgenden Schluss-Schemata auf

Gltigkeit (Prmissen links von '/' und durch
Kommata getrennt, Konklusion rechts von '/'
[Schluss-Strich]):
A B, A / B;

(A B), A / B;

(A B), B / A;

(A B), A / B;

(A B), A / B;

(A B), (C B) / (C A);

(A B), (A C), B / C.
 Hinweis: Schreiben Sie die Schlsse zunchst in eine
Implikation um.

2010

Jrgen Reischer

67

Aussagenlogische Schlsse

Prfen Sie die folgenden Aussagen mittels einer

Wertetabelle auf quivalenz:

2010

A f A;
A A A;
A A A;
A (A B) A;
A (A B) A;
A (B C) (A B) (A C);
A (B C) (A B) (A C);
(A B) A B;
(A B) A B.
Jrgen Reischer

68

Aussagenlogische Gesetze

2010

In der Aussagenlogik gelten algebraische

Gesetze, die eine Boolesche Algebra bilden.
Diese Gesetze (Axiome) sind als Tautologien
formuliert, d. h. sie sind immer wahr.
Die Gesetze knnen zur algebraischen
Umschreibung und/oder Vereinfachung
aussagenlogischer Terme verwendet werden.
Einige der Gesetze finden sich auch in der
Zahlenalgebra wieder.
Insgesamt existieren zehn Gesetze in jeweils
zwei oder drei Ausprgungen:
Jrgen Reischer

69

Aussagenlogische Gesetze

Kommutativgesetze:

A (B C) (A B) C
A (B C) (A B) C

(A);
(A).

Distributivgesetze:

2010

(K);
(K).

Assoziativgesetze:

ABBA
ABBA

A (B C) (A B) (A C)
A (B C) (A B) (A C)
Jrgen Reischer

(D);
(D).
70

Aussagenlogische Gesetze

Absorptionsgesetze:

A A f
A A w

(Kontradiktion)
(Tautologie)

(C);
(C).

Identittsgesetze:

2010

(S);
(S).

Komplementgesetze:

A (A B) A
A (A B) A

AwA
AfA

(I);
(I).
Jrgen Reischer

71

Aussagenlogische Gesetze

DeMorgan-Gesetze:

AAA
AAA

(P);
(P).

Dominanzgesetze:

2010

(M);
(M).

Idempotenzgesetze:

(A B) A B
(A B) A B

Aff
Aww

(O);
(O).
Jrgen Reischer

72

Aussagenlogische Gesetze

Negationsgesetze:

2010

(A) A
f w
w f

(N);
(Nf);
(Nw).

w bzw. f heien neutrale Elemente bezglich der

Konjunktion bzw. Disjunktion, da sich der Wert
von A nicht ndert (vgl. Identittsgesetze).
Dualittsprinzip: Vertauscht man in einem Gesetz
der Aussagenlogik und sowie w und f, so erhlt
man wieder ein Gesetz der Aussagenlogik.
Jrgen Reischer

73

Aussagenlogische Gesetze

Alternative Schreibweisen:

Aufgrund der hnlichkeit von Konjunktion und

Disjunktion mit Multiplikation und Addition wird
oftmals '' anstelle von '
' (bzw. gar kein Zeichen)
und '+' anstelle von '
' geschrieben.
Vergleiche die entsprechenden Wertetabellen
(0 = f, 1 = w):
| 0
0
0
1
0

2010

1
0
1

|+ 0
0
0
1
1
Jrgen Reischer

1
1
1|2
74

Aussagenlogische Gesetze

Beispiele fr algebraische Vereinfachung

eines aussagenlogischen Terms:

Es soll algebraisch ermittelt werden, wer

lgt und wer die Wahrheit sagt:
1) "Wenn Hans lgt, sagt Maria die Wahrheit.";
2) "Kurt lgt, wenn Hans die Wahrheit sagt.";
3) "Wenn Maria die Wahrheit sagt, dann sagen Kurt
und Hans beide zugleich die Wahrheit.".

Alle drei Bedingungen mssen zugleich

gelten.
2010

Jrgen Reischer

75

Aussagenlogische Gesetze
Lsungsansatz:
1) Aussagen formulieren:

H = "Hans lgt." bzw. "Hans sagt die Wahrheit.";

M = "Maria lgt." bzw. "Maria sagt die Wahrheit.";
K = "Kurt lgt." bzw. "Kurt sagt die Wahrheit.".

2) Formel aufstellen (Variante "H/M/K lgt."):

X = (H M) (H K) (M [K H])
Man beachte, welche Aussage tatschlich hinter dem
"Wenn" steht (Reihenfolge des "Wenn-Dann")!

3) Formel vereinfachen:
Man beachte, dass gilt: (A B) = A B!
2010

Jrgen Reischer

76

Aussagenlogische Gesetze
X = (H M) (H K) (M [K H]) =
(H M) (H K) (M [K H]) =
(H M) (H K) (M K
H) =
(H
H H
K M
H M
K) (M K
H) =
(H
H H
K M
H M
K) (M K
H) =
(f H
K M
H M
K) (M K
H) =
(f [H
K M
H M
K]) (M K
H) =
K M
H M
K]) (M K
H) =
([H
(H
K M
H M
K) (M K
H) =
H
K
M H
K
K
H M
H
M
M
H
K
H M
K
M M
K
K
H =

2010

Jrgen Reischer

(D)
(C)
(I)
(D)

77

Aussagenlogische Gesetze
H
K
M H
K
K
H M
H
M
M
H
K
H M
K
M M
K
K
H =
H
K
M H
K
K
H M
H
M
K
H M
K
M M
K
K
H =
M
H
H
K
M K
K
H
H M
M
H
H
H
M
K M
M
K K
K
M
H =
H
K
M f
[H
H] f
H
f
[M
K] f
[K] f
[M
H] =
H
K
M f f f f f =
H
K
M f f f f f =
H
K
M

2010

Jrgen Reischer

(K)

(O)

(I)

78

Aussagenlogische Gesetze
4) Ergebnis interpretieren:

"Hans sagt die Wahrheit."

"Kurt lgt."
"Maria lgt."

und
und

 Vergleicht man dieses Ergebnis mit den drei

Bedingungen, so ergibt sich kein Widerspruch
zu den Aussagen, d. h. die gefundene Lsung
ist korrekt.
 Die alternative Formel mit "H/M/K sagt die
Wahrheit." fhrt zum selben Ergebnis; hier sind
lediglich die Negationszeichen in der Formel
bei Schritt 2) umgekehrt verteilt.
2010

Jrgen Reischer

79

Aussagenlogische Gesetze

Beispiel fr den algebraischen Beweis des

'modus tollendo tollens':
[(A B) B] A =
[(A B) B] A =
[A
B B
B] A =
[A
B f] A =
[A
B]X AY =
[A
B]X AY =
[A B] A =
A A B =
wB=
w

2010

mit A B = A B
mit D
mit C
mit I
mit X Y = X Y
mit M
mit K
mit C
mit O
Jrgen Reischer

80

Aussagenlogische Gesetze

bungsaufgabe:

Lsen Sie folgende Textaufgaben, indem

Sie einen Ansatz aufstellen und algebraisch
vereinfachen:

Ermitteln Sie, wer zur Party eingeladen wird

und wer nicht:
1) "Wenn Christoph nicht eingeladen wird, dann wird
Anna eingeladen.";
2) "Wenn Berta eingeladen wird, dann auch Anna und
Christoph.";
3) "Anna und Berta oder Berta und Christoph werden
eingeladen.".

2010

Jrgen Reischer

81

Aussagenlogische Gesetze

Ermitteln Sie, wer zur Party eingeladen wird

und wer nicht:
1) "Anton oder Berta wird eingeladen.";
2) "Anton wird eingeladen und Christoph wird nicht
eingeladen.";
3) "Wenn Berta eingeladen wird, dann wird auch
Christoph eingeladen.".

Ermitteln Sie, wer Mathe liebt und wer nicht:

1) "Christian liebt Mathe, wenn Berta es hasst.";
2) "Weder Anton noch Christian lieben Mathe.";
3) "Berta oder Anton hasst Mathe.".

2010

Jrgen Reischer

82

Aussagenlogische Gesetze

Stellen Sie fr folgende Textaufgabe einen Ansatz auf und

berlegen Sie, ob er vereinfacht werden kann:
Ein Logiker wurde von einer Bande gefangen genommen. Der
Bandenchef verband ihm die Augen und setzte ihn in einen
verschlossenen Raum, in dem zwei Ksten standen. Er gab ihm die
folgenden Anweisungen:
"Ein Kasten enthlt den Schlssel zu diesem Raum, der andere eine
Giftschlange. Greife in einen der Ksten hinein, und wenn Du den
Schlssel findest, kannst Du ihn benutzen, um Dich zu befreien. Zu
Deiner Hilfe darfst Du meinem Diener eine einzige Frage stellen,
die mit 'ja' oder 'nein' zu beantworten ist. Er braucht jedoch nicht
die Wahrheit zu sagen. Er kann lgen, wenn er will."
Nach einem Augenblick der berlegung stellt der Logiker eine
Frage, greift in den Kasten mit dem Schlssel und verlsst den
Raum. Welche Frage stellte er, so dass er sicher sein konnte,
freizukommen?

2010

Jrgen Reischer

83

Aussagenlogische Gesetze

Vereinfachung aussagenlogischer Terme

mittels Karnaugh-Diagrammen:

2010

Fr Terme mit 2 bis 4 Variablen bietet sich eine

grafische Lsung zur Vereinfachung an;
hierzu werden zunchst Felder mit 22 (zwei
Variablen), 24 (drei Variablen) und 44 (vier
Variablen) Kstchen angelegt, die spter mit
Wahrheitswerten belegt werden;
jeder Variablen A, B, C, D wird ein eigener Bereich
auf dem Felderschema zugeordnet, so dass jedes
Feld eindeutig durch eine Variablenkombination
(negiert oder nicht) identifiziert werden kann:
Jrgen Reischer

84

Aussagenlogische Gesetze

Karnaugh-Diagramme fr zwei, drei und vier

Variablen:
A A
B
B

A A A A
B
B
C C C C

A A A A
B
B
B
B

D
D
D
D
C C C C

Karnaugh-Diagramme mit mehr Variablen wren

mglich, sie sind jedoch unbersichtlich.
2010

Jrgen Reischer

85

Aussagenlogische Gesetze

Ausgehend von einer Wertetabelle werden alle

erwnschten "Wahr"-Zustnde in das KarnaughDiagramm eingetragen:
A B C

2010

Dazu muss jeweils die DNF fr einen 'w'Eintrag gebildet werden, z. B. A

B
C
fr die 3. Zeile (erstes 'w' von oben);
davon ausgehend werden die 'w'-Werte
am entsprechenden
Kreuzungspunkt im
A A A A
Diagramm eingeB w
w w
tragen.
B w
Danach kann vereinC C C C
facht werden.
Jrgen Reischer

f
f
f
f
w
w
w
w

f
f
w
w
f
f
w
w

f
w
f
w
f
w
f
w

F
f
f
w
w
f
w
f
w
86

Aussagenlogische Gesetze

Prinzipien der Vereinfachung:

Es sind mglichst groe Gruppen von benachbarten 'w'Werten zusammenzufassen, so dass immer 1, 2, 4, 8 oder
16 'w'-Werte in einem rechteckigen Block vereinigt sind.
Dabei gilt, dass

2010

so groe Blcke wie mglich und dadurch so wenig Blcke

wie mglich gebildet werden;
sich Blcke berlappen drfen (je grer der Block, desto
weniger Variablen werden zu seiner Beschreibung bentigt)
und Blcke ber die Rnder hinaus auf die entgegengesetzte
Seite hineinreichen drfen (aber nicht diagonal);
alle 'w'-Werte mindestens einem Block zugehren mssen,
aber auch in beliebig vielen Blcken enthalten sein drfen.

Es kann durchaus mehrere gleichwertige Mglichkeiten

der Zusammenfassung geben, die allesamt minimale
Komplexitt aufweisen (d. h. krzestmglich sind).
Jrgen Reischer

87

Aussagenlogische Gesetze

Beispiele (erstes fr obiges Diagramm):

Die sich ergebenden zwei
Blcke lassen sich durch
A
B A
C beschreiben.
Sofern die Methode korrekt
angewendet wurde, kann der resultierende Term
nicht weiter vereinfacht werden.
Aus den drei Einzeltermen links, die
A A
durch A
B A
B A
B darstellbar
B w w
sind, ergibt sich schlielich nurmehr
B w
A B.
A A A A
B w
w w
B w
C C C C

2010

Jrgen Reischer

88

Aussagenlogische Gesetze

Beispiele fr korrekte Gruppierungen:

A A A A
B
w w w D
B w w
D
B w w
D
B
w w D
C C C C

Zwei Vierergruppen und eine

Zweiergruppe ergeben einen
krzestmglichen Term:
A
D A
D A
B
C
Alternativ mglich:
A
D A
D B
C
D

Bei vier Variablen gilt: Isolierte Einzelterme

bentigen vier konjungierte Variablen zur
Darstellung, Zweiergruppen drei, Vierergruppen
zwei und Achtergruppen eine.
2010

Jrgen Reischer

89

Aussagenlogische Gesetze

bungsaufgabe:
Erzeugen Sie zunchst eine Tabelle mit den
Binrwerten von 0 bis 15 (vier Binrstellen = vier
Variablen A bis D).
Markieren Sie alle Zeilen als 'w', in denen mindestens
zwei Einsen nebeneinander stehen.
Erzeugen Sie ein Karnaugh-Diagramm mit vier
Variablen und tragen sie alle markierten Zeilen als 'w'
ein, indem sie Einsen in der Zeile entsprechend als
A/B/C/D, Nullen als A/B/C/D interpretieren.
Stellen Sie anhand des Karnaugh-Diagramms einen
krzestmglichen Term auf. berlegen Sie, ob es
weitere krzeste Terme gibt.

2010

Jrgen Reischer

90