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

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	${}\sum$
Punkte	3	3	1	1	3	2	3	7	1	3	5	6	4	3	45

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Ableitbarkeit eines Aussage ${}\alpha \in L^{V}$ aus einer Aussagenmenge ${}\Gamma \subseteq L^{V}$ in der Sprache der Aussagenlogik zu einer Aussagevariablenmenge ${}V$.
2. Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$.
3. Die Erfüllbarkeit eines ${}S$-Ausdruckes ${}\alpha \in L^{S}$, wobei ${}S$ ein Symbolalphabet bezeichnet.
4. Die elementare Äquivalenz für Elemente ${}m,n\in M$ für eine ${}S$-Struktur ${}M$.
5. Die aufzählbare Axiomatisierbarkeit einer Theorie ${}T\subseteq L_{0}^{S}$ zu einem Symbolalphabet ${}S$.
6. Die Gültigkeit eines modallogischen Ausdrucks ${}\alpha$ in einem modallogischen Rahmen ${}(M,R)$.

Lösung

1. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ ableitbar ist, wenn es endlich viele Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma$ derart gibt, dass

   $\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha$

   gilt.

2. Die Relation ${}\preccurlyeq$ heißt Ordnungsrelation, wenn folgende drei Bedingungen erfüllt sind.
   1. Es ist ${}i\preccurlyeq i$ für alle ${}i\in I$.
   2. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq k$ folgt stets ${}i\preccurlyeq k$.
   3. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq i$ folgt ${}i=j$.
3. Man nennt ${}\alpha$ erfüllbar, wenn es eine ${}S$- Interpretation ${}I$ mit ${}I\vDash \alpha$ gibt.
4. Zwei Elemente ${}m,n\in M$ heißen elementar äquivalent, wenn für jeden Ausdruck ${}\alpha \in L_{1}^{S}$ in der einen freien Variablen ${}x$ und jede Variablenbelegung ${}\lambda$ auf ${}M$ die Beziehung

   $I{\frac {m}{x}}\vDash \alpha {\text{ genau dann, wenn }}I{\frac {n}{x}}\vDash \alpha$

   gilt.

5. Eine Theorie ${}T\subseteq L_{0}^{S}$ heißt aufzählbar axiomatisierbar, wenn es eine ${}R$- aufzählbare Satzmenge ${}\Gamma \subseteq L_{0}^{S}$ mit ${}T=\Gamma ^{\vdash }$ gibt.
6. Die Gültigkeit in einem modallogischen Rahmen bedeutet, dass für jede Wahrheitsbelegung ${}\mu$

   $(M,R,\mu )\vDash \alpha$

   gilt.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Substitutionslemma.
2. Der Vollständigkeitssatz der Aussagenlogik.
3. Der zweite Gödelsche Unvollständigkeitssatz.

Lösung

1. Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben und es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$-Terme. Es sei eine ${}S$-Interpretation ${}I$ gegeben. Dann gelten folgende Aussagen.
   1. Für jeden ${}S$-Term ${}s$ gilt

      ${}I\left(s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)=\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)(s)\,.$

   2. Für jeden ${}S$-Ausdruck ${}\alpha$ gilt

      $I\vDash \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}{\text{ genau dann, wenn }}{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}\vDash \alpha .$

2. Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine Teilmenge der zugehörigen Sprache der Aussagenlogik. Es sei ${}\alpha \in L^{V}$. Dann ist

   $\Gamma \vdash \alpha {\text{ genau dann, wenn }}\Gamma \vDash \alpha .$

3. Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und entscheidbar sei und die Peano-Arithmetik umfasse. Dann ist die Widerspruchsfreiheit ${}WF(\Gamma )$ nicht aus ${}\Gamma$ ableitbar, d.h. es ist

   $\Gamma \not \vdash WF(\Gamma ).$

Aufgabe (1 Punkt)

Formuliere die Kontraposition zu folgender Aussage von Professor Knopfloch: „Wenn Sie mein Schreiben vollständig gelesen und verstanden haben, dann antworten Sie mit Ihrer Uni-email“.

Lösung

Wenn Sie nicht mit Ihrer Uni-email antworten, dann haben Sie mein Schreiben nicht vollständig gelesen oder nicht verstanden.

Aufgabe (1 Punkt)

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

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

Lösung

${}\neg p$.

Aufgabe (3 Punkte)

Die Klasse 8c hat an jedem Wochentag eine Stunde mathematische Logik. Der Lehrer sagt am Freitag: „nächste Woche werden wir eine Klassenarbeit schreiben, und das wird eine Überraschung sein“. Begründe, dass der Lehrer lügt.

Lösung Woche/Klassenarbeit/Überraschung/Aufgabe/Lösung

Aufgabe (2 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Begründe die Fallunterscheidungsregel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \neg \alpha \rightarrow \beta$, dann ist auch ${}\Gamma \vdash \beta$.

Lösung

Es gilt

$\vdash (\alpha \rightarrow \beta )\wedge (\neg \alpha \rightarrow \beta )\rightarrow \beta$

nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (6). Nach Voraussetzung und Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (5) ergibt sich daraus ${}\vdash \beta$.

Aufgabe (3 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge ${}V$ und es seien ${}\alpha ,\beta \in L^{V}$. Zeige, dass

$\Gamma \cup \{\alpha \}\vdash \beta$

zu

$\Gamma \vdash \alpha \rightarrow \beta$

äquivalent ist.

Lösung

Die Ableitungsbeziehung

$\Gamma \vdash \alpha \rightarrow \beta$

bedeutet, dass es Ausdrücke ${}\gamma _{1},\ldots ,\gamma _{n}\in \Gamma$ mit

$\vdash \gamma _{1}\wedge \ldots \wedge \gamma _{n}\rightarrow {\left(\alpha \rightarrow \beta \right)}$

gibt. Aufgrund der aussagenlogischen Tautologie

$\vdash {\left(\varphi \rightarrow {\left(\psi \rightarrow \theta \right)}\right)}\leftrightarrow {\left(\varphi \wedge \psi \rightarrow \theta \right)}$

ist dies äquivalent zu

$\vdash \gamma _{1}\wedge \ldots \wedge \gamma _{n}\wedge \alpha \rightarrow \beta .$

Dies bedeutet gerade

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

Aufgabe (7 Punkte)

Beweise den Satz von Hamel mit dem Lemma von Zorn.

Lösung

Es sei ${}V$ ein Vektorraum über einem Körper ${}K$. Es sei

$M={\left\{T\subseteq V\mid {\text{ Die Elemente aus }}T{\text{ sind linear unabhängig}}\right\}}\,.$

Die leere Menge gehört zu ${}M$, also ist ${}M$ nicht leer. Es sei ${}N\subseteq M$ eine total geordnete Teilmenge. Wir behaupten, dass

${}S=\bigcup _{T\in N}T\,$

ebenfalls linear unabhängig ist und daher eine obere Schranke von ${}N$ in ${}M$ bildet. Andernfalls gäbe es nämlich eine endliche Teilmenge ${}E\subseteq S$, deren Elemente linear abhängig sind, und es gäbe auch ein ${}T\in N$, das ${}E$ umfasst und daher selbst linear abhängig wäre. Nach dem Lemma von Zorn besitzt ${}M$ also maximale Elemente, d.h. es gibt eine Teilmenge ${}T\subseteq V$, die linear unabhängig ist und derart, dass es keine echt größere linear unabhängige Teilmenge von ${}V$ gibt. Wir behaupten, dass ${}T$ auch ein Erzeugendensystem von ${}V$ ist. Es sei dazu ${}v\in V$. Bei ${}v\in T$ sind wir fertig. Bei ${}v\notin T$ ist ${}T\cup \{v\}$ linear abhängig, d.h. es gibt eine Linearkombination

${}\sum _{i=1}^{n}c_{i}t_{i}+cv=0\,$

mit Elementen ${}t_{i}\in T$ und Koeffizienten ${}c_{i},c\in K$, die nicht alle ${}0$ sind. Dabei kann ${}c$ nicht ${}0$ sein, da sonst eine lineare Abhängigkeit zwischen Elementen aus ${}T$ vorliegen würde. Also kann man ${}v$ als Linearkombination der ${}t_{1},\ldots ,t_{n}$ ausdrücken.

Aufgabe (1 Punkt)

Wir betrachten den Satz „Kein Mensch ist illegal“. Negiere diesen Satz durch eine Existenzaussage.

Lösung

Es gibt einen Menschen, der nicht legal ist.

Aufgabe (3 Punkte)

Erläutere Vor- und Nachteile des axiomatischen Aufbaus der Mathematik.

Lösung Axiomatischer Aufbau/Vor- und Nachteile/Aufgabe/Lösung

Aufgabe (5 (2+3) Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben.

1. Zeige, dass die Substitution ${}{\frac {x}{x}}$ für die Terme die Identität ist.
2. Zeige, dass die Substitution ${}{\frac {x}{x}}$ für die Ausdrücke die Identität ist.

Lösung

1. Wir beweisen die Aussage durch Induktion über den Aufbau der Terme. Für Variablen ist bei ${}y\neq x$ direkt ${}y{\frac {x}{x}}=y$ und ferner ${}x{\frac {x}{x}}=x$. Konstanten bleiben bei jeder Substitution unverändert. Für ein ${}n$-stelliges Funktionssymbol ${}f$ und Terme ${}t_{1},\ldots ,t_{n}$ ist

   ${}(ft_{1}\ldots t_{n}){\frac {x}{x}}=ft_{1}{\frac {x}{x}}\ldots t_{n}{\frac {x}{x}}=ft_{1}\ldots t_{n}\,$

   nach Induktionsvoraussetzung.

2. Wir beweisen die Aussage durch Induktion über den Aufbau der Sprache für alle Variablen gleichzeitig. Wenn ${}\alpha$ eine Identität von Termen oder eine Relationsaussage ist, so ergibt sich die Behauptung unmittelbar aus Teil (1). Der Induktionsschritt für die aussagenlogischen Junktoren ergibt sich unmittelbar aus der Definition der Substitution. Bei ${}\forall y\beta$ mit ${}y\neq x$ kommt ${}y$ nicht im substituierenden Term vor, und daher ist ${}v=y$ und

   ${}(\forall y\beta ){\frac {x}{x}}=\forall y(\beta {\frac {y}{y}})=\forall y\beta \,$

   nach Induktionsvoraussetzung. Bei ${}\forall x\beta$ ist ${}x$ nicht frei in ${}\beta$ und somit ist die relevante Termmenge leer und ${}v=x$, also

   ${}(\forall x\beta ){\frac {x}{x}}=\forall x(\beta {\frac {x}{x}})=\forall x\beta \,$

   nach Induktionsvoraussetzung.

Aufgabe (6 Punkte)

Es sei ${}S$ ein Symbolalphabet erster Stufe, ${}\alpha$ ein ${}S$- Ausdruck und ${}x$ eine Variable. Zeige, dass ${}\vdash \alpha$ genau dann gilt, wenn ${}\vdash \forall x\alpha$ gilt.

Lösung

Nach der Allquantorversion von Axiom 11.1 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

$\vdash \forall x\alpha \rightarrow \alpha {\frac {x}{x}},$

also

$\vdash \forall x\alpha \rightarrow \alpha .$

Daher folgt aus

$\vdash \forall x\alpha$

mittels Modus ponens direkt

$\vdash \alpha .$

Es sei umgekehrt ${}\vdash \alpha$ gegeben. Es sei ${}\beta$ ein beliebiger Ausdruck, in dem ${}x$ nicht vorkomme. Nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) und Modus ponens ergibt sich

$\vdash \beta \rightarrow \alpha$

und

$\vdash \neg \beta \rightarrow \alpha .$

Auf diese beiden abgeleiteten Ausdrücke wird nun die Allquantorversion der Existenzeinführung im Antezedens (also die Alleinführung im Sukzedens) angewendet. Dies ist möglich, da ${}x$ in ${}\beta$ überhaupt nicht und in ${}\forall x\alpha$ nicht frei vorkommt. Man erhält

$\vdash \beta \rightarrow \forall x\alpha$

und

$\vdash \neg \beta \rightarrow \forall x\alpha .$

Daraus ergibt sich mit der Fallunterscheidungsregel

$\vdash \forall x\alpha .$

Aufgabe (4 (2+2) Punkte)

Es sei ${}M$ ein kommutativer Halbring und ${}x,y\in M$. Es sei

${}I:={\left\{u\in M\mid \exists a\exists b\exists c\exists d{\text{ mit }}u+ax+by=cx+dy\right\}}\,.$

1. Zeige, dass ${}I$ die folgenden drei Eigenschaften erfüllt.
   1. ${}0\in I$.
   2. Wenn ${}u,v\in I$ sind, so ist auch ${}u+v\in I$.
   3. Wenn ${}u\in I$ und ${}r\in M$ ist, so ist auch ${}ru\in I$.
2. ${}M$ erfülle nun die Abziehregel. Zeige, dass aus ${}u,v\in I$ mit ${}u=v+z$ auch ${}z\in I$ folgt.

Lösung

Es sei ${}M$ ein kommutativer Halbring und ${}x,y\in M$. Es sei

${}I:={\left\{u\in M\mid \exists a\exists b\exists c\exists d,\,u+ax+by=cx+dy\right\}}\,.$

1. 1. Die Zugehörigkeit ${}0\in I$ ergibt sich aus ${}a=b=c=d=0$.
   2. Sei ${}u+ax+by=cx+dy$ und ${}v+a'x+b'y=c'x+d'y$. Dann ist durch Addition der beiden Gleichungen direkt

      ${}u+v+(a+a')x+(b+b')y=u+v+ax+by+a'x+b'y=cx+dy+c'x+d'y=(c+c')x+(d+d')y\,.$

   3. Sei ${}u+ax+by=cx+dy$. Durch Multiplikation mit ${}r$ ergibt sich direkt

      ${}ru+rax+rby=rcx+rcy\,.$

2. Sei ${}u=v+z$ und ${}u+ax+by=cx+dy$ und ${}v+a'x+b'y=c'x+d'y$. Durch Addition der beiden Gleichungen über Kreuz erhält man

   ${}v+cx+dy+a'x+b'y=u+ax+by+c'x+d'y=v+z+ax+by+c'x+d'y\,.$

   Aufgrund der Abziehregel gilt

   ${}cx+dy+a'x+b'y=z+ax+by+c'x+d'y\,,$

   was die Zugehörigkeit ${}z\in I$ bedeutet.

Aufgabe (3 Punkte)

Charakterisiere den Punkt ${}d$ im skizzierten Graphen mit einem Ausdruck in einer freien Variablen ${}x$ über dem Symbolalphabet, das neben Variablen aus einem einzigen zweistelligen Relationssymbol ${}R$ besteht, das im angegebenen Modell durch einen Pfeil wiedergegeben wird.

Lösung

Den Ausdruck

$\exists u\exists v\exists w(u\neq v\wedge u\neq w\wedge v\neq w\wedge Rux\wedge Rvx\wedge Rwx)$

erfüllen genau die beiden Punkte ${}d$ und ${}e$, da diese für drei Pfeile die Endpunkte sind. Ein Unterschied zwischen ${}d$ und ${}e$ ist, dass bei ${}d$ nur Pfeile von Punkten ankommen, an denen jeweils höchstens ein Pfeil ankommt, während in ${}e$ ein Pfeil, nämlich der von ${}d$ ankommt, auf dem mehr als ein Pfeil ankommt. Daher ist

$\exists u\exists v\exists w(u\neq v\wedge u\neq w\wedge v\neq w\wedge Rux\wedge Rvx\wedge Rwx)\wedge \forall y\forall z\forall s(yRx\wedge zRy\wedge sRy\rightarrow z=s).$