Mathematische Grundlagen

Aussagenlogik

 aufwärts

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­reihen, 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.

Definition:  Ein arithmetischer Ausdruck ist eine Zeichenreihe, die sich nach folgenden Regeln erzeugen lässt:

  • die Variablen a, b, c, ... sind arithmetische Ausdrücke;
  • die Konstanten 0, 1, 2, 3, 4, 5, ... sind arithmetische Ausdrücke;
  • sind X und Y arithmetische Ausdrücke, so sind auch (X + Y) und (X · Y) arithmetische Ausdrücke.

Beispiel:  Folgende Zeichen­reihen sind arithmetische Ausdrücke:

a
3
(5 + 3)
(a + b)
(a + (3 · a))
(((1 + 2) + 3) + 4)

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 inter­pretiert 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:

 + 0123456789
00123456789
112345678910
2234567891011
33456789101112
445678910111213
5567891011121314
66789101112131415
778910111213141516
8891011121314151617
99101112131415161718
Bild 1: Verknüpfungstafel für die Addition

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 Zeichenreihe "(5 + 3)" die Zahl 8 zu.

Was aber ordnet die semantische Abbildung der Zeichenreihe "(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:

((X + Y) + Z)  =  (X + (Y + Z)) (Assoziativität)
((X · Y) · Z)  =  (X · (Y · Z)) 
(X + Y)  =  (Y + X) (Kommutativität)
(X · Y)  =  (Y · X) 
(X · (Y + Z))  =  ((X · Y) + (X · Z)) (Distributivität)

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.

Definition:  Eine logische Formel ist eine Zeichenreihe, die sich nach folgenden Regeln erzeugen lässt:

  • die Variablen A, B, C, ... sind logische Formeln;
  • die Konstanten 0 und 1 sind logische Formeln;
  • sind X und Y logische Formeln, so sind auch (¬X), (X oder Y) und (X und Y) logische Formeln.

Beispiel:  Folgende Zeichen­reihen sind logische Formeln:

A
0
(A und 0)
((A und 1) oder (¬A))
(((¬(A und 0)) oder Aoder ((¬Aund B))

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) inter­pretiert werden und die Zeichen ¬,  oder  und  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 ¬,  oder  und  und  sind im Folgenden angegeben:

 ¬ 
01
10
 
 oder 01
001
111
 
  und  01
000
101
Bild 2: Verknüpfungstafeln für logische Verknüpfungen

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.

 A  B (A oder B)
000
011
101
111
 
 A  B (A und B)
000
010
100
111
 
Bild 3: Wahrheitstafeln für das logische Oder und das logische Und

Aus den Ver­knüpfungstafeln bzw. den Wahrheits­tafeln lässt sich ablesen, dass (A oder B) genau dann wahr ist, also den Wert 1 annimmt, wenn A wahr ist oder B wahr ist (oder beide), und dass (A und 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 oder B) stets denselben Wahrheits­wert annimmt wie (B oder 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  kongruent  für die Bezeichnung von Äquivalenz benutzt:

(A oder B)  kongruent  (B oder A)

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

(X oder Y)  kongruent  (Y oder 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 ¬,  oder  und  und  eine algebraische Struktur. Es handelt sich um eine boolesche Algebra (nach G. Boolezur Person).

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  und  bindet stärker als  oder . Außerdem können äußerere Klammern weggelassen werden. Die logische Formel

((A und 1) oder (¬A))

vereinfacht sich so zu

A und 1  oder  ¬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  oder  und  und  assoziativ sind, vereinfacht sich die logische Formel

((A oder Boder C)

zu

A oder B oder 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 ¬,  oder  und  und  zurückführen lassen.

Definition:  Die logischen Ver­knüpfungen  →  (logische Implikation) und  ↔  (beider­seitige logische Implikation) werden wie folgt definiert:

A → B    kongruent    ¬A oder B

A ↔ B    kongruent    (A → B)  und  (B → A)

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

 A  B (A → B)
001
011
100
111
 
 A  B (A ↔ B)
001
010
100
111
 
Bild 4: Wahrheitstafeln für die Verknüpfungen  →  und  ↔ 

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

Definition:  Eine logische Formel, die immer wahr ist, die also unabhängig von der Belegung ihrer Variablen mit Wahrheits­werten stets den Wert 1 (wahr) annimmt, heißt allgemein­gültig oder eine Tautologie.

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  oder  lautet, als Tautologie formuliert, wie folgt. Um darzustellen, dass es sich um eine Tautologie handelt, wird das Zeichen es gilt verwendet:

es gilt   A oder B  ↔  B oder A

Aufgrund der Tatsache, dass die logische Äquivalenz  kongruent  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.

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

In mathe­matischen Beweisen verwenden wir die Zeichen folgt und genau dann wenn, 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 folgt B

anstelle von

Δ  es gilt  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.

(Java-Applet zur Prüfung von logischen Formeln)

Da die Zeichen  und ,  oder  usw. auf der Tastatur nicht vorhanden sind, werden für die Eingabe ersatzweise folgende Zeichen verwendet:
¬ !
 und  *
 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

Aufgabe 1:  Überprüfen Sie mithilfe von Wahrheits­tafeln, welche der folgenden logischen Formeln allgemein­gültig sind, d.h. Tautologien sind.

  1. A → A oder B
  2. A und B → A
  3. (A → B)  und  (A → C)  ↔  A → (B und C)
  4. A → B  ↔  B → A
  5. (A ↔ B)  →  (B ↔ A)

 

 Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.03.2014   Updated: 20.06.2016
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik