_01-Logik.tex

\setchapterpreamble[c][.7\textwidth]{\itshape\color{gray}\small
    In diesem Vortrag werden diejenigen sprachlichen Strukturen vorgestellt, die in der Mathematik verwendet werden, um Definitionen, Sätze und Beweise zu formulieren.
\vspace{24pt}}
    

\chapter{Logik} \label{chap:logik}


\section{Variablen und Terme}

\begin{defin}[Objekte und Typen] \index{mathematisches Objekt} \index{Typ}
    Es gibt keine strenge Definition dessen, was ein \textbf{mathematisches Objekt} sein soll. Darunter werden alle abstrakten Entitäten verstanden, mit denen sich Mathematiker beschäftigen, wie zum Beispiel die Zahl $5$, die Funktion $f(x)=x^2+1$ und der Vektor $\begin{psmallmatrix} 2 \\ 3 \end{psmallmatrix}$. Ihnen ist gemein, dass sie nicht in der „Wirklichkeit“ existieren, sondern lediglich Gegenstand unserer Gedanken sind.

    In der typentheoretischen Sichtweise wird jedes mathematische Objekt gedacht als von einem gewissen \textbf{Typ}, einer Sorte von Dingen, der es angehört. Beispielsweise sind $3$ und $\pi$ zwei Objekte vom Typ „reelle Zahl“ und „$3X^2+1$“ und „$X-5$“ zwei Objekte vom Typ „reelles Polynom“. Oft können Objekte des einen Typs je nach Kontext auch als Objekte eines anderen Typs mitgedacht werden. Beispielsweise ist in der Mathematik jede ganze Zahl auch eine reelle Zahl und in der Informatik kann jeder \emph{integer} zu einem \emph{float} konvertiert werden. Es gibt ebenfalls keine einheitliche Definition dessen, was ein Typ sei. Zwar wird der Begriff in der \emph{Typentheorie} formalisiert, dort ist er jedoch meist ein Grundbegriff, der nicht auf noch grundlegenderen Begriffen aufbauend definiert wird.
\end{defin}


\begin{defin}[Variable] \label{def:variable} \index{Variable}
    Eine \textbf{Variable} ist ein Zeichen, das als Platzhalter dient, an dessen Stelle Objekte eines gewissen Typs eingesetzt werden können. Letzterer heißt der \emph{Typ der Variable}.
\end{defin}


\begin{nota}
    Anstatt zu schreiben: „Ich verwende das Zeichen $n$ als Variable vom Typ natürliche Zahl“, bedienen sich Mathematiker eines Konjunktivs\footnote{Um genau zu sein, eines \emph{Jussivs}, der im Deutschen mit dem Konjunktiv formuliert wird.} und schreiben schlicht:
    \begin{quote}
        „Sei $n$ eine natürliche Zahl.“
    \end{quote}
    In diesem Skript werden Variablen meist als kursive Buchstaben gedruckt. Ansonsten ist aber alles erlaubt: Großbuchstaben, Kleinbuchstaben, griechische Buchstaben usw. Beispielsweise können die folgenden Zeichen alle als Variablen verwendet werden:
        \[ A,B,x,y,\gamma,\delta,\dots \]
    Prinzipiell kannst du jedes Zeichen als Variable verwenden, solange du vorher seinen Typ festlegst (z.B. „Seien $x,y$ zwei reelle Zahlen“). Allerdings haben sich in der Mathematik Konventionen eingebürgert, die gewisse Zeichen mit gewissen Typen assoziieren, und die du befolgen solltest, um deinen Text für andere Mathematiker leichter lesbar zu machen. Zum Beispiel:
    \begin{itemize}
        \item Natürliche Zahlen werden meist mit den Buchstaben $m,n\dots$ bezeichnet.
        \item Reelle Zahlen mit den Buchstaben $x,y,\dots$.
        \item Abbildungen mit den Buchstaben $f,g,\dots$.
        \item Mengen werden meist mit Großbuchstaben notiert und deren Elemente mit naheliegenden Kleinbuchstaben („Sei $R$ eine Menge und seien $r,s\in R$“).
        \item Aussagen (\cref{def:aussage}) werden meist mit den Buchstaben $A,B,\dots$ bezeichnet. In der englischen Literatur sind dagegen die Buchstaben $P,Q,\dots$ gebräuchlich ($P$ wie ``proposition'').
        \item In der mathematischen Logik kommt es sogar vor, dass \emph{Metavariablen} vom Typ „Variable“ auftauchen („Seien $x,y$ zwei Variablen“).
    \end{itemize}
    Das alles sind aber keine strikten Regeln und du wirst mit der Zeit ein Gespür für guten Stil entwickeln.
\end{nota}


\begin{bem} \quad
    \begin{itemize}
        \item Für das Einsetzen von Objekten für Variablen gelten folgende Grundsätze:
        \begin{itemize}
            \item Gleiche Variablen bezeichnen gleiche Objekte. Bezeichnet beispielsweise $x$ eine reelle Zahl, so wird in
                \[ x^2-2x \]
            vorausgesetzt, dass an beiden Vorkommen von $x$ dieselbe Zahl eingesetzt wird.
            \item In verschiedene Variablen darf dasselbe Objekt eingesetzt werden. Schreiben Mathematiker so etwas wie „Seien $m,n$ zwei natürliche Zahlen“, so schließt dies auch den Fall mit ein, dass $m$ und $n$ dieselbe Zahl sein können. Andernfalls schriebe man so etwas wie „Seien $m,n$ zwei \emph{verschiedene} natürliche Zahlen“.
        \end{itemize}
        \item(Variablen nie vom Himmel fallen lassen!) Erstsemester vergessen nicht selten, ihre Variablen sachgemäß einzuführen. Wann immer du eine Variable wie „$x$“ oder „$A$“ verwendest, solltest du, z.B. mit einem „Sei\dots“-Satz, ihren Typ klarstellen. Für die Tutoren ist es immer wieder nervig, wenn in Aufgabenlösungen plötzlich Buchstaben auftreten, für die nie klargestellt wurde, was sie zu bedeuten haben.
    \end{itemize}
\end{bem}


\begin{defin}[Cantorsche Mengendefinition] \label{mengenimlogikkapitel}
    Die Einführung des Mengenbegriffs in die Mathematik erfolgte durch Georg Cantor\footnote{\href{https://de.wikipedia.org/wiki/Georg_Cantor}{Georg Cantor (1845-1918)}} in den 1870er Jahren. Cantor beschrieb seine Idee in \cite{Can95} wie folgt:
    \begin{quote}
        „Unter einer \textbf{Menge} $M$ verstehen wir jede Zusammenfassung von bestimmten wohlunterschiedenen Objekten $m$ unserer Anschauung oder unseres Denkens (welche die \textbf{Elemente} von $M$ genannt werden) zu einem Ganzen.“\footnote{Eine (möglicherweise fiktive) Anekdote aus \cite{Ded32}, S. 449 beschreibt folgende „Veranschaulichungen“ des Mengenbegriffs:
    \begin{quote}
        Dedekind äußerte, hinsichtlich des Begriffes der Menge: er stelle sich eine Menge vor wie einen geschlossenen Sack, der ganz bestimmte Dinge enthalte, die man aber nicht sähe, und von denen man nichts wisse, außer dass sie vorhanden und bestimmt seien. Einige Zeit später gab Cantor seine Vorstellung einer Menge zu erkennen: Er richtete seine kolossale Figur hoch auf, beschrieb mit erhobenem Arm eine großartige Geste und sagte mit einem ins Unbestimmte gerichteten Blick: „Eine Menge stelle ich mir vor wie einen Abgrund.“
    \end{quote}
    Dedekinds Vorstellung kommt der des Durchschnittsmathematikers wohl näher.}
    \end{quote}
    Die Formalisierung des Mengenbegriffs ist Aufgabe der \emph{Mengenlehre}. Dort ist der Begriff der Menge meist ein Grundbegriff, der nicht auf anderen Begriffen aufbauend definiert wird.
\end{defin}


\begin{nota}[Elementzeichen]
    Sind $M$ eine Menge und $a$ ein Objekt, so schreibt man
    \begin{align*}
        a\in M\qquad&\text{für}\qquad a\ \text{ist ein Element von}\ M \\
        a\notin M\qquad&\text{für}\qquad a\ \text{ist kein Element von}\ M
    \end{align*}
\end{nota}


\begin{bsp}[Zahlbereiche]
    Beispielsweise notiert man mit
    \begin{itemize}
        \item $\N$ die Menge der natürlichen Zahlen (manchmal mit Null, manchmal ohne).
        \item $\Z$ die Menge der ganzen Zahlen.
        \item $\Q$ die Menge der rationalen Zahlen.
        \item $\R$ die Menge der reellen Zahlen.
        \item $\C$ die Menge der komplexen Zahlen.
    \end{itemize}
    Es gilt dann beispielsweise $-3\in \Z$ und $\frac{3}{2}\in\Q$, aber $-3\notin \N$ und $\frac{3}{2}\notin \Z$.
\end{bsp}


\begin{bem}[* Mengen vs. Typen]
    Ähnlich wie in der Typentheorie jedes Objekt von einem bestimmten Typ ist, ist in der Mengenlehre jedes Objekt ein Element einer Menge. Die Mengenlehre ist in der Lage, gewisse Typentheorien zu emulieren, d.h. sie stellt ein Modell für den Begriff „Typ“ zur Verfügung. Man definiert dann schlicht: Ein Typ $T$ ist eine Menge und ein Objekt vom Typ $T$ ist ein Element der Menge $T$. Beispielsweise wird „$n$ ist ein Objekt vom Typ ganze Zahl“ im Mengen-Formalismus zu „$n\in\Z$“. Mathematiker bedienen sich dieser Sprache auch beim Einführen von Variablen: Anstelle von „Sei $n$ eine ganze Zahl“ schreiben sie schlicht „Sei $n\in \Z$“; oder anstelle von „Sei $A$ eine reelle $(m\times n)$-Matrix“ schreiben sie „Sei $A\in \R^{m\times n}$“.

    Umgekehrt ist die Typentheorie in der Lage, die Mengenlehre zu emulieren. Hier ist dann „Menge“ schlicht ein Typ unter vielen, der gewissen Regeln unterliegt. Während Mathematiker meist typentheoretisch \emph{denken}, dominiert im \emph{Geschriebenen} die $\in$-Sprache der Mengenlehre und auch dieses Skript wird dieser Sprache folgen. Ihre Rolle als „Typen in spe“ ist erstmal die einzige, die Mengen in diesem Kapitel spielen werden. Die weiterführende Beschäftigung mit Mengen ist Inhalt von \cref{chap:mengen}.
\end{bem}


\begin{defin}[Term] \label{def:term} \index{Term}
    Seien $n\in \N$ und $x_1,\dots , x_n$ ein paar Variablen und $T$ ein Typ. Ein \textbf{Term vom Typ $T$} in den Variablen $x_1,\dots , x_n$ ist ein sprachliches Gebilde $t$, das, setzt man für jede der Variablen $x_1,\dots ,x_n$ jeweils ein konkretes Objekt ein, selbst ein konkretes Objekt vom Typ $T$ bezeichnet. Um hervorzuheben, dass $t$ ein Term in den Variablen $x_1,\dots , x_n$ ist, schreibt man auch
    \begin{align*}
        t(x_1,\dots , x_n) && (\text{lies: „$t$ von $x_1,\dots , x_n$“})
    \end{align*}

\end{defin}


\begin{bsp} \label{bsp:term} \quad
    \begin{enumerate}
        \item Für $x,y\in \R$ ist der Ausdruck
            \[ x^2+3xy-y^3 \]
        ein Term vom Typ „reelle Zahl“ in den Variablen $x$ und $y$. Setzt man beispielsweise für $x$ die Zahl $3$ und für $y$ die Zahl $2$ ein, erhält man den Zahlenwert $19$.
        \item Steht die Variable $m$ für einen Menschen, so ist der Ausdruck „Das Geburtsjahr von $m$“ ein Term vom Typ „ganze Zahl“ in der Variable $m$. Setzt man für $m$ einen konkreten Menschen ein, erhält man mit dessen Geburtsjahr eine ganze Zahl.
        \item In \cref{def:term} ist auch $n=0$ erlaubt, d.h. ein Term braucht nicht unbedingt Variablen enthalten. Beispielsweise sind die Ausdrücke
        \begin{align*}
             2+2 && 6{,}02\cdot 10^{23} && (\text{Die Quersumme von $420$})
        \end{align*}
        drei Terme vom Typ „reelle Zahl“, in denen keine Variablen vorkommen. Sie bezeichnen daher von vornherein eine konkrete reelle Zahl.
        \item In einem Term in den Variablen $x_1,\dots , x_n$ braucht nicht unbedingt auch jede dieser Variablen vorkommen. Beispielsweise kann „$3x+y$“ auch als „Term in den Variablen $x,y,z$“ verstanden werden, obwohl die Variable $z$ gar nicht darin vorkommt.
    \end{enumerate}
\end{bsp}


\begin{nota}[Klammersetzung] \label{klammern}
    Häufig lassen sich durch wiederholte Anwendung elementarer Operationen immer komplizierter verschachtelte Terme hervorbringen. Beispielsweise lässt sich in der Sprache der reellen Zahlen, mit den Verknüpfungen $+$ und $\cdot$, der Term
        \[ (x_1 +(x_2\cdot x_3))+(x_4\cdot ((x_5+x_6)\cdot (x_7+x_8)))\]
    hinschreiben. Als weiteres Beispiel werden die aussagenlogischen Junktoren aus \cref{sec:aussagenlogik} den Aufbau verschachtelter Aussageterme ermöglichen.

    Um deutlich zu machen, auf welche Weise ein Term aus kleineren Teiltermen zusammengebaut ist, bedient man sich \textbf{Klammern} und Konventionen wie der Regel „Punkt- vor Strichrechnung“, die vorschreiben, dass gewisse Operationen „stärker binden“ sollen als andere. Die wichtigste Ermächtigung zum Fortlassen von Klammern liefern die \emph{Assoziativgesetze}, siehe dazu \cref{klammerfrei}. Mit den gängigen Konventionen würde anstelle des obigen Terms geschrieben werden:
        \[ x_1 + x_2x_3+x_4(x_5+x_6)(x_7+x_8)\]
\end{nota}


\begin{nota}[$:=$]
    Komplizierte Terme möchte man nicht jedes Mal erneut aufschreiben und führt neue Zeichen ein, um diese Terme abzukürzen. Dabei bedient man sich des Zeichens
    \begin{align*}
        := &&& (\text{lies: „ist definiert als“ oder „ist per Definition gleich“})
    \end{align*}
    Beispielsweise wird mit der Formel
        \[ y(x) := 2x^2-3x \]
    festgelegt, dass das Zeichen „$y$“ fortan einen Term $y(x)$ bezeichne, nämlich „$2x^2-3x$“.

    Der Term $y$ braucht nicht unbedingt Variablen enthalten. Schreibt man beispielsweise
        \[ \alpha:= \pi + e\]
    so wird damit festgelegt, dass der Buchstabe $\alpha$ die Summe von $\pi$ (der Kreiszahl) und $e$ (der Eulerschen Zahl\footnote{\href{https://de.wikipedia.org/wiki/Leonhard_Euler}{Leonhard Euler (1707-1783)}}) bezeichnen soll. Näherungsweise ist $\alpha \approx 5{,}86$. Bis heute ist unbekannt, ob $\alpha$ eine rationale oder eine irrationale Zahl ist.
\end{nota}


\begin{defin}[* Variablensubstitution] \label{def:substitution}
    Sei $t(x)$ ein Term in der Variablen $x$. Ist $y$ ein weiterer Term, dessen Typ mit demjenigen der Variable $x$ übereinstimmt, so kann $y$ für die Variable $x$ \textbf{eingesetzt} (oder auch: \textbf{substituiert}) werden. Der so entstandene Term wird notiert mit
    \begin{align*}
        t(y) && (\text{lies: „$t$ von $y$“})
    \end{align*}
\end{defin}


\begin{bsp}[*] \quad \label{bsp:substitution}
    \begin{enumerate}
        \item Für $x,y\in\R$ sind $t(x):=x^2$ und $s(y):=y-1$ zwei Terme vom Typ „reelle Zahl“. Setzt man für die Variable $y$ den Term $t$ ein, ergibt sich $s(t)=x^2-1$. Setzt man dagegen in $t$ den Term $s$ ein, ergibt sich $t(s)=(y-1)^2$.
        \item Substituieren wir im Term „Das Geburtsjahr von $m$“ für die Variable $m$ den Term „die Mutter von $m$“, ergibt sich der Term „Das Geburtsjahr der Mutter von $m$“.
        \item Für $x,\varphi\in \R$ mit $-1\le x\le 1$ sind
            \[ y(x):=\sqrt{\strut 1-x^2} \qquad\text{und}\qquad s:=\sin(\varphi) \]
        zwei Terme vom Typ „reelle Zahl“ mit $-1\le s\le 1$. Substituieren wir für $x$ den Term $s$, ergibt sich $y(s)=\sqrt{1-\sin\!\smash{(\varphi)}^2}$, was gleichwertig zu $\vert\cos(\varphi)\vert$ ist. Substitutionen dieser Art sind dir vielleicht von der \emph{Integration durch Substitution} aus der Schule vertraut.
    \end{enumerate}
\end{bsp}


\begin{bem}[* Parameter] \index{Parameter}
    Manchmal enthält ein Term Variablen, die nicht dazu intendiert sind, Objekte an ihre Stelle einzusetzen, oder die hinsichtlich Einsetzen von Objekten eine geringere Priorität als andere Variablen haben. Man spricht dann gelegentlich von \textbf{Parametern}. Schreibt man beispielsweise
        \[ y(x):=x^2-ax \]
    so wäre dies eigentlich ungenau, weil der Term $y(x)$ ja neben $x$ auch noch die Variable $a$ enthält. Stattdessen soll deren Unterdrückung in der Notation darauf hinweisen, dass sie als Parameter angesehen wird. Zur Präzisierung könnte man auch sowas wie „$y_a(x)$“ schreiben. In der Schule ist dir dieses Vorgehen bereits bei Funktionenscharen begegnet.
\end{bem}


\begin{vorschau}[* Currying\protect\footnotemark]
    \footnotetext{\href{https://de.wikipedia.org/wiki/Haskell_Brooks_Curry}{Haskell Curry (1900-1982)}}
    Fassen wir $y$ als Funktionsterm auf (siehe \cref{def:zuordnung}), können wir $y$ sowohl als Funktion „in zwei Variablen“, die $a$ und $x$ die Zahl $x^2-ax$ zuordnet, verstehen, als auch als funktionenwertige Funktion, die $a$ die Funktion $y_a(x)$ zuordnet. Beide Betrachtungsweisen lassen sich per \href{https://ncatlab.org/nlab/show/currying}{Currying} ineinander überführen.
\end{vorschau}


\begin{nota}[* Gebundene Variablen] \label{gebundenevariable} \index{gebundene Variable} \index{freie Variable}
    Für $x\in\R$ betrachte einmal den Term
        \[ y(x):=2x^2+3x+1 \]
    Dies ist ein Term in der Variablen $x$, in den für $x$ eine beliebige reelle Zahl eingesetzt werden kann. Zum Beispiel wäre $y(-2)=3$. Im Term
        \[ \int_0^1 (2x^2+3x+1)\ dx\]
    ist dies nicht mehr der Fall. Hier ergäbe es keinen Sinn mehr, für das Zeichen $x$ irgendein Objekt einzusetzen. Ein Ausdruck wie etwa „$\int_0^1 (2\cdot 4^2+3\cdot 4+1)\ d4$“ wäre syntaktisch unzulässig.

    Obwohl man $x$ in diesem Kontext die Integrations\emph{variable} nennt, handelt es sich nicht um eine Variable im Sinne von \cref{def:variable}, sondern nur noch um ein „Dummy-Zeichen“, das darauf hinweist, über welche Variable integriert wird. Man nennt $x$ in dieser Situation eine \textbf{gebundene Variable}. Weitere Situationen, die solche Dummy-Variablen involvieren, sind die Laufvariablen unterm Summenzeichen (\cref{mehrfachprodukt}), der Folgenindex bei einer Limesbildung (\cref{def:konvergenz}), Variablen, die durch Anwendung eines Quantors gebunden werden (\cref{quantorbindung}), das „generische Element“ in der Extension einer Eigenschaft (\cref{def:extension}) oder in einer Abbildungsvorschrift (\cref{def:zuordnung}):
        \[ \sum_{k=1}^m (k^2-2) \quad \lim_{n\to \infty} \frac{n}{n+1} \qquad \forall x\in\R: x^2\ge 0 \qquad \{p\in \N \mid p\ \text{ist eine Primzahl}\} \quad n\mapsto n+1 \]
    Hier wären $k,n,x,p$ die gebundenen Variablen. Um gebundene Variablen von den eigentlichen Variablen im Sinne von \cref{def:variable} abzugrenzen, nennt man letztere auch \textbf{freie Variablen}. Ein Term kann durchaus mehrere gebundene und freie Variablen zugleich enthalten: Der Term $\sum_{k=1}^m(k^2-2)$ enthält neben der gebundenen Variable $k$ auch noch die freie Variable $m$ und der Term
        \[ \int_0^z e^{-cx^2} dx \]
    enthält neben einer gebundenen Variable $x$ auch noch die freien Variablen $z$ und $c$ (wobei letztere je nach Kontext als Parameter behandelt wird, worauf bereits der Buchstabe $c$ wie ``constant'' hinweist).
\end{nota}





\section{Bausteine der Aussagenlogik} \label{sec:aussagenlogik}


\begin{defin}[Aussage] \label{def:aussage}
    Eine \textbf{Aussage} ist ein sprachliches Gebilde, dem ein Wahrheitswert zugeordnet werden kann.
\end{defin}
	

\begin{bsp}
    Parallel zur abstrakten Theorie werden uns in diesem Paragraphen die folgenden Beispielaussagen begleiten:
    \begin{labeling}[label={$B_{\arabic*}:=$}, labelindent=1.5em, series=propbsp]
        \item „Der Döner wurde in Deutschland erfunden.“
        \item „Heute ist Mittwoch.“
        \item „Es gibt außerirdisches Leben.“
        \item „Der FC Bayern spielte eine schlechte Hinrunde.“
        \item „Die Relativitätstheorie ist fehlerhaft.“
    \end{labeling}
    Nicht jeder deutsche Satz ist eine Aussage. Sätze, die eher nicht als Aussagen durchgehen würden, sind zum Beispiel: \quad
    \begin{labeling}[resume*=propbsp]
        \item[] „Frohe Weihnachten!“
        \item[] „Was möchten Sie trinken?“
        \item[] „Ein großes Bier, bitte!“
    \end{labeling}
\end{bsp}


\begin{defin}[Junktor] \index{Junktor}
    Eine systematische Operation, die aus einer Handvoll Aussagen eine neue Aussage hervorbringt, heißt \textbf{Junktor} oder auch \textbf{logischer Operator}.
\end{defin}


Es werden nun die gebräuchlichen Junktoren vorgestellt.


\begin{defin}[Und-Verknüpfung] \index{Konjunktion}
    Zwei Aussagen $A,B$ können zu ihrer \textbf{Konjunktion}
    \begin{align*}
        A\land B && (\text{lies: „$A$ und $B$“})
    \end{align*}
    verknüpft werden, deren intendierte Bedeutung ist, dass sowohl $A$ als auch $B$ zutreffen.
\end{defin}


\begin{bsp}
    Beispiele für Konjunktionen sind etwa:
    \begin{labeling}[resume*=propbsp]
        \item[$B_2\land B_4=$] „Heute ist Mittwoch und der FC Bayern spielte eine schlechte Hinrunde.“
        \item[$B_3\land B_5=$] „Es gibt außerirdisches Leben, aber die Relativitätstheorie ist fehlerhaft.“
        \item[$B_1\land B_5=$] „Obwohl der Döner in Deutschland erfunden wurde, ist die Relativitätstheorie fehlerhaft.“
    \end{labeling}
    An den Beispielen wird deutlich, dass die Konjunktion zweier Aussagen nicht immer durch das Wort „und“ erfolgen braucht.
\end{bsp}
	
	
\begin{defin}[Oder-Verknüpfung] \index{Disjunktion}
    Zwei Aussagen $A,B$ können zu ihrer \textbf{Disjunktion}
    \begin{align*}
        A\lor B && (\text{lies: „$A$ oder $B$“})
    \end{align*}
    verknüpft werden, deren intendierte Bedeutung ist, dass mindestens eine der Aussagen $A$ und $B$ zutrifft.
\end{defin}
    

\begin{bsp}
    Beispiele für Disjunktionen sind:
    \begin{labeling}[resume*=propbsp]
        \item[$B_1\lor B_3=$] „Der Döner wurde in Deutschland erfunden oder es gibt außerirdisches Leben.“
        \item[$B_2\lor B_5=$] „Heute ist Mittwoch oder die Relativitätstheorie ist fehlerhaft.“
        \item[$B_4\lor B_4=$] „Der FC Bayern spielte eine schlechte Hinrunde oder der FC Bayern spielte eine schlechte Hinrunde.“
    \end{labeling}
\end{bsp}

		
\begin{bem}[Fachbegriffe]
    Du brauchst dir im Vorkurs nicht gleich alle Fachbegriffe zu merken. Sofern du weißt, dass es eine Und- und eine Oder-Verknüpfung gibt, brauchst du dir nicht merken, dass sie auch „Konjunktion“ und „Disjunktion“ genannt werden. In diesem und den folgenden Kapiteln werde ich dennoch oft mehrere Wörter für dasselbe Konzept nennen, um dir das Nachschlagen der Begriffe in Literatur und Internet zu erleichtern.
\end{bem}

	
\begin{bem}[* Ausschließendes Oder] \label{entwederoder}
    Die Disjunktion bezeichnet ein \emph{einschließendes Oder}, d.h. $A\lor B$ schließt auch den Fall ein, dass $A$ und $B$ beide gelten. In einer Mathematiker-Beziehung würde das Ultimatum „Ich -- oder deine dummen Fernsehserien!“ keine Besorgnis erregen. Das „oder“ lässt ja auch zu, dass beides vorliegen kann. Möchtest du ein ausschließendes Oder verwenden, kannst du dies mit
    \begin{align*}
        A\ \dot\lor\ B && (\text{lies: „Entweder $A$ oder $B$“})
    \end{align*}
    notieren. Das „Entweder $A$ oder $B$“ soll soviel wie „$A$ oder $B$ aber nicht beides“ bedeuten. Das Ultimatum „\emph{Entweder} ich oder deine dummen Fernsehserien“ könnte selbst bei einem Mathematiker-Pärchen eine handfeste Beziehungskrise auslösen.
    \begin{center}
    \begin{tabular}{cccc}
        Junktor &  Formelzeichen & Latein & Bezeichnung in der Informatik \\
        \midrule
        Oder &  $\lor$ & vel & OR \\
        Ausschließendes Oder & $\dot\lor$ & aut & XOR
    \end{tabular}
    \end{center}
\end{bem}


\begin{bsp}[*]
    Beispielsweise ist
    \begin{quote}
        „Eine natürliche Zahl ist entweder eine gerade oder eine ungerade Zahl.“
    \end{quote}
    eine korrekte Aussage, während
    \begin{quote}
        „Jeder Vorkursteilnehmer studiert entweder Mathematik oder Informatik.“
    \end{quote}
    falsch ist, da manche ja auch beides studieren.
\end{bsp}


\begin{defin}[Negation] \index{Negation}
    Für eine Aussage $A$ wird mit
    \begin{align*}
        \neg A   && (\text{lies: „nicht $A$“})
    \end{align*}
    die \emph{Negation} von $A$ notiert. $\neg A$ ist die Verneinung von $A$, d.h. $\neg A$ soll besagen, dass $A$ nicht zutrifft.
    
    Manchmal wird die Negation einer Aussage $A$ auch mit einem Oberstrich notiert: $\overline{A}$.
\end{defin}


\begin{bsp}    
    Beispiele für Negationen sind:
    \begin{labeling}[resume*=propbsp]
        \item[$\neg B_1 =$] „Der Döner wurde nicht in Deutschland erfunden.“
        \item[$\neg B_2 =$] „Heute ist nicht Mittwoch.“
        \item[$\neg B_3 =$] „Es gibt kein außerirdisches Leben.“
        \item[$\neg B_4 =$] „Der FC Bayern spielte keine schlechte Hinrunde.“
        \item[$\neg B_5 =$] „Die Relativitätstheorie ist fehlerfrei.“
    \end{labeling}
\end{bsp}


\begin{defin}[Implikationspfeil] \index{Implikation}
    Zwei Aussagen $A,B$ können zur („materiellen“) \textbf{Implikation}
    \begin{align*}
        A\to B   && (\text{lies: „$A$ impliziert $B$“})
    \end{align*}
    verknüpft werden: Deren intendierte Bedeutung ist, dass $B$ von $A$ impliziert wird. Weitere Lesarten sind unter Anderem:
    \begin{itemize}
        \item „$B$ folgt aus $A$“
        \item „$B$ ist eine Konsequenz von $A$“
        \item „Wenn $A$, dann $B$“
        \item „$A$ ist eine hinreichende Bedingung für $B$“
        \item „$B$ ist eine notwendige Bedingung für $A$“
    \end{itemize}
    Der Pfeil „$\to$“ heißt \textbf{Implikationspfeil} und die Aussage $A\to B$ ein \textbf{Konditional}.
\end{defin}


\begin{bsp}
    Beispiele für $\to$-Aussagen sind:
    \begin{labeling}[resume*=propbsp]
        \item[$B_1\to B_5=$] „Wenn der Döner in Deutschland erfunden wurde, ist die Relativitätstheorie fehlerhaft.“
        \item[$B_2\to B_4=$] „Sofern der FC Bayern eine schlechte Hinrunde spielte, ist heute Mittwoch.“
        \item[$B_3\to B_5=$] „Gibt es außerirdisches Leben, so ist die Relativitätstheorie fehlerhaft.“
    \end{labeling}
\end{bsp}


\begin{bem}
    Beachte, dass es beim Implikationspfeil „$\to$“ wesentlich auf die Reihenfolge ankommt. Während sich etwa die Aussagen $A\land B$ und $B\land A$ nicht in ihrer Bedeutung unterscheiden, sind $A\to B$ und $B\to A$ zwei grundlegend verschiedene Aussagen. Beispielsweise sind
    \begin{enumerate}[(1)]
        \item „Wenn heute Freitag ist, ist morgen Wochenende.“
        \item „Falls morgen Wochenende ist, ist heute Freitag.“
    \end{enumerate}
    zwei wesentlich verschiedene Aussagen. Aussage (1) ist korrekt, aber Aussage (2) ist falsch, da ja auch Samstag sein könnte.
\end{bem}


\begin{defin}[Äquivalenz] \index{Aequivalenz (von Aussagen)@Äquivalenz (von Aussagen)}
    Zwei Aussagen $A$ und $B$ lassen sich zur \textbf{Äquivalenz}
    \begin{align*}
        A\leftrightarrow B  && (\text{lies: „$A$ äquivalent zu $B$“})
    \end{align*}
    verknüpfen, deren intendierte Bedeutung ist, dass sich $A$ und $B$ gegenseitig implizieren. Lesarten dafür sind:
    \begin{itemize}
        \item „$A$ genau dann wenn $B$“. Ist wenig Platz vorhanden, schreibt man abkürzend „$A$ gdw. $B$“. Im Englischen schreibt man ``$A$ iff $B$''.
        \item „$A$ gilt dann und nur dann, wenn $B$“
    \end{itemize}
    Der Doppelpfeil „$\leftrightarrow$“ heißt \textbf{Äquivalenzpfeil} und die Aussage $A\leftrightarrow B$ ein \textbf{Bikonditional}.
\end{defin}

    
\begin{bsp}
    Beispiele für Äquivalenzaussagen sind:
    \begin{labeling}[resume*=propbsp]
        \item[\hfill\textbullet] „Genau dann ist heute Mittwoch, wenn morgen Donnerstag ist.“
        \item[\hfill\textbullet] „Eine reelle Zahl $x$ ist dann und nur dann negativ, wenn $-x$ positiv ist.“
        \item[$B_1\leftrightarrow B_3=$] „Dass der Döner in Deutschland erfunden wurde, ist äquivalent dazu, dass es außerirdisches Leben gibt.“
    \end{labeling}
\end{bsp}

	
\begin{bem}[* Die Pfeile $\to$ und $\Leftrightarrow$]
    Für Implikation und Äquivalenz sind sowohl die einfachen Pfeile $\to$, $\leftrightarrow$ als auch die doppelten Pfeile $\Rightarrow$, $\Leftrightarrow$ gebräuchlich.
    
    Gelegentlich werden verschachtelte Aussagen übersichtlicher, wenn die doppelten Pfeile zur Darstellung von Implikationen, die „eine Ebene höher“ liegen, verwendet werden. So mache ich es zum Beispiel in \cref{relgleich}.
    
    In der mathematischen Logik können beide Pfeilarten verwendet werden, um rigoros zwischen Implikationen auf der „Objektebene“ und solchen auf der „Metaebene“ zu unterscheiden; oder um zwischen „syntaktischer Implikation“ und „semantischer Implikation“ zu unterscheiden. Abseits der Logik sind diese Unterscheidungen aber überflüssig und es gibt, auch wenn manche Profs meinen, ihre Hörer auf ihre Privatnotation einschwören zu müssen, keine eindeutige Vorschrift, ob und wie zwischen „$\to$“ und „$\Rightarrow$“ unterschieden werden müsse. Benutze einfach den Pfeil, der dir besser gefällt.
\end{bem}

	
\begin{bem}[Verschachtelte Aussageterme]
    Im Sinne von \cref{klammern} erlauben die Junktoren die Konstruktion beliebig kompliziert verschachtelter Aussagen. Wie z.B. $(B_1\lor \neg B_2) \to (B_3\land \neg B_5)$:
    \begin{quote}
        „Sofern der Döner in Deutschland erfunden wurde oder heute nicht Mittwoch ist, gibt es außerirdisches Leben und die Relativitätstheorie ist fehlerfrei.“
    \end{quote}
    oder $B_1\lor (\neg B_2 \to (B_3\land \neg B_5))$:
    \begin{quote}
        „Der Döner wurde in Deutschland erfunden oder aber es gilt: wenn heute nicht Mittwoch ist, gibt es außerirdisches Leben und die Relativitätstheorie ist fehlerfrei.“
    \end{quote}
    Möchtest du Klammern vermeiden, kannst du verschieden große Leerstellen zwischen den Zeichen lassen:
    \begin{align*}
        B_1\lor \neg B_2\quad &\to \quad B_3\land \neg B_5 \\[0.5em]
        B_1\quad  &\lor \quad \neg B_2 \to (B_3\land \neg B_5)
    \end{align*}
    Es gibt auch Konventionen, die, ähnlich der Regel „Punkt- vor Strichrechnung“, die Erstausführung gewisser Junktoren vor anderen Junktoren regeln. Man legt dann z.B. fest, dass $\land$ „stärker binde“ als $\to$. Solche Konventionen solltest du nur dann stillschweigend verwenden, wenn du dir sicher bist, dass dein Leser dieselbe Konvention auch kennt und benutzt.
\end{bem}

	
\begin{vorschau}[* weitere Junktoren]
    Prinzipiell können unendlich viele weitere Junktoren definiert werden. Hinsichtlich der bivalenten Interpretationen aus \cref{def:interpretation} gibt es jedoch bis auf semantische Äquivalenz nur 16 zweistellige. Darunter:
    \begin{itemize}
        \item Der Sheffer-Strich\footnote{\href{https://de.wikipedia.org/wiki/Henry_Maurice_Sheffer}{Henry Maurice Sheffer (1882-1964)}} „$A\mid B$“ („Nicht sowohl $A$ als auch $B$“). In der Informatik spricht man von der \emph{NAND-Verknüpfung}.
        \item Die Peirce-Funktion\footnote{\href{https://de.wikipedia.org/wiki/Charles_Sanders_Peirce}{Charles Sanders Peirce (1839-1914)}} „$A\downarrow B$“ („Weder $A$ noch $B$“). In der Informatik spricht man von der \emph{NOR-Verknüpfung}.
    \end{itemize}
    NAND und NOR besitzen die besondere Eigenschaft, dass sich in der Schaltalgebra jeder andere Junktor \href{https://en.wikipedia.org/wiki/NAND_logic}{allein aus NAND's} oder \href{https://en.wikipedia.org/wiki/NOR_logic}{allein aus NOR's} zusammenbauen lässt. In dieser Hinsicht sind sie für die technische Informatik von großer Bedeutung. In der Mathematik sind sie jedoch weit weniger wichtig als die anderen Junktoren.
\end{vorschau}




	
\section{Bausteine der Prädikatenlogik}


\begin{defin}[Prädikat] \label{def:praedikat} \index{Praedikat@Prädikat} \index{Relation (Logik)}
    Sei $n\in \N$. Ein \textbf{$n$-stelliges Prädikat} ist ein Term vom Typ „Aussage“ in $n$-vielen Variablen.
    \begin{itemize}
        \item $1$-stellige Prädikate heißen auch \textbf{Eigenschaften}. Sprechen Mathematiker schlicht von „Prädikaten“, so meinen sie in der Regel einstellige Prädikate.
        \item Ist $n\ge 2$, so spricht man auch von \textbf{$n$-stelligen Relationen}. Sprechen Mathematiker einfach nur von „Relationen“, so meinen sie in der Regel zweistellige Relationen.
        \item Ein $0$-stelliges Prädikat ist schlicht eine Aussage.
    \end{itemize}
\end{defin}


\begin{bsp}
    Beispiele für einstellige Prädikate, also für Eigenschaften:
    \begin{enumerate}
        \item $E(m):\Leftrightarrow$ „$m$ ist eine gerade Zahl“, wobei $m\in \N$. Setzt man hier für die Variable $m$ beispielsweise die Zahlen $4$ und $5$ ein, erhält man die Aussagen „$4$ ist eine gerade Zahl“ und „$5$ ist eine gerade Zahl“.
        \item $D(X):\Leftrightarrow$ „$X$ wurde in Deutschland erfunden“, wobei sich die Variable $X$ auf kulinarische Errungenschaften beziehen soll. Setzt man hier für die Variable $X$ das Objekt „Der Döner“ ein, erhält man die Aussage „Der Döner wurde in Deutschland erfunden“. Setzt man dagegen das Objekt „Die Pizza“ ein, erhielte man die Aussage „Die Pizza wurde in Deutschland erfunden“.
        \item $M(x):\Leftrightarrow $ „$x$ ist der größte Mathematiker“, wobei die Variable $x$ vom Typ „MathematikerIn“ sei. Setzt man hier für die Variable $x$ das Objekt „Alexander Grothendieck“ ein, erhält man die Aussage „Alexander Grothendieck ist der größte Mathematiker“. Dagegen ergäbe es keinen Sinn, für $x$ das Objekt „Der Döner“ einzusetzen.
    \end{enumerate}
    Ich habe hier, um eine Eigenschaft mit einem Buchstaben zu bezeichnen, nicht das Symbol „$:=$“ sondern das Symbol „$:\Leftrightarrow$“ verwendet. Bei der Definition von Aussagen und Prädikaten kommt das schonmal vor, du könntest aber genausogut auch immer „$:=$“ schreiben. Ist Geschmackssache.
\end{bsp}


\begin{bsp}
    Zweistellige Prädikate sind zum Beispiel:
    \begin{enumerate}
        \item „$x$ ist kleiner als $y$“, wobei $x,y\in \R$. Diese Relation lässt sich auch kompakt als Formel $x<y$ notieren.
        \item $A(X,Y):\Leftrightarrow$ „$X$ ist älter als $Y$“, wobei für die Variablen konkrete Menschen eingesetzt werden sollen.
        \item $L(X,Y):\Leftrightarrow$ „$X$ liebt $Y$“, wobei die Variablen vom Typ „Figur aus Mozarts `Die Hochzeit des Figaro'“ seien.
    \end{enumerate}
    Viele weitere Beispiele werden in \cref{chap:relationen} untersucht.
\end{bsp}


\begin{nota}[Extension einer Eigenschaft] \label{extensionimlogikkapitel}
    Sei $E(x)$ eine Eigenschaft. Dann wird mit
        \[ \{ x\mid E(x) \} \qquad (\text{lies: „Menge aller $x$, für die gilt: $E(x)$“})\]
    die Menge all derjenigen Objekte (vom Typ der Variablen $x$), die die Eigenschaft $E$ besitzen, bezeichnet. Sie heißt die \textbf{Extension} (oder auch „Umfang“ oder „Ausdehnung“) des Prädikats $E$. Das Zeichen $x$ wird hierbei zu einer gebundenen Variable im Sinne von \cref{gebundenevariable}.

    Manche Autoren schreiben anstelle des Querstrichs $\vert$ einen Doppelpunkt: $\{x: E(x) \}$.
\end{nota}


\begin{bsp}
    Beispielsweise ist $\{M\mid M$ ist ein Mensch$\}$ die Menge aller Menschen und $\{p\mid p$ ist eine Primzahl$\}$ die Menge aller Primzahlen. Manchmal schreibt man auch nur so etwas wie „$\{\text{Menschen}\}$“ und „$\{\text{Primzahlen}\}$“, und spart sich den Umweg über die gebundene Variable.
\end{bsp}


\begin{vorschau}[* Eigenschaften vs. Teilmengen] \label{mengenvseig}
    Sei $E(x)$ eine Eigenschaft und $X$ die Menge aller Objekte vom Typ der Variablen $x$. Dann ist die Extension $M:=\{x\mid E(x)\}$ eine sogenannte \emph{Teilmenge}\footnote{siehe \cref{def:teilmenge}} von $X$, d.h. jedes Element der Menge $M$ ist auch ein Element der Menge $X$. Umgekehrt lässt sich für jede Teilmenge $N$ von $X$ die Eigenschaft $E(x)\ :\Leftrightarrow\ x\in N$ formulieren. Auf diese Weise hat man eine wechselseitige Beziehung zwischen Eigenschaften und Teilmengen. Es handelt sich hierbei um einen Aspekt der Dualität zwischen Syntax und Semantik. Mehr dazu in \cref{syntaxvssemantik}.
\end{vorschau}





\subsection*{Quantoren}


\begin{defin}[Allaussage] \label{def:allquant}
    Sei $E(x)$ eine Eigenschaft. Dann lässt sich die \textbf{Allaussage}
    \begin{align*}
        \forall x &:\  E(x) && (\text{lies: „Für jedes $x$ gilt $E(x)$“})
    \end{align*}
    formen, deren intendierte Bedeutung ist, dass \emph{jedes} Objekt (vom Typ der Variablen $x$) die Eigenschaft $E$ besitzt.
    
    Ist $M$ eine Menge von Objekten (vom Typ der Variablen $x$), so definiert man
    \begin{align*}
        \forall x\in M:\ E(x) \qquad :& \Leftrightarrow\qquad \forall x:\ (x\in M\ \to\ E(x))  \\
        (\text{lies: „Für jedes $x$ aus $M$ gilt $E(x)$“}) &
    \end{align*}
    was bedeuten soll, dass jedes Element der Menge $M$ die Eigenschaft $E$ besitzt.
    
    Das Zeichen $\forall$ heißt \textbf{Allquantor}.
\end{defin}


\begin{bsp}
    Beispiele für Allaussagen:
    \begin{enumerate}
        \item Sind $M$ die Menge der Bewohner meiner WG und $A(m):\Leftrightarrow$ „$m$ ist heute früh aufgestanden“, so besagt $\forall m\in M: A(m)$, dass jeder in meiner WG heute früh aufgestanden ist.
        \item Sind $\bbP$ die Menge aller Primzahlen und $U(p):\Leftrightarrow$ „$p$ ist eine ungerade Zahl“, so bezeichnet $\forall p\in\bbP : U(p)$ die (falsche) Aussage, dass jede Primzahl eine ungerade Zahl ist.
    \end{enumerate}
\end{bsp}


\begin{defin}[Existenzaussage]\label{def:existquant}
    Für eine Eigenschaft $E(x)$ lässt sich die \textbf{Existenzaussage}
    \begin{align*}
        \exists x &:\ E(x) && (\text{lies: „Es gibt ein $x$, für das $E(x)$ gilt“})
    \end{align*}
    formen, deren intendierte Bedeutung ist, dass \emph{mindestens ein} Objekt (vom Typ der Variablen $x$) die Eigenschaft $E$ besitzt.
    
    Ist $M$ eine Menge von Objekten (vom Typ der Variablen $x$), so definiert man
    \begin{align*}
        \exists x\in M:\ E(x) \qquad :& \Leftrightarrow\qquad \exists x:\ (x\in M\ \land\ E(x))  \\
        (\text{lies: „Es gibt ein $x$ in $M$, für das $E(x)$ gilt“}) &
    \end{align*}
    was bedeuten soll, dass mindestens ein Element der Menge $M$ die Eigenschaft $E$ besitzt.
    
    Das Zeichen $\exists$ heißt \textbf{Existenzquantor}.
\end{defin}
    

\begin{bsp}
    Beispiele für Existenzaussagen:
    \begin{enumerate}
        \item Sind $M$ die Menge der Bewohner meiner WG und $A(m):\Leftrightarrow$ „$m$ ist heute früh aufgestanden“, so besagt $\exists m\in M: A(m)$, dass mindestens einer in meiner WG heute früh aufgestanden ist.
        \item Sind $\bbP$ die Menge aller Primzahlen und $U(p):\Leftrightarrow$ „$p$ ist eine ungerade Zahl“, so bezeichnet $\exists p\in \bbP: U(p)$ die (wahre) Aussage, dass es mindestens eine Primzahl gibt, die ungerade ist.
    \end{enumerate}
\end{bsp}


\begin{nota}
    Die Negation einer Existenzaussage notiert man mit dem Zeichen $\nexists$. Das heißt, anstelle von „$\neg (\exists x: E(x))$“ schreibt man
    \begin{align*}
        \nexists x &:\ E(x) && (\text{lies: „Es existiert kein $x$, für das $E(x)$ gilt“})
    \end{align*}
    Ebenso schreibt man $\nexists x\in M: E(x)$ anstelle von $\neg (\exists x\in M: E(x))$.
    
    Für den Allquantor hat diese Notation kein Pendant. So etwas wie „$\forall\mkern-11mu/$“ ist meiner Erfahrung nach nicht gebräuchlich.
\end{nota}


\begin{bsp}
    Im Beispiel von gerade eben hieße „$\nexists m\in M: A(m)$“, dass in meiner WG heute niemand früh aufgestanden ist.
\end{bsp}


\begin{bsp}[Syllogistik]
    Die Prädikatenlogik ist in der Lage, die Satzformen der \emph{Syllogistik}, der vorherrschenden Logik im europäischen Mittelalter, zu formalisieren. Für ein Beispiel seien
    \begin{align*}
        M & := \{ x\mid  \text{$x$ ist ein Mensch} \} \\
        G &  : = \{x\mid \text{$x$ ist ein Gott} \} \\
        H(x) & :\Leftrightarrow\ \text{„$x$ ist ein Grieche“} \\
        S(x) & :\Leftrightarrow\ \text{„$x$ ist sterblich“}
    \end{align*}
    Damit lassen sich nun folgende Aussagen formulieren:
    \begin{align*}
        \forall x\in M& :\ S(x) && \text{„Alle Menschen sind sterblich“} \\
        \exists x \in M & :\ H(x)&& \text{„Einige Menschen sind Griechen“} \\
        \exists x \in M& :\ \neg H(x) && \text{„Einige Menschen sind keine Griechen“} \\
        \nexists x\in G & :\ S(x)&& \text{„Keine Götter sind sterblich“}
    \end{align*}
\end{bsp}


\begin{bem}[Variablen mit Quantoren binden] \label{quantorbindung}
    In Formeln wie „$\exists x: x(x+1)=2$“ oder „$\forall x: x^2\ge 0$“ ist das Zeichen $x$ eine gebundene Variable im Sinne von \cref{gebundenevariable}. Man sagt auch: „die Variable wird durch den Quantor gebunden“.

    Es lassen sich nicht nur Eigenschaften zu Aussagen reduzieren, sondern allgemein $n$-stellige Prädikate zu $(n-1)$-stelligen Prädikaten. Die Anwendung eines Quantors reduziert die Anzahl der freien Variablen um Eins. Beispielsweise wird das für reelle Zahlen $x,y$ formulierte zweistellige Prädikat
        \[ x < y \]
    durch Binden der Variable $x$ zu
        \[ \exists x:\ x<y \]
    In dieser Formel sind nun $x$ eine gebundene Variable und $y$ eine freie Variable, es liegt also ein einstelliges Prädikat vor. Dieses kann zu einer Aussage gemacht werden, indem man wahlweise für $y$ ein konkretes Objekt einsetzt, wie z.B. „$\exists x: x < 3$“, oder aber auch $y$ mit einem Quantor bindet, wie z.B. in
        \[ \forall y:\ \exists x:\ x < y \]
    Jedes $n$-stellige Prädikat kann zu einer Aussage gemacht werden, indem jede der Variablen wahlweise durch ein konkretes Objekt ersetzt oder aber durch einen Quantor gebunden wird.
\end{bem}
 
 
\begin{nota}[Schreibkonvention bei mehreren Quantoren]
    Verwende ich mehrere Quantoren unmittelbar hintereinander, schreibe ich den Doppelpunkt oft nur hinter den letzten Quantor:
    \begin{align*}
        \forall x\ \exists y &:\ x < y && (\text{lies: „Für jedes $x$ gibt es ein $y$, für das $x<y$ gilt“}) \\
        \exists y\ \forall x &:\ x < y && (\text{lies: „Es gibt ein $y$ derart, dass für alle $x$ gilt: $x<y$“})
    \end{align*}
    Einige Autoren lassen die Doppelpunkte hinter Quantoren auch ganz weg.
    
    Kommen mehrere Quantoren derselben Art hintereinander vor, schreibe ich oft nur ein Quantorzeichen auf und trenne die gebundenen Variablen mit einem Komma:
    \begin{align*}
        \forall x,y:\ x<y \quad&:\Leftrightarrow\quad \forall x\ \forall y:\ x<y && (\text{lies: „Für alle $x,y$ gilt $x<y$“}) \\
        \exists x,y:\ x<y \quad&:\Leftrightarrow\quad \exists x\ \exists y:\ x<y && (\text{lies: „Es gibt $x,y$, für die $x<y$ gilt“})
    \end{align*}
\end{nota}

 
\begin{bem} \label{quantorreihenfolge}
    Beachte, dass es bei Quantoren verschiedener Art auf die Reihenfolge ankommt. Für Menschen $x,y$ sei beispielsweise $M(x,y):\Leftrightarrow$ „$y$ ist (biologische) Mutter von $x$“. Dann sind
    \begin{enumerate}[(1)]
        \item $\forall x\ \exists y: M(x,y)$: „Für jeden Menschen $x$ gilt: es gibt einen Menschen $y$, der Mutter von $x$ ist“.
        \item $\exists y\ \forall x: M(x,y)$: „Es gibt einen Menschen $y$ derart, dass für jeden Menschen $x$ gilt: $y$ ist Mutter von $x$“.
    \end{enumerate}
    zwei grundlegend verschiedene Aussagen. (1) ist wahr, da jeder Mensch eine (biologische) Mutter hat; (2) ist dagegen falsch, weil nicht alle Menschen dieselbe Mutter haben.
    
    Quantoren derselben Sorte dürfen dagegen miteinander vertauscht werden, siehe \cref{quantorentausch}.
\end{bem}


\begin{defin}[Existenz-und-Eindeutigkeit-Aussage] \label{def:eindquant}
    Für eine Eigenschaft $E(x)$ bezeichnet
    \begin{align*}
        \exists ! x& :\ E(x) && (\text{lies: „Es gibt genau ein $x$, für das $E(x)$ gilt“})
    \end{align*}
    die Aussage, dass es \emph{genau ein} Objekt (vom Typ der Variablen $x$) gibt, das die Eigenschaft $E$ besitzt. Ist $M$ eine Menge von Objekten (vom Typ der Variablen $x$), so besagt die Formel
    \begin{align*}
        \exists ! x\in M :\ E(x) \qquad &:\Leftrightarrow\qquad \exists ! x:\ (x\in M\ \land\ E(x)) \\
        (\text{lies: „Es gibt genau ein $x$ in $M$, für das $E(x)$ gilt“})
    \end{align*}
    dass es genau ein Element von $M$ gibt, das die Eigenschaft $E$ besitzt (außerhalb von $M$ darf es aber auch andere solcher Objekte geben).
    
    Das Zeichen $\exists !$ heißt \textbf{Eindeutigkeitsquantor}.
\end{defin}


\begin{bsp}
    Beispiele für $\exists !$-Aussagen:
    \begin{enumerate}
        \item Ist $M$ die Menge der Bewohner meiner WG und $A(m):\Leftrightarrow$ „$m$ ist heute früh aufgestanden“, so besagt $\exists ! m\in M: A(m)$, dass genau ein Bewohner meiner WG heute früh aufgestanden ist.
        \item Die Formel „$\exists ! n\in \N : 32+n = 101$“ bezeichnet die Aussage: „Es gibt genau eine natürliche Zahl $n$, für die $32+n=101$ ist.“
        \item Die Formel „$\exists ! x\in \R: x^2=3$“ bezeichnet die (falsche) Aussage: „Es gibt genau eine reelle Zahl $x$, für die $x^2=3$ ist.“
    \end{enumerate}
\end{bsp}


\begin{bem}[Definition von $\exists !$ über die anderen beiden Quantoren] \label{eindquantzerlegung}
    Mithilfe der Gleichheitsrelation „$=$“ kann der Eindeutigkeitsquantor aus den anderen beiden Quantoren zusammengesetzt werden:
        \[ \exists ! x:\ E(x)\quad :\Leftrightarrow\qquad\qquad \exists x: E(x) \quad \land\quad \forall y\ \forall z:\ (E(y)\land E(z)) \to y=z \]
    Die erste Hälfte $\exists x: E(x)$ besagt, dass es \emph{mindestens} ein Objekt mit der Eigenschaft $E$ gibt, während die zweite Hälfte $\forall y\ \forall z:\dots$ besagt, dass es \emph{höchstens} ein Objekt mit der Eigenschaft $E$ gibt. Diese Definition von $\exists!$ wird wichtig, wenn es um das Beweisen von Existenz-und-Eindeutigkeit-Aussagen geht, siehe \cref{eindbeweis}.

    Eine weitere Möglichkeit zur Definition des Eindeutigkeitsquantors wäre:
        \[ \exists ! x:\ E(x)\quad :\Leftrightarrow\qquad\qquad \exists x:\quad E(x)\ \land\ \forall y: (E(y)\ \to\ x=y) \]
    Mit den Beweistechniken aus \cref{chap:beweise} lässt sich beweisen, dass beide Definitionen äquivalent sind (was du dir aber auch einmal intuitiv überlegen solltest).
\end{bem}


\begin{nota}[Definition per Kennzeichnung] \label{kennzeichnung} \index{Kennzeichnung}
    Sei $E(x)$ eine Eigenschaft, für die $\exists ! x: E(x)$ gilt, d.h. es gibt nur genau ein Objekt (vom Typ der Variablen $x$), das die Eigenschaft $E$ besitzt. Ist dann $a$ ein Objekt, das die Eigenschaft $E$ besitzt, so ist es legitim, von $a$ mit einem bestimmten Artikel zu sprechen: $a$ ist nicht nur \emph{ein} Objekt mit der Eigenschaft $E$, sondern \emph{das} Objekt mit der Eigenschaft $E$. Die Eigenschaft $E$ lässt sich dadurch für eine Definition verwenden. Mit
    \begin{quote}
        „Sei $a$ dasjenige Objekt, das die Eigenschaft $E$ besitzt.“
    \end{quote}
    legt man fest, das das Zeichen „$a$“ fortan das (eindeutig bestimmte) Objekt mit der Eigenschaft $E$ bezeichne. Man sagt auch, $a$ werde durch die Eigenschaft $E$ \emph{gekennzeichnet}, und nennt $E(a)$ eine (definite) \textbf{Kennzeichnung} von $a$ (Englisch: \emph{(definite) description}).
\end{nota}


\begin{bsp} \label{zeichendefinieren} \quad
    \begin{enumerate}
        \item Eine in der Analysis beliebte Definition der Kreiszahl $\pi$ lautet
        \begin{quote}
            $\pi$ ist definiert als die kleinste positive Nullstelle der Sinus-Funktion.
        \end{quote}
        Beachte, dass im Vorfeld dieser Definition sichergestellt werden muss, dass die Sinus-Funktion überhaupt eine kleinste positive Nullstelle besitzt.
        \item Mit Methoden der Kurvendiskussion lässt sich zeigen, dass die Gleichung $x^5=x+1$ genau eine Lösung in den reellen Zahlen besitzt (vgl. \cref{bsp:exverwendung}), wohingegen sich mit Methoden der Galoistheorie\footnote{\href{https://de.wikipedia.org/wiki/\%C3\%89variste_Galois}{Évariste Galois (1811-1832)}} zeigen lässt, dass sich diese Lösung nicht mit den Operationen $+$, $-$, $\cdot$, $:$, $\sqrt{}$ konstruieren lässt\footnote{Algebraiker sagen: \emph{die Gleichung $x^5=x+1$ ist nicht auflösbar}. Galoistheorie wird in Heidelberg typischerweise in der Drittsemestervorlesung „Algebra 1“ vermittelt.}. Möchte man nun komfortabel mit dieser Lösung arbeiten, ist eine Definition per Kennzeichnung ratsam:
        \begin{quote}
            „Sei $\xi$ die eindeutige reelle Lösung der Gleichung $x^5=x+1$.“
        \end{quote}
        Nun lassen sich bequem Aussagen wie etwa „Es ist $\xi>1$“ formulieren.
        \item \emph{Rekursive Definitionen} lassen sich als Definitionen per Kennzeichnung verstehen. Beispielsweise lässt sich beweisen, dass es genau eine Zahlenfolge $a_0,a_1,a_2,a_3,\dots$ gibt, die die \emph{Rekursionsvorschrift}
        \begin{align*}
            a_0 & = 0 & a_1 & = 1 & a_n & = a_{n-2} + a_{n-1}  && \text{für alle}\ n\in \N_{\ge 2}
        \end{align*}
        erfüllt. Die Rekursionsvorschrift fungiert hier als kennzeichnende Eigenschaft. Die durch sie definierte Zahlenfolge heißt \emph{Fibonacci-Folge}. Sie beginnt mit $0,1,1,2,3,5,8,13,21,34,\dots$
    \end{enumerate}
\end{bsp}


\begin{bem}[Mäßigung in der Verwendung von Formelsprache!]
    Nach den ganzen Formeln aus diesem Abschnitt eine \textbf{Warnung}: Einige Mathe-Anfis gelangen zu der Meinung, in der Mathematik käme es darauf an, Aussagen möglichst formelhaft zu notieren und Quantoren und Junktoren möglichst nie in Alltagssprache, sondern so oft wie möglich als Formelzeichen aufzuschreiben. Manche schreiben auch monströse Mutanten wie: „Daher $\exists$ eine Zahl $n$, die ein Teiler von $a$ $\land$ ein Teiler von $b$ ist.“
    
    Widerstehe dieser Idee! Mathematische Texte und Beweise sind zuallererst ein Akt der Kommunikation, in dem der Autor / die Autorin dem Leser eine Information übermitteln möchte. Die Effizienz dieser Informationsübermittlung muss für dich immer an erster Stelle stehen. Lass dich nicht knechten von (unter Mathematikern recht verbreiteten) Formel-Neurosen! Die Einführung der Symbole $\land,\to,\neg,\forall,\exists$ usw. geschieht \textbf{nicht}, damit wir ab sofort alles in diesen Zeichen aufschreiben. Sondern sie dient uns dazu, die Strukturen mathematischer Aussagen und Argumente analysieren und in aller Allgemeinheit besprechen und reflektieren zu können.
\end{bem}


\begin{vorschau}[* Logiken höherer Stufe] \label{higherorder}
    Die bis hierhin entwickelte Sprache heißt \emph{Prädikatenlogik erster Stufe}. Das Attribut „erststufig“ kommt daher, dass Objekte zwar Eigenschaften besitzen können, nicht jedoch auch Eigenschaften wieder Eigenschaften besitzen können. Dies wird in der \emph{Prädikatenlogik zweiter Stufe} ermöglicht. Hier können Eigenschaften wiederum „Eigenschaften zweiter Stufe“ besitzen und, was noch viel wichtiger ist, die Quantoren können auf Eigenschaften erster Stufe angewendet werden. Eine Eigenschaft zweiter Stufe“ wäre beispielsweise
        \[ \calE(E) \quad:\Leftrightarrow\quad \forall n:\ (E(n)\ \to\ \exists m:\ (m>n)\land E(m)) \]
    wobei sich die Objektvariablen $m,n$ auf natürliche Zahlen beziehen sollen. Dann besagt $\calE(E)$ letztendlich, dass unendlich viele Zahlen die Eigenschaft $E$ besitzen. Für $a\in \N$ lassen sich nun Formeln wie $\forall E:(\calE(E)\to E(a))$ („$a$ besitzt alle Eigenschaften, die von unendlich vielen Zahlen erfüllt sind“) formulieren.

    In Logiken noch höherer Stufen hat man dann „Eigenschaften von Eigenschaften von Eigenschaften von\dots“, die auf jeder Stufe mit ihrem eigenen Quantorenpaar $\forall,\exists$ daherkommen. In der Mathematik gehören höherstufige Logiken jedoch nicht zum Mainstream, sie werden dort schlichtweg nicht benötigt. Der Grund dafür ist die Mengenlehre. Indem Mengen sowohl Elemente enthalten können und dadurch als Surrogat für Eigenschaften fungieren (vgl. \cref{mengenvseig}), als auch selbst wiederum als Objekte in anderen Mengen enthalten sein können (siehe \cref{mengeniterativ}), eröffnen sie auf einen Rutsch die gesamte Spannweite beliebig höherstufiger Logiken, ja gelangen in gewisser Weise sogar über alle endlichen Stufen hinaus zu \emph{transfiniten} Stufen. Hierin liegt die Mächtigkeit der Mengenlehre begründet, die es ihr als „Universaltheorie“ ermöglicht, ein formales Fundament für weite Teile der Mathematik bereitzustellen.
\end{vorschau}





\section{Zweiwertige Interpretationen}


\subsection*{Wahrheitswerte}


\begin{vorschau}[Bivalenzprinzip] \label{bivalenz} \index{Bivalenzprinzip}
    Eine Interpretation einer Aussage ist die Zuweisung eines Wahrheitswerts nach gewissen Regeln.

    In der klassischen Aussagenlogik trägt die Menge der Wahrheitswerte in natürlicher Weise die Struktur einer sogenannten \href{https://en.wikipedia.org/wiki/Boolean_algebra_(structure)}{Boolschen Algebra}\footnote{\href{https://de.wikipedia.org/wiki/George_Boole}{George Boole (1815-1864)}}, in der allgemeineren intuitionistischen Logik die Struktur einer sogenannten \href{https://ncatlab.org/nlab/show/Heyting+algebra}{Heyting-Algebra}\footnote{\href{https://de.wikipedia.org/wiki/Arend_Heyting}{Arend Heyting (1898-1980)}}. Da sich ein Bit stets genau in einem der beiden Zustände $1$ oder $0$ befindet, besteht \emph{die} Boolsche Algebra der Informatiker aus genau diesen beiden Wahrheitswerten, auch ``true'' und ``false'' genannt. Auch in diesem Vorkurs beschränken wir uns auf die zweielementige boolsche Algebra, die ausschließlich aus den beiden Wahrheitswerten „wahr“ und „falsch“ besteht. Diese Einschränkung heißt \emph{Prinzip der Zweiwertigkeit} oder \textbf{Bivalenzprinzip}.\footnote{Philosophen sprechen hier manchmal vom „Satz vom ausgeschlossenen Dritten“. In der mathematischen Logik wird als „Satz vom ausgeschlossenen Dritten“ jedoch etwas Anderes bezeichnet, nämlich \cref{excludedmiddle}.}
    
    Während das Bivalenzprinzip in der Informatik ganz natürlich aus dem Binärsystem erwächst, ist es für die Mathematik eher unangemessen, siehe dazu \cref{bsp:lindenbaum}. In manchen einführenden Texten wirst du finden, dass die Junktoren $\land,\lor,\neg,\dots$ über Wahrheitswerte \emph{definiert} werden. Diese Vorgehensweise ist in meinen Augen irreführend, weil sie die Syntax an eine Semantik koppelt, die ihre Allgemeinheit nicht angemessen einfängt, und sie der Möglichkeit beraubt, für weitere Logiken, wie etwa konstruktive Logik (vgl. \cref{nichtkonstruktiv}) oder parakonsistente Logik (vgl. \cref{explosion}), verwendbar zu sein. Siehe hierzu auch \cref{goedelvollstaendig}.

    Beachte, dass es sich bei unseren Wahrheitswerten, trotz der philosophisch aufgeladenen Wörter „Wahrheit“ und „falsch“, erstmal nur um irgendwelche Dinger handelt, für die wir später Wahrheitstafeln aufstellen. Anstelle von „wahr“ und „falsch“ könnten wir genausogut auch mit $1$ und $0$ oder $\clubsuit$ und $\diamondsuit$ rechnen.
\end{vorschau}


\begin{defin}[Interpretation] \label{def:interpretation} \index{Interpretation (Logik)} \index{Wahrheitstafel}
    Eine \textbf{(bivalente) Interpretation} einer Aussage $X$ ist die Zuweisung eines der beiden Wahrheitswerte „wahr“ oder „falsch“ zu $X$. Diese Zuweisung darf allerdings nicht vollkommen frei erfolgen, sondern muss den folgenden Regeln gehorchen:
    \begin{itemize}
        \item  Ist $X$ eine Aussage, die sich mittels der Junktoren $\neg,\land,\lor,\to,\leftrightarrow$ aus anderen Aussagen $A,B$ zusammensetzt, so leitet sich der Wahrheitswert von $X$ nach den folgenden Regeln aus den Wahrheitswerten von $A$ und $B$ ab:
        \begin{center}
        \begin{tabular}{cc|cccc}
            $A$ & $B$  & $A\land B$ & $A\lor B$ & $A\to B$ & $A\leftrightarrow B$ \\
            \hline
            w&w& w & w & w & w \\
            w&f& f & w & f & f \\
            f&w& f & w & w & f \\
            f&f& f & f & w & w
        \end{tabular} \qquad\quad \begin{tabular}{c|c}
            $A$ & $\neg A$ \\
            \hline
            w& f \\
            f& w
        \end{tabular}
        \end{center}
        Diese \textbf{Wahrheitstafeln} sind folgendermaßen zu lesen: In den linken Spalten sind alle möglichen Kombinationen aufgelistet, wie $A$ und $B$ mit Wahrheitswerten belegt sein können. Für jede solche Kombination muss dann der Wahrheitswert von $A\land B$, $A\lor B$ etc. aus der jeweiligen Zeile übernommen werden. Beispielsweise muss die Aussage „$A\lor B$“ als falsch interpretiert werden, wenn sowohl $A$ als auch $B$ als falsch interpretiert wurden; in den anderen drei Fällen, also falls mindestens eine der beiden Aussagen $A,B$ als wahr interpretiert wird, muss auch $A\lor B$ als wahr interpretiert werden.
        \item Ist $E$ eine Eigenschaft, so ist die Allaussage $\forall x: E(x)$ als wahr zu interpretieren, falls für jedes Objekt $a$ (vom Typ der Variablen $x$) die Aussage $E(a)$ als wahr interpretiert ist. Wurde dagegen für ein Objekt $a$ die Aussage $E(a)$ als falsch interpretiert, so ist auch $\forall x: E(x)$ als falsch zu interpretieren.
        \item Ist $E$ eine Eigenschaft, so ist die Existenzaussage $\exists x: E(x)$ als wahr zu interpretieren, falls es mindestens ein Objekt $a$ (vom Typ der Variablen $x$) gibt, für das die Aussage $E(a)$ als wahr interpretiert ist. Wurde dagegen für jedes Objekt $a$ die Aussage $E(a)$ als falsch interpretiert, so ist auch $\exists x: E(x)$ als falsch zu interpretieren.
    \end{itemize}
\end{defin}


\begin{bsp}
    Seien $A,B,C$ drei Aussagen. Um die Wahrheitswerte von
        \[ D:= \qquad (A\lor \neg B) \to C\quad \land\quad \neg C\]
    für alle möglichen Interpretationen von $A,B,C$ zu ermitteln, kannst du eine Wahrheitstafel aufstellen, die auf der linken Seite mit allen möglichen Wahrheitswerte-Kombinationen für $A,B,C$ startet und in den rechten Spalten in wachsender Komplexität mit Teiltermen von $D$ fortfährt, bis in der Spalte ganz rechts die gesuchten Wahrheitswerte stehen:
    \begin{center}
    \begin{tabular}{ccc|ccccc}
        $A$ & $B$ & $C$ & $\neg B$ & $A\lor \neg B$ & $(A\lor \neg B)\to C$ & $\neg C$ & $((A\lor \neg B) \to C)\land \neg C$ \\
        \hline
        w & w & w &  f & w & w & f & f \\
        w & w & f &  f & w & f & w & f \\
        w & f & w &  w & w & w & f & f \\
        w & f & f &  w & w & f & w & f \\
        f & w & w &  f & f & w & f & f \\
        f & w & f &  f & f & w & w & w \\
        f & f & w &  w & w & w & f & f \\
        f & f & f &  w & w & f & w & f
    \end{tabular}
    \end{center}
    Also gibt es nur einen Fall, in dem $D$ eine wahre Aussage ist: nämlich wenn $B$ wahr ist und $A,C$ falsch sind.
\end{bsp}


\begin{bem}
    Die Wahrheitstafel des Implikationspfeils
    \[\begin{tabular}{cc|c}
        $A$ & $B$ &  $A\to B$  \\
        \hline
        w&w& w\\
        w&f& f\\
        f&w& w\\
        f&f& w\\
    \end{tabular}\]
    verwirrt Neulinge seit Jahrhunderten, weil sie in zweierlei Hinsicht nicht das alltagssprachliche Verständnis von „Wenn $A$, dann $B$“ wiedergibt:
    \begin{enumerate}[1.]
        \item Die Implikation $A\to B$ sagt lediglich aus, dass im Fall von $A$ auch $B$ gelten muss. Über den Fall, dass $A$ falsch ist, gibt sie keine Auskunft. Beispielsweise ist die Aussage
        \begin{quote}
            „Falls ich verschlafe, komme ich zu spät zur Uni.“
        \end{quote}
        in der Alltagssprache mehrdeutig und kann eine der beiden Aussagen
        \begin{enumerate}[(i)]
            \item „Wenn ich verschlafe, komme ich zu spät zur Uni. Andernfalls komme ich pünktlich.“
            \item „Wenn ich verschlafe, komme ich zu spät. Wenn ich nicht verschlafe, komme ich vielleicht pünktlich, vielleicht aber auch trotzdem zu spät.“
        \end{enumerate}
        bedeuten. In der Mathematik wird der Implikationspfeil ausschließlich im Sinne von (ii) gebraucht.
        \item Die Implikation $A\to B$ kann wahr oder falsch sein, selbst wenn gar kein Zusammenhang zwischen $A$ und $B$ besteht. Setzt man beispielsweise
        \begin{labeling}[labelindent=1.5em]
            \item[$A:=$] „Der Döner wurde in Deutschland erfunden“
            \item[$B:=$] „$529$ ist eine Quadratzahl.“
        \end{labeling}
        so ist $B$ eine wahre Aussage. Egal, ob $A$ nun wahr oder falsch ist, ergibt sich aus der Wahrheitstafel, dass „Sofern der Döner in Deutschland erfunden wurde, ist $529$ eine Quadratzahl“ eine wahre Aussage ist, obwohl $A$ mit $B$ ja gar nichts zu tun hat.
    \end{enumerate}
    Der Implikationspfeil in der Mathematik braucht nichts mit einem kausalen Zusammenhang zu tun zu haben. „$A\to B$“ besagt eher soviel wie „Mit der Annahme von $A$ lässt sich $B$ beweisen“. In \cref{chap:beweise} wird noch einmal darauf eingegangen, siehe \cref{direkterbeweis} und \cref{keinekausalitaet}.
\end{bem}





\subsection*{Tautologien}


\begin{defin} \label{def:tautologie} \index{Tautologie}
    Eine Aussage heißt
    \begin{itemize}
        \item \textbf{Tautologie} oder \textbf{allgemeingültig}, falls sie unter jeder möglichen Interpretation eine wahre Aussage ist.
        \item \textbf{erfüllbar}, falls es mindestens eine Interpretation gibt, unter der sie eine wahre Aussage ist.
        \item \textbf{unerfüllbar}, falls sie unter keiner möglichen Interpretation eine wahre Aussage ist.
    \end{itemize}
\end{defin}


\begin{bsp}
    Es gilt:
    \begin{enumerate}
        \item Die Aussage „Heute ist Mittwoch“ ist erfüllbar, aber keine Tautologie.
        \item Die Aussage „Genau dann ist heute Mittwoch, wenn heute Mittwoch ist“ ist eine Tautologie.
        \item Für beliebige Aussagen $A,B$ sind
            \[ A \to A \qquad A\lor \neg A  \qquad A \to (A\lor B) \]
        jeweils Tautologien, was mit Wahrheitstafeln überprüft werden kann.
        \item Für beliebige Aussagen $A,B$ sind
            \[ A \leftrightarrow \neg A \qquad A\land \neg A \qquad  \neg(A\to (A\lor B))\]
        unerfüllbar.
    \end{enumerate}
\end{bsp}
 
 
\begin{satz} \label{tauto}
    Seien $A,B$ zwei Aussagen. Es gilt:
    \begin{enumerate}
        \item Genau dann ist $A$ unerfüllbar, wenn $\neg A$ eine Tautologie ist.
        \item Genau dann ist $A\leftrightarrow B$ eine Tautologie, wenn $A$ und $B$ unter jeder Interpretation derselbe Wahrheitswert zukommt.
        \item Genau dann ist $A\to B$ eine Tautologie, wenn unter jeder Interpretation, unter der $A$ eine wahre Aussage ist, auch $B$ eine wahre Aussage ist. Diejenigen Interpretationen, unter denen $A$ falsch ist, spielen hierbei keine Rolle.
    \end{enumerate}
\end{satz}
\begin{proof}
    \begin{enumerate}
        \item Betrachte die Wahrheitstafel der Negation:
        \[\begin{tabular}{c|c}
            $A$ &  $\neg A$ \\
            \hline
            w&f\\
            f&w
        \end{tabular}\]
        Unter einer festen Interpretation ist $\neg A$ genau dann wahr, wenn $A$ falsch ist. Dass $\neg A$ unter allen Interpretationen wahr ist, heißt dann genau, dass $A$ unter allen Interpretationen falsch ist.
        \item Aus der Wahrheitstafel der Äquivalenz
        \[\begin{tabular}{cc|c}
            $A$ &  $B$ & $A \leftrightarrow B$ \\
            \hline
            w&w&w\\
            w&f&f \\
            f & w & f\\
            f & f & w
        \end{tabular}\]
        liest man ab, dass $A\leftrightarrow B$ genau dann wahr ist, wenn $A$ und $B$ denselben Wahrheitswert haben. Also ist $A\leftrightarrow B$ genau dann eine Tautologie, wenn $A$ und $B$ unter jeder Interpretation denselben Wahrheitswert haben.
        \item Betrachte die Wahrheitstafel der Implikation:
        \[\begin{tabular}{cc|c}
            $A$ &  $B$ & $A \to B$ \\
            \hline
            w&w&w\\
            w&f&f \\
            f & w & w\\
            f & f & w
        \end{tabular}\]
        Dass $A\to B$ eine Tautologie ist, heißt, dass $A\to B$ unter jeder möglichen Interpretation wahr sein muss. Dies ist äquivalent dazu, dass der Fall, dass $A$ wahr und $B$ falsch ist, niemals auftreten kann. Und das heißt gerade, dass unter jeder Interpretation, unter der $A$ wahr ist, auch $B$ wahr sein muss. \qedhere
    \end{enumerate}
\end{proof}
 

\begin{bem}
    Eine große Liste aussagenlogischer Tautologien findest du in \cref{anhang:formelsammlung}. Versuch mal, dir intuitiv für ein paar der Formeln klarzumachen, dass es sich um Tautologien handelt. So kannst du ein besseres Verständnis für die Junktoren erwerben.
\end{bem}


\begin{vorschau}[* Entscheidbarkeit der Aussagenlogik] \label{entscheidbar}
    Ist $A$ eine noch so kompliziert verschachtelte Aussage, die keine Prädikate und Quantoren enthält, sondern sich ausschließlich mittels aussagenlogischer Junktoren aus unzerlegbaren Aussagen zusammensetzt, so lässt sich mithilfe von Wahrheitstafeln stets überprüfen ob $A$ eine Tautologie ist. Mit genügend Rechenkapazität kann mir mein Computer also einfach ausrechnen, ob eine Tautologie vorliegt oder nicht. Man spricht von der (algorithmischen) \textbf{Entscheidbarkeit der Aussagenlogik}. Wie effizient ein solcher Entscheidungsalgorithmus sein kann, ist eine andere Frage. Das \emph{Erfüllbarkeitsproblem der Aussagenlogik} (kurz: SAT, für ``satisfiability'') ist \emph{NP-vollständig}: Sofern es einen Algorithmus gibt, der einen beliebigen aussagenlogischen Term in polynomialer Laufzeit darauf überprüfen kann, ob er eine Tautologie (hinsichtlich zweiwertiger Interpretationen) ist, wäre die berühmte \href{https://de.wikipedia.org/wiki/P-NP-Problem}{Frage nach P=NP} zu bejahen. Das Auffinden eines P-effizienten Entscheidungsalgorithmus könnte gravierende Konsequenzen für die Cybersicherheit haben, da diverse Verschlüsselungsalgorithmen auf einem NP-Problem, der Berechnung der Primfaktorzerlegung, beruhen, für dessen Brechung es derzeit keinen effizienten Algorithmus gibt. Obwohl die Frage nach P=NP nachwievor offen ist, dominiert die Vermutung, dass sie zu verneinen bzw. höchstens nichtkonstruktiv bejahbar ist.

    Sobald Quantoren ins Spiel kommen, reichen Wahrheitstafeln nicht mehr aus. In der Berechenbarkeitstheorie wird sogar bewiesen, dass es keinen Algorithmus geben kann, der für eine beliebige, mittels Junktoren und Quantoren aus Prädikaten und Aussagen zusammengesetzte Aussage entscheiden kann, ob eine Tautologie vorliegt. Man spricht von der \textbf{Unentscheidbarkeit der Prädikatenlogik}. Das wäre auch zu schön, denn ein solcher Algorithmus wäre ein „mathematisches Orakel“, das für jede (in Prädikatenlogik formulierbare) mathematische Aussage ausrechnen könnte, ob sie allgemeingültig ist oder nicht.
\end{vorschau}





\clearpage
\section{Aufgabenvorschläge}


\begin{aufg}[Alltagssprache in Formeln übersetzen]
    Zerlegt die folgenden Aussagen mithilfe der im Vortrag behandelten Junktoren und Quantoren in möglichst einfache Grundbausteine (es gibt hier nicht „die eine“ Lösung).
    \begin{enumerate}
        \item Wird ein hartgekochtes Ei nicht mit kaltem Wasser abgeschreckt, so klebt die Schale am Eiweiß und das Ei lässt sich nicht gut schälen.
        \item Sofern er morgen Abend weder arbeiten muss noch Besuch von seiner Schwester kriegt, würde er sich mit mir treffen.
        \item Die Gleichung $x^5=x+1$ besitzt genau eine reelle Lösung.
        \item Wenn es irgendjemand schafft, dann Henrik.
        \item(Goldbach-Vermutung) Jede gerade natürliche Zahl, die größer als $2$ ist, ist eine Summe zweier Primzahlen.
        \item Wenn ich entweder alle Prüfungen im ersten Versuch bestehe oder aber durch alle Prüfungen im ersten Versuch durchfalle, werde ich die ganze Nacht hindurch feiern.
    \end{enumerate}
\end{aufg}


\begin{aufg}[Formeln in Alltagssprache übersetzen]
    Übersetzt die folgenden Aussageformeln in Alltagssprache und beurteilt, ob es sich um wahre oder falsche Aussagen handelt:
    \begin{align*}
        \text{a)}&\qquad \forall x,y\in \R:\ ((x<0)\land (y<0)\ \to\ xy>0) \\[0.4em]
        \text{b)}&\qquad \forall x\in \R\ \exists n\in \Z:\ x<n \\[0.4em]
        \text{c)}&\qquad \exists n\in \Z\ \forall x\in \R:\ x<n \\[0.4em]
        \text{d)}&\qquad \exists! x\in \R\ \exists y\in \R:\ (y\neq0\ \land\ x\cdot y=0) \\[0.4em]
        \text{e)}&\qquad \forall x\in \R\ \exists y\in \R\ \forall z\in \R:\ yz = (x+z)^2-(x^2+z^2) \\[0.4em]
        \text{f)}&\qquad \forall n\in\N_0\ \exists a,b,c,d\in \N_0:\ n=a^2+b^2+c^2+d^2 \tag{Vier-Quadrate-Satz}
    \end{align*}
\end{aufg}
	
	
\begin{aufg}[Wahrheitstafeln (L)] \label{aufg:wtafeln}
    Seien $A,B$ zwei beliebige Aussagen. Entscheidet mithilfe von Wahrheitstafeln, in welchen Fällen die folgenden Aussagen wahr sind:
    \begin{align*}
        \text{a)}&\qquad \neg(A\lor B) \\
        \text{b)}&\qquad (\neg A \to A) \to A \tag{Consequentia mirabilis} \\
        \text{c)}&\qquad A\land(B\to\neg(A\land B)) \\
        \text{d)}&\qquad (A\to B)\lor(B\to A) \tag{Linearitätsaxiom}
    \end{align*}
\end{aufg}


\begin{aufg}[freestyle]
    An der Tafel von Captain Chaos stehen die folgenden Ausdrücke:
    \begin{align*}
        (i)\quad& A\ {\neg}{\to}\ \neg A&(iv)\quad& \exists x\in x:\ x\in x  \\
        (ii)\quad&   \forall n\in \N:\ 1<3 & (v)\quad& \forall E :\ E(x) \\
        (iii)\quad& \forall x\in \R :\ x^2+1 &(vi)\quad& \forall x_1\ \exists x_2\ \forall x_3\ \exists x_4\ \forall x_5\ \ldots:\ E(x_1,x_2,x_3,\dots)
    \end{align*}
    Was haltet ihr davon?
\end{aufg}