Kurs:Einführung in die mathematische Logik/9/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}{ 6 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 2 }
\renewcommand{\asieben}{ 8 }
\renewcommand{\aacht}{ 0 }
\renewcommand{\aneun}{ 4 }
\renewcommand{\azehn}{ 6 }
\renewcommand{\aelf}{ 4 }
\renewcommand{\azwoelf}{ 3 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 3 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 6 }
\renewcommand{\asiebzehn}{ 52 }
\renewcommand{\aachtzehn}{ }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellesechzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden
\zusatzklammer {kursiv gedruckten} {} {} Begriffe.
\aufzaehlungsechs{Eine
\stichwort {maximal widerspruchsfreie} {}
Teilmenge
\mathl{\Gamma \subseteq L^V}{} zu einer Menge $V$ an
\definitionsverweis {Aussagenvariablen}{}{.}
}{Die rekursive Definition für die \stichwort {Ausdrücke} {} in einer Sprache erster Stufe.
}{Die \stichwort {Interpretation der Terme} {} zu einem \definitionsverweis {Symbolalphabet}{}{} $S$ in einer gegebenen $S$-\definitionsverweis {Interpretation}{}{} auf einer Grundmenge $M$.
}{Ein \stichwort {atomarer} {} Ausdruck in der Prädikatenlogik.
}{Eine \stichwortpraemath {R} {berechenbare Funktion}{} \maabbdisp {F} {\N^k} {\N } {.}
}{Das modallogische \stichwort {Reflexivitätsaxiom} {.} }
}
{
\aufzaehlungsechs{Die Teilmenge
\mathl{\Gamma \subseteq L^V}{} heißt
maximal widerspruchsfrei,
wenn $\Gamma$
\definitionsverweis {widerspruchsfrei}{}{}
ist und jede echt größere Menge
\mathl{\Gamma \subset \Gamma'}{} widersprüchlich ist.
}{Die folgenden rekursiv definierten Wörter heißen die
\stichwort {Ausdrücke} {}
dieser Sprache.
\aufzaehlungvier{Wenn
\mathkor {} {t_1} {und} {t_2} {}
Terme sind, so ist
\mathdisp {t_1 = t_2} { }
ein Ausdruck.
}{Wenn $R$ ein $n$-stelliges Relationssymbol ist und
\mathl{t_1 , \ldots , t_n}{} Terme sind, so ist
\mathdisp {R t_1 { \ldots } t_n} { }
ein Ausdruck.
}{Wenn
\mathkor {} {\alpha} {und} {\beta} {}
Ausdrücke sind, so sind auch
\mathdisp {\neg { \left( \alpha \right) } ,\, { \left( \alpha \right) } \wedge { \left( \beta \right) },\, { \left( \alpha \right) } \vee { \left( \beta \right) },\, { \left( \alpha \right) } \rightarrow { \left( \beta \right) }, \, { \left( \alpha \right) } \leftrightarrow { \left( \beta \right) }} { }
Ausdrücke.
}{Wenn $\alpha$ ein Ausdruck ist und $x$ eine Variable, so sind auch
\mathdisp {\forall x { \left( \alpha \right) } \text{ und } \exists x { \left( \alpha \right) }} { }
Ausdrücke.
}
}{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.
}
}{Unter einem
atomaren Ausdruck
versteht man Ausdrücke der Form
\mathl{s=t}{,} wobei $s$ und $t$ Terme sind, und der Form
\mathl{Rt_1 \ldots t_n}{,} wobei $R$ ein $n$-stelliges Relationssymbol ist und
\mathl{t_1 , \ldots , t_n}{} Terme sind.
}{Die Funktion
\maabbdisp {F} {\N^k} {\N
} {}
heißt
$R$-berechenbar,
wenn es ein Programm $P$ für eine Registermaschine gibt, die bei jeder Eingabe
\mathl{(r_1 , \ldots , r_k)}{}
\zusatzklammer {in den ersten $k$ Registern} {} {}
anhält und
\mathl{F(r_1 , \ldots , r_k)}{} als
\zusatzklammer {einzige} {} {}
Ausgabe besitzt.
}{Unter dem Reflexivitätsaxiom versteht man das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\Box \alpha \rightarrow \alpha} { . }
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz über die Division mit Rest in einem Peano-Halbring.}{Der \stichwort {Vollständigkeitssatz} {} der Prädikatenlogik.}{Der \stichwort {erste Gödelsche Unvollständigkeitssatz} {.}}
}
{
\aufzaehlungdrei{Es sei $M$ ein
\definitionsverweis {Peano-Halbring}{}{}
und
\mathl{d \geq 1}{.}
Dann gibt es zu jedem
\mathl{m \in M}{} eindeutig bestimmte
\mathl{q,r \in M}{} mit
\mathbed {r} {}
{r < d} {}
{} {} {} {,} und mit
\mavergleichskettedisp
{\vergleichskette
{m
}
{ =} {qd+r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}{Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{,}
$\Gamma$ eine Menge an
$S$-\definitionsverweis {Ausdrücken}{}{}
und $\alpha$ ein weiterer $S$-Ausdruck. Dann gilt
\mathl{\Gamma \vDash \alpha}{} genau dann, wenn
\mathl{\Gamma \vdash \alpha}{} gilt.}{Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine arithmetische Ausdrucksmenge, die
\definitionsverweis {widerspruchsfrei}{}{}
und
\definitionsverweis {aufzählbar}{}{}
sei und
\definitionsverweis {Repräsentierungen erlaube}{}{.}
Dann ist
\mathl{\Gamma^\vdash}{}
\definitionsverweis {unvollständig}{}{.}}
}
\inputaufgabeklausurloesung
{1}
{
Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt. \wahrheitstabellezweieins{ } {\tabellenzeiledrei {$ p $} {$ q $} {$? $} } {\tabellenzeiledrei {w} {w} {w} } {\tabellenzeiledrei {w} {f} {w} } {\tabellenzeiledrei {f} {w} {f} } {\tabellenzeiledrei {f} {f} {f} }
}
{
$p$.
}
\inputaufgabeklausurloesung
{6 (2+1+3)}
{
Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest. \aufzaehlungvier{Ein Tag heißt \stichwort {sockenzerstreut} {,} wenn er verschiedene Socken anhat. }{Ein Tag heißt \stichwort {schuhzerstreut} {,} wenn er verschiedene Schuhe anhat. }{Ein Tag heißt \stichwort {zerstreut} {,} wenn er sockenzerstreut oder schuhzerstreut ist. }{Ein Tag heißt \stichwort {total zerstreut} {,} wenn er sowohl sockenzerstreut als auch schuhzerstreut ist. }
a) Vom Jahr
\mathl{2015}{} weiß man, dass $17$ Tage sockenzerstreut und $11$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?
b) Vom Jahr
\mathl{2013}{} weiß man, dass $270$ Tage sockenzerstreut und $120$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?
c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.
}
{
a) Zerstreutheit: Die sockenzerstreuten Tage sind jedenfalls zerstreut. Das Minimum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind $17$. Das Maximum ergibt sich, wenn kein Tag gleichzeitig sockenzerstreut und schuhzerstreut war, das ergibt
\mathl{28}{} Tage.
Totale Zerstreutheit: Die total zerstreuten Tage sind insbesondere schuhzerstreut. Das Maximum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind $11$ Tage. Das Minimum ergibt sich, wenn kein Tag gleichzeitig schuh- und sockenzerstreut war, also $0$.
b) Wegen
\mavergleichskettedisp
{\vergleichskette
{270 + 120
}
{ =} {390
}
{ \geq} {365
}
{ } {
}
{ } {
}
}
{}{}{}
können alle Jahre des Tages zerstreut gewesen sein, also
\mathl{365}{.} Minimal waren $25$ Tage total zerstreut.
c) Es sei $s$ die Anzahl der sockenzerstreuten Tage, $x$ die Anzahl der schuhzerstreuten Tage, $z$ die Anzahl der zerstreuten Tage und $t$ die Anzahl der total zerstreuten Tage. Dann gilt die Formel
\mavergleichskettedisp
{\vergleichskette
{s+x
}
{ =} {z+t
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Beide Seiten der Formel sind additiv in den Tagen, sie muss also nur für einen Tag nachgewiesen werden. Wenn der Tag nicht zerstreut ist, steht beidseitig $0$. Wenn der Tag sockenzerstreut ist, aber nicht schuhzerstreut
\zusatzklammer {oder umgekehrt} {} {,}
so ist der Tag zerstreut, aber nicht total zerstreut, und beidseitig steht $1$. Wenn der Tag total zerstreut ist, so steht beidseitig $2$.
}
\inputaufgabeklausurloesung
{3}
{
Erläutere das Konzept der \stichwort {Wohldefiniertheit} {} anhand eines typischen Beispiels.
}
{Wohldefiniertheit/Typisches Beispiel/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 folgende Regel für die
\definitionsverweis {Ableitungsbeziehung}{}{:}
Wenn
\mathl{\Gamma \vdash \alpha_1 , \ldots , \Gamma \vdash \alpha_n}{} und
\mathl{\Gamma \vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \beta}{,} dann auch
\mathl{\Gamma \vdash \beta}{.}
}
{
Aus der Voraussetzung und der Konjunktionsregel
\zusatzklammer {Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021)) (1)} {} {}
ergibt sich
\mathdisp {\Gamma \vdash \alpha_1 \wedge \ldots \wedge \alpha_n} { . }
Daraus und aus der Voraussetzung
\mathdisp {\Gamma \vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \beta} { }
ergibt sich mittels Modus ponens
\zusatzklammer {Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021)) (3)} {} {}
\mathdisp {\Gamma \vdash \alpha} { . }
}
\inputaufgabeklausurloesung
{8 (3+5)}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
erster Stufe und
\mathl{U \subseteq S}{} eine Teilmenge. Es sei $t$ ein
$U$-\definitionsverweis {Term}{}{} und $\alpha$ ein $U$-\definitionsverweis {Ausdruck}{}{.}
Es seien zwei
$S$-\definitionsverweis {Interpretationen}{}{}
\mathkor {} {I_1} {und} {I_2} {}
in einer gemeinsamen Grundmenge $M$ gegeben, die auf $U$ identisch seien. Beweise die folgenden Aussagen.
\aufzaehlungzwei {Es ist
\mathl{I_1(t)=I_2(t)}{.}
} {Es ist
\mathl{I_1 \vDash \alpha}{} genau dann, wenn
\mathl{I_2 \vDash \alpha}{} (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus $U$ und auf den in $\alpha$ frei vorkommenden Variablen identisch sind).
}
}
{
\teilbeweis {}{}{}
{(1). Wir führen Induktion über den Aufbau der $U$-Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus $U$ betrachten. Für eine Variable $x$
\zusatzklammer {oder eine Konstante} {} {}
aus $U$ ist nach Voraussetzung
\mavergleichskette
{\vergleichskette
{I_1(x)
}
{ = }{I_2(x)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Im Induktionsschritt können wir annehmen, dass ein $n$-stelliges Funktionssymbol $f$ aus $U$ gegeben ist sowie $U$-Terme
\mathl{t_1 , \ldots , t_n}{,} für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird $f$ in beiden Interpretationen durch die gleiche Funktion
\mathl{f^M}{} interpretiert. Daher ist
\mavergleichskettealign
{\vergleichskettealign
{ I_1(ft_1 \ldots t_n)
}
{ =} { f^M (I_1(t_1) , \ldots , I_1 (t_n))
}
{ =} { f^M (I_2(t_1) , \ldots , I_2 (t_n))
}
{ =} { I_2(ft_1 \ldots t_n)
}
{ } {
}
}
{}
{}{.}}
{}
\teilbeweis {}{}{}
{(2). Wir führen Induktion über den Aufbau der $U$-Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol $R$ aus $U$ folgt die Aussage unmittelbar aus (1), da ja $R$ in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form
\mathl{\neg \alpha,\, \alpha \wedge \beta,\, \alpha \rightarrow \beta}{} aufgrund der Modellbeziehung unmittelbar klar. Es sei nun ein $U$-Ausdruck der Form
\mathl{\exists x \alpha}{} gegeben, und es gelte
\mathl{I_1 \vDash \exists x \alpha}{.} Dies bedeutet aufgrund der Modellbeziehung, dass es ein
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart gibt, dass
\mathl{I_1\frac{m}{x} \vDash \alpha}{} gilt. Die beiden umbelegten Interpretationen
\mathkor {} {I_1\frac{m}{x}} {und} {I_2\frac{m}{x}} {}
stimmen auf den Symbolen aus $U$ und den in $\alpha$ frei vorkommenden Variablen überein: Die Variable $x$ wird so oder so als $m$ interpretiert und die anderen freien Variablen aus $\alpha$ sind auch in
\mathl{\exists x \alpha}{} frei. Nach Induktionsvoraussetzung gilt
\mathl{I_2 \frac{m}{x} \vDash \alpha}{} und daher wiederum
\mathl{I_2 \vDash \exists x \alpha}{.}}
{}
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{4}
{
Es seien
\mathl{A,B,C}{} einstellige Relationssymbole. Zeige, dass der \stichwort {Modus Darii} {,} also die Aussage
\mathdisp {( \forall x (Ax \rightarrow Bx) \wedge \exists x (Ax \wedge Cx) ) \rightarrow ( \exists x (Bx \wedge Cx) )} { }
im Prädikatenkalkül
\definitionsverweis {ableitbar}{}{}
ist.
}
{
Es gilt die aussagenlogische Ableitbarkeit
\mathdisp {\vdash (Ax \rightarrow Bx) \rightarrow { \left( Ax \wedge Cx \rightarrow Bx \wedge Cx \right) }} { . }
Dies fassen wir als eine Aussage vom Typ
\mathdisp {\vdash p \rightarrow (q \rightarrow r)} { }
auf. Nach
Aufgabe 11.7 (Einführung in die mathematische Logik (Osnabrück 2021))
gilt in dieser Situation auch
\mathdisp {\vdash \forall x p \rightarrow \forall x (q \rightarrow r)} { . }
Nach
Lemma 11.9 (Einführung in die mathematische Logik (Osnabrück 2021)) (3)
ist
\mathdisp {\vdash \forall x (q \rightarrow r) \rightarrow { \left( \exists x q \rightarrow \exists x r \right) }} { . }
Dies zusammengenommen ergibt mit dem Kettenschluss
\mathdisp {\vdash \forall x p \rightarrow { \left( \exists x q \rightarrow \exists x r \right) }} { , }
was im obigen Spezialfall die gewünschte Ableitbarkeit
\mathdisp {\vdash \forall x (Ax \rightarrow Bx) \rightarrow { \left( \exists x Ax \wedge Cx \rightarrow \exists x Bx \wedge Cx \right) }} { }
liefert.
}
\inputaufgabeklausurloesung
{6 (3+3)}
{
Es sei $(M,0,N)$ ein
\definitionsverweis {Modell}{}{}
für die
\definitionsverweis {Peano-Axiome für den Nachfolger}{}{.}
\aufzaehlungzwei {Zeige, dass $N$
\definitionsverweis {fixpunktfrei}{}{}
ist, d.h. dass
\mavergleichskettedisp
{\vergleichskette
{N(x)
}
{ \neq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle $x \in M$.
} {Zeige, dass $N$ periodenfrei ist. D.h. für jedes
\mathl{\ell \in \N_+}{} ist
\mavergleichskettedisp
{\vergleichskette
{N^\ell ( x)
}
{ \neq} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei
\mavergleichskettedisp
{\vergleichskette
{ N^\ell
}
{ =} { N \circ \cdots \circ N
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die $\ell$-fache Hintereinanderschaltung von $N$ bedeutet.
}
}
{
\aufzaehlungzwei {Wir zeigen die Aussage
\mavergleichskettedisp
{\vergleichskette
{Nx
}
{ \neq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
durch Induktion über $x$. Bei
\mavergleichskettedisp
{\vergleichskette
{x
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ergibt sich
\mavergleichskette
{\vergleichskette
{N0
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
unmittelbar aus dem Axiom, dass $0$ kein Nachfolger ist. Es sei die Aussage für $x$ richtig, also
\mavergleichskettedisp
{\vergleichskette
{Nx
}
{ \neq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{N Nx
}
{ =} {Nx
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
wäre in Verbindung mit der Induktionsvoraussetzung ein direkter Widerspruch zur Injektivität der Nachfolgerabbildung. Also ist
\mavergleichskettedisp
{\vergleichskette
{NNx
}
{ \neq} {Nx
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und die Aussage ist bewiesen.
} {Es sei nun $\ell$ und
\mavergleichskettedisp
{\vergleichskette
{N^\ell
}
{ =} {N \circ \cdots \circ N
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
fixiert. Wir zeigen
\mavergleichskettedisp
{\vergleichskette
{ N^\ell (x)
}
{ \neq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
durch Induktion über $x$. Bei
\mavergleichskette
{\vergleichskette
{x
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergibt sich
\mavergleichskettedisp
{\vergleichskette
{N^\ell(0)
}
{ \neq} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
da sonst $0$ der Nachfolger von
\mathl{N^{\ell -1}(0)}{} wäre. Es sei die Aussage nun für $x$ richtig, also
\mavergleichskettedisp
{\vergleichskette
{N^\ell (x)
}
{ \neq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Nehmen wir an, dass die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{N^\ell Nx
}
{ =} {Nx
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt. Wegen
\mavergleichskettedisp
{\vergleichskette
{ N^\ell (N(x))
}
{ =} { N(N^\ell (x))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
folgt aus der Injektivität der Nachfolgerabbildung direkt
\mavergleichskettedisp
{\vergleichskette
{N^\ell x
}
{ =} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
im Widerspruch zur Induktionsvoraussetzung. Also ist
\mavergleichskettedisp
{\vergleichskette
{N^\ell Nx
}
{ \neq} {Nx
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und die Aussage ist bewiesen.
}
}
\inputaufgabeklausurloesung
{4}
{
Zeige, dass es einen
\definitionsverweis {Peano-Halbring}{}{}
$M$ mit der Eigenschaft gibt, dass es darin ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt, das größer als jede natürliche Zahl in $M$
\zusatzklammer {also Zahlen der Form
\mathl{1+1 + \cdots + 1}{}} {} {}
ist.
}
{
Es sei $\Gamma$ die Menge der aus den erststufigen Peano-Axiomen ableitbaren Ausdrücke. Wir betrachten die Ausdrücke
\mathl{\alpha_n}{} mit
\mavergleichskettedisp
{\vergleichskette
{ \alpha_n
}
{ =} { \neg { \left( x = 1+1 + \cdots + 1 \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei rechts die $n$-fache formale Summe der $1$ mit sich selbst steht. Es sei
\mavergleichskettedisp
{\vergleichskette
{\Delta
}
{ =} { { \left( \Gamma \cup \bigcup_{n \in \N} \{ \alpha_n \} \right) }^\vdash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Menge ist widerspruchsfrei, da jede endliche Teilmenge davon widerspruchsfrei ist, da sie in $\N$ mit einer hinreichend großen Belegung für $x$ erfüllbar ist. Nach
Korollar 15.10 (Einführung in die mathematische Logik (Osnabrück 2021))
ist also auch $\Delta$ erfüllbar, und es sei $M$ ein erfüllendes Modell. Es gibt dann in $M$ ein Element
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wodurch $x$ belegt wird. Dieses $m$ ist dann von allen natürlichen Zahlen, die in $M$ natürlicherweise eingebettet sind, verschieden, und somit ist
\mavergleichskette
{\vergleichskette
{M
}
{ \neq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{3 (1+1+1)}
{
Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze
\mathl{1,2,3,4}{} nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz $3$ bestreiten. Von einer solchen Runde seien die Mannschaften $A,B,C,D$ und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.
\aufzaehlungdrei{Welche Information über die Platzierung kann man stets aus den Daten erschließen?
}{Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
}{unter welcher nicht?
}
}
{
\aufzaehlungdrei{Es gibt genau eine Mannschaft, die zweimal gewinnt, diese ist Weltmeister, und genau eine Mannschaft, die zweimal verliert, diese ist Vierter. Die beiden anderen Mannschaften gewinnen einmal und verlieren einmal und sind Zweiter oder Dritter. }{Wenn der Erste gegen den Vierten \zusatzklammer {die ja beide bekannt sind} {} {} spielt, so muss dieses Spiel ein Hauptfinale sein. Das komplementäre Spiel ist ebenfalls ein Halbfinale, das andere Spiel des Ersten muss das Finale und das andere Spiel des Vierten muss das Spiel um Platz drei sein. Somit sind alle Platzierungen bekannt. }{Wenn der Erste nicht gegen den Vierten spielt, so kann man den Zweiten nicht vom Dritten unterscheiden. }
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\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
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{6 (4+2)}
{
\aufzaehlungzwei {Skizziere ein modallogisches Modell, bei dem es verschiedene Weltpunkte $v,w$ mit
\mathdisp {v \vDash \neg \Box p} { }
und
\mathdisp {w \vDash \Box \Box p \wedge \Diamond p \wedge \Diamond \neg p} { }
gibt.
} {Was ist die minimale Anzahl von Welten in einem modallogischen Modell, in dem die Anforderungen aus 1) realisierbar sind.
}
}
{
\aufzaehlungzwei {Wir betrachten das Modell bestehend aus den vier Welten
\mathl{u,v,w,z}{} mit der Erreichbarkeitsrelation
\mathdisp {Rwz, Rwu, Rvu} { }
und der Belegung
\mathdisp {z \vDash p, \, u \vDash \neg p} { }
\zusatzklammer {die Belegung von $p$ auf $v,w$ ist irrelevant} {} {.}
Dann gilt
\mathdisp {z \vDash \Box p,\, u \vDash \Box p} { , }
da es für diese beiden Welten keine erreichbaren Welten gibt. In allen von $w$ aus erreichbaren Welten gilt somit $\Box p$ und daher
\mathdisp {w \vDash \Box \Box p} { . }
Ferner gilt
\mathdisp {w \vDash \Diamond p} { }
wegen der Erreichbarkeit $Rwz$ und
\mathdisp {w \vDash \Diamond \neg p} { }
wegen der Erreichbarkeit $Rwu$ und auch
\mathdisp {v \vDash \Diamond \neg p} { , }
also
\mathdisp {v \vDash \neg \Box p} { , }
wegen der Erreichbarkeit $Rvu$.
} {Wir behaupten, dass die Anforderungen nicht mit weniger als vier Welten realisierbar sind. Nach Voraussetzung müssen
\mathkor {} {v} {und} {w} {}
verschieden sein. Wegen
\mathdisp {w \vDash \Diamond \neg p \text{ und } v \vDash \Diamond \neg p} { }
kann von $w$ weder $v$ noch $w$ selbst erreichbar sein, da dies ein Widerspruch zu
\mathl{w \vDash \Box \Box p}{} ergeben würde. Zugleich braucht man, um die Gültigkeit von
\mathkor {} {w \vDash \Diamond p} {und} {w \vDash \Diamond \neg p} {}
zu realisieren, zwei von $w$ aus erreichbare Welten, also insgesamt mindestens vier Welten.
}
}