Kurs:Einführung in die mathematische Logik/20/Klausur mit Lösungen

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	${}\sum$
Punkte	3	3	2	2	2	1	3	6	3	0	2	3	0	2	0	0	4	36

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Sprache der Aussagenlogik ${}L^{V}$ zu einer Aussagenvariablenmenge ${}V$.
2. Ein maximales Ideal ${}{\mathfrak {m}}$ in einem kommutativen Ring ${}R$.
3. Die Uminterpretation ${}I{\frac {m}{x}}$ zu einer ${}S$- Interpretation ${}I$ in einer Menge ${}M$, wobei ${}x$ eine Variable und ${}m\in M$ ein Element der Grundmenge ist.
4. Ein Nichtstandardmodell zu einem fixierten ${}S$-Modell ${}M$.
5. Eine arithmetisch repräsentierbare Relation ${}R\subseteq \mathbb {N} ^{r}$.
6. Die Gültigkeit eines modallogischen Ausdrucks ${}\alpha$.

Lösung

1. Die Sprache der Aussagenlogik ${}L^{V}$ wird rekursiv durch folgende Regeln definiert.
   1. Jedes ${}p\in V$ gehört zu ${}L^{V}$.
   2. Wenn ${}\alpha \in L^{V}$, so ist auch ${}\neg (\alpha )\in L^{V}$.
   3. Wenn ${}\alpha ,\beta \in L^{V}$, so sind auch ${}(\alpha )\wedge (\beta ),\,(\alpha )\vee (\beta ),\,(\alpha )\rightarrow (\beta ),\,(\alpha )\leftrightarrow (\beta )\in L^{V}$.
2. Das Ideal ${}{\mathfrak {m}}$ heißt maximal, wenn ${}{\mathfrak {m}}\neq R$ ist und wenn es zwischen ${}{\mathfrak {m}}$ und ${}R$ keine weiteren Ideale gibt.
3. Unter der Uminterpretation ${}I{\frac {m}{x}}$ versteht man diejenige Interpretation von ${}S$ in ${}M$, die strukturgleich zu ${}I$ ist und für deren Variablenbelegung

   $\left(I{\frac {m}{x}}\right)(y)={\begin{cases}I(y),\,{\text{ falls }}y\neq x\,,\\m,\,{\text{ falls }}y=x\,,\end{cases}}$

   gilt.

4. Man nennt eine weitere ${}S$-Struktur ${}M'$, die zu ${}M$ elementar äquivalent, aber nicht zu ${}M$ ${}S$- isomorph ist, ein Nichtstandardmodell von ${}M$.
5. Die Relation ${}R\subseteq \mathbb {N} ^{r}$ heißt arithmetisch repräsentierbar, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r$ freien Variablen derart gibt, dass für alle ${}r$-Tupel ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die Äquivalenz ${}(n_{1},\ldots ,n_{r})\in R$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r})$ gilt.
6. Man sagt, dass ein modallogischer Ausdruck ${}\alpha$ in einem modallogischen Modell ${}(M,R,\mu )$ gilt, wenn

   $w\vDash \alpha$

   für alle ${}w\in M$ gilt.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Koinzidenzlemma.
2. Der Satz über die Vorgängereigenschaft in einem Peano-Halbring.
3. Der Satz über das Halteproblem.

Lösung

1. Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}U\subseteq S$ eine Teilmenge. Es sei ${}t$ ein ${}U$- Term und ${}\alpha$ ein ${}U$- Ausdruck. Es seien zwei ${}S$- Interpretationen ${}I_{1}$ und ${}I_{2}$ in einer gemeinsamen Grundmenge ${}M$ gegeben, die auf ${}U$ identisch seien. Dann gelten folgende Aussagen.
   1. Es ist ${}I_{1}(t)=I_{2}(t)$.
   2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$.
2. In einem Peano-Halbring ${}M$ gilt für jedes ${}x\in M$ die Eigenschaft: Entweder ist ${}x=0$ oder es gibt ein ${}u\in M$ mit ${}x=u+1$.
3. Die Menge

   ${\left\{n\in \mathbb {N} \mid n{\text{ ist die Nummer eines Registerprogramms }}P{\text{ und }}P(0){\text{ hält an}}\right\}}$

   ist nicht ${}R$-

   entscheidbar.

Aufgabe (2 Punkte)

In einer U-Bahn-Station wird der Zugang und der Ausgang über eine elektronische Karte geregelt, die man an einen Sensor halten muss, damit sich die Schranke öffnet. Es gibt 5 Ausgänge, aber nur 2 Zugänge. Was haben sich die Leute dabei vermutlich gedacht?

Lösung U-Bahn/Zugang und Ausgang/Aufgabe/Lösung

Aufgabe (2 Punkte)

Betrachte die beiden Aussagen „Alkohol ist keine Lösung“ und „Kein Alkohol ist auch keine Lösung“. Formalisiere die beiden Aussagen. Man nehme an, dass beide Aussagen wahr sind. Mit welcher aussagenlogischen Regel kann man daraus auf eine Aussage schließen, in der Alkohol nicht vorkommt?

Lösung

Die erste Aussage kann man als

$A\rightarrow \neg L$

und die zweite Aussage als

$\neg A\rightarrow \neg L$

formalisieren. Aus der Fallunterscheidungsregel ergibt sich die Gültikeit von

$\neg L,$

dass es also keine Lösung gibt.

Aufgabe (2 Punkte)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

${}p$ ${}q$ ${}r$ ${}?$ w w w w w w f f w f w f w f f f f w w f f w f f f f w f f f f w

Lösung

$(p\leftrightarrow q)\wedge (p\leftrightarrow r).$

Aufgabe (1 Punkt)

Lege in der Skizze für die drei Häuser überschneidungsfrei Wege zu den zugehörigen gleichfarbigen Gartentoren an.

Lösung Häuser/Gartentor/Verbindung/Aufgabe/Lösung

Aufgabe (3 Punkte)

Skizziere ein Verfahren, wie man (bei ${}V$ abzählbar) eine Auflistung sämtlicher syntaktischer Tautologien aus ${}L^{V}$ erhalten kann.

Lösung Aussagenlogik/Ableitungskalkül/Skizziere vollständige Auflistung/Aufgabe/Lösung

Aufgabe (6 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine aussagenlogische Ausdrucksmenge und es sei ${}\alpha \in L^{V}$ mit ${}\Gamma \not \vdash \alpha$. Zeige mit dem Lemma von Zorn, dass es eine maximal widerspruchsfreie Ausdrucksmenge ${}\Gamma \subseteq \Gamma '$ mit ${}\Gamma '\not \vdash \alpha$ gibt.

Lösung

Zunächst ist auch

$\Gamma \cup \{\neg \alpha \}\not \vdash \alpha ,$

da andernfalls

$\Gamma \vdash \neg \alpha \rightarrow \alpha$

gelten würde, woraus man mit Hilfe von ${}\vdash \alpha \rightarrow \alpha$ und der Fallunterscheidungsregel ${}\Gamma \vdash \alpha$ erhalten würde. Wir können also im Folgenden davon ausgehen, dass ${}\neg \alpha$ zu ${}\Gamma$ gehört.

Wir betrachten die Menge

${}M:={\left\{\Delta \subseteq L^{V}\mid \Delta \supseteq \Gamma ,\,\Delta \not \vdash \alpha \right\}}\,$

mit der durch Inklusion gegebenen Ordnung. Wegen ${}\Gamma \in M$ ist diese Menge nicht leer. Es sei ${}N\subseteq M$ eine nichtleere total geordnete Teilmenge. Die Vereinigung

${}\Theta =\bigcup _{\Delta \in N}\Delta \,$

besitzt ebenfalls die Eigenschaft, dass man aus ihr ${}\alpha$ nicht ableiten kann. Eine solche Ableitung nimmt nämlich nur Bezug auf endlich viele Voraussetzungen, und wäre dann schon aus einem der ${}\Delta$ ableitbar. Also besitzt die Kette in ${}M$ eine obere Schranke. Nach dem Lemma von Zorn gibt es also in ${}M$ maximale Elemente. Ein solches ist maximal widerspruchsfrei. Wenn man nämlich zu einem solchen maximalen ${}\Delta$ einen neuen Ausdruck ${}\beta$ hinzunimmt, so gilt

$\Delta \cup \{\beta \}\vdash \alpha .$

Doch wegen ${}\neg \alpha \in \Gamma \subseteq \Delta \subseteq \Delta \cup \{\beta \}$ ist ${}\Delta \cup \{\beta \}$ widersprüchlich.

Aufgabe (3 Punkte)

Es seien ${}x_{1},x_{2}$ Variablen, ${}t_{1},t_{2}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Zeige, dass

$\alpha {\frac {t_{1},t_{2}}{x_{1},x_{2}}}\rightarrow {\left(\alpha {\frac {t_{1}}{x_{1}}}\right)}{\frac {t_{2}}{x_{2}}}$

im Allgemeinen nicht allgemeingültig ist.

Lösung

Es sei ${}+$ ein zweistelliges Funktionssymbol und sei der Ausdruck ${}\alpha$ gleich ${}x_{1}=x_{2}$. Wir setzen

${}t_{1}=t_{2}=x_{1}+x_{2}\,.$

Dann ist einerseits (wir schreiben ${}\equiv$ für die Gleichheit von Ausdrücken)

${}{\begin{aligned}\alpha {\frac {t_{1},t_{2}}{x_{1},x_{2}}}&\equiv (x_{1}=x_{2}){\frac {x_{1}+x_{2},x_{1}+x_{2}}{x_{1},x_{2}}}\\&\equiv x_{1}+x_{2}=x_{1}+x_{2},\end{aligned}}$

was allgemeingültig ist, und andererseits

${}{\begin{aligned}{\left(\alpha {\frac {t_{1}}{x_{1}}}\right)}{\frac {t_{2}}{x_{2}}}&\equiv {\left((x_{1}=x_{2}){\frac {x_{1}+x_{2}}{x_{1}}}\right)}{\frac {x_{1}+x_{2}}{x_{2}}}\\&\equiv {\left(x_{1}+x_{2}=x_{2}\right)}{\frac {x_{1}+x_{2}}{x_{2}}}\\&=x_{1}+(x_{1}+x_{2})=x_{1}+x_{2},\end{aligned}}$

was nicht allgemeingültig ist (beispielsweise bei Interpretation in ${}\mathbb {N}$). Somit ist die Implikation nicht allgemeingültig.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 Punkte)

Man bringe die Aussage

$((p\vee (r\rightarrow q))\wedge (q\rightarrow p))\vee (((p\wedge \neg q)\wedge (\neg r\vee \neg p))\wedge (r\rightarrow (p\vee \neg q)))$

in disjunktive Normalform.

Lösung

Der Ausdruck

$(p\vee (r\rightarrow q))\land (q\rightarrow p)$

ist äquivalent zum Ausdruck

$(p\land q\land r)\vee (p\land q\land \neg r)\vee (p\land \neg q\land \neg r)\vee (p\land \neg q\land r)\vee (\neg p\land \neg q\land \neg r)$

und der Ausdruck

$((p\land \neg q)\land (\neg r\vee \neg p))\land (r\rightarrow (p\vee \neg q))$

ist äquivalent zu

$p\wedge \neg q\wedge \neg r.$

Der Gesamtausdruck ist somit äquivalent zu

$(p\land q\land r)\vee (p\land q\land \neg r)\vee (p\land \neg q\land \neg r)\vee (p\land \neg q\land r)\vee (\neg p\land \neg q\land \neg r)\vee (p\land \neg q\land \neg r),$

der disjunktive Normalform besitzt.

Aufgabe (3 Punkte)

Es sei ${}L^{V}$ die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ und es sei ${}\lambda$ eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation ${}I$. Zeige, dass ${}I^{\vDash }$ maximal widerspruchsfrei ist.

Lösung

Sei ${}\Gamma =I^{\vDash }$. Da der Ableitungskalkül korrekt ist, ist ${}\Gamma$ abgeschlossen unter Ableitungen. Aufgrund der rekursiv definierten Wahrheitsbelegung gilt für jedes ${}\alpha \in L^{V}$ entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$. Somit ist ${}\Gamma$ widerspruchsfrei. Sobald man zu ${}\Gamma$ einen Ausdruck ${}\alpha$ hinzunimmt, hat man ${}\alpha ,\neg \alpha \in \Gamma$ und daraus kann man einen Widerspruch ableiten. Die Menge ist also maximal widerspruchsfrei.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 Punkte)

Es sei ${}x$ eine Variable, ${}t$ ein Term und ${}\alpha \in L^{S}$ ein Ausdruck. Zeige

${}(\forall x\alpha ){\frac {t}{x}}=\forall x\alpha \,.$

Lösung

Die Variable ${}x$ ist in ${}\forall x\alpha$ nicht frei. Daher ist die Menge der relevanten zu substituierenden Variablen leer und somit auch die Menge der substituierenden Terme. Also ist ${}v=x$ und daher

${}(\forall x\alpha ){\frac {t}{x}}=\forall x(\alpha {\frac {x}{x}})=\forall x\alpha \,.$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Formuliere den Vollständigkeitssatz der Modallogik und skizziere in Grundzügen, wie man ihn beweist.

Lösung Modallogik/Vollständigkeitssatz/Skizziere/Aufgabe/Lösung