Mathematische Grundlagen

Aussagenlogik

 aufwärts

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

Syntax und Semantik

Ein Alphabet ist eine endliche Menge von Zeichen. Eine endliche Folge von irgendwelchen Zeichen ist ein Wort, und eine (endliche oder unendliche) Menge von irgendwelchen 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 unterscheiden zwischen den Wörtern als syntaktischen Konstrukten, also als bloßen Zeichenfolgen, 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 veranschaulichen, betrachten wir zunächst die uns wohlvertrauten 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 Grundrechenarten Addition und Multiplikation) lassen wir zunächst beiseite. Diese wird dann später getrennt hiervon durch Semantikregeln festgelegt.

Definition:  Ein arithmetischer Ausdruck ist eine Zeichenfolge, 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 Zeichenfolgen 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 Verknüpfungen zwischen Zahlen interpretiert werden. Die durch Verknüpfung von Zahlenwerten zustande kommenden Werte werden durch Verknüpfungstafeln definiert. Die Verknü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 entsprechende Verknüpfungstafel lässt sich für das Zeichen · angeben (kleines Einmaleins). Die Verknüpfung von mehrstelligen Zahlen wird durch bestimmte Rechenverfahren (schriftliches Addieren bzw. Multiplizieren) auf die Verknüpfung von einstelligen Zahlen zurückgefü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 Interpretation von Konstanten und Variablen als bestimmte Werte aus einer bestimmten Wertemenge M und von weiteren Zeichen als bestimmte Verknüpfungen zwischen Werten ist typisch für semantische Abbildungen. Häufig wird festgestellt, dass diese Art von semantischen Abbildungen Rückwirkungen 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 Verknüpfungstafel für + symmetrisch zur Hauptdiagonalen 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 entsprechende Vertauschungen durchgeführt werden. Es handelt sich um eine Gesetzmäßigkeit, die unabhängig von der Belegung mit Werten ist; diese wird als Kommutativgesetz bezeichnet.

Die Gesetzmäßigkeiten der Arithmetik umfassen die Assoziativgesetze der Addition und der Multiplikation, die Kommutativgesetze der Addition und der Multiplikation sowie das Distributivgesetz:

((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 Gesetzmäßigkeiten verleihen der Wertemenge M eine algebraische Struktur. Im dargestellten Beispiel ist diese Struktur ein sogenannter Semiring.

Präzedenzregeln und Assoziativität

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

(a + (3 · a))

vereinfacht sich so zu

a + 3 · a

Bei assoziativen Verknü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 Vorgehensweise 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 Zeichenfolge, 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 Zeichenfolgen 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 Wahrheitswerte false (falsch) und true (wahr) interpretiert werden und die Zeichen ¬,  oder  und  und  als logische Verknüpfungen. Die Variablen A, B, C, ... stellen wir uns als Aussagen vor; dies sind Sätze, denen sich ein Wahrheitsgehalt zuschreiben lässt, z.B. "Die Erde ist eine Scheibe" oder "1 + 1 = 2". Zunächst jedoch abstrahieren wir von konkreten Aussagen und deren Wahrheitsgehalt 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 Wahrheitswerten zustande kommenden Werte werden durch Verknüpfungstafeln definiert. Die Verknü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 zweistelligen Verknüpfungen für die beiden Werte 0 und 1 nur vier mögliche Wertekombinationen gibt, werden die Verknüpfungstafeln aus praktischen Gründen in folgender Form, als Wahrheitstafeln, dargestellt. Die Variablen A und B durchlaufen hierbei die möglichen Wertekombinationen.

 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 Verknüpfungstafeln bzw. den Wahrheitstafeln 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 Verknü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ückwirkungen auf die syntaktische Ebene. So lässt sich etwa mithilfe einer Wahrheitstafel die Gesetzmäßigkeit beweisen, dass (A oder B) stets denselben Wahrheitswert 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 entsprechende Vertauschungen durchgeführt werden. Es handelt sich um eine Gesetzmäßigkeit, die unabhängig von der Belegung mit Wahrheitswerten ist; diese wird als Kommutativgesetz bezeichnet.

Es gibt noch eine ganze Reihe von anderen Äquivalenzen, die sich mithilfe von Wahrheitstafeln ableiten lassen. Wir werden im Folgenden zahlreiche logische Äquivalenzen kennenlernen. Diese Äquivalenzen verleihen der Menge der Wahrheitswerte mit den Verknüpfungen ¬,  oder  und  und  eine algebraische Struktur. Es handelt sich um eine boolesche Algebra (nach G. Boolezur Person).

Präzedenzregeln und Assoziativität

Damit logische Formeln einfacher lesbar sind, wird eine Ausführungsrangfolge (Präzedenz) der Verknü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 Verknüpfungen ist die Reihenfolge der Auswertung unerheblich, daher können dort ebenfalls Klammern weggelassen werden. Da die Verknü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 Verknüpfungen eingeführt, die sich auf die bereits vorhandenen Verknüpfungen ¬,  oder  und  und  zurückführen lassen.

Definition:  Die logischen Verknüpfungen  →  (logische Implikation) und  ↔  (beiderseitige logische Implikation) werden wie folgt definiert:

A → B    kongruent    ¬A oder B

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

Die Wahrheitstafeln für diese Verknü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 Verknü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 Wahrheitswerten stets den Wert 1 (wahr) annimmt, heißt allgemeingültig oder eine Tautologie.

Eine Tautologie haben wir bereits indirekt kennengelernt: Logisch äquivalente Formeln lassen sich nämlich durch Verknüpfung mit  ↔  als Tautologie ausdrücken. Das Kommutativgesetz 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 beiderseitige Implikation  ↔  dieser Formeln nach sich zieht, verschwimmt ein wenig der Unterschied zwischen diesen Begriffen. Daher wird auch oft die beiderseitige 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 Kontraposition
es gilt A und (A → B) → B modus ponens
es gilt ¬A → 0 ↔ A reductio ad absurdum – Beweis durch Widerspruch
Schreibweise

In mathematischen 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 beispielsweise

A folgt B

anstelle von

Δ  es gilt  A → B

wobei Δ die Menge aller weiteren Voraussetzungen ist, die stillschweigend 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 Verknüpfungen an: ! bindet am stärksten, <-> bindet am schwächsten. Verknüpfungen gleicher Präzedenz werden von links nach rechts ausgewertet.

Aufgaben

Aufgabe 1:  Überprüfen Sie mithilfe von Wahrheitstafeln, welche der folgenden logischen Formeln allgemeingültig sind, d.h. Tautologien sind.

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

 

 Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 25.03.2014   Updated: 04.06.2018
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