Wissen: Aussagenlogik (Klassische Logik)

Autor: Dr. Volkmar Naumburger ❤️ Bedanken

Die mathematische Logik umfasst die vier Teilgebiete: Mengenlehre, Beweistheorie, Modelltheorie und Rekursionstheorie.

Mit Ausnahme der Modelltheorie, die den Rahmen dieses Skriptes sprengen würde, werden alle Teilgebiete der Logik wenigstens streifend behandelt. Nur so viel zur Modelltheorie: ihre Aufgabe es ist, für jedes (logische) Problem formal und methodologisch präzise ein konsistentes System, d.h. Modell zur Verfügung zu stellen.

Einführung Aussagenlogik

Eigentlich ist die Logik eine philosophische Disziplin. Sie befasst sich mit den Gesetzmäßigkeiten der Vernunft. Dabei sind es besonders zwei Fragen, die im Zentrum dieser Lehre stehen:

- die Entscheidbarkeit eines Problems, d.h. gibt es überhaupt eine sinnvolle Lösung, kann der Wahrheitsgehalt einer Aussage überprüft werden,

- die Kausalität, d.h. der Zusammenhang von Ursache und Wirkung.

Eine Schwierigkeit stellt die Formulierung der Gedanken in der Umgangssprache dar:

Der Satz „Sie kennen alle Mengen von der Schule her.“ kann bedeuten:

- Sie alle kennen die Mengen(lehre) seit Ihrer Schulzeit oder aber

- Sie kenne alle Mengen(typen) seit Ihrer Schulzeit.

Ebenso ungenau und teilweise falsch werden in der Umgangssprache die Begriffe und und oder verwendet. Größte Schwierigkeiten verursachen Sätze, in denen Negationen vorkommen:

„Sie ist nichts weniger als unschön!“ – Ist sie nun schön oder nicht????

Wegen der Unschärfe der Umgangssprache ist eine künstliche Sprache erforderlich, die auf wohlbegründeten und allgemein anerkannten Definitionen beruht. Dies leistet die mathematische oderformale Logik. Die Einheiten der formalen Logik sind Aussagen, also Feststellungen und Behauptungen, die wahr oder falsch sind. Da es in dieser Logik nur zwei Zustände, nämlich wahr oder falsch, gibt, wird diese Logik zweiwertig oder auch Boolesche Logik (BOOLE George, 1815-1864) genannt.

Es gibt auch mehrwertige Logiken. Die mehrwertige Logik befasst sich mit Zuständen, die nicht nur wahr oder falsch sind. Beispielhaft sei hier die Fuzzy Logik genannt, deren Zustände beliebig feingestufte Werte zwischen 0 und 1 sein können. Sie ist ebenso formalisiert wie die zweiwertige Logik, soll aber nicht Gegenstand dieser Vorlesung sein.

Die formale Logik stellt ein Kalkül für logische Schlussfolgerungen und Beweise dar. Mit diesem Kalkül werden die Ungenauigkeiten und Mehrdeutigkeiten der Umgangssprache beseitigt.

Ein Ziel der formalen Logik besteht darin, zu Aussagen zu gelangen (Aussagenlogik oder Prädikatenlogik).

Aussagen der Booleschen, d.h. zweiwertigen, Logik können nur wahr oder falsch sein.

In der Aussagenlogik werden Behauptungen in Gleichungen (oder auch Ungleichungen) formuliert. Die in einer solchen Gleichung verknüpften Aussagen werden durch Aussagenvariable A, B, C, ... ausgedrückt, deren Wahrheitswert zunächst noch offen ist. Die folgenden Überlegungen sollen anhand eines einfachen Beispiels transparent gemacht werden:

Beispiel 1:

Aussage A: Der Student ist fleißig.

Aussage B: Der Student ist pünktlich.

Beispiel 2:

Aussage A: x ist eine gerade natürliche Zahl.

Aussage B: y > 4.

Symbolik

Zunächst soll aber eine Einführung in die gebräuchlichsten logischen Operationszeichen erfolgen. Auch wenn ein Ziel der formalen Logik darin zu sehen ist, das Denken von den Mängeln der Umgangssprache zu befreien, werden hier dennoch für die Operationszeichen, die sog. Junktoren (lat. Aussagen), umgangssprachliche Interpretationen anzugeben. Eine Übersicht der Junktoren gibt folgende Tabelle:

Junktor Funktion Umgangssprachliche Interpretation
¬ Negation nicht
Konjunktion und
Disjunktion oder
Implikation wenn ..., dann ...
Äquivalenz wenn ..., dann ... und nur dann
| Sheffer-Strich nicht beide
Peirce-Funktion weder, noch

Wahrheitstafel

Um sich über die Bedeutung der Junktoren unmissverständlich austauschen zu können, werden deren Eigenschaften über Wahrheitstafeln definiert. In einer Wahrheitstafel werden allen an der Gleichung beteiligten Variablen die Werte für wahr oder falsch in vollständigen Kombinationen zugeordnet. In einer zeilenweisen Anordnung werden dann den jeweiligen Kombinationen die entsprechenden Ergebnisse gegenüber gestellt.

Zur Vereinfachung und aus Gründen der besseren Übersicht werden im folgenden die Wahrheitswerte wahr durch 1 und falsch durch 0 dargestellt.

Logische Operationen

Negation (¬)

Kehrt einen Wahrheitswert ins Gegenteil.

Wahrheitstafel:

A ¬A
1 0
0 1

Beispiel: A: x ist gerade.

¬A: x ist nicht gerade (also ungerade).

Die doppelte Verneinung führt auf den ursprünglichen Wert zurück: ¬(¬A) = A

Konjunktion (∧)

Variable, die durch den Junktor ∧ (UND) mit einander verknüpft sind, führen zu einer Aussage, die nur dann wahr ist, wenn beide Aussagen für sich wahr sind, sonst ist sie falsch.

Wahrheitstafel:

A B A∧B
1 1 1
0 1 0
1 0 0
0 0 0

Die Konjunktion wird auch aussagenlogisches Produkt genannt, und folglich werden die zu verknüpfenden Aussagen Faktoren genannt.

Beispiel 1:

Aussage A: Der Student ist fleißig.

Aussage B: Der Student ist pünktlich.

Die Aussage A∧B „Der Student, ist ein guter Student“ ist nur dann wahr, wenn der Student fleißig und pünktlich ist.

Beispiel 2:

Aussage A: x ist eine gerade natürliche Zahl.

Aussage B: y > 4.

Aussage A∧B: 6 8 10 12 …

Disjunktion (∨)

Variable, die durch den Junktor ∨ (ODER) mit einander verknüpft sind, führen zu einer Aussage, die nur dann wahr ist, wenn eine der beide Aussagen wahr ist oder wenn beide Aussagenwahr sind. Nur wenn beide Variablen den Wert falsch haben, ist die verknüpfte Aussage falsch.

Wahrheitstafel:

A B A∨B
1 1 1
0 1 1
1 0 1
0 0 0

Die Disjunktion wird auch aussagenlogische Summe genannt.

Beispiel 1:

Aussage A: Es regnet.

Aussage B: Der Himmel ist bedeckt.

Die Aussage ist richtig, wenn der Himmel bedeckt ist oder es regnet oder der Himmel ist bedeckt und es regnet. Die Aussage A∨B „Das Wetter ist schlecht“ ist nur dann falsch, wenn der Himmel nicht bedeckt (= wolkenlos) ist und es nicht regnet (= niederschlagsfrei).

Die letzte Aussage im Beispiel führt auf eine alternative Gleichung, nämlich die konjunktive Verknüpfung negierter Wahrheitswerte. Für disjunktive Verknüpfungen gibt es ähnliche Alternativen → Regeln von De Morgan.

Beispiel 2:

Aussage A: x ist eine gerade natürliche Zahl.

Aussage B: y > 4.

Aussage A ∨ B: 2 4 5 6 7 8 9 10 11 12 …

Implikation (⇒)

Die Implikation findet insbesondere in der Beweisführung Anwendung. Dabei wird die links vom Junktor stehende Aussage Voraussetzung und die rechtsstehende Schlussfolgerung genannt.

Eine Aussage A ⇒ B ist nur dann falsch, wenn A wahr und B falsch ist. Eine Aussage, die von einer falschen Voraussetzung A ausgeht und eine wahre Schlussfolgerung B hervorbringt, gilt der Implikation als richtig (auch unter falschen Vorraussetzungen kann man zu richtigen Schlussfolgerungen kommen!).

Die Implikation ist die Verknüpfung, die sich am weitesten von der umgangssprachlichen Logik entfernt. Deshalb ist die umgangssprachliche Übersetzung der Implikation in die Formulierung Aus A folgt B (oder wenn A, dann B), mit Vorsicht anzuwenden! Anstelle dessen wird die Formulierung A impliziert B zur Verwendung empfohlen.

Weitere gebräuchliche Formulierungen sind:

A ist hinreichend für B

B ist notwendig für A

Wahrheitstafel:

A B A⇒B ¬A ¬A∨B
1 1 1 0 1
0 1 1 1 1
1 0 0 0 0
0 0 1 1 1

Beispiel 1:

Die Aussage „Wenn Feuer ausbricht, dann gibt es dort Sauerstoff“ soll durch die Implikation ausgedrückt werden.

Aussage A: Feuer bricht aus

Aussage B: dort gibt es Sauerstoff

Die Aussage A ⇒ B ist richtig,

- wenn ein Feuer ausbricht und Sauerstoff vorhanden ist (das Vorhandensein von Sauerstoff ist für das Ausbrechen eines Feuers notwendig, also:

(B ist notwendig für A),

Hingegen ist das Ausbrechen eines Feuers hinreichend für die Existenz von Sauerstoff.

(A ist hinreichend für B).

- wenn kein Feuer ausbricht aber Sauerstoff vorhanden ist *),

- wenn kein Feuer ausbricht und kein Sauerstoff vorhanden ist.

Die Aussage ist nur falsch,

- wenn ein Feuer ausbricht und es gibt dort keinen Sauerstoff.

*) Dass Schlussfolgerung B trotz nicht erfüllter Voraussetzung A richtig ist, kann als ein nicht definierter Zustand verstanden werden: Wenn Sauerstoff vorhanden ist, bricht nicht zwingend ein Feuer aus. Auf jeden Fall ist die umgangssprachliche Interpretation von ⇒ mit „aus A folgt B“ nicht zweifelsfrei möglich. Im vorliegenden Beispiel ist die Formulierung „notwendig, aber nicht hinreichend“ geeigneter.

Beispiel 2:

Aussage A: x ist eine gerade natürliche Zahl.

Aussage B: y > 4.

Aussage A ⇒ B: 5 7 9 11 13 …

Aus der Definition für die Implikation folgt

A ⇒ B ist gleichwertig zu ¬A ⇒ ¬B und wird Kontraposition genannt. Diese ist nicht mit der Umkehrung B ⇒ A zu verwechseln.

Äquivalenz (⇔)

Die Aussage A ⇔ B ist eine zweiseitige Implikation:

\( A ⇔ B ≡ A ⇒ B ∧ B ⇒ A \) Gl. 1

Die umgangssprachliche Übersetzung der Äquivalenz ist der logischen Bedeutung sehr nahe: Aus A folgt B und umgekehrt oder wenn A, dann B und wenn nicht A, dann auch nicht B. Das Gegenteil der Äquivalenz ist die Antivalenz ¬(A ⇔ B).

Wahrheitstafel:

A B A ⇔ B ¬A ∨ B A ∨ ¬B (¬A ∨ B) ∧ (A ∨ ¬B)
1 1 1 1 1 1
0 1 0 1 0 0
1 0 0 0 1 0
0 0 1 1 1 1

Äquivalenz – Antivalenz

Wahrheitstafel:

A B A ⇔ B ¬(A ⇔ B)
1 1 1 0
0 1 0 1
1 0 0 1
0 0 1 0

Beispiel 1:

Aussage A: Es regnet.

Aussage B: Der Himmel ist bedeckt.

Die Aussage A ⇔ B ist wahr,

- wenn der Himmel bedeckt ist und es regnet,

- wenn der Himmel nicht bedeckt ist und es auch nicht regnet.

Die Aussage ist falsch,

- wenn der Himmel bedeckt ist und es regnet nicht,

- wenn der Himmel nicht bedeckt ist und es regnet.

Das ist doch schon eher logisch?

Beispiel 2:

Aussage A: x ist eine gerade natürliche Zahl.

Aussage B: y > 4.

Aussage A ⇔ B: 1 3 6 8 10 12 …

Sheffer-Symbol (|)

Variable, die durch den Junktor | mit einander verknüpft sind, führen zu einer Aussage, die nur dann falsch ist, wenn beide Aussagen für sich wahr sind, sonst ist sie wahr. Mit dem Sheffer-Symbol (H. M.Sheffer, 1883 - 1964) wird die negierte Konjunktion ausgedrückt. In der Schaltungslogik wird eine solche Operation NAND genannt.

Wahrheitstafel:

A B A|B ¬(A ∧ B)
1 1 0 0
0 1 1 1
1 0 1 1
0 0 1 1

Zu lesen als: „Nicht sowohl A als auch B.“

Peirce-Symbol (↓)

Variable, die durch den Junktor ↓ mit einander verknüpft sind, führen zu einer Aussage, die nur dann wahr ist, wenn beide Aussagen für sich falsch sind, in jedem anderen Fall ist siewahr. In der Schaltungslogik wird eine solche Operation NOR genannt.

Mit dem Peirce-Symbol (Charles Sanders PEIRCE, 1839 - 1914) wird die negierte Disjunktion ausgedrückt.

Wahrheitstafel:

A B A ↓ B ¬(A ∨ B)
1 1 0 0
0 1 0 0
1 0 0 0
0 0 1 1

Zu lesen als: „weder A noch B“.

Der Satz vom ausgeschlossenen Dritten

Es gibt logische Aussagen, die immer wahr sind, sog. Tautologien. Diese sind von grundlegender erkenntnistheoretischer Bedeutung. So sind Beweise, die sich selbst zur Grundlage nehmen, Tautologien.

Beispiel:

In seinen „Mathematischen Prinzipien der Naturlehre“ benutzte Isaac Newton (1642-1727) die Begriffe „absoluter Raum“ und „absolute Zeit“. Zur Definition der absoluten Zeit schrieb er: „Die absolute, wahre und mathematische Zeit verfließt an sich und vermöge ihrer Natur gleichförmig, und ohne Beziehung auf irgendeinen äußeren Gegenstand.“

„Die absolute Zeit verfließt gleichförmig“ ist eine tautologische Aussage. Denn wie könnte diese Aussage anders überprüft werden, als mit einer absoluten Uhr, deren Zeit „gleichförmig“ verfließt? Und wie könnte dann der gemessene Zeitverlauf anders als gleichförmig sein?

Eine Tautologie ist auch der Satz vom ausgeschlossenen Dritten in der zweiwertigen Logik:

Die Aussage A ∧ ¬A = ¬(A ∨ ¬A) ist immer falsch. Diese Aussage wird als Kontradiktion (Widerspruch) bezeichnet.

Sie besagt, es kommt nie vor, dass eine Aussage und deren Verneinung zugleich richtig sind.

Anders ausgedrückt lautet der Satz vom ausgeschlossenen Dritten:

Die Aussage A ∨ ¬A = ¬(A ∧ ¬A) ist immer wahr.

De Morgansche Regeln

Wie schon angedeutet können logische Sachverhalte auch in verneinter Form ausgedrückt werden. Umgangssprachlich führen Negationen sehr häufig zu Missverständnissen. Hier sind die De Morganschen Regeln (Augustus De MORGAN, 1806-1871) sehr hilfreich bei der Auflösung solcher Konstrukte.

1. De Morgansche Regel

\( ¬(A ∧ B) ⇔ A | B ⇔ ¬A ∨ ¬B \) Gl. 2

A ¬A B ¬B A ∧ B ¬(A ∧ B) ¬A ∨ ¬B
1 0 1 0 1 0 0
0 1 1 0 0 1 1
1 0 0 1 0 1 1
0 1 0 1 0 1 1

Beispiel:

Aussage A: Es regnet.

Aussage B: Der Himmel ist bedeckt.

Die Aussage

„Es ist nicht wahr, dass es regnet und gleichzeitig der Himmel bedeckt ist“

ist äquivalent zu der Aussage

„Es regnet nicht oder der Himmel ist nicht bedeckt“!

2. De Morgansche Regel

\( ¬(A ∨ B) ⇔ A ↓ B ⇔ ¬A ∧ ¬B \) Gl. 3

A ¬A B ¬B A ∨ B ¬(A ∨ B) ¬A ∧ ¬B
1 0 1 0 1 0 0
0 1 1 0 1 0 0
1 0 0 1 1 0 0
0 1 0 1 0 1 1

Beispiel:

Aussage A: Es regnet.

Aussage B: Der Himmel ist bedeckt.

Die Aussage

„Es ist nicht wahr, dass es regnet oder der Himmel bedeckt ist“

ist äquivalent zu der Aussage

„Es regnet nicht und der Himmel ist nicht bedeckt“!

Die Regeln von De Morgan sind auch auf mehrfache Negationen anwendbar:

\( ¬¬(A ∧ B) ⇔ A ∧ B ⇔ ¬(¬A ∨ ¬B) \) Gl. 4

\( ¬¬(A ∨ B) ⇔ A ∨ B ⇔ ¬(¬A ∧ ¬B) \) Gl. 5

Verknüpfungsregeln

Kommutativgesetz

\( A ∨ B ⇔ B ∨ A ; \quad A ∧ B ⇔ B ∧ A \) Gl. 6

Assoziativgesetz

\( (A ∨ B) ∨ C ⇔ A ∨ (B ∨ C) ; \quad (A ∧ B) ∧ C ⇔ A ∧ (B ∧ C) \) Gl. 7

Distributivgesetz

\( A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C) ; \quad A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C) \) Gl. 8

Sonderfall: Computerlogik

Computer können nicht rechnen, sie tun nur so! Das Innenleben eines Prozessors besteht nur aus Speichern und logischen Gattern. Rechenoperationen müssen auf logische Operationen zurückgeführt werden.

Die Computerlogik ist auch eine zweiwertige Logik. Statt der Wahrheitswerte wahr und falsch, werden in einem Computerchip Ströme oder Spannungen ein- oder ausgeschaltet. In der englischsprachigen Literatur werden die beiden Zustände High (H) für ein, bzw. Low (L) für aus abgekürzt. Alle logischen Operationen, wie oben ausgeführt, werden mittels elektronischer Schaltungen (Gatter) ausgeführt.

Wie kann aber eine Berechnung, z.B. eine Addition, durch logische Funktionen ausgeführt werden? Zunächst sei angemerkt, dass im Computer nicht im Dezimal-, sondern im → Binärsystem gerechnet wird. Das heißt zum Beispiel, dass die dezimale 5 wird durch die binäre Zahl 101 (entspricht in logischen Termini H, L, H) ausgedrückt wird. Die Addition einer 3 (011) erfolgt so:

4. Stelle 3. Stelle 2. Stelle 1. Stelle
Wert 23 22 21 20
OP1: 5 0 1 0 1
OP2: 3 0 0 1 1
Übertrag 1 1 1
Summe 1 0 0 0

also gleich 8.

In logischer Schreibweise für die n-te Stelle:

\( \begin{align} Ü_n & = (OP1_{n-1} ∧ OP2_{n-1}) ∨ (OP1_{n-1} ∧ Ü_{n-1}) ∨ (OP2_{n-1} ∧ Ü_{n-1}); \quad Ü_1 = 0 \quad n ∈ \mathbb{N} \\ & = (OP1_{n-1} ∧ OP2_{n-1}) ∨ (OP1_{n-1} ∨ OP2_{n-1}) ∧ Ü_{n-1} \end{align} \)

\( S_n = ¬(¬(OP1_n ⇔ OP2_n) ⇔ Ü_{n-1}) \)

Wahrheitstafeln für

- Übertrag

OP1n-1 OP2n-1 Ün-1 (OP1n-1 ∧ OP2n-1) (OP1n-1 ∨ OP2n-1) ∧ Ün-1 Ün
L L L L L L
L (H) H (L) L L L L
H H L H L H
L L H L L L
L (H) H (L) H L H H
H H H H H H

- Summe

OP1n-1 OP2n-1 Ün-1 (OP1n-1 ⇔ OP2n-1) ¬ ¬(OP1n-1 ⇔ OP2n-1) ⇔ Ün-1 Sn
L L L H L H L
L (H) H (L) L L H L H
H H L H L H L
L L H H L L H
L (H) H (L) H L H H L
H H H H L L H

Eine logische Schaltung, die beide Operation ausführt, wird ADDER genannt.

Für fast jede logische Operation gibt es äquivalente elektronische Schaltungen:

Logische Funktion Operation Elektronisches Äquivalent
Negation ¬A Negator
Konjunktion A ∧ B AND
Disjunktion A ∨ B OR
Antivalenz ¬(A ⇔ B) XOR
Sheffer-Symbol A|B NAND
Peirce-Symbol A↓B NOR

Aus technologischer Sicht sind viele unterschiedliche Gatter-Typen nicht erwünscht, weil jeder Typ besondere Prozessschritte bei der Herstellung logischer Schaltkreise erfordert. Darum steht die Aufgabe, die Zahl der unterschiedlichen Gatter-Typen auf das absolut notwendige zu beschränken. In der Praxis genügen zwei Typen: den Negator und das NAND (bzw. Negator und NOR). Dank der Regeln von De Morgan können alle anderen Operationen auf diese beiden Grundschaltungen zurückgeführt werden.

  Schreib uns deine Hinweise