Kurs:Einführung in die mathematische Logik/5/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}{ 14 }
\renewcommand{\afuenf}{ 5 }
\renewcommand{\asechs}{ 8 }
\renewcommand{\asieben}{ 4 }
\renewcommand{\aacht}{ 5 }
\renewcommand{\aneun}{ 3 }
\renewcommand{\azehn}{ 4 }
\renewcommand{\aelf}{ 4 }
\renewcommand{\azwoelf}{ 3 }
\renewcommand{\adreizehn}{ 7 }
\renewcommand{\avierzehn}{ 64 }
\renewcommand{\afuenfzehn}{ }
\renewcommand{\asechzehn}{ }
\renewcommand{\asiebzehn}{ }
\renewcommand{\aachtzehn}{ }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabelledreizehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Die zu einer \zusatzklammer {aussagenlogischen} {} {} Wahrheitsbelegung \maabbdisp {\lambda} { V} { \{0,1\} } {} auf einer Aussagenvariablenmenge $V$ zugehörige \stichwort {Interpretation} {} auf der Sprache $L^V$.
}{Das \stichwort {Alphabet einer Sprache erster Stufe} {.}
}{Ein \stichwort {Nichtstandardmodell} {} zu einem fixierten $S$-Modell $M$.
}{Die \stichwort {Arithmetische Repräsentierbarkeit} {} einer Abbildung \maabbdisp {F} {\N^r} {\N^s } {.}
}{Eine
\stichwort {vollständige} {}
Theorie
\mathl{T \subseteq L^S_0}{.}
}{Das \stichwort {universelle modallogische Modell} {} zu einem $K$-\definitionsverweis {modallogischen System}{}{} $\Gamma$. }
}
{
\aufzaehlungsechs{Die zugehörige
Interpretation
\mavergleichskette
{\vergleichskette
{I
}
{ = }{I^\lambda
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
wird rekursiv über den Aufbau der Sprache wie folgt festgelegt.
\aufzaehlungsechs{
\mathl{I(v)= \lambda (v)}{} für jede Aussagenvariable
\mathl{v \in V}{.}
}{Bei
\mathl{\alpha = \neg ( \beta)}{} ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1, \text{ falls } I( \beta) = 0 \, , \\ 0 , \text{ falls } I( \beta)= 1 \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ (\beta) \wedge ( \gamma)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1, \text{ falls } I( \beta) = I( \gamma) = 1\, , \\ 0 \text{ sonst}\, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ (\beta) \vee (\gamma)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1, \text{ falls } I( \beta) = 1 \text{ oder } I( \gamma) = 1 \, , \\ 0, \text{ falls } I( \beta) = I( \gamma) = 0 \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{( \beta) \rightarrow ( \gamma)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1 , \text{ falls } I( \beta) = 0 \text{ oder } I( \gamma) = 1 \, , \\ 0 , \text{ falls } I( \beta) = 1 \text{ und } I( \gamma) = 0 \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{( \beta) \leftrightarrow ( \gamma)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{I( \alpha)
}
{ =} { \begin{cases} 1 , \text{ falls } I( \beta) = I( \gamma) \, , \\ 0 , \text{ falls } I( \beta) \neq I( \gamma) \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}
}{Das
Alphabet einer Sprache erster Stufe
umfasst die folgenden Daten.
\aufzaehlungsechs{Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
}{Zu jeder natürlichen Zahl
\mathl{n \in \N_+}{} eine Menge
\mathl{R_n}{} von $n$-stelligen Relationssymbolen.
}{Die aussagenlogischen Junktoren
\mathdisp {\neg, \, \wedge, \, \vee, \, \rightarrow , \, \leftrightarrow} { . }
}{Das Gleichheitszeichen
\mathl{=}{.}
}{Die Quantoren
\mathkor {} {\forall} {und} {\exists} {.}
}{Klammern, also $($ und $)$.
}
}{Man nennt eine weitere $S$-Struktur $M'$, die zu $M$
\definitionsverweis {elementar äquivalent}{}{,}
aber nicht zu $M$
$S$-\definitionsverweis {isomorph}{}{}
ist, ein
Nichtstandardmodell
von $M$.
}{Die Abbildung $F$ heißt arithmetisch repräsentierbar, wenn es einen
\mathl{L^{\rm Ar}}{-}Ausdruck $\psi$ in
\mathl{r+s}{}
\definitionsverweis {freien Variablen}{}{}
derart gibt, dass für alle $(r+s)$-Tupel
\mathl{(n_1 , \ldots , n_{r+s}) \in \N^{r+s}}{} die Äquivalenz
\mavergleichskette
{\vergleichskette
{ F(n_1 , \ldots , n_{r})
}
{ = }{(n_{r+1} , \ldots , n_{r+s})
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann, wenn
\mathl{\N \vDash \psi(n_1 , \ldots , n_{r+s})}{} gilt.
}{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}{.}
}{Die Menge $U_\Gamma$ aller $\Gamma$ umfassenden,
\zusatzklammer {aussagenlogisch} {} {}
maximal widerspruchsfreien Teilmengen
\mavergleichskettedisp
{\vergleichskette
{W
}
{ \subseteq} {L
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit der durch
\mathdisp {WRV \text { genau dann, wenn für jedes } \alpha \in L \text { mit } \alpha \in V \text{ die Beziehung } \Diamond \alpha \in W \text{ gilt}} { . }
gegebenen Erreichbarkeitsrelation und der durch
\mathl{W \vdash p}{,} wenn
\mathl{p \in W}{,} festgelegten Belegung $\nu$ heißt das $\Gamma$-universelle modallogische Modell.
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz von Henkin.}{Der Satz über das \stichwort {Halteproblem} {.}}{Der Satz über die Unvollständigkeit der Peano-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 erststufige
\definitionsverweis {Peano-Arithmetik}{}{}
ist
\definitionsverweis {unvollständig}{}{.}}
}
\inputaufgabeklausurloesung
{1}
{
Beurteile die Snookerweisheit \anfuehrung{Ein Snookerspiel kann man in der ersten Session nicht gewinnen, aber verlieren}{} vom logischen Standpunkt aus.
}
{
Es spielen zwei Spieler gegeneinander, der eine gewinnt genau dann, wenn der andere verliert. Wenn einer also in der ersten Session verlieren kann, so kann auch einer \zusatzklammer {nämlich der andere} {} {} in der ersten Session gewinnen. Die Weisheit ist also unlogisch.
}
\inputaufgabeklausurloesung
{14 (2+5+2+5)}
{
Es sei
\mathbed {p_i} {}
{i \in I} {}
{} {} {} {,}
eine Familie von Aussagenvariablen und $L$ die zugehörige aussagenlogische Sprache. Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
bestehend aus den Variablen
\mathbed {x_i} {}
{i \in I} {}
{} {} {} {,}
und dem einen Konstantensymbol $c$ und es sei $L^S$ die zugehörige prädikatenlogische Sprache. Es sei
\mavergleichskettedisp
{\vergleichskette
{ \beta_i
}
{ \defeq} { x_i = c
}
{ \in} { L^S
}
{ } {
}
{ } {
}
}
{}{}{.}
\aufzaehlungvier{Definiere rekursiv eine natürliche Abbildung
\maabbdisp {\Psi} {L} {L^S
} {,}
die $p_i$ auf $\beta_i$ abbildet.
}{Ist $\Psi$ injektiv?
}{Ist $\Psi$ surjektiv?
}{Zeige für alle
\mathl{\alpha \in L}{,} dass
\mathl{\vdash \alpha}{}
\zusatzklammer {im Ableitungskalkül der Aussagenlogik} {} {}
genau dann gilt, wenn
\mathl{\vdash \Psi ( \alpha)}{}
\zusatzklammer {im Ableitungskalkül der Prädikatenlogik} {} {} gilt.
}
}
{
\aufzaehlungvier{Wir definieren die Abbildung $\Psi$ rekursiv über den Aufbau von $L$. Für eine Aussagenvariable $p_i$ setzen wir
\mavergleichskettedisp
{\vergleichskette
{\Psi(p_i)
}
{ \defeq} { \beta_i
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Für
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { \neg \beta
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
setzen wir
\mavergleichskettedisp
{\vergleichskette
{ \Psi ( \alpha)
}
{ =} { \neg \Psi ( \beta)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und für
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { \alpha_1 \wedge \alpha_2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
setzen wir
\mavergleichskettedisp
{\vergleichskette
{ \Psi ( \alpha)
}
{ =} { \Psi ( \alpha_1) \wedge \Psi ( \alpha_1)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und entsprechend für $\rightarrow$.
}{Wir beweisen die Injektivität in der Form, dass sich aus
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ \neq} { \alpha'
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die Verschiedenheit
\mavergleichskettedisp
{\vergleichskette
{ \Psi( \alpha )
}
{ \neq} { \Psi( \alpha' )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ergibt, und zwar durch Induktion über den Aufbau von $\alpha$
\zusatzklammer {simultan für alle $\alpha'$} {} {.}
Für
\mavergleichskettedisp
{\vergleichskette
{\alpha
}
{ =} {p_i
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist $\alpha'$ entweder eine andere Aussagenvariable, sagen wir
\mathl{p_j}{} mit
\mavergleichskette
{\vergleichskette
{i
}
{ \neq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder ein Ausdruck, der zumindest einen aussagenlogischen Junktor enthält. Im ersten Fall ist
\mavergleichskettedisp
{\vergleichskette
{\Psi (p_j)
}
{ =} { (x_j = c)
}
{ \neq} { (x_i = c)
}
{ =} { \Psi(p_i)
}
{ } {
}
}
{}{}{}
und im zweiten Fall enthält
\mathl{\Psi( \alpha')}{} mindestens einen Junktor und ist deshalb von
\mathl{\Psi(p_i)}{} verschieden.
Es sei nun
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { \neg \beta
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und dies sei von $\alpha'$ verschieden. Wenn $\alpha'$ keine Negation ist, so ist auch
\mathl{\Psi ( \alpha')}{} keine Negation und damit von
\mavergleichskette
{\vergleichskette
{ \Psi ( \alpha)
}
{ = }{ \neg \Psi( \beta )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
verschieden. Wenn hingegen $\alpha'$ eine Negation ist, so ist
\mavergleichskette
{\vergleichskette
{ \alpha'
}
{ = }{ \neg \beta'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und wegen der Verschiedenheit ist
\mavergleichskette
{\vergleichskette
{ \beta
}
{ \neq }{\beta'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Nach Induktionsvoraussetzung ist
\mavergleichskettedisp
{\vergleichskette
{\Psi ( \beta )
}
{ \neq} {\Psi ( \beta' )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und dies überträgt sich auf die negierten Ausdrücke.
Es sei nun
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { \alpha_1 \wedge \alpha_2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und dies sei von $\alpha'$ verschieden. Wenn $\alpha'$ kein konjugierter Ausdruck ist, so ist auch
\mathl{\Psi ( \alpha')}{} kein konjugierter Ausdruck und damit ist
\mavergleichskette
{\vergleichskette
{ \Psi ( \alpha)
}
{ \neq }{ \Psi( \alpha' )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wenn hingegen $\alpha'$ ebenfalls ein konjugierter Ausdruck ist, so ist
\mavergleichskette
{\vergleichskette
{ \alpha'
}
{ = }{ \alpha_1' \wedge \alpha_2'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und wegen der Verschiedenheit ist
\mavergleichskette
{\vergleichskette
{ \alpha_1
}
{ \neq }{\alpha_1'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{ \alpha_2
}
{ \neq }{\alpha_2'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Sagen wir der erste Fall liegt vor. Nach Induktionsvoraussetzung ist dann
\mavergleichskettedisp
{\vergleichskette
{\Psi ( \alpha_1 )
}
{ \neq} {\Psi ( \alpha_1' )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und dies überträgt sich auf die konjugierten Ausdrücke.
}{Die Abbildung ist nicht surjektiv, da der Ausdruck
\mavergleichskette
{\vergleichskette
{c
}
{ = }{c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nicht zum Bild gehört, da jedes $\alpha$ mindestens eine Aussagenvariable $p_i$ und somit $\Psi(p_i)$ mindestens eine Variable $x_i$ enthält.
}{Es gelte zunächst
\mathdisp {\vdash \alpha} { . }
Dann gibt es eine Ableitung im Aussagenkalkül für diesen Ausdruck. Diese Ableitung beruht allein auf aussagenlogischen Grundtautologien und dem Modus ponens. Wenn man in dieser Ableitung überall die Aussagenvariablen $p_i$ durch
\mathl{\beta_i}{} ersetzt, so werden aus den aussagenlogischen Grundtautologien prädikatenlogische Grundtautologien und der Modus ponens bleibt erhalten. Man erhält also durch diese Ersetzung eine prädikatenlogische Ableitung für
\mathl{\Psi( \alpha )}{} und somit ist
\mathl{\vdash \Psi( \alpha )}{.}
Wenn hingegen
\mathdisp {\not\vdash \alpha} { }
gilt, so ist $\alpha$ nach dem Vollständigkeitssatz der Aussagenlogik nicht allgemeingültig. Es gibt also eine Wahrheitsbelegung $\lambda$ für die Aussagenvariablen derart, dass $\alpha$ unter der zugehörigen
\zusatzklammer {aussagenlogischen} {} {}
Interpretation $I^\lambda$ den Wahrheitswert $0$ bekommt. Es sei nun
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\{a,b \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine zweielementige Menge. Wir definieren eine $S$-Interpretation $J$ auf $M$ durch
\mavergleichskettedisp
{\vergleichskette
{c^M
}
{ =} {a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{x_i^M
}
{ \defeq} { \begin{cases} a, \text{ falls } \lambda (p_i) = 1 \, ,\\ b, \text{ falls } \lambda (x_i) = 0 \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Mit dieser Festlegung ist
\mathl{I^\lambda \vDash p_i}{} genau dann, wenn
\mathl{J \vDash \beta_i}{} ist. Da die aussagenlogischen Junktoren unter $I^\lambda$ und $J$ gleichermaßen interpretiert werden, ist wegen
\mathl{I^\lambda \not \vDash \alpha}{} auch
\mathl{J \not \vDash \Psi( \alpha )}{.} Daher ist $\Psi(\alpha )$ nicht allgemeingültig und kann wegen der Korrektheit des Ableitungkalküls für die Prädikatenlogik auch nicht ableitbar sein. Also
\mathl{\not \vdash \Psi(\alpha)}{.}
}
}
\inputaufgabeklausurloesung
{5}
{
Es seien
\mathl{A,B,C}{} einstellige Relationssymbole. Zeige, dass der \stichwort {Modus Barbara} {,} also die Aussage
\mathdisp {( \forall x (Ax \rightarrow Bx) \wedge \forall x (Bx \rightarrow Cx) ) \rightarrow ( \forall x (Ax \rightarrow Cx) )} { }
im Prädikatenkalkül
\definitionsverweis {ableitbar}{}{}
ist.
}
{
Aus aussagenlogischen Gründen
\zusatzklammer {Transitivität der Implikation} {} {}
gilt
\mathdisp {\vdash (Ax \rightarrow Bx) \wedge (Bx \rightarrow Cx) \rightarrow (Ax \rightarrow Cx)} { . }
Aus einer ableitbaren Implikation
\mathdisp {\vdash \alpha \rightarrow \beta} { }
ergibt sich mittels der Alleinführung im Antezedens
\mathdisp {\vdash \forall x \alpha \rightarrow \alpha} { }
und dem Kettenschluss
\mathdisp {\vdash \forall x \alpha \rightarrow \beta} { }
und daraus mit der Alleinführung im Sukzedens, die anwendbar ist, da $x$ vorne und in
\mathl{\forall x \beta}{} gebunden ist,
\mathdisp {\vdash \forall x \alpha \rightarrow \forall x \beta} { . }
Angewendet auf die eingangs aufgeführte Situation ergibt dies
\mathdisp {\vdash \forall x ( (Ax \rightarrow Bx) \wedge (Bx \rightarrow Cx) ) \rightarrow \forall x (Ax \rightarrow Cx)} { . }
Nach
Lemma 11.9 (Einführung in die mathematische Logik (Osnabrück 2021)) (2)
ist
\mathdisp {\vdash \forall x { \left( \alpha \wedge \beta \right) } \leftrightarrow { \left( \forall x \alpha \wedge \forall x \beta \right) }} { }
und so kann man vorne die Allaussage der Konjunktion durch die Konjunktion der Allaussagen ersetzen und erhält die Behauptung.
}
\inputaufgabeklausurloesung
{8}
{
Beweise den Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell $(N,0,\prime)$.
}
{
Wir betrachten Teilmengen
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit den Eigenschaften
\aufzaehlungdrei{
\mavergleichskette
{\vergleichskette
{0
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Für jedes
\mathbed {n \in S} {,}
{n \neq 0} {}
{} {} {} {,}
gibt es ein
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{n
}
{ = }{k'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Es gibt eine eindeutig bestimmte Abbildung
\maabbdisp {\varphi_S} {S} {M
} {}
mit
\mavergleichskette
{\vergleichskette
{\varphi_S(0)
}
{ = }{ s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{\varphi_S (n')
}
{ =} { F( \varphi_S (n) )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ n,n'
}
{ \in }{ S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Wir betrachten nun die Menge
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{T
}
{ =} { { \left\{ k \in N \mid \text{Es gibt ein } S \text{ mit den beschriebenen Eigenschaften und mit } k \in S \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir zeigen durch Induktion, dass
\mavergleichskette
{\vergleichskette
{T
}
{ = }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Für
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
können wir
\mavergleichskettedisp
{\vergleichskette
{S
}
{ =} {\{0\}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
wählen, wobei $\varphi_{ \{0\} }$ durch die erste Abbildungseigenschaft eindeutig festgelegt ist. Es sei nun
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vorausgesetzt. Das bedeutet, dass es
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und eine Abbildung $\varphi_S$ mit den angegebenen Eigenschaften gibt. Bei
\mavergleichskette
{\vergleichskette
{k'
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind wir fertig, sei also
\mavergleichskette
{\vergleichskette
{k'
}
{ \notin }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir setzen
\mavergleichskette
{\vergleichskette
{S'
}
{ = }{ S \cup \{k'\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und wir definieren
\mavergleichskettedisp
{\vergleichskette
{ \varphi_{S'} ( n)
}
{ =} { \begin{cases} \varphi_{S} ( n)\, , \text{ falls } n \in S \, , \\ F(\varphi_S(k)) \, , \text{ falls } n = k' \, .\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Dies erfüllt die Eigenschaften und ist auch die einzige Möglichkeit, da die Einschränkung von
\mathl{\varphi_{S'}}{} auf $S$ wegen der Eindeutigkeit mit $\varphi_S$ übereinstimmen muss. Also ist
\mavergleichskette
{\vergleichskette
{T
}
{ = }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir zeigen nun durch Induktion über $k$, dass
\mathl{\varphi_S(k)}{} unabhängig von der gewählten Menge
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Bei
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dies klar, sei diese Aussage für ein gewisses $k$ schon bekannt, und sei
\mavergleichskette
{\vergleichskette
{k'
}
{ \in }{ S_1, S_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit zugehörigen Abbildungen
\mathl{\varphi_1=\varphi_{S_1},\varphi_2=\varphi_{S_2}}{.} Aufgrund der zweiten Eigenschaft ist
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{ S_1, S_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
daher ist nach Induktionsvoraussetzung
\mavergleichskettedisp
{\vergleichskette
{ \varphi_1(k')
}
{ =} { F( \varphi_1 (k))
}
{ =} { F( \varphi_2 (k))
}
{ =} { \varphi_2(k')
}
{ } {
}
}
{}{}{.}
Damit erhält man durch
\mavergleichskettedisp
{\vergleichskette
{\varphi(k)
}
{ \defeq} { \varphi_S(k)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit einem beliebigen
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine wohldefinierte Abbildung auf ganz $N$ mit den in der Formulierung des Satzes geforderten Eigenschaften. Die Eindeutigkeit von $\varphi$ ergibt sich aus der Eindeutigkeit der Einschränkungen.
}
\inputaufgabeklausurloesung
{4}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Ausdrucksmenge}{}{.}
Begründe, warum man im Allgemeinen bei der Hinzunahme von Beispielen
\zusatzklammer {innerhalb des Beweises des Vollständigkeitssatzes} {} {}
nicht für alle Existenzaussagen
\mathl{\exists x \alpha \in L^S}{} mit einer einzigen neuen Variablen $z$ arbeiten kann.
}
{
Es sei $\Gamma$ derart, dass es eine Aussage
\mathl{\alpha \in L^S}{} gibt, für die sowohl
\mathl{\exists x \alpha}{} als auch
\mathl{\exists x \neg \alpha}{} zu $\Gamma$ gehört. Beispielsweise kann man
\mavergleichskettedisp
{\vergleichskette
{\Gamma
}
{ =} { \{\exists x x = c , \exists x \neg x = c \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit einer Konstanten $c$ nehmen. Eine solche Ausdrucksmenge ist widerspruchsfrei, da sie
\zusatzklammer {über jeder Menge mit mindestens zwei Elementen} {} {}
erfüllbar ist. Wenn man nur eine neue Variable $z$ zur Verfügung hat, so muss man die beiden Aussagen
\mathkor {} {\exists x \alpha \rightarrow \alpha { \frac{ z }{ x } }} {und} {\exists x \neg \alpha \rightarrow \neg \alpha { \frac{ z }{ x } }} {}
hinzunehmen. Aus der neuen Ausdrucksmenge $\Gamma'$ würde dann sowohl
\mathl{\alpha { \frac{ z }{ x } }}{} als auch
\mathl{\neg \alpha { \frac{ z }{ x } }}{} ableitbar sein, und somit wäre $\Gamma'$ widersprüchlich.
}
\inputaufgabeklausurloesung
{5}
{
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 die Beziehungen
\mathdisp {MA,MB,MC,MD,ME,MF, PA,PD, SAD,SBE} { . }
\aufzaehlungfuenf{Für welche Personen ist die Äquivalenzklasse zur elementaren Äquivalenz einelementig, für welche nicht?
}{Bestimme die
\definitionsverweis {Automorphismengruppe}{}{}
des Zugabteils.
}{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 $E$.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{M,P,S}{} diejenigen Äquivalenzklassen, die aus mindestens zwei Personen bestehen.
}
}
{
\aufzaehlungfuenf{Für
\mathl{A,B,D,E}{} sind die Äquivalenzklassen einelementig, die Teilmenge
\mathl{\{C,F\}}{} bilden eine Äquivalenzklasse.
}{Die Automorphismengruppe ist eine zyklische Gruppe der Ordnung $2$, da man $C$ und $F$ miteinander vertauschen kann und die anderen Personen nicht.
}{$A$ ist diejenige Person, die am Fenster sitzt und eine Fahrkarte klaut.
}{
\mathl{\neg Px \wedge \exists y Syx}{.}
}{
\mathl{\neg \exists y Sxy \wedge \neg \exists y Syx}{.}
}
}
\inputaufgabeklausurloesung
{3 (1+1+1)}
{
Die Registerabteilung des VW-Konzerns hat
\zusatzgs {ohne Wissen des Vorstandes und am Aufsichtsrat vorbei} {}
in jedes real existierende Registerprogramm $P$ an einer willkürlich gewählten Stelle die aufeinanderfolgenden Befehlszeilen eingebaut
\zusatzklammer {und dabei die Zeilennummern und die Sprungbefehlsnummern angepasst, $k$ ist die Nummer eines in $P$ nicht verwendeten Registers und $h'$ ist die neue Haltebefehlsnummer} {} {}
\mathdisp {k+} { }
\mathdisp {k+} { }
\mathdisp {\text{Drucke}} { }
\mathdisp {C(k,h')} { . }
\aufzaehlungdrei{Ändert sich durch diese Manipulation die Halteeigenschaft des Programms?
}{Ändert sich durch diese Manipulation die Programmabbildung?
}{Nachdem der Skandal herauskommt und die Öffentlichkeit eine Erklärung fordert, diskutieren Vorstand, Aufsichtsrat und Abteilungsleiter die folgenden möglichen Stellungsnahmen für die anstehende Pressekonferenz:
a) Man wollte Speicherplatz sparen.
b) Man wollte aus Werbezwecken erreichen, dass jedes Registerprogramm mindestens einmal \anfuehrung{VW}{} ausdruckt.
c) Man wollte einen Beitrag zur Entschleunigung leisten, indem man manche Programme etwas langsamer macht.
d) Man wollte einen Beitrag zur Entschleunigung leisten, indem man alle Programme etwas langsamer macht.
Welche dieser Erklärungen passen inhaltlich zu den Manipulationen? }
}
{
\aufzaehlungdrei{Nein. Da die Zeilennummern angepasst werden, wird der neue Programmabschnitt
\zusatzklammer {wenn überhaupt} {} {}
von Anfang an durchlaufen und wenn der Befehl
\mathl{C(k,h')}{} abgearbeitet wird ist das $k$-te Register nicht leer, also wird nicht zum Haltebefehl gewechselt, und das Programm läuft einfach weiter.
}{Ja, und zwar schon deshalb, da sich die Anzahl der Programmzeilen ändert.
}{Da ein Register mehr verwendet wird, wird kein Speicherplatz gespart und da der zusätzliche Befehl den Inhalt des ersten Registers ausdruckt, dessen Inhalt aber eine Zahl und nicht \anfuehrung{VW}{} ist, sind a) und b) inhaltlich unpassend. Da das neue Programm zusätzliche Befehle abarbeitet, wird das Programm langsamer, allerdings nur, wenn der neue Programmabschnitt auch durchlaufen wird. Es kann aber durch Sprungbefehle sein, dass der neue Programmabschnitt übersprungen wird. Daher ist nur c) richtig.
}
}
\inputaufgabeklausurloesung
{4}
{
Erläutere die Unentscheidbarkeit der Arithmetik und skizziere in Grundzügen, wie man sie beweisen kann.
}
{Unentscheidbarkeit der Arithmetik/Erläuterung/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{4}
{
Es sei
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine fixierte natürliche Zahl und
\mavergleichskettedisp
{\vergleichskette
{ \alpha (x)
}
{ \defeq} { x = n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei $n$ durch die $n$-fache Summe der $1$ mit sich selbst realisiert werde. Zeige direkt, dass es Sätze
\mavergleichskette
{\vergleichskette
{ p,q
}
{ \in }{ L^{\rm Ar}_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathdisp {\N \vDash \alpha(GN(p)) \leftrightarrow p} { }
und mit
\mathdisp {\N \vDash \neg \alpha(GN(q)) \leftrightarrow q} { }
gibt.
}
{
Es gibt unendlich viele arithmetische Sätze, die bei der Interpretation in $\N$ gültig sind und unendlich viele arithmetische Sätze, die bei der Interpretation in $\N$ ungültig sind. Insbesondere gibt es solche Sätze, deren Gödelnummer nicht $n$ ist. Es sei nun $p$ ein in $\N$ ungültiger Satz, dessen Gödelnummer nicht $n$ ist. Dann ist
\mathdisp {\N \vDash \neg \alpha(GN(p)) \text{ und } \N \vDash \neg p} { , }
also
\mathdisp {\N \vDash \alpha(GN(p)) \leftrightarrow p} { . }
Wenn hingegen $q$ ein in $\N$ gültiger Satz ist, dessen Gödelnummer nicht $n$ ist, so ist
\mathdisp {\N \vDash \neg \alpha(GN(q)) \text{ und } \N \vDash q} { , }
also
\mathdisp {\N \vDash \neg \alpha(GN(q)) \leftrightarrow q} { . }
}
\inputaufgabeklausurloesung
{3}
{
Zeige, dass im
$K$-\definitionsverweis {System}{}{}
der Ausdruck
\mathdisp {\Box ( \alpha \rightarrow \beta ) \rightarrow ( \Diamond \alpha \rightarrow \Diamond \beta )} { }
\definitionsverweis {ableitbar}{}{}
ist.
}
{
Das Distributionsaxiom liefert
\mathdisp {\vdash \Box( \neg \beta \rightarrow \neg \alpha) \rightarrow (\Box \neg \beta \rightarrow \Box \neg \alpha)} { . }
Dabei ist aufgrund der Kontraposition und
Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021)) (1)
der Vordersatz äquivalent zu
\mathdisp {\Box (\alpha \rightarrow \beta)} { . }
Nach Kontraposition ist der Nachsatz äquivalent zu
\mathdisp {\neg \Box \neg \alpha \rightarrow \neg \Box \neg \beta} { , }
was gerade
\mathdisp {\Diamond \alpha \rightarrow \Diamond \beta} { }
bedeutet. Es ergibt sich also die Ableitung
\mathdisp {\vdash \Box (\alpha \rightarrow \beta) \rightarrow (\Diamond \alpha \rightarrow \Diamond \beta)} { . }
}
\inputaufgabeklausurloesung
{7}
{
Zeige, dass in einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} das modallogische
\definitionsverweis {Löb-Axiom}{}{}
genau dann gilt, wenn $R$
\definitionsverweis {transitiv}{}{}
ist und es in $M$ keine unendlichen Ketten gibt.
}
{
Wir arbeiten mit der Kontraposition des Löb-Axioms, also mit
\mathdisp {\Diamond \alpha \rightarrow \Diamond (\alpha \wedge \neg \Diamond \alpha )} { . }
Es sei zunächst vorausgesetzt, dass
\mathl{(M,R)}{} die graphentheoretischen Eigenschaften besitzt. Sei
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mathdisp {w \vDash \Diamond \alpha} { . }
Dann gibt es eine Welt
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{wRv}{} und mit
\mathdisp {v \vDash \alpha} { . }
Wir betrachten Ketten
\mathl{vRv_2, v_2Rv_3, \ldots}{} mit
\mathl{v_i \vDash \alpha}{.} Da es keine unendliche Kette gibt, bricht eine solche Kette ab, sagen wir in $v_n$. In $v_n$ gilt dann
\mathdisp {v_n \vDash \alpha \wedge \neg \Diamond \alpha} { . }
Wegen der Transitivität ist $v_n$ von $w$ aus erreichbar und somit ist
\mathdisp {w \vDash \Diamond (\alpha \wedge \neg \Diamond \alpha)} { . }
Es sei nun vorausgesetzt, dass
\mathl{(M,R)}{} nicht die Eigenschaften erfüllt. Wenn $R$ nicht transitiv ist, so ist nach
Lemma 25.18 (Einführung in die mathematische Logik (Osnabrück 2021))
in Verbindung mit
Lemma 26.9 (Einführung in die mathematische Logik (Osnabrück 2021))
die Gültigkeit des Löb-Axioms ausgeschlossen. Es sei also eine unendlich lange Kette der Form
\mathl{w_n R w_{n+1}}{} gegeben. Wir belegen
\mathl{w_n \vDash p}{} für alle
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mathl{v \vDash \neg p}{} für alle anderen Welten. Dann gilt
\mathdisp {w_0 \vDash \Diamond p \wedge \neg \Diamond ( p \wedge \neg \Diamond p )} { , }
da außerhalb der Kette stets
\mathl{\neg p}{} gilt und innerhalb der Kette stets
\mathl{\Diamond p}{} gilt.
}