Kurs:Einführung in die mathematische Logik/10/Klausur mit Lösungen/latex
%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}{ 1 }
\renewcommand{\avier}{ 2 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 3 }
\renewcommand{\asieben}{ 6 }
\renewcommand{\aacht}{ 4 }
\renewcommand{\aneun}{ 3 }
\renewcommand{\azehn}{ 1 }
\renewcommand{\aelf}{ 2 }
\renewcommand{\azwoelf}{ 4 }
\renewcommand{\adreizehn}{ 3 }
\renewcommand{\avierzehn}{ 3 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 4 }
\renewcommand{\aachtzehn}{ 0 }
\renewcommand{\aneunzehn}{ 5 }
\renewcommand{\azwanzig}{ 4 }
\renewcommand{\aeinundzwanzig}{ 54 }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellezwanzig
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden
\zusatzklammer {kursiv gedruckten} {} {} Begriffe.
\aufzaehlungsechs{Die
\stichwort {Ableitbarkeit} {}
\mathl{\Gamma \vdash \alpha}{} eines $S$-Ausdrucks $\alpha$ aus einer Menge $\Gamma$ an
$S$-\definitionsverweis {Ausdrücken}{}{.}
}{Eine \stichwort {Abbildung} {} $F$ von einer Menge $L$ in eine Menge $M$.
}{Die \stichwort {endliche Axiomatisierbarkeit} {} einer
\definitionsverweis {Theorie}{}{}
\mathl{T \subseteq L^S_0}{.}
}{Ein \stichwort {reell-abgeschlossener} {} \definitionsverweis {Körper}{}{.}
}{Die Eigenschaft einer Menge $\Gamma$ von \definitionsverweis {arithmetischen Ausdrücken}{}{,} \stichwort {Repräsentierungen zu erlauben} {.}
}{Das \definitionsverweis {modallogische}{}{} \stichwort {Symmetrieaxiom} {.} }
}
{
\aufzaehlungsechs{Man sagt, dass $\alpha$ aus $\Gamma$ \stichwort {ableitbar} {} ist, wenn es endlich viele Ausdrücke
\mathl{\alpha_1 , \ldots , \alpha_n \in \Gamma}{} derart gibt, dass
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \alpha} { }
gilt.
}{Eine Abbildung $F$ von $L$ nach $M$ ist dadurch gegeben, dass jedem Element der Menge $L$ genau ein Element der Menge $M$ zugeordnet wird.
}{Die endliche Axiomatisierbarkeit von $T$ liegt vor, wenn es endlich viele Sätze
\mathl{\alpha_1 , \ldots , \alpha_n \in L^S_0}{} mit
\mavergleichskette
{\vergleichskette
{ T
}
{ = }{\{ \alpha_1 , \ldots , \alpha_n\}^\vdash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt.
}{Ein
\definitionsverweis {angeordneter Körper}{}{}
$K$ heißt
reell-abgeschlossen,
wenn folgende Eigenschaften gelten.
\aufzaehlungzwei {Jedes nichtnegative Element aus $K$ besitzt eine Quadratwurzel in $K$.
} {Jedes Polynom
\mathl{P \in K[X]}{} mit ungeradem Grad besitzt in $K$ eine Nullstelle.
}
}{Man sagt, dass $\Gamma$
Repräsentierungen erlaubt,
wenn $\Gamma$ jede
$R$-\definitionsverweis {berechenbare Relation}{}{}
und jede
$R$-\definitionsverweis {berechenbare Funktion}{}{}
\definitionsverweis {repräsentiert}{}{.}
}{Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\alpha \rightarrow \Box \Diamond \alpha} { }
nennt man
Symmetrieaxiom.
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz von Wiles (Großer Fermat).}{Der Satz von Henkin.}{Der \stichwort {Fixpunktsatz} {} für arithmetische Ausdrücke.}
}
{
\aufzaehlungdrei{Die diophantische Gleichung
\mavergleichskettedisp
{\vergleichskette
{ x^n+y^n
}
{ =} { z^n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besitzt für kein
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine ganzzahlige nichttriviale Lösung.}{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$.}{Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube. Dann gibt es zu jedem
\mathl{\alpha \in L^{\rm Ar}_1}{} einen Satz
\mathl{q \in L^{\rm Ar}_0}{} mit
\mathdisp {\Gamma \vdash q \longleftrightarrow \alpha ( GN(q))} { . }
}
}
\inputaufgabeklausurloesung
{1}
{
Petra fliegt zu ihrer ersten internationalen Konferenz. Als sie auf dem Weg zum Flughafen ihre Wohnung \zusatzklammer {sie wohnt allein} {} {} verlässt und gerade die Wohnungstür zugemacht hat, merkt sie \zusatzklammer {eine der drei Möglichkeiten} {} {} \aufzaehlungdrei{Sie hat ihr Flugticket auf dem Schreibtisch vergessen. }{Sie hat ihre Schlüssel auf dem Schreibtisch vergessen. }{Sie hat ihren Reisepass auf dem Schreibtisch vergessen. } Was ist am schlimmsten?
}
{
(1) und (3) sind jedenfalls nicht schlimm, da Petra die Schlüssel hat und daher direkt die vergessenen Sachen holen kann. Bei (2) hat sie dagegen ein Problem, wenn sie zurückkommt.
}
\inputaufgabeklausurloesung
{2}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Mercedes Benz Atego 1624 container truck.JPG} }
\end{center}
\bildtext {} }
\bildlizenz { Mercedes Benz Atego 1624 container truck.JPG } {} {High Contrast} {Commons} {CC-ba-sa 3.0} {}
Die Absetzmulde ist voll mit Schutt und soll durch eine leere Mulde ersetzt werden, die das Absetzkipperfahrzeug bringt, das auch die volle Mulde mitnehmen soll. Auf dem Fahrzeug und auf dem Garagenvorplatz, wo die volle Mulde steht, ist nur Platz für eine Mulde. Dafür kann die Straße als Zwischenablage genutzt werden. Wie viele Ladevorgänge sind vor Ort nötig, bis der Gesamtaustausch vollständig abgeschlossen ist?
}
{
\aufzaehlungsechs{Leere Mulde auf dem Straßenplatz $A$ abladen. }{Volle Mulde auf Fahrzeug hochladen. }{Volle Mulde auf dem Straßenplatz $B$ abladen. }{Leere Mulde auf Fahrzeug hochladen. }{Leere Mulde auf den Garagenvorplatz abladen. }{Volle Mulde auf Fahrzeug hochladen. } Es sind also sechs Ladevorgänge nötig.
}
\inputaufgabeklausurloesung
{3}
{
Beweise den Satz, dass es unendlich viele Primzahlen gibt.
}
{
Angenommen, die Menge aller Primzahlen sei endlich, sagen wir
\mathl{\{p_1,p_2 , \ldots , p_r\}}{.} Man betrachtet die Zahl
\mavergleichskettedisp
{\vergleichskette
{N
}
{ =} {p_1\cdot p_2\cdot p_3 { \cdots } p_r\ + 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Zahl ist durch keine der Primzahlen $p_i$ teilbar, da bei Division von $N$ durch $p_i$ immer ein Rest $1$ verbleibt. Damit sind die Primfaktoren von $N$, die es nach
Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024))
geben muss, nicht in der Ausgangsmenge enthalten - Widerspruch.
}
\inputaufgabeklausurloesung
{3}
{
Zeige, dass der aussagenlogische Ausdruck
\mathdisp {{ \left( r \rightarrow { \left( p \wedge \neg q \right) } \right) } \rightarrow { \left( \neg p \rightarrow { \left( \neg r \vee q \right) } \right) }} { }
\definitionsverweis {allgemeingültig}{}{}
ist
}
{
Wir müssen zeigen, dass für jede Wahrheitsbelegung $\lambda$ der Variablen $r,p,q$ der Wahrheitswert der Gesamtaussage gleich $1$ ist. Bei
\mavergleichskette
{\vergleichskette
{\lambda(p)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{\lambda(\neg p)
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und damit ist der Nachsatz und die Gesamtaussage wahr. Es sei also im Folgenden
\mavergleichskette
{\vergleichskette
{\lambda(p)
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskette
{\vergleichskette
{\lambda(p \wedge \neg q )
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei
\mavergleichskette
{\vergleichskette
{\lambda(r)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist der Vordersatz falsch und somit die Gesamtaussage wahr. Es sei also
\mavergleichskette
{\vergleichskette
{\lambda(r)
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist der Vordersatz wahr und wir müssen zeigen, dass auch der Nachsatz wahr ist. Es ist dann
\mavergleichskette
{\vergleichskette
{\lambda(\neg r)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{\lambda( \neg r \vee q)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also ist auch in diesem Fall der Nachsatz und die Gesamtaussage wahr.
}
\inputaufgabeklausurloesung
{6 (2+4)}
{
Es seien
\mathkor {} {\alpha} {und} {\beta} {}
Aussagen.
\aufzaehlungzwei {Zeige
\mathdisp {\vdash { \left( \alpha \rightarrow \beta \right) } \rightarrow \neg { \left( \alpha \wedge \neg \beta \right) }} { . }
} {Zeige
\mathdisp {\vdash \neg { \left( \alpha \wedge \neg \beta \right) } \rightarrow { \left( \alpha \rightarrow \beta \right) }} { . }
}
}
{
\aufzaehlungzwei {Mit
\zusatzklammer {einer Variante von} {} {}
Lemma 3.17 (Einführung in die mathematische Logik (Osnabrück 2021))
ist
\mathdisp {\vdash \alpha \rightarrow { \left( { \left( \alpha \rightarrow \beta \right) } \rightarrow \beta \right) }} { . }
Mit Kontraposition des Nachsatzes ergibt sich daraus
\mathdisp {\vdash \alpha \rightarrow { \left( \neg \beta \rightarrow \neg { \left( \alpha \rightarrow \beta \right) } \right) }} { . }
Mit
Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))
(4)
folgt
\mathdisp {\vdash \alpha \wedge \neg \beta \rightarrow \neg { \left( \alpha \rightarrow \beta \right) }} { }
und mit Kontraposition
\mathdisp {\vdash { \left( \alpha \rightarrow \beta \right) } \rightarrow \neg { \left( \alpha \wedge \ \neg \beta \right) }} { . }
} {Es ist
\mathdisp {\vdash \beta \rightarrow { \left( \alpha \rightarrow \beta \right) }} { }
und
\mathdisp {\vdash \neg \alpha \rightarrow { \left( \neg \beta \rightarrow \neg \alpha \right) }} { }
nach
Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))
(1).
Mit
Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021)) (6)
\zusatzklammer {Kontraposition} {} {}
ergibt sich
\mathdisp {\vdash { \left( \neg \beta \rightarrow \neg \alpha \right) } \rightarrow { \left( \alpha \rightarrow \beta \right) }} { }
und daraus und der zweiten Zeile
mit der Kettenschlussregel
\mathdisp {\vdash \neg \alpha \rightarrow { \left( \alpha \rightarrow \beta \right) }} { . }
Mit Kontraposition
\zusatzklammer {als Regel} {} {}
ergibt sich aus der ersten und der letzten Zeile unter Verwendung von
Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021))
wiederum
\mathdisp {\vdash \neg { \left( \alpha \rightarrow \beta \right) } \rightarrow \neg \beta} { }
und
\mathdisp {\vdash \neg { \left( \alpha \rightarrow \beta \right) } \rightarrow \alpha} { . }
Daraus ergibt sich wegen
Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))
(3)
\mathdisp {\vdash \neg { \left( \alpha \rightarrow \beta \right) } \rightarrow \alpha \wedge \neg \beta} { }
und somit
\mathdisp {\vdash \neg { \left( \alpha \wedge \neg \beta \right) } \rightarrow { \left( \alpha \rightarrow \beta \right) }} { . }
}
}
\inputaufgabeklausurloesung
{4}
{
Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {maximal widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}
Zeige, dass für jedes
\mathl{\alpha \in L^V}{} entweder
\mathl{\alpha \in \Gamma}{} oder
\mathl{\neg \alpha \in \Gamma}{} gilt.
}
{
Wegen der Widerspruchsfreiheit können nicht sowohl $\alpha$ als auch
\mathl{\neg \alpha}{} zu $\Gamma$ gehören. Wenn weder $\alpha$ noch
\mathl{\neg \alpha}{} zu $\Gamma$ gehören, so ist entweder
\mathl{\Gamma \cup \{ \alpha \}}{} oder
\mathl{\Gamma \cup \{ \neg \alpha \}}{} widerspruchsfrei, was der maximalen Widerspruchsfreiheit von $\Gamma$ widerspricht. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck $\beta$ sowohl
\mathdisp {\Gamma \cup \{ \alpha \} \vdash \beta} { }
als auch
\mathdisp {\Gamma \cup \{ \neg \alpha \} \vdash \beta} { }
gelten. Dies bedeutet
nach Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021))
\mathdisp {\Gamma \vdash \alpha \rightarrow \beta} { }
und
\mathdisp {\Gamma \vdash \neg \alpha \rightarrow \beta} { , }
woraus aufgrund der
Fallunterscheidungsregel
\mathdisp {\Gamma \vdash \beta} { }
folgt. Dies würde aber bedeuten, dass $\Gamma$ widersprüchlich wäre.
}
\inputaufgabeklausurloesung
{3 (2+1)}
{
Es sei
\mathl{G}{} eine Menge und
\mavergleichskette
{\vergleichskette
{M
}
{ \subseteq }{ \mathfrak {P} \, (G )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge der Potenzmenge, die unter beliebigen Vereinigungen abgeschlossen ist.
\aufzaehlungzwei {Zeige, dass $(M, \subseteq)$
\definitionsverweis {induktiv geordnet}{}{}
ist.
} {Zeige, dass $M$ ein
\definitionsverweis {größtes Element}{}{}
besitzt.
}
}
{
\aufzaehlungzwei {Es sei
\mavergleichskette
{\vergleichskette
{N
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Kette}{}{}
in $M$. Nach Voraussetzung gehört
\mathl{\bigcup_{ S \in N} S}{} zu $M$ und offenbar gilt
\mavergleichskettedisp
{\vergleichskette
{T
}
{ \subseteq} {\bigcup_{ S \in N} S
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für jedes $T$ aus $N$. Für die Kette gibt es also eine obere Schranke in $M$, so dass die Menge induktiv geordnet ist.
} {Die Menge
\mathdisp {\bigcup_{ S \in M} S} { }
enthält jede Menge von $M$ und gehört zu $M$, sie ist somit das größte Element von $M$.
}
}
\inputaufgabeklausurloesung
{1}
{
Wir betrachten den Satz \anfuehrung{Diese Vorlesung versteht keine Sau}{.} Negiere diesen Satz durch eine Existenzaussage.
}
{
Es gibt eine Sau, die diese Vorlesung versteht.
}
\inputaufgabeklausurloesung
{2}
{
Zeige, dass der
\definitionsverweis {prädikatenlogische Ausdruck}{}{}
\mathdisp {\exists x \exists y ( \neg (x=y) \wedge \forall z ( (z=x) \vee (z=y) ))} { }
\definitionsverweis {erfüllbar}{}{}
ist.
}
{
Es sei
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\{m,n\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine zweielementige Menge. Bei der Interpretation $I$ mit
\mavergleichskette
{\vergleichskette
{I(x)
}
{ = }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{I(y)
}
{ = }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{I(x)
}
{ \neq }{I(y)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und für alle
\mathl{r \in M}{} muss
\mavergleichskette
{\vergleichskette
{r
}
{ = }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{r
}
{ = }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sein. Also gilt
\mathdisp {I \vDash \neg (x=y)} { }
und
\mathdisp {I \vDash \forall z ( (z=x) \vee (z=y) )} { }
und damit
\mathdisp {I \vDash \neg (x=y) \wedge \forall z ( (z=x) \vee (z=y) )} { . }
Also ist die Existenzaussage erfüllbar.
}
\inputaufgabeklausurloesung
{4}
{
Beweise den Satz über die Vorgängereigenschaft in einem Peano-Halbring.
}
{
Beide Teilaussagen können wegen
des ersten Peano-Axioms
nicht zugleich wahr sein. Es geht also um die Aussage
\mathdisp {\forall x { \left( { \left( x = 0 \right) } \vee { \left( \exists u { \left( x = u+1 \right) } \right) } \right) }} { , }
die wir durch Induktion beweisen. Der Induktionsanfang für
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist durch den linken Bestandteil gesichert. Es sei also die Aussage für ein gewisses $x$ schon bewiesen, und sie ist für
\mathl{x+1}{} zu beweisen. Bei
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{x+1
}
{ = }{ 0+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so dass man
\mavergleichskette
{\vergleichskette
{u
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nehmen kann. Bei
\mavergleichskette
{\vergleichskette
{x
}
{ = }{u+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{x+1
}
{ =} {(u+1)+1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und somit kann man
\mathl{u+1}{} nehmen.
}
\inputaufgabeklausurloesung
{3}
{
Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen. Zeige, dass die Addition die Abziehregel erfüllt, also die Aussage, dass aus einer Gleichung
\mavergleichskette
{\vergleichskette
{n+k
}
{ = }{m+k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Gleichheit
\mavergleichskette
{\vergleichskette
{n
}
{ = }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\zusatzklammer {dabei dürfen grundlegendere Regeln wie die Assoziativität der Addition und ähnliches verwendet werden} {} {.}
}
{
Wir führen Induktion über $k$
\zusatzklammer {für die Aussage für beliebige $n,m$} {} {.}
Für
\mavergleichskettedisp
{\vergleichskette
{k
}
{ =} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
folgt die Aussage daraus, dass $0$ das neutrale Element der Addition ist. Die Aussage gelte nun für ein bestimmtes $k$. Wir müssen zeigen, dass sie auch für den Nachfolger
\mathl{k'}{} gilt. Es sei also
\mavergleichskettedisp
{\vergleichskette
{n + k'
}
{ =} { m + k'
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Aufgrund von
Lemma 12.6 (Einführung in die mathematische Logik (Osnabrück 2021)) (2)
bedeutet dies
\mavergleichskettedisp
{\vergleichskette
{n' +k
}
{ =} {m' +k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
woraus nach Induktionsvoraussetzung
\mavergleichskettedisp
{\vergleichskette
{n'
}
{ =} {m'
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
folgt. Aufgrund der Injektivität der Nachfolgerabbildung ergibt sich
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {m
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{3 (1+1+1)}
{
In einem Zugabteil sitzen die sechs Personen
\mathl{A,B,C,D,E,F}{.} Wir betrachten die folgenden Relationen:
\aufzaehlungdrei{$Mx$ bedeutet, dass $x$ über die deutsche Bahn motzt.
}{$Px$ bedeutet, dass $x$ einen Fensterplatz hat.
}{$Sxy$ bedeutet, dass $x$ der Person $y$ die Fahrkarte klaut.
}
Es gelten ausschließlich die Beziehungen
\mathdisp {MA,MB,MC,MD,ME,MF, PA,PD, SAD,SBE,SFB} { . }
\aufzaehlungdrei{Charakterisiere umgangssprachlich die Person $A$ allein unter Bezugnahme auf die gegebenen Relationen.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{M,P,S}{} die Person $B$.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{M,P,S}{} die Person $E$.
}
}
{Zugabteil/Relationen/Elementare Äquivalenz/2/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{4}
{
Zeige, dass die erststufige Peano-Arithmetik $PA$ eine vollständige widerspruchsfreie erststufige Erweiterung $M$, also
\mavergleichskette
{\vergleichskette
{PA
}
{ \subseteq }{M
}
{ \subseteq }{L^{\rm Ar}_0
}
{ }{
}
{ }{
}
}
{}{}{,}
besitzt, die von $\N^\vDash_0$ verschieden ist.
}
{
Nach
Korollar 21.13 (Einführung in die mathematische Logik (Osnabrück 2021))
liegt eine echte Erweiterung
\mavergleichskette
{\vergleichskette
{PA
}
{ \subset }{ \N^\vDash_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vor. Es gibt somit Sätze
\mathl{\alpha \in \N^\vDash_0}{} mit
\mathl{\alpha \notin PA}{.} Es ist ferner
\mathl{\neg \alpha \notin PA}{,} da andernfalls
\mathl{\N^\vDash_0}{} widersprüchlich wäre. Es ist
\mathl{PA \cup \{ \neg \alpha \}}{} widerspruchsfrei, da man sonst aus $PA$ den Satz $\alpha$ ableiten könnte, was wegen der Abgeschlossenheit unter Ableitungen und wegen
\mathl{\alpha \notin PA}{} nicht der Fall ist. Nach
dem Vollständigkeitssatz
gibt es somit ein Modell $M$ mit
\mavergleichskettedisp
{\vergleichskette
{PA \cup \{ \neg \alpha \}
}
{ \subseteq} { M^\vDash_0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dabei ist
\mathl{M^\vDash_0}{} vollständig. Wegen
\mathl{\neg \alpha \in M^\vDash_0}{} und
\mathl{\neg \alpha \notin \N^\vDash_0}{} ist
\mavergleichskette
{\vergleichskette
{ M^\vDash_0
}
{ \neq }{ \N^\vDash_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{5}
{
Zeige, dass in einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} das modallogische
\definitionsverweis {Symmetrieaxiom}{}{}
genau dann gilt, wenn $R$
\definitionsverweis {symmetrisch}{}{}
ist.
}
{
Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst $R$ symmetrisch und sei
\mathdisp {w \vDash \alpha} { . }
Es sei eine von $w$ aus erreichbare Welt $v$ gegeben, also
\mathl{wRv}{.} Wegen der Symmetrie ist auch
\mathl{vRw}{} und somit ist
\mathdisp {v\vDash \Diamond \alpha} { . }
Also ist
\mathdisp {w \vdash \Box \Diamond \alpha} { . }
Wenn $R$ hingegen nicht symmetrisch ist, so seien
\mavergleichskette
{\vergleichskette
{w,v
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Welten mit
\mathl{wRv}{,} aber nicht
\mathl{vRw}{.} Es sei $p$ eine Aussagenvariable und es sei $\mu$ die Belegung, bei der
\mathdisp {w \vDash p} { }
gelte und so, dass in allen von $v$ aus erreichbaren Welten
\mathl{z \vDash \neg p}{} gelte. Dann ist
\mathdisp {v \vDash \neg \Diamond p} { , }
und somit ist
\mathdisp {w \not \vDash \Box \Diamond p} { , }
also
\mathdisp {w \not \vDash p \rightarrow \Box \Diamond p} { . }
}
\inputaufgabeklausurloesung
{4}
{
Es sei $\Gamma$ die durch das
\definitionsverweis {Löb-Axiom}{}{}
gegebene
$K$-\definitionsverweis {Modallogik}{}{,}
also die Beweisbarkeitslogik. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ \bot
}
{ \defeq} { p \wedge \neg p
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {als Abkürzung für einen Widerspruch} {} {.}
Zeige, dass
\mathdisp {\Gamma \vdash \neg \Box \neg \Box \bot \leftrightarrow \neg \Box \bot} { }
ableitbar ist.
}
{
Wegen Kontraposition genügt es,
\mathdisp {L \vdash \Box \neg \Box \bot \leftrightarrow \Box \bot} { }
zu zeigen, wobei wir die einzelnen Implikationen getrennt zeigen. Aus einem Widerspruch folgt Beliebiges, also
\mathdisp {\vdash \bot \rightarrow \neg \Box \bot} { . }
Nach
Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021)) (1)
folgt
\mathdisp {\vdash \Box \bot \rightarrow \Box \neg \Box \bot} { . }
Eine Instanz des Löb-Axioms ist
\mathdisp {L \vdash \Box( \Box \bot \rightarrow \bot ) \rightarrow \Box \bot} { . }
Das Widerspruchsaxiom ergibt
\mathdisp {\vdash \neg \Box \bot \wedge \Box \bot \rightarrow \bot} { , }
was wir als
\mathdisp {\vdash \neg \Box \bot \rightarrow ( \Box \bot \rightarrow \bot )} { }
schreiben. Mit
Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021)) (1)
erhalten wir
\mathdisp {\vdash \Box \neg \Box \bot \rightarrow \Box ( \Box \bot \rightarrow \bot )} { . }
Der Kettenschluss liefert
\mathdisp {L \vdash \Box \neg \Box \bot \rightarrow \Box \bot} { . }
}