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

Aus Wikiversity

%Daten zur Institution

%\input{Dozentdaten}

%\renewcommand{\fachbereich}{Fachbereich}

%\renewcommand{\dozent}{Prof. Dr. . }

%Klausurdaten

\renewcommand{\klausurgebiet}{ }

\renewcommand{\klausurtyp}{ }

\renewcommand{\klausurdatum}{ . 20}

\klausurvorspann {\fachbereich} {\klausurdatum} {\dozent} {\klausurgebiet} {\klausurtyp}


%Daten für folgende Punktetabelle


\renewcommand{\aeins}{ 3 }

\renewcommand{\azwei}{ 3 }

\renewcommand{\adrei}{ 2 }

\renewcommand{\avier}{ 2 }

\renewcommand{\afuenf}{ 2 }

\renewcommand{\asechs}{ 2 }

\renewcommand{\asieben}{ 5 }

\renewcommand{\aacht}{ 2 }

\renewcommand{\aneun}{ 3 }

\renewcommand{\azehn}{ 7 }

\renewcommand{\aelf}{ 2 }

\renewcommand{\azwoelf}{ 8 }

\renewcommand{\adreizehn}{ 4 }

\renewcommand{\avierzehn}{ 5 }

\renewcommand{\afuenfzehn}{ 3 }

\renewcommand{\asechzehn}{ 3 }

\renewcommand{\asiebzehn}{ 2 }

\renewcommand{\aachtzehn}{ 2 }

\renewcommand{\aneunzehn}{ 4 }

\renewcommand{\azwanzig}{ 64 }

\renewcommand{\aeinundzwanzig}{ }

\renewcommand{\azweiundzwanzig}{ }

\renewcommand{\adreiundzwanzig}{ }

\renewcommand{\avierundzwanzig}{ }

\renewcommand{\afuenfundzwanzig}{ }

\renewcommand{\asechsundzwanzig}{ }

\punktetabelleneunzehn


\klausurnote

\newpage


\setcounter{section}{0}





\inputaufgabeklausurloesung
{3}
{

Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Eine \stichwort {maximal widerspruchsfreie} {} prädikatenlogische Ausdrucksmenge $\Gamma \subseteq L^S$.

}{Ein \stichwort {topologischer Filter} {} auf einem \definitionsverweis {topologischen Raum}{}{} $X$.

}{Die \stichwort {Interpretation der Terme} {} zu einem \definitionsverweis {Symbolalphabet}{}{} $S$ in einer gegebenen $S$-\definitionsverweis {Interpretation}{}{} auf einer Grundmenge $M$.

}{Eine \stichwort {funktional abgeschlossene} {} Teilmenge
\mavergleichskette
{\vergleichskette
{T }
{ \subseteq }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} einer $S$-\definitionsverweis {Struktur}{}{} $M$, wobei $S$ ein \definitionsverweis {erststufiges Symbolalphabet}{}{} bezeichnet.

}{Eine \stichwort {vollständige} {} Theorie
\mathl{T \subseteq L^S_0}{.}

}{Ein \stichwort {modallogisches Modell} {.} }

}
{

\aufzaehlungsechs{Die Menge $\Gamma$ heißt maximal widerspruchsfrei, wenn sie \definitionsverweis {widerspruchsfrei}{}{} ist und wenn jede Hinzunahme eines jeden Ausdrucks
\mathl{\alpha \not\in \Gamma}{} die Menge widersprüchlich macht. }{Ein System $F$ aus offenen Teilmengen von $X$ heißt Filter, wenn folgende Eigenschaften gelten \zusatzklammer {\mathlk{U,V}{} seien offen} {} {.} \aufzaehlungdrei{
\mathl{X \in F}{.} }{Mit
\mathl{U \in F}{} und
\mavergleichskette
{\vergleichskette
{U }
{ \subseteq }{V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist auch
\mathl{V \in F}{.} }{Mit
\mathl{U \in F}{} und
\mathl{V \in F}{} ist auch
\mathl{U \cap V \in F}{.} } }{Die Terminterpretation
\mathl{I(t) \in M}{} wird induktiv über den Aufbau der Terme für jeden $S$-\definitionsverweis {Term}{}{} $t$ definiert. \aufzaehlungzwei {Für jede Konstante $c$ und jede Variable $x$ ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also
\mathl{I(c)=c^M}{} und
\mathl{I(x)=x^M}{.} } {Wenn
\mathl{t_1 , \ldots , t_n}{} Terme mit Interpretationen
\mathl{I(t_1) , \ldots , I(t_n)}{} sind und wenn $f$ ein $n$-stelliges Funktionssymbol ist, so wird der Term
\mathl{ft_1 \ldots t_n}{} als
\mathl{f^M(I(t_1) , \ldots , I(t_n))}{} interpretiert. } }{Die Teilmenge $T$ heißt funktional abgeschlossen, wenn für jede Konstante
\mathl{c \in S}{} das Element
\mathl{c^M}{} zu $T$ gehört und für jedes $k$-stellige Funktionssymbol $f$ und beliebige Elemente
\mathl{m_1 , \ldots , m_k \in T}{} auch
\mathl{f^M(m_1 , \ldots , m_k )}{} zu $T$ gehört. }{Die \definitionsverweis {Theorie}{}{} $T$ heißt vollständig, wenn für jeden Satz
\mathl{\alpha \in L^S_0}{} gilt
\mathl{\alpha \in T}{} oder
\mathl{\neg \alpha \in T}{.} }{Unter einem modallogischen Modell versteht man einen \definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} zusammen mit einer \definitionsverweis {Wahrheitsbelegung}{}{} $\mu$ für die \definitionsverweis {Aussagenvariablen}{}{} für jeden Knotenpunkt
\mathl{w \in M}{.} }


}





\inputaufgabeklausurloesung
{3}
{

Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz von Henkin.}{Der Satz über das \stichwort {Halteproblem} {.}}{Die \stichwort {Unentscheidbarkeit der Arithmetik} {.}}

}
{

\aufzaehlungdrei{Es sei $\Gamma$ eine Menge an $S$-\definitionsverweis {Ausdrücken}{}{} \zusatzklammer {über einem Symbolalphabet $S$} {} {,} die \definitionsverweis {maximal widerspruchsfrei}{}{} ist und \definitionsverweis {Beispiele enthält}{}{.} Dann ist die durch die kanonische Termidentifizierung gegebene Interpretation ein Modell für $\Gamma$.}{Die Menge
\mathdisp {{ \left\{ n \in \N \mid n \text { ist die Nummer eines Registerprogramms } P \text{ und } P(0) \text{ hält an} \right\} }} { }
ist nicht $R$-\definitionsverweis {entscheidbar}{}{.}}{Die Menge der wahren arithmetischen Ausdrücke \zusatzklammer {ohne freie Variablen} {} {} ist nicht $R$-\definitionsverweis {entscheidbar}{}{.}}


}





\inputaufgabeklausurloesung
{2}
{

$E$ wurde ermordet. Es gelten folgende Sachverhalte. \aufzaehlungsechs{Der Mörder ist $A$ oder $B$ oder $C$ oder $D$. }{Wenn $C$ der Mörder ist, dann ist $D$ nicht der Mörder oder $A$ ist der Mörder. }{$A,B,C,D$ sind alle verschieden. }{Es gibt genau einen Mörder. }{Wenn $A$ nicht der Mörder ist, dann ist $D$ nicht der Mörder. }{$A$ ist genau dann der Mörder, wenn $B$ der Mörder ist. } Wer ist der Mörder?

}
{

Aus (6), (3) und (4) folgt, dass $A$ und $B$ beide nicht der Mörder sind, denn sonst wären beide der Mörder. Nach (5) ist somit auch $D$ nicht der Mörder. Wegen (1) muss also $C$ der Mörder sein. \zusatzklammer {(2) wird nicht verwendet} {.} {}


}





\inputaufgabeklausurloesung
{2}
{

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt. \wahrheitstabelledreieins{ } {\tabellenzeilevier {$ p $} {$ q $} {$ r $} {$? $} } {\tabellendoppelzeilevier {w} {w} {w} {w} {w} {w} {f} {f} } {\tabellendoppelzeilevier {w} {f} {w} {w} {w} {f} {f} {f} } {\tabellendoppelzeilevier {f} {w} {w} {f} {f} {w} {f} {w} } {\tabellendoppelzeilevier {f} {f} {w} {f} {f} {f} {f} {w} }

}
{


\mathdisp {p \leftrightarrow r} { . }


}





\inputaufgabeklausurloesung
{2}
{

Erläutere die Beziehung zwischen dem \definitionsverweis {Modus ponens}{}{} und
\mathdisp {\vdash \alpha \wedge { \left( \alpha \rightarrow \beta \right) } \rightarrow \beta} { . }

}
{Modus ponens/Interne Version/Erläuterung/Aufgabe/Lösung }





\inputaufgabeklausurloesung
{2}
{

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

}
{

Es gilt
\mathdisp {\vdash \neg \alpha \wedge \alpha \rightarrow \beta} { }
nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (5). Nach der Voraussetzung und Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (5) ergibt sich daraus
\mathl{\vdash \beta}{.}


}





\inputaufgabeklausurloesung
{5 (2+2+1)}
{

Es sei $N$ ein einstelliges Funktionssymbol, $F$ und $G$ seien zweistellige Funktionssymbole und
\mathl{x,y}{} seien Variablen.

Wir betrachten die folgenden Modelle \zusatzklammer {wobei $M$ die Grundmenge bezeichnet} {} {.}

a)
\mavergleichskette
{\vergleichskette
{M }
{ = }{\R }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} $N$ ist die Quadrierung, $F$ die Addition und $G$ die Multiplikation.


b)
\mavergleichskette
{\vergleichskette
{M }
{ = }{ C^\infty(\R,\R) }
{ = }{ { \left\{ f:\R \rightarrow \R \mid f \text{ unendlich oft differenzierbar} \right\} } }
{ }{ }
{ }{ }
} {}{}{,} $N$ ist das Differenzieren von Funktionen, $F$ die Multiplikation und $G$ die Addition von Funktionen. Bestimme, ob in diesen Modellen die folgenden Aussagen wahr werden. \aufzaehlungdrei{
\mathdisp {\forall x \forall y { \left( NFxy = GFxNyFNxy \right) }} { . }
}{
\mathdisp {\forall y \exists x { \left( NFxy = GFxNyFNxy \right) }} { . }
}{
\mathdisp {\exists y \forall x { \left( NFxy = GFxNyFNxy \right) }} { . }
}

}
{

Im ersten Modell ist $NFxy$ als
\mathl{(x+y)^2}{} und
\mathl{GFxNyFNxy}{} als
\mathl{(x+y^2) \cdot ( x^2 +y)}{} zu interpretieren, wobei $x,y$ reelle Zahlen sind. \aufzaehlungdrei{Die Gleichung
\mavergleichskettedisp
{\vergleichskette
{ (x+y)^2 }
{ =} { ( x+y^2) \cdot ( x^2 +y) }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt in $\R$ definitiv nicht für alle reelle Zahlen, beispielsweise gilt sie für
\mavergleichskette
{\vergleichskette
{x }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{y }
{ = }{2 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} nicht. }{Wir schreiben die Gleichung als
\mavergleichskettedisp
{\vergleichskette
{ y^3 +x^2y^2 + x^3+xy-x^2-2xy-y^2 }
{ =} { 0 }
{ } { }
{ } { }
{ } { }
} {}{}{.} Für ein beliebiges aber fixiertes $x$ ist der Ausdruck links ein normiertes Polynom vom Grad $3$ in $y$. Dieses besitzt nach dem Zwischenwertsatz eine Nullstelle, deshalb ist die Aussage wahr. }{Zu jedem $y$ ist der Ausdruck links aus (2) ein Polynom in $x$ vom Grad $3$, also definitiv nicht das Nullpolynom, die Aussage ist also falsch. }

Im zweiten Modell ist $NFxy$ als
\mathl{(x \cdot y)'}{} und
\mathl{GFxNyFNxy}{} als
\mathl{( x' \cdot y) + ( x \cdot y')}{} zu interpretieren, wobei $x,y$ unendlich oft differenzierbare Funktionen sind. Dies ist die Produktregel für die Ableitung, also wahr für beliebige $x,y$. Damit gilt insbesondere auch (2) und (3), da es ja unendlich oft differenzierbare Funktionen gibt.


}





\inputaufgabeklausurloesung
{2}
{

Es sei ein \definitionsverweis {Symbolalphabet}{}{} $S$ erster Stufe mit der Variablenmenge
\mavergleichskettedisp
{\vergleichskette
{V }
{ =} {\{x,y,z,w\} }
{ } { }
{ } { }
{ } { }
} {}{}{} gegeben und eine $S$-\definitionsverweis {Interpretation}{}{} $I$ in der Menge $\R$ mit
\mathdisp {I(x)= 5,\, I(y)= \pi, \, I(z) = -\sqrt{2}, \, I(w) = -3} { . }
Bestimme die Werte von
\mathl{x,y,z,w}{} bei der Interpretation
\mavergleichskette
{\vergleichskette
{J }
{ \defeq }{ I { \frac{ e , -\sqrt{2} , { \frac{ 4 }{ 7 } } , I(x) }{ x,z,x,y } } }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} auf $V$.

}
{

Es ist
\mavergleichskettedisp
{\vergleichskette
{J }
{ \defeq} { I { \frac{ e , -\sqrt{2} , { \frac{ 4 }{ 7 } } , I(x) }{ x,z,x,y } } }
{ =} { I { \frac{ e , -\sqrt{2} , { \frac{ 4 }{ 7 } } , 5 }{ x,z,x,y } } }
{ } { }
{ } { }
} {}{}{.} Ferner ist dieser Ausdruck von innen nach außen, bzw. von links nach rechts zu lesen, also als
\mathdisp {{ \left( { \left( { \left( I { \frac{ e }{ x } } \right) } { \frac{ - \sqrt{2} }{ z } } \right) } { \frac{ { \frac{ 4 }{ 7 } } }{ x } } \right) } { \frac{ 5 }{ y } }} { . }
Daher ist
\mathdisp {J(x) = { \frac{ 4 }{ 7 } } ,\, J(y) = 5 ,\, J(z) = - \sqrt{2} ,\, J(w) = -3} { . }


}





\inputaufgabeklausurloesung
{3}
{

Es seien $x,y,z$ Variablen \zusatzklammer {mit der angegebenen Reihenfolge} {} {,} $c$ eine Konstante und $f$ ein einstelliges Funktionssymbol. \aufzaehlungdrei{Bestimme
\mathdisp {(\exists x (x=c)) { \frac{ z }{ x } }} { . }
}{Bestimme
\mathdisp {( \exists x (x=c)) { \frac{ x }{ x } }} { . }
}{Bestimme
\mathdisp {( \exists x (x=c) ) { \frac{ fx }{ x } }} { . }
}

}
{

Die zu substituierende Variable $x$ kommt im Ausdruck
\mathl{\exists x (x=c)}{} nicht frei vor. Somit ist jedenfalls für den jeweiligen Term $t$
\mavergleichskettedisp
{\vergleichskette
{ (\exists x (x = c)) { \frac{ t }{ x } } }
{ =} { \exists v (( x = c) { \frac{ v }{ x } } ) }
{ } { }
{ } { }
{ } { }
} {}{}{.} Da die relevante Termmenge leer ist, ist
\mavergleichskettedisp
{\vergleichskette
{v }
{ =} {x }
{ } { }
{ } { }
{ } { }
} {}{}{} Also ist \aufzaehlungdrei{
\mavergleichskettedisp
{\vergleichskette
{ (\exists x ( x = c)) { \frac{ z }{ x } } }
{ =} { \exists x ((x = c)) { \frac{ x }{ x } } ) }
{ =} { \exists x (x = c) }
{ } { }
{ } { }
} {}{}{.} }{
\mavergleichskettedisp
{\vergleichskette
{ (\exists x (x = c)) { \frac{ x }{ x } } }
{ =} { \exists x ((x = c) { \frac{ x }{ x } } ) }
{ =} { \exists x (x = c) }
{ } { }
{ } { }
} {}{}{.} }{
\mavergleichskettedisp
{\vergleichskette
{ (\exists x (x = c)) { \frac{ fx }{ x } } }
{ =} { \exists x ((x = c) { \frac{ x }{ x } } ) }
{ =} { \exists x (x = c) }
{ } { }
{ } { }
} {}{}{.} }


}





\inputaufgabeklausurloesung
{7}
{

Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.

}
{

Es sei
\mathl{\alpha \frac{y}{x} \rightarrow \beta}{} \definitionsverweis {allgemeingültig}{}{,} d.h.
\mathdisp {I \vDash \alpha \frac{y}{x} \rightarrow \beta} { }
für jede $S$-\definitionsverweis {Interpretation}{}{} $I$. Wir müssen zeigen, dass dann auch
\mathl{\exists x \alpha \rightarrow \beta}{} allgemeingültig ist \zusatzklammer {unter den gegebenen Voraussetzungen} {} {.} Es sei dazu $I$ eine Interpretation mit
\mathdisp {I \vDash \exists x \alpha} { . }
Aufgrund der \definitionsverweis {Modellbeziehung}{}{} bedeutet dies, dass es ein
\mavergleichskette
{\vergleichskette
{m }
{ \in }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \zusatzklammer {aus der Grundmenge der Interpretation} {} {} mit
\mathdisp {I \frac{m}{x} \vDash \alpha} { }
gibt. Die Variable $y$ kommt nach Voraussetzung in $\exists x \alpha$ nicht frei vor, d.h. bei
\mavergleichskette
{\vergleichskette
{y }
{ \neq }{x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} dass $y$ in $\alpha$ nicht frei vorkommt. Wir können daher das Koinzidenzlemma anwenden und erhalten
\mathdisp {{ \left( I \frac{m}{x} \right) } \frac{m}{y} \vDash \alpha} { . }
Diese Aussage gilt trivialerweise auch bei
\mavergleichskette
{\vergleichskette
{x }
{ = }{y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Damit gilt auch
\mathdisp {{ \left( I \frac{m}{y} \right) } \frac{m}{x} \vDash \alpha} { . }
Wir schreiben dies \zusatzklammer {etwas künstlich} {} {} als
\mathdisp {{ \left( I \frac{m}{y} \right) } \frac{ { \left( I\frac{m}{y} \right) }(y) }{x} \vDash \alpha} { . }
Darauf können wir das Substitutionslemma \zusatzklammer {für die Interpretation
\mavergleichskettek
{\vergleichskettek
{ J }
{ = }{I \frac{m}{y} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und den Term $y$} {} {} anwenden und erhalten
\mathdisp {I \frac{m}{y} \vDash \alpha \frac{y}{x}} { . }
Wegen der vorausgesetzten Allgemeingültigkeit von
\mathl{\alpha \frac{y}{x} \rightarrow \beta}{} folgt
\mathdisp {I \frac{m}{y} \vDash \beta} { . }
Da $y$ in $\beta$ nicht frei vorkommt, liefert das Koinzidenzlemma
\mathdisp {I \vDash \beta} { . }


}





\inputaufgabeklausurloesung
{2}
{

Zeige, dass in einem \definitionsverweis {kommutativen Halbring}{}{} die Beziehung
\mavergleichskette
{\vergleichskette
{0 \cdot 0 }
{ = }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt.

}
{

Dies ergibt sich aus
\mavergleichskettedisp
{\vergleichskette
{0 \cdot 0 }
{ =} { 0 \cdot 0 +0 }
{ =} { 0 \cdot 0 + 0 \cdot 1 }
{ =} { 0 \cdot (0+1) }
{ =} { 0 \cdot 1 }
} {
\vergleichskettefortsetzung
{ =} { 0 }
{ } {}
{ } {}
{ } {}
}{}{.}


}





\inputaufgabeklausurloesung
{8 (1+2+3+2)}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $L^S$ die zugehörige Sprache erster Stufe. Es sei $I$ eine $S$-\definitionsverweis {Interpretation}{}{} mit der Grundmenge $N$ und es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \defeq }{ I^\vDash }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit der \definitionsverweis {zugehörigen Äquivalenzrelation}{}{} $\sim$ auf der Termmenge $T$. \aufzaehlungvier{Zeige, dass
\mavergleichskette
{\vergleichskette
{s }
{ \sim }{t }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} genau dann gilt, wenn
\mavergleichskette
{\vergleichskette
{I(s) }
{ = }{I(t) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt. }{Zeige, dass es eine injektive Abbildung \maabbdisp {\psi} {T/\sim } { N } {} mit
\mavergleichskettedisp
{\vergleichskette
{ \psi([t]) }
{ =} { I(t) }
{ } { }
{ } { }
{ } { }
} {}{}{} gibt. }{Zeige, dass $\psi$ ein $S$-\definitionsverweis {Homomorphismus}{}{} ist, wenn die Quotientenmenge
\mathl{T/\sim}{} mit der kanonischen $S$-\definitionsverweis {Struktur}{}{} versehen wird. }{Es sei $J$ die kanonische Interpretation auf $T/\sim$. Es sei vorausgesetzt, dass die Terminterpretation für $N$ surjektiv sei. Zeige, dass
\mathl{I \vDash \alpha}{} genau dann gilt, wenn
\mathl{J \vDash \alpha}{} gilt. }

}
{

\aufzaehlungvier{Es ist
\mathl{s \sim t}{} genau dann, wenn
\mathl{s=t \in \Gamma=I^\vDash}{} ist, und dies ist genau dann der Fall, wenn
\mathl{I \vDash s=t}{} gilt, was nach Definition
\mavergleichskette
{\vergleichskette
{I(s) }
{ = }{I(t) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} bedeutet. }{Die Termabbildung \maabbeledisp {I} {T} {N } {t} { I(t) } {,} besitzt nach Teil (1) die Eigenschaft, dass äquivalente Terme auf das gleiche Element abgebildet werden. Dies bedeutet nach Lemma 11.13 (Diskrete Mathematik (Osnabrück 2020)), dass es eine Abbildung \maabbdisp {\psi} {T/\sim } { N } {} mit
\mavergleichskette
{\vergleichskette
{ \psi([t]) }
{ = }{ I(t) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt. Da nichtäquivalente Terme nach Teil (1) unter $I$ auf verschiedene Elemente abgebildet werden, werden verschiedene Klassen unter $\psi$ auf verschiedene Elemente abgebildet und somit ist $\psi$ injektiv. }{Sei
\mavergleichskettedisp
{\vergleichskette
{M }
{ =} { T/\sim }
{ } { }
{ } { }
{ } { }
} {}{}{.} Für eine Konstante
\mathl{c \in T}{} ist
\mavergleichskettedisp
{\vergleichskette
{ \psi (c^M) }
{ =} { \psi( [c]) }
{ =} { I(c) }
{ =} { c^N }
{ } { }
} {}{}{.} Für ein $n$-stelliges Funktionssymbol $f$ und $n$ Termklassen
\mathl{[t_1] , \ldots , [t_n]}{} ist
\mavergleichskettealign
{\vergleichskettealign
{ \psi( f^M ( [t_1] , \ldots , [t_n])) }
{ =} { \psi( [ ft_1 \ldots t_n ]) }
{ =} { I( ft_1 \ldots t_n ) }
{ =} { f^N (I(t_1) , \ldots , I( t_n ) ) }
{ =} { f^N (\psi ([t_1]) , \ldots , \psi ([t_n]) ) }
} {} {}{.} Es sei nun eine $n$-stellige Relation $R$ und $n$ Termklassen
\mathl{[t_1] , \ldots , [t_n]}{} gegeben und sei die Gültigkeit von
\mathl{R^M [t_1] , \ldots , [t_n]}{} in $M$ vorausgesetzt. Dies bedeutet, dass
\mathl{Rt_1 \ldots t_n \in \Gamma=I^{\vDash}}{} ist. Somit ist
\mathl{I \vDash Rt_1 \ldots t_n}{,} was
\mathl{R^N (I(t_1) , \ldots , I(t_n))}{} bedeutet. Somit ist
\mathl{R^N (\psi([t_1]) , \ldots , \psi([t_n]))}{.} Es liegt also ein $S$-\definitionsverweis {Homomorphismus}{}{} vor. }{Nach Definition von $\Gamma$ ist $\alpha \in \Gamma$ genau dann, wenn $I \vDash \alpha$ gilt. Nach Lemma 14.5 (Einführung in die mathematische Logik (Osnabrück 2021)) ist $\Gamma$ maximal widerspruchsfrei und enthält Beispiele und nach dem Satz von Henkin ist
\mavergleichskettedisp
{\vergleichskette
{\Gamma }
{ =} { J^\vDash }
{ } { }
{ } { }
{ } { }
} {}{}{.} }


}





\inputaufgabeklausurloesung
{4}
{

Bestimme die \definitionsverweis {Äquivalenzklassen}{}{} zur \definitionsverweis {elementaren Äquivalenz}{}{} in der \definitionsverweis {Gruppe}{}{}
\mathl{\Z/(2) \times \Z/(3)}{} zum Symbolalphabet
\mavergleichskette
{\vergleichskette
{S }
{ = }{ \{ 0,+ \} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

}
{

Die Äquivalenzklassen sind
\mathdisp {\{ (0,0) \} ,\, \{ (1,0) \} , \, \{ (0,1), (0,2) \}, \, \{ (1,1), (1,2) \}} { . }
Nach \zusatzklammer {dem Zusatz zu} {} {} Satz 16.7 (Einführung in die mathematische Logik (Osnabrück 2021)) sind Elemente, die unter einem Automorphismus aufeinander abgebildet werden, zueinander elementar äquivalent. Die Abbildung, die in der ersten Komponente die Identität und in der zweiten Komponente \mathkor {} {1} {und} {2} {} vertauscht, ist ein Automorphismus. Daher sind die in den zweielementigen Klassen angegebenen Elemente zueinander elementar äquivalent. Es ist also noch zu zeigen, dass die vier Klassen voneinander trennbar sind. Die in der angegebenen Sprache formulierbare Eigenschaft
\mavergleichskette
{\vergleichskette
{ x }
{ = }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} wird nur durch das neutrale Element erfüllt und ist somit ein charakterisierender Ausdruck für $\{ (0,0) \}$. Die Eigenschaft
\mathdisp {x \neq 0 \wedge x+x =0} { }
charakterisiert die zweite Klasse. Die Eigenschaft
\mathdisp {x \neq 0 \wedge x+x+x =0} { }
charakterisiert die dritte Klasse. Die Eigenschaft
\mathdisp {x+x \neq 0 \wedge x+x+x \neq 0 \wedge x+x+x+x+x+x =0} { }
\zusatzklammer {der letzte Teil der Konjunktion ist nicht nötig} {} {} charakterisiert die vierte Klasse.


}





\inputaufgabeklausurloesung
{5}
{

Man entwerfe ein Programm für eine Registermaschine, das bei der Eingabe $n$ im ersten Register den Rest bei der Division mit Rest von $n$ durch $5$ ausgibt.

}
{Registermaschine/Modulo 5/Rest/Aufgabe/Lösung }





\inputaufgabeklausurloesung
{3 (2+1)}
{

\aufzaehlungzwei {Zeige, dass die Teilmenge der natürlichen Zahlen, die man als Summe von drei Quadraten schreiben kann, \definitionsverweis {arithmetisch repräsentierbar}{}{} ist. } {Formuliere in der arithmetischen Sprache, dass die $7$ keine Summe von drei Quadraten ist. }

}
{

\aufzaehlungzwei {Wir betrachten die Ausdruck
\mavergleichskettedisp
{\vergleichskette
{ \Psi }
{ =} { \exists u \exists v \exists w (x = u \cdot u + v \cdot v + w \cdot w) }
{ } { }
{ } { }
{ } { }
} {}{}{} in der einen freien Variablen $x$. Offenbar kann man eine natürliche Zahl $n$ genau dann als Summe von drei Quadraten schreiben, wenn innerhalb von $\N$ der Ausdruck
\mathl{\Psi (n)}{} gilt. } {Eine Formulierung ist
\mathdisp {\forall u \forall v \forall w \neg( 1+1+1+1+1+1+1 = u \cdot u + v \cdot v + w \cdot w )} { . }
}


}





\inputaufgabeklausurloesung
{3}
{

Beweise den ersten Gödelschen Unvollständigkeitssatz mit dem Unvollständigkeitslemma.

}
{

 Wir nehmen an, dass $\Gamma^\vdash$ vollständig ist. Da $\Gamma$ \definitionsverweis {aufzählbar}{}{} ist, ist $\Gamma^\vdash$ nach Lemma 21.9 (Einführung in die mathematische Logik (Osnabrück 2021)) \definitionsverweis {aufzählbar}{}{} und nach Satz 21.10 (Einführung in die mathematische Logik (Osnabrück 2021)) auch \definitionsverweis {entscheidbar}{}{.} Da $\Gamma$ \definitionsverweis {Repräsentierungen erlaubt}{}{,} ist insbesondere $\Gamma^\vdash$ repräsentierbar. Daher sind die Voraussetzungen von Lemma 23.1 (Einführung in die mathematische Logik (Osnabrück 2021)) erfüllt und es ergibt sich ein Widerspruch zur angenommenen Vollständigkeit.


}





\inputaufgabeklausurloesung
{2}
{

Zeige, dass in der $K$-\definitionsverweis {Modallogik}{}{} das Schema
\mathdisp {\Box \alpha \wedge \Box \neg \alpha \rightarrow \Box \beta} { }
ableitbar ist.

}
{

Aus der aussagenlogischen Tautologie
\mathdisp {\vdash \alpha \wedge \neg \alpha \rightarrow \beta} { }
ergibt sich mit Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1)
\mathdisp {\vdash \Box ( \alpha \wedge \neg \alpha ) \rightarrow \Box \beta} { . }
Wegen Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (4) gilt
\mathdisp {\vdash \Box \alpha \wedge \Box \neg \alpha \rightarrow \Box ( \alpha \wedge \neg \alpha)} { . }
Der Kettenschluss liefert
\mathdisp {\vdash \Box \alpha \wedge \Box \neg \alpha \rightarrow \Box \beta} { . }


}





\inputaufgabeklausurloesung
{2}
{






\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Baby Category 2.svg} }
\end{center}
\bildtext {} }

\bildlizenz { Baby Category 2.svg } {} {Melikamp} {Commons} {CC-by-sa 3.0} {}

Wir arbeiten mit den Aussagenvariablen
\mathl{p,q,r}{.} Im Weltpunkt $a$ gelte
\mathdisp {a \vDash p, q , \neg r} { }
und im Weltpunkt $b$ gelte
\mathdisp {b \vDash p, \neg q , r} { . }
Bestimme die Wahrheitswerte von
\mathl{\Box p \wedge \Diamond ( \neg q) \rightarrow \Box r}{} in den beiden Weltpunkten.

}
{

Wegen
\mathl{a \vDash p}{} und
\mathl{b \vDash p}{} gilt
\mathl{a \vDash \Box p}{.} Wegen
\mathl{b \vDash \neg q}{} gilt
\mathl{a \vDash \Diamond \neg q}{} und somit gilt in $a$ der Vordersatz der Aussage. Wegen
\mathl{a \vDash \neg r}{} gilt
\mathl{a \vDash \neg \Box r}{.} Daher ist der Nachsatz der Aussage falsch in $a$ und somit ist die Gesamtaussage dort falsch.

Von $b$ aus ist nur $b$ erreichbar ist, dort gilt $r$ also auch $\Box r$. Damit gilt der Nachsatz und damit die Gesamtaussage in $b$.


}





\inputaufgabeklausurloesung
{4}
{

Beweise den Vollständigkeitssatz der Modallogik.

}
{

Die Hinrichtung ergibt sich aus Lemma 26.9 (Einführung in die mathematische Logik (Osnabrück 2021)). Für die Rückrichtung nehmen wir
\mathdisp {\Gamma \not \vdash \alpha} { }
an. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ \Gamma' }
{ =} { \Gamma \cup \{ \neg \alpha \} }
{ } { }
{ } { }
{ } { }
} {}{}{} \zusatzklammer {aussagenlogisch} {} {} nicht widersprüchlich und wir müssen zeigen, dass $\Gamma'$ durch ein $\Gamma$-modallogisches Modell erfüllbar ist. Wir betrachten dazu das $\Gamma$-\definitionsverweis {universelle modallogische Modell}{}{} $(U_\Gamma,R,\nu)$, in dem $\Gamma$ \zusatzklammer {in jedem Weltpunkt} {} {} gilt. Nach Lemma 27.1 (Einführung in die mathematische Logik (Osnabrück 2021)) gibt es eine maximal widerspruchsfreie $\Gamma'$-Ausdrucksmenge $\tilde{\Gamma}$, die wir als Welt
\mavergleichskette
{\vergleichskette
{W }
{ = }{ \tilde{\Gamma} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} in $U_\Gamma$ betrachten können. Nach Lemma 27.6 (Einführung in die mathematische Logik (Osnabrück 2021)) gilt
\mathl{W \vDash \tilde{\Gamma}}{,} was insbesondere die Gültigkeit von
\mathl{\Gamma \cup \{ \neg \alpha\}}{} in $W$ zeigt.


}