1. Grundlagen


 

1.1 Mathematische Logik

 

1.1.1 Aussagen und Aussageformen

 

Mathematik ist das Aufstellen und Analysieren von Aussagen, wie zum Beispiel:

  • Die Zahl \( 3 \) ist eine Primzahl.
  • Die Zahl \( 4 \) ist eine Primzahl.
  • Es gibt unendlich viele Primzahlzwillinge.

Die erste Aussage ist richtig, die zweite falsch. Über den Wahrheitsgehalt der dritten Aussage köonnen wir nicht abschließend entscheiden, sind aber überzeugt, dass sie entweder wahr oder falsch ist.

 

Definition: Eine Aussage ist ein umgangssprachlicher Satz, der entweder wahr oder falsch ist.

 

Diese Definition beinhaltet die Zweiwertigkeit der Aussagenlogik. Außer wahr und falsch gibt keine weitere, dritte Möglichkeit.

 

Es gibt auch sprachliche Formulierungen, die keine Aussagen sind, da wir ihnen auf sinnvolle Weise keinen Wahrheitswert zuordnen können, wie Glückwünsche, Fragen oder Aufforderungen der folgenden Art:

  • Herzlichen Glückwunsch!
  • Wollen wir wetten?
  • Komm jetzt endlich!

Mathematische Ausdrücke, wie

  • \( x+7=28 \)
  • \( {\mathcal R}(0,3,1) \)

bezeichnen wir als Aussageformen. Sie werden zu Aussagen, nachdem wir einmal den „Platzhalter“ \( x \) durch eine Zahl substituieren und so \( x+7=28 \) zu einer wahren oder einer falschen Aussage machen, oder \( {\mathcal R}(x,y,z) \) beispielsweise als die Relation \( x\lt y\lt z \) interpretieren, was die Aussage \( {\mathcal R}(x,y,z) \) in unserem Beispiel falsch macht.

 

Aufgaben

 

Aufgabe 1.1.1: (Beispiele für Aussagen)

Welche der folgenden Sätze sind Aussagen, welche sind keine Aussagen?

(i) Berlin ist die Hauptstadt der Bundesrepublik Deutschland.
(ii) Alle Studenten sind fleißig.
(iii) Gestern hat es den ganzen Tag geregnet.
(iv) Reisen bildet.
(v) Hat die Vorlesung bereits begonnen?
(vi) Mathematik soll also schwer sein!

 

Lösung

 

(i) Es handelt sich um eine Aussage.
(ii) Es handelt sich um eine Aussage.
(iii) Es handelt sich um eine Aussage.
(iv) Es handelt sich um eine Aussage.
(v) Es handelt sich nicht um eine Aussage.
(vi) Es handelt sich nicht um eine Aussage.

 

Damit ist die Aufgabe gelöst.\( \qquad\Box \)

 

 

Aufgabe 1.1.2: (Eigene Beispiele für Aussagen)

Formulieren Sie wenigstens

(i) fünf eigene Beispiele für Aussagen,
(ii) fünf eigene Beispiele von Sätzen, die keine Aussagen sind.

 

Lösung

 

(i) Fünf Beispiele für Aussagen sind:
 
\( \circ \) Lesen bildet.
\( \circ \) Schwimmen ist gut für die Rückenmuskulatur.
\( \circ \) Mathematische Logik ist wichtig.
\( \circ \) Schokolade ist ungesund.
\( \circ \) Üben ist wichtig für das Verstehen.
(ii) Fünf Beispiele von Sätzen, die keine Aussagen sind:
 
\( \circ \) Gehen wir zusammen ins Kino?
\( \circ \) Das darf doch nicht wahr sein!
\( \circ \) Wann, wenn nicht jetzt?
\( \circ \) Mögen Sie Schumanns Klaviermusik?
\( \circ \) Lernen, lernen und nochmals lernen!

 

Das sind unsere geforderten Beispiele.\( \qquad\Box \)

 

 

Aufgabe 1.1.3: (Aussageformen)

Geben Sie jeweils ein Beispiel einer mathematischen Aussageform \( {\mathcal R}(x) \) mit einer, \( {\mathcal S}(x,y) \) mit zwei und \( {\mathcal T}(x,y,z) \) mit drei freien Variablen, so dass

(i) \( {\mathcal R}(6) \) wahr ist,
(ii) \( {\mathcal S}(1,7) \) wahr ist,
(iii) \( {\mathcal T}(1,3,12) \) wahr ist.

 

Lösung

 

(i) \( {\mathcal R}(x) \) sei die Aussageform \( x-6=0, \) dann ist \( {\mathcal R}(6) \) wahr.
(ii) \( {\mathcal S}(x,y) \) sei die Aussageform \( x\cdot y=7, \) dann ist \( {\mathcal S}(1,7) \) wahr.
(iii) \( {\mathcal T}(x,y,z) \) sei die Aussageform \( y=x+z, \) dann ist \( {\mathcal T}(1,13,12) \) wahr.

 

Das haben wir Aussageformen mit den geforderten Eigenschaften angegeben.\( \qquad\Box \)

 

 

Aufgabe 1.1.4: (Ungelöste Probleme der Mathematik)

Formulieren Sie als Aussagen je zwei

(i) ungelöste Probleme der Mathematik,
(ii) unmöglich lösbare Probleme der Mathematik.

 

Lösung

 

(i) Gibt es unendlich viele Primzahlzwillinge? Läßt sich jede gerade natürliche Zahl, die größer oder gleich \( 4 \) ist, als Summe zweier Primzahlen schreiben (Goldbachvermutung)?
(ii) Nicht möglich ist die Konstruktion eines zu einem gegebenen Kreis flächengleiches Quadrat in endlich vielen Schritten im Rahmen der elementaren Euklidischen Geometrie (Quadratur des Kreises). Nicht möglich ist auch ein Beweis Cantorschen Kontinuumshypothese, nach der es keine Menge gibt, deren Mächtigkeit echt größer ist als die der natürlichen Zahlen und echt kleiner als die der reellen Zahlen.

 

Das sind unsere geforderten Beispiele.\( \qquad\Box \)

 

 

Aufgabe 1.1.5: (Primzahlen und Primzahlzwillinge)

Erstellen Sie eine Liste aller Primzahlen kleiner oder gleich \( 300. \) Kennzeichnen Sie insbesondere alle in Ihrer Liste enthaltenen Primzahlzwillinge.

 

Lösung

 

Zunächst die Liste der Primzahlen:

 

2 3 5 7 11 13 17 19
23 29 31 37 41 43 47 53
59 61 67 71 73 79 83 89
97 101 103 107 109 113 127 131
137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223
227 229 233 239 241 251 257 263
269 271 277 281 283 293    

 

In der Liste finden sich die folgenden Primzahlzwillinge:

 

(2,3) (3,5) (5,7) (11,13)
(17,19) (29,31) (41,43) (59,61)
(71,73) (101,103) (107,109) (137,139)
(149,151) (179,181) (191,193) (197,199)
(227,229) (239,241) (269,271) (281,283)

 

Das sind die gesuchten Primzahlen und Primzahlzwillinge.\( \qquad\Box \)

 

 

Aufgabe 1.1.6: (Primzahldrillinge)

Zeigen Sie: Es ist \( (3,5,7) \) das einzig mögliche Beispiel eines Primzahldrillings, so dass also \( p, \) \( p+2 \) und \( p+4 \) mit \( p\ge 3 \) drei aufeinander folgende Primzahlen sind. Gehen Sie dabei wie folgt vor:

\( \circ \) Angenommen, \( (p,p+2,p+4) \) ist ein Primzahldrilling mit \( p\gt 3. \)
\( \circ \) Als Primzahl besitzt \( p \) nach Division durch \( 3 \) den Rest \( 1 \) oder \( 2. \)
\( \circ \) Welche Reste besitzen dann \( p+2 \) und \( p+4 \) nach Division durch \( 3? \)

Warum führt diese Argumentation im Fall \( p=3 \) nicht zum Widerspruch?

 

Lösung

 

Es sei \( (p,p+2,p+4) \) ein Primzahldrilling mit \( p\gt 3. \) Dann besitzt \( p \) nach Division durch \( 3 \) entweder den Rest \( 1 \) oder den Rest \( 2. \)

\( \circ \) Besitzt \( p \) nach Division durch \( 3 \) den Rest \( 1, \) so ist \( p+2 \) ohne Rest durch \( 3 \) teilbar und damit keine Primzahl. Das ist ein Widerspruch.
\( \circ \) Besitzt \( p \) nach Division durch \( 3 \) den Rest \( 2, \) so ist \( p+1 \) ohne Rest durch \( 3 \) teilbar und damit keine Primzahl. Das ist ebenfalls ein Widerspruch

Es kann also keinen Primzahldrilling \( (p,p+2,p+4) \) mit \( p\gt 3 \) geben. Andererseits wissen wir, dass \( (3,5,7) \) ein Primzahldrilling ist. Vorige Argumentation ist nicht anwendbar, da in diesem Fall \( p \) ohne Rest durch \( 3 \) teilbar ist.\( \qquad\Box \)

 

 


 

 

1.1.2 Logische Paradoxien

 

Ein umgangssprachlicher Satz kann grammatikalisch korrekt sein, inhaltlich aber eine logische Paradoxie darstellen. So kennt jeder das Beispiel

 

Dieser Satz ist falsch.

 

Ist nämlich dieser Satz wahr, so ist er nach seiner eigenen Behauptung falsch. Ist er aber falsch, so muss er mit derselben Begründung doch wahr sein.

 

Was stimmt aber nun?

 

Offenbar werden verschiedene Sprachebenen vermischt: Der Ausdruck dieser Satz

\( \circ \) bezieht sich einmal auf den umgangssprachlichen Satz Dieser Satz ist falsch,
\( \circ \) dann aber auch auf das Subjekt des Satzes Dieser Satz ist falsch.

 

Um Paradoxien dieser Art zu vermeiden, wird die Aussagenlogik zunächst auf

\( \circ \) axiomatische Art und Weise

d.h. rein formal, aufbauend auf endlich vielen Axiomen und Schlussregeln und ohne jede inhaltliche Interpretation formuliert. Aussagen werden dann allein vermittels der Axiome und Schlussregeln nach strengen Beweisregeln in neue Aussagen überführt.

 

Erst im zweiten Schritt wird dieser syntaktischen Form der Logik eine

\( \circ \) semantische Formulierung

gegenübergestellt. Hierunter versteht man beispielsweise eine Zuordnung von Aussagen und Aussagenverknüpfungen in die aus den beiden natürlichen Zahlen \( 0 \) und \( 1 \) bestehende Menge \( \{0,1\} \) oder in die Menge \( \{f,w\}, \) wobei \( 0 \) bzw. \( f \) für falsch und \( 1 \) bzw. \( w \) für wahr stehen.

 

Wahr und falsch sind also semantische Begriffe, denen innerhalb der Aussagenlogik die syntaktischen Begriffe beweisbar bzw. nicht beweisbar gegenüberstehen.

 

Im Folgenden diskutieren wir wichtige Aspekte der Semantik der Aussagenlogik, die für die mathematische Analysis wichtig sind. Daran anschließend geben wir einen ersten Einblick in die axiomatische Methode, da wir auch später mit verschiedenen Axiomensystemen zu arbeiten haben. Bei dieser Gelegenheit und nur aus historischem Interesse stellen wir verschiedene Axiomensysteme der Aussagenlogik dar.

 

Aufgaben

 

Aufgabe 1.2.1: (Die Lügnerparadoxie)

In dem Brief des Paulus an Titus (Der notwendige Kampf gegen Irrlehren) lesen wir (Zitat nach Wikipedia, Die freie Enzyklop\"adie, Seite "Paradoxon des Epimenides"):

Es hat einer von ihnen gesagt, ihr eigener Prophet: Die Kreter sind immer Lügner, böse Tiere und faule Bäche.

Im Jahre 1908 greift ➝ Russell (1908) dieses Zitat wieder auf:

The oldest contradiction of the kind in question is the Epimenides. Epimenides the Cretan said that all Cretans were liars, and all other statements made by Cretans were certainly lies. Was this a lie?

Das ist die Quelle einer der bekanntesten logischen Paradoxien: Alle Kreter lügen (siehe ➝ Zoglauer (2008)). Diskutieren Sie diese Paradoxie.

 


 

 

1.1.3 Verknüpfungen von Aussagen

 

 

 

Aufgaben

 


 

 

1.1.4 Aussagenlogische Beweisprinzipien

 

 

 

Aufgaben

 


 

 

1.1.5 Quantoren

 

 

 

Aufgaben

 


 

1.2 Die axiomatische Methode

 

1.3.1 Historische Axiomensysteme

 

Wir können - obwohl nicht in jedem Fall vorgesehen und eventuell als Theoreme zu beweisen - die Einsetzungsregel wie auch die Ersetzungsregel, also \[ \genfrac{}{}{1pt}{}{\varphi(a)}{\varphi[\psi/a]} \quad\mbox{bzw.}\quad \genfrac{}{}{1pt}{}{\varphi\leftrightarrow\psi}{\chi(\varphi)\leftrightarrow\chi[\psi/\varphi]}\,, \] jedem Axiomensystem als Schlussregeln zufügen.

 

Die Einsetzungsregel besagt: Ist \( \varphi(a) \) allgemeingültig, so auch \( \varphi[\psi/a], \) wobei \( \varphi[\psi/a] \) nach Einsetzen der Formel \( \psi \) an allen Stellen von \( a \) in \( \varphi(a) \) entsteht.

 

Die Ersetzungsregel besagt: Sind \( \varphi \) und \( \psi \) äquivalent, so auch \( \chi(\varphi) \) und \( \chi(\psi/\varphi) \) mit einer beliebigen Formel \( \chi, \) wobei \( \chi[\psi/\varphi] \) nach Ersetzen von \( \varphi \) durch \( \psi \) an einigen oder auch an allen Stellen, wo \( \varphi \) in \( \chi \) auftaucht, entsteht.

 

Das Axiomensystem von Frege 1879

 

Entnommen aus: ➝ Begriffsschrift (1879); siehe auch ➝ Begriffsschrift und andere Aufsätze (2014)

 

Axiome:

  1. \( \quad a\to(b\to a) \)
  2. \( \quad [c\to(b\to a)]\to[(c\to b)\to(c\to a)] \)
  3. \( \quad [c\to(b\to a)]\to[b\to(c\to a)] \)
  4. \( \quad (b\to a)\to(\neg a\to\neg b) \)
  5. \( \quad \neg\neg a\to a \)
  6. \( \quad a\to\neg\neg a \)

 

Das Axiomensystem von Russell und Whitehead 1910

 

Entnommen aus: ➝ Principia mathematica 1 (1910)

 

Axiome:

  1. \( \quad a\vee a\to a \)
  2. \( \quad b\to a\vee b \)
  3. \( \quad a\vee b\to b\vee a \)
  4. \( \quad a\vee(b\vee c)\to b\vee(a\vee c) \)
  5. \( \quad (b\to c)\to(a\vee b\to a\vee c) \)

 

Das Axiomensystem von Hilbert 1922

 

Entnommen aus: ➝ Die logischen Grundlagen der Mathematik (1922)

 

Axiome:

  1. \( \quad a\to(b\to a) \)
  2. \( \quad [a\to(a\to b)]\to(a\to b) \)
  3. \( \quad [a\to(b\to c)]\to[b\to(a\to c)] \)
  4. \( \quad (b\to c)\to[(a\to b)\to(a\to c)] \)
  5. \( \quad a\to(\neg a\to b) \)
  6. \( \quad (a\to b)\to[(\neg a\to b)\to b] \)

Schlussregel:

  1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

 

Das Axiomensystem von Ackermann und Hilbert 1928

 

Entnommen aus: ➝ Grundzüge der theoretischen Logik (1928)

 

Axiome:

  1. \( \quad a\vee a\to a \)
  2. \( \quad a\to a\vee b \)
  3. \( \quad a\vee b\to b\vee a \)
  4. \( \quad (a\to b)\to(c\vee a\to c\vee b) \)

Schlussregel:

  1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

 

Das Axiomensystem von Lukasiewicz und Tarski 1930

 

Entnommen aus: ➝ Untersuchungen über den Aussagenkalkül (1930); siehe auch ➝ J. Lukasiewicz: Elements of mathematical logic (1963)

 

Axiome:

  1. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
  2. \( \quad (\neg a\to a)\to a \)
  3. \( \quad a\to(\neg a\to b) \)

 

Das Axiomensystem von Bernays und Hilbert 1934

 

Entnommen aus: ➝ Grundlagen der Mathematik I (1934)

 

Axiome:

  1. \( \quad a\to(b\to a) \)
  2. \( \quad [a\to(a\to b)]\to(a\to b) \)
  3. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
  4. \( \quad a\wedge b\to a \)
  5. \( \quad a\wedge b\to b \)
  6. \( \quad (a\to b)\to[(a\to c)\to(a\to b\wedge c)] \)
  7. \( \quad a\to a\vee b \)
  8. \( \quad b\to a\vee b \)
  9. \( \quad (a\to c)\to[(b\to c)\to(a\vee b\to c)] \)
  10. \( \quad (a\leftrightarrow b)\to(a\to b) \)
  11. \( \quad (a\leftrightarrow b)\to(b\to a) \)
  12. \( \quad (a\to b)\to[(b\to a)\to(a\leftrightarrow b)] \)
  13. \( \quad (a\to b)\to(\neg b\to\neg a) \)
  14. \( \quad a\to\neg\neg a \)
  15. \( \quad \neg\neg a\to a \)

 

Das Axiomensystem von Rosser 1953

 

Entnommen aus: ➝ Logic for mathematicians (1953)

 

Axiome:

  1. \( \quad a\to(a\wedge a) \)
  2. \( \quad (a\wedge b)\to a \)
  3. \( \quad (a\to b)\to[\neg(b\wedge c)\to\neg(c\wedge a)] \)

Schlussregel:

  1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

 

Das Axiomensystem von Ackermann und Hilbert 1959, erste Variation

 

Entnommen aus: ➝ Grundzüge der theoretischen Logik (1959)

 

Axiome:

  1. alle Formeln
    • die aus einer Disjunktion \( a_1\vee\ldots\vee a_n \) bestehen, worin die \( a_i \) Aussagenvariablen oder negierte Aussagenvariablen sind
    • eine gewisse Aussagenvariable tritt einmal negiert und einmal unnegiert auf

Schlussregel:

  1. \(\displaystyle \quad\genfrac{}{}{1pt}{}{a\vee b\vee c}{a\vee \neg\neg b\vee c} \)
  2. \(\displaystyle \quad\genfrac{}{}{1pt}{}{a\vee\neg c\vee b,a\vee\neg d\vee b}{a\vee\neg(c\vee d)\vee b} \)

 

Das Axiomensystem von Lukasiewicz 1963

 

Entnommen aus: siehe auch ➝ J. Lukasiewicz: Elements of mathematical logic (1963)

 

Axiome:

  1. \( \quad (a\to b)\wedge(b\to c)\to(a\to c) \)
  2. \( \quad (\neg a\to a)\to a \)
  3. \( \quad a\to(\neg a\to b) \)

Schlussregel:

  1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

 

Das Axiomensystem von Lukasiewicz 1963, erste Variation

 

Entnommen aus: siehe auch ➝ J. Lukasiewicz: Elements of mathematical logic (1963)

 

Axiome:

  1. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
  2. \( \quad (\neg a\to b)\to[(b\to a)\to a] \)
  3. \( \quad a\to(\neg a\to b) \)

Schlussregel:

  1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

 

Das Axiomensystem von Lukasiewicz 1963, zweite Variation

 

Entnommen aus: siehe auch ➝ J. Lukasiewicz: Elements of mathematical logic (1963)

 

Axiome:

  1. \( \quad [(a\to b)\to c]\to(b\to c) \)
  2. \( \quad [(a\to b)\to c]\to(\neg a\to a) \)
  3. \( \quad (\neg a\to c)\to\{(b\to c)\to[(a\to b)\to c]\} \)

Schlussregel:

  1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

 

Das Axiomensystem von Kleene 1967

 

Entnommen aus: ➝ Mathematical logic (1967); siehe auch ➝ Mathematical logic (2013);

 

Axiome:

  1. \( \quad a\to(b\to a) \)
  2. \( \quad (a\to b)\to\{[a\to(b\to c)]\to(a\to c)\} \)
  3. \( \quad a\to(b\to a\wedge b) \)
  4. \( \quad a\wedge b\to a \)
  5. \( \quad a\wedge b\to b \)
  6. \( \quad a\to a\vee b \)
  7. \( \quad b\to a\vee b \)
  8. \( \quad (a\to c)\to[(b\to c)\to(a\vee b\to c)] \)
  9. \( \quad (a\to b)\to[(a\to\neg b)\to\neg a] \)
  10. \( \quad \neg\neg a\to a \)
  11. \( \quad (a\to b)\to[(b\to a)\to(a\leftrightarrow b)] \)
  12. \( \quad (a\leftrightarrow b)\to(a\to b) \)
  13. \( \quad (a\leftrightarrow b)\to(b\to a) \)

Schlussregel:

  1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

 

Das Axiomensystem von Tanaka 1967

 

Entnommen aus: ➝ On axiom systems of propositional logic XXV (1967)

 

Axiome:

  1. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
  2. \( \quad [(a\to b)\to a]\to a \)
  3. \( \quad a\to[(a\to b)\to b] \)

 

Das Axiomensystem von Mendelson 1997

 

Entnommen aus: ➝ Introduction to mathematical logic (4. Auflage, 1997)

 

Axiome:

  1. \( \quad a\to(b\to a) \)
  2. \( \quad a\to(b\to c)\to[(a\to b)\to(a\to c)] \)
  3. \( \quad (\neg b\to\neg a)\to[(\neg b\to a)\to b] \)

Schlussregel:

  1. Modus Ponens \(\quad\displaystyle \quad\genfrac{}{}{1pt}{}{a,\ a\to b}{a} \)

 

Aufgaben

 


 

1.3 Axiomensysteme der Aussagenlogik