Mathematische Grundlagen

Die Sprache der formalen Logik ist eine der elementaren Grundlagen von Mathematik und Informatik. Im Folgenden betrachten wir die Aussagen­logik.

Syntax und Semantik

Ein Alphabet ist eine endliche Menge von Zeichen. Eine endliche Folge von irgend­welchen Zeichen ist ein Wort, und eine (endliche oder unendliche) Menge von irgend­welchen Wörten ist eine Sprache.

Interessant sind diejenigen Sprachen, deren Wörter nach bestimmten Regeln gebildet sind. Die Menge dieser Regeln wird als die Syntax der Sprache bezeichnet.

Meist wird mit den Wörtern der Sprache jeweils eine bestimmte Bedeutung verbunden. Es ist aber wichtig, zu unter­scheiden zwischen den Wörtern als syntaktischen Konstrukten, also als bloßen Zeichen­folgen, und den jeweiligen Bedeutungen, die ihnen beigemessen werden.

Die Menge der Regeln, nach denen den Wörtern einer Sprache ihre Bedeutung zugeordnet wird, heißt Semantik. Durch die Semantik wird eine Abbildung der Sprache in die Menge der möglichen Bedeutungen festgelegt. Diese Abbildung wird als semantische Abbildung bezeichnet.

Um die Begriffe Syntax und Semantik zu ver­anschaulichen, betrachten wir zunächst die uns wohl­vertrauten arithmetischen Ausdrücke.

Arithmetische Ausdrücke

Syntax

Wir geben zunächst die Syntaxregeln für den Aufbau einfacher arithmetischer Ausdrücke an. Die Bedeutung dieser Ausdrücke (Rechnen mit ganzen Zahlen in den Grund­rechenarten Addition und Multi­plikation) lassen wir zunächst beiseite. Diese wird dann später getrennt hiervon durch Semantik­regeln festgelegt.

Semantik

Die Bedeutung eines arithmetischen Ausdrucks ist der Wert, der herauskommt, wenn die Konstanten als ganze Zahlen und die Zeichen + und · als Ver­knüpfungen zwischen Zahlen interpretiert werden. Die durch Verknüpfung von Zahlenwerten zustande kommenden Werte werden durch Ver­knüpfungstafeln definiert. Die Ver­knüpfungstafel des Zeichens + für die einstelligen Zahlen ist im Folgenden angegeben:

Eine ent­sprechende Ver­knüpfungstafel lässt sich für das Zeichen · angeben (kleines Einmaleins). Die Verknüpfung von mehr­stelligen Zahlen wird durch bestimmte Rechen­verfahren (schrift­liches Addieren bzw. Multi­plizieren) auf die Verknüpfung von einstelligen Zahlen zurück­geführt.

Somit ergibt die Verknüpfung 5 + 3 zum Beispiel 8. Die semantische Abbildung ordnet hier also der Zeichenfolge "(5 + 3)" die Zahl 8 zu.

Was aber ordnet die semantische Abbildung der Zeichenfolge "(a + b)" für eine Zahl zu? Dies hängt davon ab, mit welchen Zahlenwerten die Variablen belegt werden. Eine Belegung ist eine Abbildung, die jeder Variablen einen Zahlenwert zuweist. Wird die Variable a mit dem Wert 17 belegt und die Variable b mit dem Wert 4, so ergibt sich als Bedeutung des Ausdrucks "(a + b)" der Wert 21. Wird die Variable a mit dem Wert 2 belegt, so ergibt "((a + 3) · a)" den Wert 10. Die Klammerung bestimmt hierbei die Reihenfolge der Auswertung.

Algebra

Die Inter­pretation von Konstanten und Variablen als bestimmte Werte aus einer bestimmten Wertemenge M und von weiteren Zeichen als bestimmte Ver­knüpfungen zwischen Werten ist typisch für semantische Abbildungen. Häufig wird festgestellt, dass diese Art von semantischen Abbildungen Rück­wirkungen auf die syntaktische Ebene hat.

So stellt sich etwa heraus, dass die semantische Abbildung arithmetischer Ausdrücke für den Ausdruck (a + b) bei jeder Belegung denselben Wert ergibt wie für den Ausdruck (b + a). Dies liegt daran, dass die Ver­knüpfungstafel für + symmetrisch zur Haupt­diagonalen ist. Ausdrücke, die bei jeder Belegung denselben Wert ergeben, werden als äquivalent bezeichnet. Bei arithmetischen Ausdrücken wird das Zeichen = für die Bezeichnung von Äquivalenz benutzt. Es gilt also

(a + b)  =  (b + a)

Dies hat zur Folge, dass auch für beliebige Ausdrücke X und Y gilt

(X + Y)  =  (Y + X)

Somit können bereits auf syntaktischer Ebene ent­sprechende Ver­tauschungen durchgeführt werden. Es handelt sich um eine Gesetz­mäßigkeit, die unabhängig von der Belegung mit Werten ist; diese wird als Kommutativ­gesetz bezeichnet.

Die Gesetz­mäßigkeiten der Arithmetik umfassen die Assoziativ­gesetze der Addition und der Multi­plikation, die Kommutativ­gesetze der Addition und der Multi­plikation sowie das Distributiv­gesetz:

Die vorhandenen Gesetz­mäßigkeiten verleihen der Wertemenge M eine algebraische Struktur. Im dar­gestellten Beispiel ist diese Struktur ein sogenannter Semiring.

Präzedenz­regeln und Assoziativität

Damit Ausdrücke einfacher lesbar sind, wird eine Ausführungs­rangfolge (Präzedenz) der Ver­knüpfungen eingeführt: Die Verknüpfung · bindet stärker als die Verknüpfung + (Punkt­rechnung geht vor Strich­rechnung). Außerdem können äußere Klammern weggelassen werden. Der Ausdruck

(a + (3 · a))

vereinfacht sich so zu

a + 3 · a

Bei assoziativen Ver­knüpfungen ist die Reihenfolge der Auswertung unerheblich, daher können dort ebenfalls Klammern weggelassen werden. Der Ausdruck

(((1 + 2) + 3) + 4)

vereinfacht sich so zu

1 + 2 + 3 + 4

Logische Formeln

Vollkommen analog zu der eben gesehenen Vorgehens­weise definieren wir zunächst die Syntax von logischen Formeln. Wir verleihen dann den logischen Formeln eine Bedeutung, indem wir eine semantische Abbildung definieren. Anschließend betrachten wir die algebraische Struktur logischer Formeln.

Syntax

Wir definieren nun, wie logische Formeln syntaktisch aufgebaut sein müssen – wiederum zunächst losgelöst von ihrer möglichen Bedeutung.

Semantik

Die Bedeutung einer logischen Formel ist der Wert, der herauskommt, wenn die Konstanten 0 und 1 als die Wahrheits­werte false (falsch) und true (wahr) interpretiert werden und die Zeichen ¬,  ∨  und  ∧  als logische Ver­knüpfungen. Die Variablen A, B, C, ... stellen wir uns als Aussagen vor; dies sind Sätze, denen sich ein Wahrheits­gehalt zuschreiben lässt, z.B. "Die Erde ist eine Scheibe" oder "1 + 1 = 2". Zunächst jedoch abstrahieren wir von konkreten Aussagen und deren Wahrheits­gehalt und betrachten Variablen lediglich als Platzhalter, die mit den Werten 0 (falsch) oder 1 (wahr) belegt werden können.

Die durch logische Verknüpfung von Wahrheits­werten zustande kommenden Werte werden durch Ver­knüpfungstafeln definiert. Die Ver­knüpfungstafeln der Zeichen ¬,  ∨  und  ∧  sind im Folgenden angegeben:

Da es bei zwei­stelligen Ver­knüpfungen für die beiden Werte 0 und 1 nur vier mögliche Werte­kombinationen gibt, werden die Ver­knüpfungstafeln aus praktischen Gründen in folgender Form, als Wahrheits­tafeln, dargestellt. Die Variablen A und B durchlaufen hierbei die möglichen Werte­kombinationen.

Aus den Ver­knüpfungstafeln bzw. den Wahrheits­tafeln lässt sich ablesen, dass (A ∨ B) genau dann wahr ist, also den Wert 1 annimmt, wenn A wahr ist oder B wahr ist (oder beide), und dass (A ∧ B) genau dann wahr ist, wenn A wahr ist und B wahr ist. Die Ver­knüpfungen heißen deshalb logisches Oder bzw. logisches Und. Die einstellige Verknüpfung ¬ heißt logisches Nicht oder logische Negation.

Algebra

Die semantische Abbildung hat Rück­wirkungen auf die syntaktische Ebene. So lässt sich etwa mithilfe einer Wahrheits­tafel die Gesetz­mäßigkeit beweisen, dass (A ∨ B) stets denselben Wahrheits­wert annimmt wie (B ∨ A). Logische Formeln, die bei jeder Belegung denselben Wert ergeben, werden als äquivalent bezeichnet. Diese beiden Formeln sind also logisch äquivalent. Bei logischen Formeln wird das Zeichen  ≡  für die Bezeichnung von Äquivalenz benutzt:

(A ∨ B)  ≡  (B ∨ A)

Dies hat zur Folge, dass auch für beliebige logische Formeln X und Y gilt:

(X ∨ Y)  ≡  (Y ∨ X).

Somit können bereits auf syntaktischer Ebene ent­sprechende Ver­tauschungen durchgeführt werden. Es handelt sich um eine Gesetz­mäßigkeit, die unabhängig von der Belegung mit Wahrheits­werten ist; diese wird als Kommutativ­gesetz bezeichnet.

Es gibt noch eine ganze Reihe von anderen Äquivalenzen, die sich mithilfe von Wahrheits­tafeln ableiten lassen. Wir werden im Folgenden zahlreiche logische Äquivalenzen kennenlernen. Diese Äquivalenzen verleihen der Menge der Wahrheits­werte mit den Ver­knüpfungen ¬,  ∨  und  ∧  eine algebraische Struktur. Es handelt sich um eine boolesche Algebra (nach G. Boole).

Präzedenz­regeln und Assoziativität

Damit logische Formeln einfacher lesbar sind, wird eine Ausführungs­rangfolge (Präzedenz) der Ver­knüpfungen eingeführt: Die Verknüpfung ¬ bindet am stärksten, und  ∧  bindet stärker als  ∨ . Außerdem können äußere Klammern weggelassen werden. Die logische Formel

((A ∧ 1) ∨ (¬A))

vereinfacht sich so zu

A ∧ 1  ∨  ¬A.

Bei assoziativen Ver­knüpfungen ist die Reihenfolge der Auswertung unerheblich, daher können dort ebenfalls Klammern weggelassen werden. Da die Ver­knüpfungen  ∨  und  ∧  assoziativ sind, vereinfacht sich die logische Formel

((A ∨ B) ∨ C)

zu

A ∨ B ∨ C.

Tautologie

Um bestimmte logische Formeln einfacher darstellen zu können, werden zwei weitere Ver­knüpfungen eingeführt, die sich auf die bereits vorhandenen Ver­knüpfungen ¬,  ∨  und  ∧  zurückführen lassen.

Die Wahrheits­tafeln für diese Ver­knüpfungen ergeben sich aus der Definition; sie sind im Folgenden angegeben:

Als Präzedenz der neuen Ver­knüpfungen wird festgelegt, dass  →  schwächer bindet als  ∨  und  ↔  am schwächsten bindet.

Eine Tautologie haben wir bereits indirekt kennen­gelernt: Logisch äquivalente Formeln lassen sich nämlich durch Verknüpfung mit  ↔  als Tautologie ausdrücken. Das Kommutativ­gesetz der logischen Verknüpfung  ∨  lautet, als Tautologie formuliert, wie folgt. Um darzustellen, dass es sich um eine Tautologie handelt, wird das Zeichen ⊨ verwendet:

⊨   A ∨ B  ↔  B ∨ A

Aufgrund der Tatsache, dass die logische Äquivalenz  ≡  von zwei Formeln X und Y die beider­seitige Implikation  ↔  dieser Formeln nach sich zieht, verschwimmt ein wenig der Unterschied zwischen diesen Begriffen. Daher wird auch oft die beider­seitige logische Implikation als logische Äquivalenz bezeichnet.

Es folgt eine Liste von Tautologien, also logischen Formeln, die immer wahr sind, ganz gleich, ob die enthaltenen Variablen wahr oder falsch sind. Diese Tautologien stellen die Gesetze der Logik dar. Die Gesetze der Logik sind die Grundlage für das logische Schließen in der Mathematik.

⊨		1				verum
⊨		¬0				non falsum
⊨		A ∨ ¬A				tertium non datur – ein Drittes gibt es nicht
⊨		¬¬A	↔	A		doppelte Negation
⊨		A ∨ A	↔	A		Idempotenz
⊨		A ∧ A	↔	A		Idempotenz
⊨		A ∨ B	↔	B ∨ A		Kommutativität
⊨		A ∧ B	↔	B ∧ A		Kommutativität
⊨		(A ∨ B) ∨ C	↔	A ∨ (B ∨ C)		Assoziativität
⊨		(A ∧ B) ∧ C	↔	A ∧ (B ∧ C)		Assoziativität
⊨		(A ∨ B) ∧ C	↔	(A ∧ C)  ∨  (B ∧ C)		Distributivität
⊨		(A ∧ B) ∨ C	↔	(A ∨ C)  ∧  (B ∨ C)		Distributivität
⊨		¬(A ∨ B)	↔	¬A ∧ ¬B		Regel von De Morgan
⊨		¬(A ∧ B)	↔	¬A ∨ ¬B		Regel von De Morgan
⊨		A → B	↔	¬A ∨ B		Definition von  →
⊨		A ↔ B	↔	(A → B) ∧ (B → A)		Definition von  ↔
⊨		A → B	↔	¬B → ¬A		Kontra­position
⊨		A ∧ (A → B)	→	B		modus ponens
⊨		¬A → 0	↔	A		reductio ad absurdum – Beweis durch Widerspruch

Schreibweise

In mathe­matischen Beweisen verwenden wir die Zeichen ⇒ und ⇔, um zulässige und korrekte Folgerungen bzw. Äquivalenzen auszudrücken. Hierbei handelt es sich um eine abkürzende Schreibweise. So schreiben wir beispiels­weise

A ⇒ B

anstelle von

Δ  ⊨  A → B

wobei Δ die Menge aller weiteren Voraus­setzungen ist, die still­schweigend mit einbezogen werden (z.B. die Gesetze der Arithmetik oder ähnliches).

Übung

Mit folgendem Programm lässt sich eine logische Formel mit den Variablen A, B und C sowie den logischen Konstanten 0 (= false) und 1 (= true) daraufhin überprüfen, ob sie eine Tautologie ist. Wenn die Formel keine Tautologie ist, wird eine Belegung der Variablen A, B und C ausgegeben, mit der die Formel den Wert false annimmt.

Tautologie oder nicht?

Da die Zeichen  ∧ ,  ∨  usw. auf der Tastatur nicht vorhanden sind, werden für die Eingabe ersatzweise folgende Zeichen verwendet:

¬		!
∧		*
∨		+
→		->
↔		=   oder  <->

Die Reihenfolge in dieser Tabelle gibt auch gleichzeitig die Präzedenz der Ver­knüpfungen an: ! bindet am stärksten, <-> bindet am schwächsten. Ver­knüpfungen gleicher Präzedenz werden von links nach rechts ausgewertet.

Aufgaben

Literatur

[Lan 21]   H.W. Lang: Vorkurs Informatik für Dummies. Wiley (2021)

Erste Schritte in der formalen Logik machen Sie auch in Kapitel 12 in meinem Buch Vorkurs Informatik für Dummies.

[Weitere Informationen]