Kurs:Vorkurs Mathematik (Osnabrück 2009)/Vorlesung 1/latex

\setcounter{section}{1}






\zwischenueberschrift{Aussagen}

Eine Aussage ist ein sprachliches Gebilde, das \stichwort {wahr} {} oder \stichwort {falsch} {} sein kann\zusatzfussnote {Statt \anfuehrung{wahr}{} sagt man auch, dass die Aussage \stichwort {gilt} {} oder dass sie \stichwort {richtig} {} ist, statt \anfuehrung{falsch}{} auch, dass sie nicht gilt.} {} {.} Dazu müssen die in der Aussage verwendeten Begriffe in ihrer Bedeutung klar definiert sein, damit Einigkeit darüber besteht, was damit gemeint ist, dass die Aussage wahr \zusatzklammer {oder eben falsch} {} {} ist. Es ist dabei durchaus erlaubt, dass man nicht entscheiden kann, ob die Aussage wahr oder falsch ist, weil man dazu Zusatzinformationen benötigt. Wichtig ist allein, dass die Prädikate wahr und falsch sinnvolle Prädikate des Gebildes aufgrund seiner syntaktischen und semantischen Gestalt sind.

Die Bedingung der Bedeutungsklarheit wird von natürlich-sprachlichen Aussagen selten erfüllt. Nehmen wir z.B. den Satz \einrueckung{Dieses Pferd ist schnell} Einerseits haben wir keine Information, um welches Pferd es sich handelt, von dem da die Rede ist, und die Gültigkeit der Aussage hängt vermutlich davon ab, welches Pferd gemeint ist. Andererseits ist die Bedeutung von \anfuehrung{schnell}{} nicht so fest umrissen, dass, selbst wenn es klar wäre, um welches Pferd es sich handelt, vermutlich Uneinigkeit herrscht, ob es als schnell gelten soll oder nicht.

In der natürlichen Sprache besteht die Möglichkeit, durch Zusatzinformationen, Kontextbezug, intersubjektive Vereinbarungen und kommunikative Bedeutungsangleichungen eine Gesprächssituation zu erzeugen, in der man über die Gültigkeit von solchen nicht scharf definierten Aussagen weitgehende Einigkeit erzielen kann. In der Logik und in der Mathematik hingegen sind diese praktischen Notlösungen nicht erlaubt, sondern die Bedeutung einer Aussage soll allein aus der Bedeutung der in ihr verwendeten Begriffe erschließbar sein, wobei diese Begriffe zuvor klar und unmissverständlich definiert worden sein müssen. Einige mathematischen Aussagen \zusatzklammer {egal ob wahr oder falsch} {} {} sind \einrueckung{ $5>3$ } \einrueckung{ $5<3$ } \einrueckung{5 ist eine natürliche Zahl} \einrueckung{Für jede natürliche Zahl gibt es eine größere Zahl} \einrueckung{Für jede natürliche Zahl gibt es eine kleinere Zahl} \einrueckung{Es gibt eine natürliche Zahl, die größer oder gleich jeder anderen natürlichen Zahl ist} \einrueckung{Es gibt eine natürliche Zahl, die kleiner oder gleich jeder anderen natürlichen Zahl ist} \einrueckung{Jede natürliche Zahl lässt sich als Produkt von Primzahlen darstellen} \einrueckung{Jede natürliche Zahl ist eine Primzahl} \einrueckung{Jede natürliche Zahl lässt sich als Summe von drei \zusatzklammer {natürlichen} {} {} Quadratzahlen darstellen} \einrueckung{Jede natürliche Zahl lässt sich als Summe von vier Quadratzahlen darstellen} \einrueckung{Jede natürliche Zahl lässt sich als Summe von beliebig vielen Quadratzahlen darstellen} \einrueckung{Es gibt eine natürliche Zahl, die sich als Summe von vier Quadratzahlen darstellen lässt, aber nicht als Summe von drei Quadratzahlen} \einrueckung{Jede gerade natürliche Zahl lässt sich als Summe von zwei Primzahlen darstellen} \einrueckung{Jede gerade natürliche Zahl $\geq 4$ lässt sich als Summe von zwei Primzahlen darstellen}

Wenn man diese Aussagen versteht, und insbesondere die in ihnen verwendeten Begriffe und Symbole kennt, so sieht man, dass es sich um Aussagen handelt, die entweder wahr oder falsch sind, und zwar unabhängig davon, ob der Leser weiß, ob sie wahr oder falsch sind. Es gibt darunter übrigens auch Aussagen, von denen niemand weiß, ob sie wahr oder falsch sind. Ob ein sprachliches Gebilde eine Aussage ist hängt eben nicht vom Wissen, ob sie wahr oder falsch ist, oder vom Aufwand ab, mit dem man durch zusätzliches Nachforschen, durch Experimente oder durch logisch-mathematisches Überlegen entscheiden könnte, ob sie wahr oder falsch ist. Bei den folgenden Beispielen handelt es sich zwar um mathematische Objekte, aber nicht um Aussagen: \einrueckung{5} \einrueckung{5+11} \einrueckung{Die Menge der Primzahlen} \einrueckung{$A \cap B$ } \einrueckung{Eine Summe von fünf Quadraten} \einrueckung{$\int_a^b f(t)dt$. }

Statt uns jetzt mit konkreten Aussagen auseinander zu setzen, nehmen wir im Folgenden den strukturellen Standpunkt ein, dass eine Aussage eine Aussagenvariable $p$ ist, die einen der beiden \stichwort {Wahrheitswerte} {} wahr oder falsch annehmen kann. Zunächst interessiert uns dann, wie sich diese Wahrheitsbelegungen bei einer Konstruktion von neuen Aussagen aus alten Aussagen verhalten.

\zwischenueberschrift{Verknüpfungen von Aussagen}

Man kann aus verschiedenen Aussagen neue Aussagen bilden. Aus der Aussage \einrueckung{Ich fresse einen Besen} kann man die \stichwort {negierte Aussage} {} \einrueckung{Ich fresse
\betonung{nicht}{} einen Besen\zusatzfussnote {Die sicherste Art, zur \stichwort {Negation} {} zu kommen, ist eine Konstruktion wie \anfuehrung{es ist nicht der Fall, dass ...}{} zu verwenden. Dies ist insbesondere beim anderen Beispielsatz zu bedenken, die Aussage \anfuehrung{Marsmenschen sind nicht grün}{} kann man so verstehen, dass alle Marsmenschen nicht-grün sind, oder dass eben nicht alle Marsmenschen grün, es also Ausnahmen gibt. Siehe auch den Abschnitt über Quantoren weiter unten} {.} {} } machen, und aus den beiden Aussagen \einrueckung{Marsmenschen sind grün} und \einrueckung{Ich fresse einen Besen} kann man beispielsweise die folgenden neuen Aussagen basteln \einrueckung{Marsmenschen sind grün
\betonung{und}{} ich fresse einen Besen} \einrueckung{Marsmenschen sind grün
\betonung{oder}{} ich fresse keinen Besen} \einrueckung{
\betonung{Wenn}{} Marsmenschen grün sind,
\betonung{dann}{} fresse ich einen Besen} \einrueckung{Wenn nicht gilt, dass Marsmenschen grün sind, dann fresse ich einen Besen} \einrueckung{Wenn Marsmenschen grün sind, dann fresse ich keinen Besen} \einrueckung{Wenn nicht gilt, dass Marsmenschen grün sind, dann fresse ich keinen Besen} \einrueckung{Marsmenschen sind
\betonung{genau dann}{} grün,
\betonung{wenn}{} ich einen Besen fresse}

Hierbei werden die einzelnen Aussagen für sich genommen nicht verändert \zusatzklammer {bis auf gewisse grammatische Anpassungen} {} {,} sondern lediglich in einen logischen Zusammenhang zueinander gebracht. Eine solche logische Verknüpfung ist dadurch gekennzeichnet, dass sich ihr Wahrheitsgehalt allein aus den Wahrheitsgehalten der beteiligten Aussagen und der Bedeutung der \stichwort {grammatischen Konjunktionen} {} \zusatzklammer {aussagenlogisch spricht man von \stichwort {Junktoren} {}} {} {} ergibt und keine weitere Information dafür erforderlich ist. Die Aussage \einrueckung{Marsmenschen sind grün und ich fresse keinen Besen} ist beispielsweise genau dann wahr, wenn sowohl Marsmenschen grün sind und ich keinen Besen fresse. Das ist jedenfalls die Bedeutung der logischen \anfuehrung{und}{-}Verknüpfung. Eine inhaltliche Beziehung zwischen den beiden Teilaussagen ist nicht nötig.

Betrachten wir zum Vergleich eine Aussage wie \einrueckung{Die grünen Marsmenschen fressen Besen} Hier entsteht eine völlig neue Aussage, die lediglich einzelne Vokabeln oder Prädikate der vorgegebenen Aussagen verwendet, ihr Wahrheitsgehalt lässt sich aber keineswegs aus den Wahrheitsgehalten der vorgegebenen Aussagen erschließen.

Eine logische Verknüpfung von Aussagen liegt vor, wenn sich der Wahrheitsgehalt der Gesamtaussage aus den Wahrheitsgehalten der Teilaussagen ergibt. Die beteiligten Verknüpfungen legen dabei fest, wie sich die Wahrheitswerte der Gesamtaussage bestimmen lassen.

\zwischenueberschrift{Aussagenvariablen und Junktoren}

Um diese Abhängigkeit allein von den einzelnen Wahrheitsgehalten und den Junktoren, nicht aber von den konkreten Aussagen und ihren Bedeutungen klarer zu machen, ist es sinnvoll, mit Aussagenvariablen zu arbeiten und die Junktoren durch Symbole zu repräsentieren. Für Aussagen schreiben wir jetzt
\mathdisp {p,q, \ldots} { , }
und wir interessieren und also nicht für den Gehalt von $p$, sondern lediglich für die möglichen Wahrheitswerte \zusatzklammer {oder \stichwort {Belegungen} {}} {} {} von $p$, die wir mit $w$ \zusatzklammer {wahr} {} {} oder $f$ \zusatzklammer {falsch} {} {} bezeichnen.\zusatzfussnote {Aussagen und ihre Verknüpfungen werden im Folgenden in einer formalen Sprache behandelt, die aus einer Menge an Aussagensymbolen $p,q, \ldots$, dem Negationszeichen $\neg$ und den Junktoren $\wedge, \vee, \rightarrow$ besteht. Dazu kommen die Klammern $(,)$, die es erlauben, ausgehend von den Aussagensymbolen mittels der Junktoren neue formale Aussagen zu bilden\zusatzklammer {die beiden Wahrheitswerten \mathkor {} {w} {und} {f} {} sind nicht Teil der Sprache, sondern die Wertemenge von Belegungsfunktionen, die auf den Aussagensymbolen erklärt werden können} {} {.} In dieser extrem reduzierten Sprache hat man eine klar definierte Menge von erlaubten formalen Aussagen. Sie dient dazu, aussagenlogische Sachverhalte deutlicher zu machen. Über diese Sprache sprechen wir in unserer gewöhnlichen Sprache, wobei man diese Ebenen stets auseinanderhalten muss. In diesem Zusammenhang nennt man eine formallogische Sprache auch \stichwort {Objektsprache} {} \zusatzklammer {weil sie das Objekt der Untersuchung ist} {} {} und die \zusatzklammer {natürliche} {} {} Sprache, in der die Untersuchung durchgeführt wird, \stichwort {Metasprache} {.}} {} {} Bei der \stichwort {Negation} {} werden einfach die Wahrheitswerte vertauscht, was man mit einer einfachen \stichwort {Wahrheitstabelle} {} ausdrückt: \wahrheitstabelleeins{Negation}{\neg p }{f}{w} Bei einer konkreten Aussage gibt es in der Regel mehrere sprachliche Möglichkeiten, die Negation zu formulieren. Um die Aussage \anfuehrung{ich fresse einen Besen}{} zu negieren, ist es egal, ob man sagt: \einrueckung{ich fresse nicht einen Besen} \einrueckung{ich fresse keinen Besen} \einrueckung{es ist nicht der Fall, dass ich einen Besen fresse} \einrueckung{es trifft nicht zu, dass ich einen Besen fresse}

Die Negation wirkt auf eine einzige Aussage, man spricht von einem \stichwort {einstelligen Operator} {.} Kommen wir nun zu \stichwort {mehrstelligen Operatoren} {,} die von mindestens zwei Aussagen abhängen. Bei der Verknüpfung von zwei Aussagen gibt es insgesamt vier mögliche Kombinationen der Wahrheitswerte, so dass jede logische Verknüpfung dadurch festgelegt ist, wie sie diesen vier Kombinationen einen Wahrheitswert zuordnet. Daher gibt es insgesamt $16$ logische Verknüpfungen, die wichtigsten sind die folgenden vier.

Die \stichwort {Konjunktion} {} ist die \stichwort {Und-Verknüpfung} {.} Sie ist genau dann wahr, wenn beide Teilaussagen wahr sind; sie ist also falsch, sobald nur eine der beteiligten Aussagen falsch ist. Die \stichwort {Wahrheitstabelle} {} der Konjunktion sieht so aus. \wahrheitstabellezweieins{Konjunktion} {\tabellenzeiledrei {$ p $} {$ q $} {$p \wedge q$} } {\tabellenzeiledrei {w} {w} {w} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {f} } {\tabellenzeiledrei {f} {f} {f} } Die \stichwort {Disjunktion} {} \zusatzklammer {oder \stichwort {Alternation} {}} {} {} ist die einschließende \stichwort {Oder-Verknüpfung} {.} Sie ist wahr sobald mindestens eine der Teilaussagen wahr ist, und insbesondere auch dann wahr, wenn beide Aussagen zugleich wahr sind. Sie ist nur in dem einzigen Fall falsch, dass beide Teilaussagen falsch sind. Offensichtlich sind bei einer Konjunktion und einer Disjunktion die beteiligten Teilaussagen gleichberechtigt. \wahrheitstabellezweieins{Disjunktion} {\tabellenzeiledrei {$ p $} {$ q $} {$p \vee q $} } {\tabellenzeiledrei {w} {w} {w} } {\tabellenzeiledrei {w} {f} {w} } {\tabellenzeiledrei {f} {w} {w} } {\tabellenzeiledrei {f} {f} {f} } Die \stichwort {Implikation} {} ist die in der Mathematik wichtigste Verknüpfung. Mathematische Sätze haben fast immer die Gestalt einer \zusatzklammer {verschachtelten} {} {} Implikation. Der logische Gehalt einer Implikation ist, dass aus der Gültigkeit einer \stichwort {Voraussetzung} {} die Gültigkeit einer \stichwort {Konklusion} {} folgt\zusatzfussnote {Genauer gesagt haben mathematische Sätze fast immer die Gestalt $p_1 \wedge p_2 \wedge \ldots \wedge p_n \rightarrow q$.} {} {.} Sie wird meistens durch \anfuehrung{Wenn $p$ wahr ist, dann ist auch $q$ wahr}{} ausgedrückt. Ihre Wahrheitsbedingung ist daher, dass wenn $p$ mit wahr belegt ist, dann muss auch $q$ mit wahr belegt sein. Dies ist erfüllt, wenn $p$ falsch ist oder wenn $q$ wahr ist\zusatzfussnote {An die Wahrheitsbelegung einer Implikation für den Fall, wo der Vordersatz falsch ist, muss man sich etwas gewöhnen. Der Punkt ist, dass wenn man eine Implikation $p \rightarrow q$ beweist, dass man dann $p$ als wahr annimmt und davon ausgehend zeigen muss, dass auch $q$ wahr ist. Der Fall, dass $p$ falsch ist, kommt also in einem Implikationsbeweis gar nicht explizit vor. In diesem Fall gilt die Implikation, obwohl sie keine \anfuehrung{Schlusskraft}{} besitzt. Nehmen wir als Beispiel die mathematische Aussage, dass wenn eine natürliche Zahl $n$ durch vier teilbar ist, dann ist sie gerade. Dies ist eine wahre Aussage für alle natürlichen Zahlen, sie gilt insbesondere auch für alle Zahlen, die
\betonung{nicht}{} durch vier teilbar sind. Es gibt auch jeweils für alle drei Wahrheitsbelegungen, die eine Implikation wahr machen, Beispiele von natürlichen Zahlen, die genau diese Wahrheitsbelegung repräsentieren, nicht aber für die vierte} {.} {.} Ihre Wahrheitstabelle ist daher \wahrheitstabellezweieins{Implikation} {\tabellenzeiledrei {$ p $} {$ q $} {$p \rightarrow q$} } {\tabellenzeiledrei {w} {w} {w} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {w} } {\tabellenzeiledrei {f} {f} {w} } Bei einer Implikation sind die beiden beteiligten Teilaussagen nicht gleichberechtigt, die Implikationen \mathkor {} {p \rightarrow q} {und} {q \rightarrow p} {} sind verschiedene Aussagen. Eine Implikation hat also eine \anfuehrung{Richtung}{}\zusatzfussnote {Bei einer Implikation $p \rightarrow q$ sagt man auch, dass $p$ eine \stichwort {hinreichende Bedingung} {} für $q$ und dass $q$ eine \stichwort {notwendige Bedingung} {} für $p$ ist. Siehe dazu auch die Wahrheitstabelle zur Kontraposition weiter unten.} {} {.} Im allgemeinen Gebrauch und auch in der Mathematik werden Implikationen zumeist dann verwendet, wenn der Vordersatz der Grund für die Konklusion ist, wenn die Implikation also einen kausalen Zusammenhang ausdrückt. Diese Interpretation spielt aber im aussagenlogischen Kontext keine Rolle.

Wenn die beiden Implikationen \mathkor {} {p \rightarrow q} {und} {q \rightarrow p} {} zugleich gelten, so wird das durch \anfuehrung{genau dann ist $p$ wahr, wenn $q$ wahr ist}{} ausgedrückt. Man spricht von einer \stichwort {Äquivalenz} {} der beiden Aussagen, die Wahrheitstabelle ist \wahrheitstabellezweieins{Äquivalenz} {\tabellenzeiledrei {$ p $} {$ q $} {$p \leftrightarrow q$} } {\tabellenzeiledrei {w} {w} {w} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {f} } {\tabellenzeiledrei {f} {f} {w} } Unter Verwendung der Negation kann man jede logische Verknüpfung durch die angeführten Verknüpfungen ausdrücken, wobei man noch nicht mal alle braucht. Z.B. kann man die Konjunktion \zusatzklammer {und ebenso die Implikation und die Äquivalenz} {} {} auf die Disjunktion zurückführen, die Wahrheitstabelle\zusatzfussnote {Im Folgenden verwenden wir, um Klammern zu sparen, die Konvention, dass die Negation stärker bindet als alle mehrstelligen Junktoren, und dass die Konjunktion stärker bindet als die anderen zweistelligen Junktoren.} {} {} \wahrheitstabellezweieins{Konjunktion als Disjunktion} {\tabellenzeiledrei {$ p $} {$ q $} {$\neg ( \neg p \vee \neg q) $} } {\tabellenzeiledrei {w} {w} {w} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {f} } {\tabellenzeiledrei {f} {f} {f} } zeigt nämlich, dass die Wahrheitsfunktion von
\mathl{\neg ( \neg p \vee \neg q)}{} mit der Wahrheitsfunktion von
\mathl{p \wedge q}{} übereinstimmt. Daher sind die beiden Ausdrücke logisch gleichwertig. Bei einem solchen nur leicht verschachtelten Ausdruck kann man die Wahrheitswerte noch einfach berechnen und damit die Wahrheitsgleichheit mit der Konjunktion feststellen. Bei komplizierteren \zusatzklammer {tiefer verschachtelten} {} {} Ausdrücken ist es sinnvoll, abhängig von den Belegungen der beteiligten Aussagenvariablen die Wahrheitswerte der Zwischenausdrücke zu berechnen. Im angegebenen Beispiel würde dies zur Tabelle \wahrheitstabellezweivier{Konjunktion als Disjunktion} {\tabellenzeilesechs {p} {q} {$\neg p $} {$ \neg q $} {$ \neg p \vee \neg q $} {$ \neg ( \neg p \vee \neg q) $} } {\tabellenzeilesechs {w} {w} { f} {f} { f} {w} } {\tabellenzeilesechs {w} {f} {f} {w} {w} {f} } {\tabellenzeilesechs {f} {w} {w} {f} {w} {f} } {\tabellenzeilesechs {f} {f} {w} {w} {w} {f} } führen. Natürlich kann man statt zwei auch beliebig viele Aussagenvariablen verwenden und daraus über die Verknüpfungen neue Aussagen konstruieren. Die Wahrheitsbelegung der zusammengesetzten Aussagen lassen sich dann ebenfalls in entsprechend größeren Wahrheitstabellen darstellen.

\zwischenueberschrift{Tautologien}

Bei Einzelaussagen und zusammengesetzten Aussagen ist jeder Wahrheitswert erlaubt, und die Wahrheitswerte bei den verknüpften Aussagen ergeben sich aus den Einzelbelegungen über die Wahrheitsregeln, die die Junktoren auszeichnen. Abhängig von den Belegungen können somit alle Aussagen wahr oder falsch sein. Besonders interessant sind aber solche Aussagen, die unabhängig von den Einzelbelegungen stets wahr sind. Solche Aussagen nennt man \stichwort {Tautologien} {.} Sie sind für die Mathematik vor allem deshalb wichtig, weil sie erlaubten Schlussweisen entsprechen, wie sie in Beweisen häufig vorkommen. Wenn man beispielsweise schon die beiden Aussagen \mathkor {} {p} {und} {p \rightarrow q} {} bewiesen hat, wobei hier \mathkor {} {p} {und} {q} {} für konkrete Aussagen stehen, so kann man daraus auf die Gültigkeit von $q$ schließen. Die zugrunde liegende aussagenlogische Tautologie ist
\mathdisp {(p \wedge ( p \rightarrow q)) \rightarrow q} { . }
Wie gesagt, eine Tautologie ist durch den konstanten Wahrheitswert wahr gekennzeichnet. Der Nachweis, dass eine gegebene Aussage eine Tautologie ist, verläuft am einfachsten über eine Wahrheitstabelle.

\wahrheitstabellezweidrei{\stichwort {Ableitungsregel} {} \zusatzklammer {\stichwort {Modus ponens} {}} {} {}} {\tabellenzeilefuenf {p} {q} {$ p \rightarrow q $} {$p \wedge ( p \rightarrow q) $} {$ (p \wedge ( p \rightarrow q)) \rightarrow q $} } {\tabellenzeilefuenf {w} {w} { w} {w} { w} } {\tabellenzeilefuenf {w} {f} {f} {f} {w} } {\tabellenzeilefuenf {f} {w} {w} {f} {w} } {\tabellenzeilefuenf {f} {f} {w} {f} {w} }

\wahrheitstabelleeinsdrei {Doppelnegation} { \tabellenzeilevier {p} {$ \neg p $} {$ \neg (\neg p) $} {$ p \leftrightarrow \neg ( \neg p) $} } { \tabellenzeilevier {w} {f} {w} { w} } { \tabellenzeilevier {f} {w } {f} {w} }

\wahrheitstabelleeinszwei{Tertium non datur}{ \neg p }{f}{w }{ p \vee \neg p }{w}{w} Die Regel \stichwort {Tertium non datur} {} geht auf Aristoteles zurück und besagt, dass eine Aussage \zusatzklammer {entweder} {} {} wahr oder falsch ist und es keine dritte Möglichkeit gibt. Die obige Regel drückt formal gesehen nur aus, dass mindestens ein Wahrheitswert gelten muss, die Regel davor sagt, dass $p$ wahr zugleich $\neg p$ wahr ausschließt, was man auch den \stichwort {Satz vom Widerspruch} {} nennt \zusatzklammer {zusammenfassend spricht man auch vom \stichwort {Bivalenzprinzip} {}} {} {.} Die Gültigkeit dieser Regeln ist bei vielen umgangssprachlichen Aussagen fragwürdig, im Rahmen der Aussagenlogik und der Mathematik haben sie aber uneingeschränkt Gültigkeit, was wiederum damit zusammenhängt, dass in diesen Gebieten nur solche Aussagen erlaubt sind, denen ein eindeutiger Wahrheitswert zukommt. Als Beweisprinzip schlägt sich dieses logische Prinzip als \stichwort {Beweis durch Fallunterscheidung} {} nieder, wobei die folgende Tautologie dieses Beweisprinzip noch deutlicher ausdrückt. \wahrheitstabellezweifuenf{Fallunterscheidung} {\tabellenzeilesieben { $ p $ } { $ q $ } {$ p \rightarrow q $} {$ \neg p $} {$ \neg p \rightarrow q $} {$((p \rightarrow q) \wedge ( \neg p \rightarrow q)) $} {$ ((p \rightarrow q) \wedge ( \neg p \rightarrow q)) \rightarrow q $} } {\tabellenzeilesieben {w} {w} { w} {f} { w} { w} { w} } {\tabellenzeilesieben {w} {f} {f} {f} {w} {f} {w} } {\tabellenzeilesieben {f} {w} {w} {w} {w} {w} {w} } {\tabellenzeilesieben {f} {f} {w} {w} {f } {f } {w } } Bei der Fallunterscheidung will man $q$ beweisen, und man beweist es dann einerseits \zusatzklammer {Fall 1} {} {} unter der zusätzlichen Annahme $p$ und andererseits \zusatzklammer {Fall 2} {} {} unter der zusätzlichen Annahme $\neg p$. Man muss dabei zweimal was machen, der Vorteil ist aber, dass die zusätzlichen Annahmen zusätzliche Methoden und Techniken erlauben.

Die \stichwort {Kontraposition} {} wird häufig in Beweisen verwendet, ohne dass dies immer explizit gemacht wird. In einem Beweis nimmt man einen pragmatischen Standpunkt ein, und manchmal ist es einfacher, von $\neg q$ nach $\neg p$ zu gelangen als von $p$ nach $q$. \wahrheitstabellezweifuenf{Kontraposition} {\tabellenzeilesieben { $ p $ } { $ q $ } {$ p \rightarrow q $} {$ \neg p $} {$ \neg q $} {$ \neg q \rightarrow \neg p $} {$ (p \rightarrow q) \leftrightarrow ( \neg q \rightarrow \neg p) $} } {\tabellenzeilesieben {w} {w} { w} {f} {f} { w} { w} } {\tabellenzeilesieben {w} {f} {f} {f} {w} {f} {w} } {\tabellenzeilesieben {f} {w} {w} {w} {f} {w} {w} } {\tabellenzeilesieben {f} {f} {w} {w} {w} {w } {w } }

Eine übersichtliche Möglichkeit, um die Wahheitsfunktionen von zusammengesetzten Aussagen darzustellen, bietet die \stichwort {disjunktive Normalform} {.} Bei zwei Aussagenvariablen \mathkor {} {p} {und} {q} {} gibt es vier mögliche Belegungen, wobei man jede von ihnen durch
\mathdisp {p \wedge q ,\, p \wedge \neg q , \, \neg p \wedge q, \, \neg p \wedge \neg q} { }
ausdrücken kann, und zwar in dem Sinne, dass die Konjunktion diejenige Belegung repräsentiert, bei der die Konjunktion wahr ist. Die vier elementaren oder atomaren Belegungsmöglichkeiten werden also durch vier Konjunktionen repräsentiert. Eine Aussage wie die Implikation
\mathl{p \rightarrow q}{} ist nur bei der Belegung
\mathl{p \wedge \neg q}{} falsch, bei den drei anderen Belegungen wahr. Daher ist die Implikation gleichwertig mit der Disjunktion der drei erlaubten Konjunktionen, also mit\zusatzfussnote {Diese Schreibweise beinhaltet implizit, dass die Konjunktion von mehr als drei Aussagen keine Klammerung bedarf, dass also die Aussagen $(p \vee q) \vee r$ und $p \vee ( q \vee r)$ äquivalent sind.} {} {}
\mathdisp {(p \wedge q) \vee ( \neg p \wedge q) \vee ( \neg p \wedge \neg q)} { . }
Einen solchen Ausdruck nennt man disjunktive Normalform, also eine Disjunktion von Konjunktionen, in denen nur die Aussagenvariablen und ihre Negation vorkommen. Im erwähnten Beispiel der Implikation liegt also eine Tautologie
\mathdisp {(p \rightarrow q) \leftrightarrow ((p \wedge q) \vee ( \neg p \wedge q) \vee ( \neg p \wedge \neg q))} { }
vor, und man kann zu jeder Aussageform einen dazu äquivalenten Ausdruck in disjunktiver Normalform angeben.

Die Negation von einer Tautologie\zusatzfussnote {Das bedeutet nicht, dass jede Aussage, die keine Tautologie ist, eine Kontradiktion sein muss, sondern dass die formale Negation einer formallogischen Tautologie eine Kontradiktion ist. Die Negation findet also innerhalb der Objektsprache statt, nicht auf der Metaebene.} {} {} ist eine \stichwort {Kontradiktion} {} \zusatzklammer {eine \stichwort {widersprüchliche Aussage} {}} {} {.} Sie ergibt bei jeder Belegung den Wahrheitswert falsch. Man spricht daher auch von unerfüllbaren Aussagen, da es keine Wahrheitsbelegung gibt, bei der eine Kontradiktion wahr wird.

\zwischenueberschrift{Quantoren}

Betrachten wir nochmal unsere beiden Beispielaussagen

\einrueckung{Marsmenschen sind grün} und \einrueckung{Ich fresse einen Besen,}

und schauen uns die innere Struktur genauer an. In der ersten Aussage wird einer gewissen Art von Lebewesen eine Eigenschaft zugesprochen, so wie wenn man sagt, dass Geparden schnell sind oder dass Faultiere faul sind. Damit kann man meinen, dass Marsmenschen \anfuehrung{im Normalfall}{} oder \anfuehrung{fast immer}{} grün sind, oder aber im strengeren Sinn, dass wirklich alle Marsmenschen grün sind. In der Mathematik interessiert man sich für Aussagen, die ohne Ausnahmen gelten \zusatzklammer {wobei man allerdings in einer mathematischen Aussage die Ausnahmen auch explizit machen kann} {} {,} so dass wir die Aussage im strengen Sinn verstehen wollen. Es handelt sich um eine sogenannte \stichwort {Allaussage} {.} In ihr kommen zwei \stichwort {Prädikate} {} \zusatzklammer {Eigenschaften, Attribute} {} {} vor, nämlich einerseits, ein Marsmensch zu sein, andererseits, grün zu sein. Ein Prädikat $P$ ist etwas, was einem Objekt \zusatzklammer {grammatisch spricht man von einem Subjekt} {} {,} einem Gegenstand, einem Element zukommen oder nicht zukommen kann. Ein Prädikat ist für sich genommen keine Aussage; aus einem Prädikat kann man aber grundsätzlich auf zwei verschiedene Arten eine Aussage machen, indem man nämlich einerseits \zusatzklammer {durch \stichwort {einsetzen} {}} {} {} für ein konkretes Objekt $a$ die Aussage
\mathdisp {P(a)} { }
bildet, die bedeutet, dass das Objekt $a$ die Eigenschaft $P$ besitzt, was wahr sein kann oder eben auch nicht. Andererseits kann man daraus durch \stichwort {Quantifizierung} {} eine Aussage gewinnen. So kann man die Aussage bilden, dass alle Objekte \zusatzklammer {typischerweise aus einer bestimmten Grundmenge} {} {} die Eigenschaft $P$ haben, was wiederum wahr oder falsch sein kann. Das drückt man formallogisch durch
\mathdisp {\forall x P(x)} { }
aus. Das Symbol
\mathdisp {\forall} { }
ist eine abkürzende Schreibweise für \anfuehrung{für alle}{,} und besitzt ansonsten keine tiefere Bedeutung. Es wird \stichwort {Allquantor} {} genannt. Die obige Marsmenschenaussage kann man als
\mathdisp {\forall x (M(x) \rightarrow G(x))} { }
schreiben. Das bedeutet, dass für alle Objekte ohne weitere Einschränkung gilt: wenn es sich um einen Marsmenschen handelt \zusatzklammer {wenn also $M$ zutrifft} {} {,} dann ist er auch grün. Für jedes $x$ steht in der großen Klammer eine Aussage in der Form einer Implikation, die eben besagt, dass wenn der Vordersatz wahr ist, dann auch der Nachsatz wahr sein muss.

Die zweite Beispielaussage kann bedeuten, dass ich genau einen Besen fresse oder aber mindestens einen Besen. Die Wortbedeutung des unbestimmten Artikels ist nicht eindeutig, in einer Aussage wie \anfuehrung{eine Pflanze braucht Wasser}{} bedeutet \anfuehrung{eine}{} sogar \anfuehrung{alle}{.} In der Mathematik bedeutet es fast immer \anfuehrung{mindestens einen}{.} Die Besenaussage kann man also paraphrasieren als \einrueckung{Es gibt einen Besen, den ich fresse.} Eine formallogische Repräsentierung ist
\mathdisp {\exists x (B(x) \wedge F(x))} { , }
wobei
\mathl{B(x)}{} bedeutet, dass das Objekt $x$ ein Besen ist und wobei
\mathl{F(x)}{} bedeutet, dass ich dieses $x$ fresse. Man könnte genauso gut
\mathdisp {\exists x (F(x) \wedge B(x))} { }
schreiben. Das Zeichen
\mathdisp {\exists} { }
wird \anfuehrung{es gibt}{} oder \anfuehrung{es existiert}{} gesprochen und wird der \stichwort {Existenzquantor} {} \zusatzklammer {oder \stichwort {Existenzoperator} {}} {} {} genannt.

Eine Allaussage behauptet, dass ein gewisses Prädikat allen Objekten \zusatzklammer {aus einer gewissen Grundmenge} {} {} zukommt. Wie alle Aussagen kann dies wahr oder falsch sein. Eine Allaussage ist genau dann falsch, wenn es mindestens ein Objekt \zusatzklammer {aus der Grundmenge} {} {} gibt, dem das Prädikat nicht zukommt. Daher sind die beiden Quantoren, also der Allquantor und der Existenzquantor, über die Negation eng miteinander verknüpft und lassen sich gegenseitig ersetzen, und zwar gelten die Regeln
\mathdisp {\neg ( \forall x P(x)) \text{ ist gleichbedeutend mit } \exists x ( \neg P(x))} { , }

\mathdisp {\neg ( \exists x P(x)) \text{ ist gleichbedeutend mit } \forall x ( \neg P(x))} { , }

\mathdisp {\forall x P(x) \text{ ist gleichbedeutend mit } \neg ( \exists x ( \neg P(x)))} { }
und
\mathdisp {\exists x P(x) \text{ ist gleichbedeutend mit } \neg ( \forall x ( \neg P(x)))} { . }
Neben einstelligen Prädikaten wie
\mathl{P(x)}{} gibt es auch mehrstellige Prädikate der Form
\mathdisp {P(x,y) \text{ oder } Q(x,y,z) \text{ etc. }} { , }
die eine Beziehung zwischen mehreren Objekten ausdrücken, wie z.B. \anfuehrung{ist verwandt mit}{,} \anfuehrung{ist größer als}{,} \anfuehrung{sind Eltern von}{} u.s.w. Entsprechend kann dann über die verschiedenen Variablen quantifiziert werden, d.h. man hat mit Ausdrücken der Form
\mathdisp {\forall x (\exists y P(x,y)),\, \exists x (\forall y P(x,y)) ,\, \forall x (\exists y (\forall z Q(x,y,z))) \text{ usw. }} { }
zu tun. Statt
\mathl{\forall x \forall y \forall z Q(x,y,z)}{} schreibt man manchmal auch
\mathl{\forall x y z Q(x,y,z)}{.} Die Variablenbezeichnung in einer quantifizierten Aussage ist grundsätzlich unwichtig, d.h. es ist egal, ob man
\mathl{\forall a P(a)}{} oder
\mathl{\forall t P(t)}{} schreibt. Man darf dabei aber nur Variablennamen \zusatzklammer {also Buchstaben} {} {} verwenden, die im gegenwärtigen Kontext nicht schon anderweitig verwendet sind. Eine Aussage wie
\mathl{\forall x (\forall x P(x,x))}{} macht keinen Sinn. Auf jede Variable darf maximal nur ein Quantor Bezug nehmen.

Die Logik, die sich mit quantifizierten Aussagen auseinandersetzt, heißt \stichwort {Prädikatenlogik} {} oder \stichwort {Quantorenlogik} {.} Wir werden sie nicht systematisch entwickeln, da sie in der Mathematik als Mengentheorie auftritt. Statt
\mathl{P(x)}{,} dass also ein Prädikat einem Objekt zukommt, schreiben wir
\mathl{x \in P}{,} wobei dann $P$ die Menge aller Objekte bezeichnet, die diese Eigenschaft haben. Die Sprache der Mathematik wird in der Sprache der Mengen formuliert. Mehrstellige Prädikate treten in der Mathematik als Relationen auf. Das nächste mal werden wir die Sprache der Mengen in ihren Grundzügen vorstellen.