Kurs:Einführung in die mathematische Logik/4/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}{ 4 }

\renewcommand{\avier}{ 8 }

\renewcommand{\afuenf}{ 2 }

\renewcommand{\asechs}{ 4 }

\renewcommand{\asieben}{ 3 }

\renewcommand{\aacht}{ 5 }

\renewcommand{\aneun}{ 5 }

\renewcommand{\azehn}{ 4 }

\renewcommand{\aelf}{ 4 }

\renewcommand{\azwoelf}{ 4 }

\renewcommand{\adreizehn}{ 4 }

\renewcommand{\avierzehn}{ 6 }

\renewcommand{\afuenfzehn}{ 5 }

\renewcommand{\asechzehn}{ 64 }

\renewcommand{\asiebzehn}{ }

\renewcommand{\aachtzehn}{ }

\renewcommand{\aneunzehn}{ }

\renewcommand{\azwanzig}{ }

\renewcommand{\aeinundzwanzig}{ }

\renewcommand{\azweiundzwanzig}{ }

\renewcommand{\adreiundzwanzig}{ }

\renewcommand{\avierundzwanzig}{ }

\renewcommand{\afuenfundzwanzig}{ }

\renewcommand{\asechsundzwanzig}{ }

\punktetabellefuenfzehn

\klausurnote

\newpage


\setcounter{section}{0}





\inputaufgabeklausurloesung
{3}
{

Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Eine \stichwort {Primzahl} {.}

}{Die \stichwort {Sprache der Aussagenlogik} {} $L^V$ zu einer Aussagenvariablenmenge $V$.

}{Die \stichwort {Uminterpretation} {}
\mathl{I { \frac{ m }{ x } }}{} zu einer $S$-\definitionsverweis {Interpretation}{}{} $I$ in einer Menge $M$, wobei $x$ eine Variable und
\mathl{m \in M}{} ein Element der Grundmenge ist.

}{Der \stichwort {Rang} {} eines prädikatenlogischen Ausdrucks
\mathl{\alpha}{.} }{Eine \stichwortpraemath {R} {berechenbare Funktion}{} \maabbdisp {F} {\N^k} {\N } {.}

}{Eine $K$-Modallogik. }

}
{

\aufzaehlungsechs{Eine \definitionsverweis {natürliche Zahl}{}{}
\mathl{n \geq 2}{} heißt eine Primzahl, wenn die einzigen natürlichen \definitionsverweis {Teiler}{}{} von ihr $1$ und $n$ sind. }{Die Sprache der Aussagenlogik
\mathl{L^V}{} wird rekursiv durch folgende Regeln definiert. \aufzaehlungdrei{Jedes
\mathl{p \in V}{} gehört zu $L^V$. }{Wenn
\mathl{\alpha \in L^V}{,} so ist auch
\mathl{\neg (\alpha) \in L^V}{.} }{Wenn
\mathl{\alpha, \beta \in L^V}{,} so sind auch
\mathl{(\alpha) \wedge (\beta) ,\, (\alpha) \vee (\beta) ,\, (\alpha) \rightarrow (\beta) ,\, (\alpha) \leftrightarrow (\beta)\in L^V}{.} } }{Unter der Uminterpretation
\mathl{I \frac{m}{x}}{} versteht man diejenige Interpretation von $S$ in $M$, die strukturgleich zu $I$ ist und für deren Variablenbelegung
\mathdisp {\left( I \frac{m}{x} \right) (y) = \begin{cases} I(y), \, \text{ falls } y \neq x\, , \\ m, \, \text{ falls } y = x \, , \end{cases}} { }
gilt. }{Der Rang $\rho$ von $\alpha$ wird rekursiv durch \aufzaehlungvier{
\mathl{\rho( \alpha ) =0}{,} falls $\alpha$ atomar ist. }{
\mathl{\rho( \alpha ) = \rho( \beta )+1}{,} falls $\alpha = \neg ( \beta )$ ist. }{
\mathl{\rho( \alpha ) = \rho( \beta ) + \rho( \gamma ) + 1}{,} falls $\alpha = ( \beta ) \circ ( \gamma )$ mit
\mathl{\circ = \wedge,\, \vee, \, \rightarrow, \leftrightarrow}{} ist. }{
\mathl{\rho( \alpha ) = \rho( \beta ) +1}{,} falls $\alpha = \exists x \beta$ oder $\alpha = \forall x \beta$ ist. } definiert. }{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. }{Eine \definitionsverweis {Modallogik}{}{} heißt eine $K$-Modallogik, wenn das Axiomenschema
\mathdisp {\vdash \Box (\alpha \rightarrow \beta) \rightarrow (\Box \alpha \rightarrow \Box \beta)} { }
für beliebige Ausdrücke
\mathl{\alpha, \beta}{} und die Nezessisierungsregel

aus
\mathl{\vdash \alpha}{} folgt
\mathl{\vdash \Box \alpha}{}

für alle $\alpha$ gilt. }


}





\inputaufgabeklausurloesung
{3}
{

Formuliere die folgenden Sätze. \aufzaehlungdrei{Das \stichwort {Substitutionslemma} {.}}{Der \stichwort {Satz über die induktive Definition einer Abbildung} {} auf einem Peano-Dedekind-Modell $(N,0,\prime)$.}{Der \stichwort {Vollständigkeitssatz} {} der Modallogik.}

}
{

\aufzaehlungdrei{Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben und es seien
\mathl{x_1 , \ldots , x_k}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k}{} fixierte $S$-Terme. Es sei eine $S$-Interpretation $I$ gegeben. Dann gelten folgende Aussagen. \aufzaehlungzwei {Für jeden $S$-Term $s$ gilt
\mavergleichskettedisp
{\vergleichskette
{ 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) }
{ } { }
{ } { }
{ } { }
} {}{}{.} } {Für jeden $S$-Ausdruck $\alpha$ gilt
\mathdisp {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} { . }
}}{Es sei $M$ eine Menge mit einem fixierten Element
\mathl{s \in M}{} und einer \definitionsverweis {Abbildung}{}{} \maabb {F} {M} {M } {.} Dann gibt es genau eine Abbildung \maabbeledisp {\varphi} {N} {M } {n} {\varphi(n) } {,} die die beiden Eigenschaften
\mathdisp {\varphi(0) = s \text{ und } \varphi(n^\prime) = F ( \varphi(n)) \text { für alle } n \in \N} { }
erfüllt.}{Es sei $\Gamma$ eine Menge von \definitionsverweis {modallogischen Ausdrücken}{}{} und $\alpha$ ein modallogischer Ausdruck. Dann ist
\mathdisp {\Gamma \vdash \alpha} { }
genau dann, wenn
\mathdisp {\Gamma \vDash \alpha} { . }
}


}





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

Folgende Aussagen seien bekannt. \aufzaehlungsieben{Der frühe Vogel fängt den Wurm. }{Doro wird nicht von Lilly gefangen. }{Lilly ist ein Vogel oder ein Igel. }{Für Igel ist 5 Uhr am Morgen spät. }{Doro ist ein Wurm. }{Für Vögel ist 5 Uhr am Morgen früh. }{Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs. } Beantworte folgende Fragen. \aufzaehlungdrei{Ist Lilly ein Vogel oder ein Igel? }{Ist sie ein frühes oder ein spätes Tier? }{Fängt der späte Igel den Wurm? }

}
{

\aufzaehlungdrei{Lilly ist ein Igel. Beweis durch Widerspruch. Nehmen wir an, dass Lilly kein Igel ist. Dann ist sie nach (3) ein Vogel. Da Lilly nach (7) um $5$ Uhr schon unterwegs ist, ist nach (6) Lilly ein früher Vogel. Nach (1) fängt Lilly also den Wurm. Da nach (5) Doro ein Wurm ist, wird er von Lilly gefangen im Widerspruch zu (2). }{Nach dem ersten Teil ist Lilly ein Igel, und nach (7) steht sie um 5 Uhr auf. Dies ist nach (4) für Igel spät, Lilly ist also ein später Igel und somit ein spätes Tier. }{Da nach dem zweiten Teil Lilly ein später Igel ist und sie nach (2) Doro, die nach (5) ein Wurm ist, nicht fängt, fängt der späte Igel im Allgemeinen nicht den Wurm. }


}





\inputaufgabeklausurloesung
{8}
{

Es sei $\alpha$ eine aussagenlogische Aussage und es seien
\mathl{p_1 , \ldots , p_n}{} die darin vorkommenden Aussagenvariablen. Es sei
\mavergleichskettedisp
{\vergleichskette
{ \gamma }
{ =} { \pm p_1 \wedge \ldots \wedge \pm p_n }
{ } { }
{ } { }
{ } { }
} {}{}{} eine fixierte Konjunktion dieser \zusatzklammer {negierten} {} {} Aussagenvariablen. Zeige, dass dann
\mathdisp {\vdash \gamma \rightarrow \alpha \text{ oder } \vdash \gamma \rightarrow \neg \alpha} { }
gilt.

}
{

Wir führen Induktion über den Aufbau der Sprache
\mathl{L^{ \{p_1 , \ldots , p_n \} }}{.} Bei
\mavergleichskettedisp
{\vergleichskette
{ \alpha }
{ =} { p_i }
{ } { }
{ } { }
{ } { }
} {}{}{} ergibt sich die Aussage aus Lemma 3.12 (Einführung in die mathematische Logik (Osnabrück 2021)). Bei
\mavergleichskettedisp
{\vergleichskette
{ \alpha }
{ =} { \neg \beta }
{ } { }
{ } { }
{ } { }
} {}{}{} ergibt sich die Aussage aus der Induktionsvoraussetzung und aus Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021))  (3). Es sei nun
\mavergleichskettedisp
{\vergleichskette
{ \alpha }
{ =} { \beta_1 \wedge \beta_2 }
{ } { }
{ } { }
{ } { }
} {}{}{.} Bei
\mathdisp {\vdash \gamma \rightarrow \beta_1 \text{ und } \vdash \gamma \rightarrow \beta_2} { }
ergibt sich die Ableitung
\mathdisp {\vdash \gamma \rightarrow \beta_1 \wedge \beta_2} { }
im Wesentlichen aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (3). Bei
\mathdisp {\vdash \gamma \rightarrow \neg \beta_1} { }
ergibt sich die Ableitung
\mathdisp {\vdash \gamma \rightarrow \neg { \left( \beta_1 \wedge \beta_2 \right) }} { }
aus Kontraposition auf Lemma 3.12 (Einführung in die mathematische Logik (Osnabrück 2021)). Es sei nun
\mavergleichskettedisp
{\vergleichskette
{ \alpha }
{ =} { \beta_1 \rightarrow \beta_2 }
{ } { }
{ } { }
{ } { }
} {}{}{.} Bei
\mathdisp {\vdash \gamma \rightarrow \neg \beta_1 \text{ oder } \vdash \gamma \rightarrow \beta_2} { }
ergibt sich die Ableitung
\mathdisp {\vdash \gamma \rightarrow { \left( \beta_1 \rightarrow \beta_2 \right) }} { }
aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) bzw. aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (5). Bei
\mathdisp {\vdash \gamma \rightarrow \beta_1 \text{ oder } \vdash \gamma \rightarrow \neg \beta_2} { }
hingegen ergibt sich die Ableitung
\mathdisp {\vdash \gamma \rightarrow \neg { \left( \beta_1 \rightarrow \beta_2 \right) }} { }
folgendermaßen. Nach Lemma 3.17 (Einführung in die mathematische Logik (Osnabrück 2021)) ist
\mathdisp {\vdash \beta_1 \wedge { \left( \beta_1 \rightarrow \beta_2 \right) } \rightarrow \beta_2} { , }
was wir als
\mathdisp {\vdash \beta_1 \rightarrow { \left( { \left( \beta_1 \rightarrow \beta_2 \right) } \rightarrow \beta_2 \right) }} { }
schreiben. Kontraposition auf den Nachsatz ergibt
\mathdisp {\vdash \beta_1 \rightarrow { \left( \neg \beta_2 \rightarrow \neg { \left( \beta_1 \rightarrow \beta_2 \right) } \right) }} { , }
was wir wiederum als
\mathdisp {\vdash \beta_1 \wedge \neg \beta_2 \rightarrow \neg { \left( \beta_1 \rightarrow \beta_2 \right) }} { }
schreiben. Aus den beiden Voraussetzungen ergibt sich mit Hilfe von Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (3)
\mathdisp {\vdash \gamma \rightarrow \beta_1 \wedge \neg \beta_2} { }
und somit mit der Kettenschlussregel
\mathdisp {\vdash \gamma \rightarrow \neg { \left( \beta_1 \rightarrow \beta_2 \right) }} { . }


}





\inputaufgabeklausurloesung
{2}
{

Es sei
\mathl{K=\{E,m,c\}}{} eine Konstantenmenge, $Q$ ein einstelliges Funktionssymbol und $P$ ein zweistelliges Funktionssymbol. Es sei $I$ die Interpretation mit
\mavergleichskette
{\vergleichskette
{M }
{ = }{\N }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} als Grundmenge, bei der $Q$ als Quadrieren, $P$ als Multiplikation und die Konstanten als
\mavergleichskette
{\vergleichskette
{I(E) }
{ = }{9 000 000 000 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{}
\mavergleichskette
{\vergleichskette
{I(m) }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{I(c) }
{ = }{300 000 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} interpretiert wird. Ist der Ausdruck
\mathdisp {E = P m Q c} { }
unter dieser Interpretation gültig?

}
{

Die Gültigkeit des Ausdrucks bei der Interpretation würde bedeuten, dass
\mavergleichskettedisp
{\vergleichskette
{I(E) }
{ =} {9 000 000 000 }
{ } { }
{ } { }
{ } { }
} {}{}{} mit
\mavergleichskettedisp
{\vergleichskette
{ I(P)( I(m), I(Q)(I(c)) ) }
{ =} { 1 \cdot 300 000^2 }
{ =} { 90 000 000 000 }
{ } { }
{ } {}
} {}{}{} übereinstimmt. Da eine $0$ fehlt, ist dies nicht richtig und daher ist der Ausdruck bei der Interpretation nicht gültig.


}





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

\aufzaehlungdrei{Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist. }{Beschreibe die Bedingung \zusatzklammer {und zwar so, dass die Bedingung erkennbar ist} {} {} aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck \zusatzklammer {also mit dem Symbolalphabet
\mathl{+,\cdot,0,1}{} und Variablen} {} {} in der einen freien Variablen $x$. }{Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen $x$. }

}
{

\aufzaehlungdrei{Da $0$ eine natürliche Zahl ist, sind die ersten Quadratzahlen
\mathl{0,1,4}{} und somit ist $5$ die erste natürliche Zahl, die größer als drei Quadratzahlen ist. }{
\mathdisp {\exists y \exists z \exists w { \left( y \neq w \wedge y \neq z \wedge z \neq w \wedge \exists r { \left( x \geq y \cdot y+r +1 \right) } \wedge \exists r { \left( x \geq z \cdot z +r +1 \right) } \wedge \exists r { \left( x \geq w\cdot w+r +1 \right) } \right) } \wedge} { }

\mathdisp {\forall u { \left( \exists y \exists z \exists w { \left( y \neq w \wedge y \neq z \wedge z \neq w \wedge \exists r { \left( u \geq y \cdot y+r +1 \right) } \wedge \exists r { \left( u \geq z \cdot z +r +1 \right) } \wedge \exists r { \left( u \geq w\cdot w+r +1 \right) } \right) } \rightarrow \exists s { \left( u = x+s \right) } \right) }} { . }
}{
\mathdisp {x=1+1+1+1+1} { . }
}


}





\inputaufgabeklausurloesung
{3}
{

Formuliere die \definitionsverweis {Injektivität}{}{} für eine Abbildung \maabbdisp {f} {D} {Z } {} prädikatenlogisch mit Hilfe der Verwendung von Sorten.

}
{

Die Symbolmenge
\mathl{S}{} bestehe aus einem einstelligen Funktionssymbol $f$ und zwei einstelligen Relationssymbolen \mathkor {} {D} {und} {Z} {.} Wir betrachten den Ausdruck
\mathdisp {\forall x (Dx \rightarrow Zfx) \wedge \forall x \forall y { \left( Dx \wedge Dy \wedge \neg { \left( x = y \right) } \rightarrow \neg { \left( fx = fy \right) } \right) }} { . }
Bei einer Interpretation in einer Gesamtmenge $M$ besagt der linke Ausdruck, dass wenn ein Element $m$ zu $D^M$ gehört, dass dann der Funktionswert
\mathl{f^M(m)}{} zu
\mathl{Z^M}{} gehört. Das bedeutet also, dass eine Abbildung \maabbdisp {f^M} {D^M} {Z^M } {} vorliegt. Der rechte Ausdruck besagt somit, dass für verschiedene Elemente aus $D^M$ die Bilder verschieden sind, was die Injektivität dieser Abbildung bedeutet.


}





\inputaufgabeklausurloesung
{5 (3+2)}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und $L^S$ die zugehörige Sprache und $T$ die zugehörige Termmenge. Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge. \aufzaehlungzwei {Zeige, dass durch
\mathdisp {s \cong_\Gamma t \text{ genau dann, wenn } I(s)=I(t) \text{ für jede Interpretation } I \text{ mit } I \vDash \Gamma} { }
eine \definitionsverweis {Äquivalenzrelation}{}{} auf $T$ definiert wird. } {Wenn man $\Gamma$ vergrößert, werden dann die Äquivalenzklassen größer oder kleiner? }

}
{

\aufzaehlungzwei {Wegen
\mathl{\vdash s=s}{} und der Korrektheit des Ableitungskalküls ist
\mathl{I (s) =I(t)}{} überhaupt für jede Interpretation. Es liegt also eine reflexive Relation vor. Es sei nun
\mathl{s \cong_\Gamma t}{.} Dann gilt für jede Interpretation $I$ mit $I\vDash \Gamma$ die Gleichheit
\mavergleichskette
{\vergleichskette
{I(s) }
{ = }{I(t) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und somit auch
\mavergleichskette
{\vergleichskette
{I(t) }
{ = }{I(s) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} also ist auch
\mathl{t \cong_\Gamma s}{,} was die Symmetrie beweist. Es gelte nun
\mathl{r \cong_\Gamma s}{} und
\mathl{s \cong_\Gamma t}{,} und es sei $I$ eine Interpretation mit
\mathl{I \vDash \Gamma}{.} Dann ist
\mavergleichskette
{\vergleichskette
{I(r) }
{ = }{I(s) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{I(s) }
{ = }{I(t) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und somit auch
\mavergleichskette
{\vergleichskette
{ I(r) }
{ = }{I(t) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} wegen der Transitivität der Gleichheit. Also gilt
\mathl{r \cong_\Gamma t}{,} was die Transitivität beweist. } {Es sei
\mathl{\Gamma \subseteq \Gamma'}{.} Wir behaupten, dass die Äquivalenz
\mathl{s \cong_\Gamma t}{} die Äquivalenz
\mathl{s \cong_{\Gamma'} t}{} impliziert. Es sei dazu
\mathl{s \cong_\Gamma t}{} und eine Interpretation $I$ mit
\mathl{I \vDash \Gamma'}{} gegeben. Dann gilt erst recht
\mathl{I \vDash \Gamma}{} und somit ist
\mathl{I (s)=I(t)}{.} Somit umfassen die Äquivalenzklassen zu $\cong_{\Gamma'}$ die Äquivalenzklassen zu
\mathl{\cong_\Gamma}{,} die Äquivalenzklassen werden also größer. }


}





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

In einer Wohngemeinschaft leben die Personen
\mathl{A,B,C,D,E}{.} Wir betrachten die folgenden Relationen: \aufzaehlungdrei{
\mathl{Txy}{} bedeutet, dass $x$ und $y$ manchmal miteinander Tennis spielen, }{
\mathl{Sxyz}{} bedeutet, dass $x,y$ und $z$ manchmal miteinander Skat spielen, }{
\mathl{Kxyzw}{} bedeutet, dass $x,y,z$ und $w$ manchmal miteinander Doppelkopf spielen. } In der WG gilt
\mathdisp {TDE, SABC, SABE, KACED} { . }
\aufzaehlungfuenf{Charakterisiere umgangssprachlich die Person $D$ allein unter Bezugnahme auf die gegebenen Spielrelationen. }{Charakterisiere umgangssprachlich die Person $C$ allein unter Bezugnahme auf die gegebenen Spielrelationen. }{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $A$. }{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $B$. }{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $E$. }

}
{

\aufzaehlungfuenf{$D$ ist diejenige Person, die manchmal Tennis spielt und kein Skat spielt. }{$C$ ist diejenige Person, die manchmal Skat spielt, und zwar nur bei einer Skatrunde beteiligt ist, und die nicht Tennis spielt. }{
\mathl{\exists y { \left( \exists z \wedge \exists w { \left( z \neq w \wedge Sxyz \wedge Sxyw \right) } \right) } \wedge \exists y \exists z \exists w Kxyzw}{.} }{
\mathl{\neg { \left( \exists y \exists z \exists w Kxyzw \right) }}{.} }{
\mathl{\exists y Txy \wedge \exists y \exists z Sxyz}{.} }


}





\inputaufgabeklausurloesung
{4}
{

Entwerfe ein Programm für eine \definitionsverweis {Registermaschine}{}{,} das nach und nach alle \definitionsverweis {Quadratzahlen}{}{} ausdruckt.

}
{Registermaschine/Alle Quadratzahlen/Druckt/Aufgabe/Lösung }





\inputaufgabeklausurloesung
{4}
{

Es seien
\mathl{T, S \subseteq \N}{} entscheidbare Mengen. Zeige, dass dann auch die Vereinigung
\mathl{T \cup S}{,} der Durchschnitt
\mathl{T \cap S}{} und auch das Komplement
\mathl{\N \setminus T}{} entscheidbar sind.

}
{N/Teilmengen/Entscheidbar/Durchschnitt und Vereinigung/Komplement/Aufgabe/Lösung }





\inputaufgabeklausurloesung
{4}
{

Zeige, dass die Abbildung \maabbeledisp {f} {\N^3} { \N } {(x,y,z)} {xy^2-z^2 + 2z^3 } {,} \zusatzklammer {wohldefiniert und} {} {} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.

}
{

Die Abbildung ist wohldefiniert, da der Ausdruck
\mavergleichskettedisp
{\vergleichskette
{ -z^2+2z^3 }
{ =} { z^2 (2z-1) }
{ } { }
{ } { }
{ } { }
} {}{}{} für
\mathl{z \in \N}{} nie negativ wird. Es sei
\mavergleichskettedisp
{\vergleichskette
{\psi(x,y,z,w) }
{ \defeq} { x \cdot y \cdot y + z \cdot z \cdot z+ z \cdot z \cdot z = w + z \cdot z }
{ } { }
{ } { }
{ } { }
} {}{}{.} Für beliebige natürliche Zahlen
\mathl{(n_1,n_2,n_3,n_4)\in \N^4}{} gilt dann
\mathdisp {\N \vDash \psi (n_1,n_2,n_3,n_4)} { }
genau dann, wenn in $\N$ die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{n_1 \cdot n_2 \cdot n_2 + n_3 \cdot n_3 \cdot n_3 + n_3 \cdot n_3 \cdot n_3 }
{ =} {n_4 + n_3 \cdot n_3 }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt, was genau dann der Fall ist, wenn in $\N$ die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ n_4 }
{ =} { n_1 \cdot n_2 \cdot n_2 - n_3 \cdot n_3 + n_3 \cdot n_3 \cdot n_3 + n_3 \cdot n_3 \cdot n_3 }
{ } { }
{ } { }
{ } { }
} {}{}{} bzw.
\mavergleichskettedisp
{\vergleichskette
{ n_4 }
{ =} { n_1 \cdot n_2^2 - n_3^2 + 2n_3^3 }
{ } { }
{ } { }
{ } { }
} {}{}{,} also
\mavergleichskettedisp
{\vergleichskette
{n_4 }
{ =} {f (n_1,n_2,n_3) }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt. Der Ausdruck $\psi$ repräsentiert also arithmetisch die Funktion $f$.


}





\inputaufgabeklausurloesung
{4}
{

Beweise das Unvollständigkeitslemma.

}
{

Aus der \definitionsverweis {Repräsentierbarkeit}{}{} von
\mathl{\Gamma^\vdash}{} folgt, dass es einen arithmetischen Ausdruck in einer freien Variablen gibt, sagen wir
\mathl{a (x)}{,} mit der Eigenschaft, dass
\mathdisp {\Gamma \vdash s} { }
genau dann gilt, wenn
\mathdisp {\Gamma \vdash a (GN(s))} { }
gilt. Wir betrachten die Negation
\mavergleichskette
{\vergleichskette
{ \beta }
{ = }{ \neg a }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Nach Satz 22.8 (Einführung in die mathematische Logik (Osnabrück 2021)) gibt es für $\beta$ einen Fixpunkt, also einen Satz $q$ mit
\mathdisp {\Gamma \vdash q \longleftrightarrow \beta (GN(q))} { }
bzw.
\mathdisp {\Gamma \vdash q \longleftrightarrow \neg a (GN(q))} { . }
Sowohl aus
\mathl{\Gamma \vdash q}{} als auch aus
\mathl{\Gamma \vdash \neg q}{} ergibt sich dann direkt ein ableitbarer Widerspruch, was der Widerspruchsfreiheit des Systems widerspricht.


}





\inputaufgabeklausurloesung
{6 (1+1+4)}
{

Wir interpretieren den Satz von Sokrates, \anfuehrung{Ich weiß, dass ich nichts weiß}{,} als modallogisches Axiomenschema
\mathdisp {\Box \neg \Box \alpha} { . }
Zeige die folgenden Aussagen. \aufzaehlungdrei{Dieses Axiomenschema ist \definitionsverweis {paradox}{}{.} }{Dieses Axiomenschema ist innerhalb der $K$-\definitionsverweis {Modallogik}{}{} äquivalent zu
\mathdisp {\Box \Diamond \alpha} { . }
}{Dieses Axiomenschema ist innerhalb der $K$-\definitionsverweis {Modallogik}{}{} äquivalent zu
\mathdisp {\Box \alpha} { , }
also zum \definitionsverweis {Leerheitsaxiom}{}{.} }

}
{

\aufzaehlungdrei{Für die Tauotologie
\mavergleichskettedisp
{\vergleichskette
{\alpha }
{ =} { p \vee \neg p }
{ } { }
{ } { }
{ } { }
} {}{}{} ergibt sich, wenn man die Boxen vergisst, der Widerspruch
\mathl{\neg \alpha}{,} also ist das Axiomenschema paradox. }{Es ist
\mathdisp {\Box \neg \Box \alpha \leftrightarrow \Box \Diamond \neg \alpha} { . }
Somit gilt die linke Seite für alle $\alpha$ genau dann, wenn die rechte Seite für alle $\alpha$ gilt, und dies ist in einer $K$-Modallogik äquivalent dazu, dass es für alle $\neg \alpha$ gilt. }{Das Leerheitsaxiom ist offenbar stärker. Wegen der Widerspruchstautologie gilt
\mathdisp {\vdash \Box \beta \wedge \neg \Box \beta \rightarrow \alpha} { . }
Nach Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1) folgt
\mathdisp {\vdash \Box ( \Box \beta \wedge \neg \Box \beta ) \rightarrow \Box \alpha} { }
und nach Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (4) gilt
\mathdisp {\vdash \Box \Box \beta \wedge \Box \neg \Box \beta \rightarrow \Box ( \Box \beta \wedge \neg \Box \beta )} { . }
Mit dem Kettenschluss ergibt sich


\mathdisp {\vdash \Box \Box \beta \wedge \Box \neg \Box \beta \rightarrow \Box \alpha} { . }
Wir setzen nun für $\beta$ eine Tautologie ein, etwa
\mavergleichskette
{\vergleichskette
{\beta }
{ = }{ p \rightarrow p }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Eine doppelte Anwendung der Nezessisierungsregel liefert
\mathdisp {\vdash \Box \Box \beta} { . }
Das Sokratesaxiom liefert
\mathdisp {S \vdash \Box \neg \Box \beta} { . }
Damit sind die beiden Voraussetzungen von oben erfüllt und somit gilt
\mathdisp {S \vdash \Box \alpha} { . }
}


}





\inputaufgabeklausurloesung
{5}
{

Zeige, dass in einem \definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} das modallogische \definitionsverweis {Transitivitätsaxiom}{}{} genau dann gilt, wenn $R$ \definitionsverweis {transitiv}{}{} ist.

}
{

Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst $R$ transitiv und sei
\mathdisp {w \vDash \Box \alpha} { . }
Es sei
\mathl{wRv}{} und
\mathl{vRz}{} und somit
\mathdisp {z \vDash \alpha} { . }
Also ist
\mathdisp {v \vDash \Box \alpha} { . }
und damit
\mathdisp {w \vDash \Box \Box \alpha} { . }

Es sei nun $R$ nicht transitiv und seien
\mavergleichskette
{\vergleichskette
{ w,v,z }
{ \in }{ M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} Punkte mit
\mathl{wRv}{,}
\mathl{vRz}{,} aber nicht
\mathl{wRz}{.} Es sei $p$ eine Aussagenvariable und sei $\mu$ die Belegung, bei der $p$ in allen von $w$ aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist
\mathdisp {w \vDash \Box p} { }
und
\mathdisp {v \not \vDash \Box p} { , }
da ja
\mathl{z \not \vDash p}{,} und somit ist
\mathdisp {w \not \vDash \Box \Box p} { , }
also
\mathdisp {w \not \vDash \Box p \rightarrow \Box \Box p} { . }


}