Kurs:Einführung in die mathematische Logik/6/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}{ 5 }
\renewcommand{\asechs}{ 1 }
\renewcommand{\asieben}{ 2 }
\renewcommand{\aacht}{ 2 }
\renewcommand{\aneun}{ 8 }
\renewcommand{\azehn}{ 3 }
\renewcommand{\aelf}{ 4 }
\renewcommand{\azwoelf}{ 0 }
\renewcommand{\adreizehn}{ 10 }
\renewcommand{\avierzehn}{ 0 }
\renewcommand{\afuenfzehn}{ 4 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 48 }
\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 {Mersennesche Primzahl} {.}
}{Die \zusatzklammer {rekursiv definierte} {} {} \stichwort {Gültigkeit} {} eines prädikatenlogischen $S$-Ausdruckes $\alpha$ bei einer $S$-\definitionsverweis {Interpretation}{}{} auf einer Menge $M$.
}{Ein \stichwort {Isomorphismus} {} \maabbdisp {\varphi} {M} {N } {} zwischen zwei $S$-Strukturen \mathkor {} {M} {und} {N} {.}
}{Die
\stichwortpraemath {R} {Aufzählbarkeit}{}
einer Teilmenge
\mathl{T \subseteq \N}{.}
}{Das \definitionsverweis {modallogische}{}{} \stichwort {Transitivitätsaxiom} {.}
}{Die rekursive Definition der
\stichwort {Gültigkeit} {}
eines modallogischen Ausdrucks $\alpha$ in einem
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R,\mu)}{.}
}
}
{
\aufzaehlungsechs{Eine
\definitionsverweis {Primzahl}{}{}
der Form
\mathl{2^n-1}{} heißt Mersennesche Primzahl.
}{Die
$S$-\definitionsverweis {Ausdrücke}{}{}
werden folgendermaßen als gültig charakterisiert
\zusatzklammer {dabei seien
\mathl{s,t,t_1 , \ldots , t_n}{} Terme und $\alpha,\beta$ Ausdrücke} {} {.}
\aufzaehlungsieben{
\mathl{I \vDash s = t}{,} wenn
\mathl{I(s)=I(t)}{.}
}{
\mathl{I \vDash Rt_1 \ldots t_n}{,} wenn
\mathl{(I(t_1) , \ldots , I(t_n)) \in R^M}{.}
}{
\mathl{I \vDash \neg { \left( \alpha \right) }}{,} wenn nicht
\mathl{I \vDash \alpha}{} gilt.
}{
\mathl{I \vDash { \left( \alpha \right) } \wedge { \left( \beta \right) }}{,} wenn
\mathl{I \vDash \alpha}{} und
\mathl{I \vDash \beta}{} gilt.
}{
\mathl{I \vDash { \left( \alpha \right) } \rightarrow { \left( \beta \right) }}{,} wenn die Gültigkeit
\mathl{I \vDash \alpha}{} die Gültigkeit
\mathl{I \vDash \beta}{} impliziert.
}{
\mathl{I \vDash \exists x \alpha}{,} wenn es ein
\mathl{m \in M}{} gibt mit
\mathl{I \frac{m}{x} \vDash \alpha}{.}
}{
\mathl{I \vDash \forall x \alpha}{,} wenn für alle
\mathl{m \in M}{} die Beziehung
\mathl{I \frac{m}{x} \vDash \alpha}{} gilt.
}
}{\maabbdisp {\varphi} {M} {N
} {}
heißt
$S$-Isomorphismus,
wenn $\varphi$
\definitionsverweis {bijektiv}{}{}
ist und sowohl $\varphi$ als auch die
\definitionsverweis {Umkehrabbildung}{}{}
\mathl{\varphi^{-1}}{} ein
$S$-\definitionsverweis {Homomorphismus}{}{}
ist.
}{Man sagt, dass $T$
$R$-aufzählbar
ist, wenn es ein Programm $P$ für eine Registermaschine gibt, die bei Eingabe von $0$ nach und nach genau die Zahlen aus $T$ ausdruckt.
}{Das
\definitionsverweis {modallogische Axiomenschema}{}{}
\mathdisp {\Box \alpha \rightarrow \Box \Box \alpha} { }
nennt man
Transitivitätsaxiom.
}{Die Gültigkeit wird rekursiv wie folgt definiert: Es sei der modallogische Ausdruck $\alpha$ schon für jeden Weltpunkt definiert. Dann setzt man für einen jeden Weltpunkt
\mathl{w \in M}{}
\mathdisp {w \vDash \Box \alpha} { }
genau dann, wenn in jeder von $w$ aus erreichbaren Welt $v$ die Beziehung
\mathdisp {v \vDash \alpha} { }
gilt.
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen (abzählbarer Fall).}{Das \stichwort {Koinzidenzlemma} {.}}{Das \stichwort {Unvollständigkeitslemma} {.}}
}
{
\aufzaehlungdrei{Es sei $V$ eine
\definitionsverweis {abzählbare}{}{}
Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mathl{\Gamma \subseteq L^V}{} eine
\definitionsverweis {widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}
Dann kann man $\Gamma$ durch sukzessive Hinzunahme von entweder
\mathl{p_n}{} oder
\mathl{\neg p_n}{} und durch Abschluss unter der
\definitionsverweis {Ableitungsbeziehung}{}{}
zu einer maximal widerspruchsfreien Teilmenge
\mathl{\Gamma' \supseteq \Gamma}{} ergänzen.}{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. Dann gelten folgende 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}{.}
}}{Es sei $\Gamma$ eine widerspruchsfreie, arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Die Ableitungsmenge
\mathl{\Gamma^\vdash}{}
\zusatzklammer {also die Menge der zugehörigen Gödelnummern} {} {}
sei
\definitionsverweis {schwach repräsentierbar}{}{}
in $\Gamma$. Dann gibt es einen arithmetischen Satz
\mathl{q \in L^{\rm Ar}_0}{} derart, dass weder $q$ noch seine Negation $\neg q$ aus $\Gamma$ ableitbar ist.}
}
\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} {f} } {\tabellenzeiledrei {f} {w} {w} } {\tabellenzeiledrei {f} {f} {f} }
}
{
\mathl{q}{.}
}
\inputaufgabeklausurloesung
{2}
{
Beweise die aussagenlogische Tautologie
\mathdisp {\vdash \alpha\rightarrow (\beta \rightarrow \alpha \wedge \beta)} { }
aus den aussagenlogischen
\definitionsverweis {Axiomen}{}{.}
}
{
Es ist
\mathdisp {\vdash \alpha \wedge \beta \rightarrow \alpha \wedge \beta} { }
nach
Lemma 3.11 (Einführung in die mathematische Logik (Osnabrück 2021))
und
\mathdisp {\vdash { \left( \alpha \wedge \beta \rightarrow \alpha \wedge \beta \right) } \rightarrow { \left( \alpha \rightarrow { \left( \beta \rightarrow \alpha \wedge \beta \right) } \right) }} { }
nach
Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))
(4).
Modus ponens liefert
\mathdisp {\vdash \alpha \rightarrow { \left( \beta \rightarrow \alpha \wedge \beta \right) }} { . }
}
\inputaufgabeklausurloesung
{5}
{
Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$. Es sei $\Gamma$
\definitionsverweis {widerspruchsfrei}{}{,}
abgeschlossen unter Ableitungen und für jede Aussagenvariable
\mathl{p \in V}{} gelte
\mathl{p \in \Gamma}{} oder
\mathl{\neg p \in \Gamma}{.} Zeige, dass dann $\Gamma$
\definitionsverweis {maximal widerspruchsfrei}{}{}
ist.
}
{
Wir zeigen zuerst durch Induktion über den Aufbau der Sprache, dass für jedes
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Alternative
\mathkor {} {\alpha \in \Gamma} {oder} {\neg \alpha \in \Gamma} {}
gilt. Daraus folgt die maximale Widerspruchsfreiheit. Für
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ p
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Aussagenvariable ist dies Teil der Voraussetzung. Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ \neg \beta
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt wegen
\mathl{\vdash \neg { \left( \neg \beta \right) } \leftrightarrow \beta}{}
die Aussage aus der Induktionsvoraussetzung, da $\Gamma$ abgeschlossen unter Ableitungen ist. Es sei nun
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ \beta \wedge \gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei
\mathkor {} {\beta \in \Gamma} {und} {\gamma \in \Gamma} {}
ist wegen der Ableitungsabgeschlossenheit auch
\mathl{\beta \wedge \gamma \in \Gamma}{.} Wenn hingegen
\mathl{\beta \notin \Gamma}{} ist, so folgt nach der Induktionsvoraussetzung
\mathl{\neg \beta \in \Gamma}{.} Aufgrund der Tautologie
\mathl{\vdash \neg \beta \rightarrow \neg { \left( \beta \wedge \gamma \right) }}{} ergibt sich
\mathl{\neg \alpha = \neg { \left( \beta \wedge \gamma \right) } \in \Gamma}{.} Der Beweis für die Implikation verläuft ähnlich, siehe
Aufgabe 4.16 (Einführung in die mathematische Logik (Osnabrück 2021)).
Zum Nachweis, dass $\Gamma$ maximal widerspruchsfrei ist, sei
\mathl{\alpha \notin \Gamma}{} angenommen. Nach dem, was wir eben bewiesen haben, gilt dann
\mathl{\neg \alpha \in \Gamma}{.} Dann ist aber
\mavergleichskette
{\vergleichskette
{ \alpha, \neg \alpha
}
{ \in }{ \Gamma \cup \{ \alpha \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit ist diese erweiterte Menge widersprüchlich.
}
\inputaufgabeklausurloesung
{1}
{
Wir betrachten den Satz \anfuehrung{Lucy Sonnenschein tanzt auf allen Hochzeiten}{.} Negiere diesen Satz durch eine Existenzaussage.
}
{
Es gibt eine Hochzeit, auf der Lucy Sonnenschein nicht tanzt.
}
\inputaufgabeklausurloesung
{2}
{
Es seien
\mathl{x,y,z,w}{} Variablen und $V$ ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?
\aufzaehlungzweireihe {\itemsechs {
\mathl{VxyzVVw}{,}
}{
\mathl{VVxyVzw}{,}
}{
\mathl{VVxyzVw}{,}
}{
\mathl{VxVyVzw}{,}
}{
\mathl{xVyVzVw}{,}
}{
\mathl{VVVxyzw}{,}
} } {\itemsechs {
\mathl{VxyVVzw}{,}
}{
\mathl{VVxVyzw}{,}
}{
\mathl{VxyVzw}{,}
}{
\mathl{Vx VyzVw}{,}
} {
\mathl{VxVVyzw}{,}
} {
\mathl{Vx yVzVw}{.}
} }
}
{
Terme sind
\mathl{2,4,6,8,11}{,} die anderen sind keine Terme.
}
\inputaufgabeklausurloesung
{2}
{
Man erläutere für einen Ableitungskalkül den Unterschied zwischen einer syntaktischen Grundtautologie und einer Ableitungsregel.
}
{Ableitungskalkül/Tautologie und Regel/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{8}
{
Es seien $x,y$ Variablen,
\mathl{s,t}{} Terme und $\alpha$ ein Ausdruck in einer
\definitionsverweis {prädikatenlogischen Sprache}{}{.}
Es seien $u,v$ neue Variablen, die weder in $s$ noch in $t$ noch in $\alpha$ vorkommen. Zeige, dass
\mathdisp {\alpha { \frac{ s,t }{ x,y } } \leftrightarrow \alpha { \frac{ s { \frac{ v }{ y } } }{ x } } { \frac{ t { \frac{ u }{ x } } }{ y } } { \frac{ x }{ u } } { \frac{ y }{ v } }} { }
\definitionsverweis {allgemeingültig}{}{}
ist, wobei der Ausdruck rechts als die Hintereinanderausführung von vier Einzelsubstitutionen
\zusatzklammer {von links nach rechts} {} {}
zu lesen ist.
}
{
Es sei $I$ eine
\definitionsverweis {Interpretation}{}{}
mit
\mathdisp {I \vDash \alpha { \frac{ s,t }{ x,y } }} { . }
Nach
dem Substitutionslemma
bedeutet dies
\mathdisp {I { \frac{ I(s),I(t) }{ x,y } } \vDash \alpha} { . }
Von der anderen Seite her ist
\mathdisp {I \vDash \alpha { \frac{ s { \frac{ v }{ y } } }{ x } } { \frac{ t { \frac{ u }{ x } } }{ y } } { \frac{ x }{ u } } { \frac{ y }{ v } }} { }
mit dem Substitutionslemma äquivalent zu
\mathdisp {I { \frac{ I(y) }{ v } } \vDash \alpha { \frac{ s { \frac{ v }{ y } } }{ x } } { \frac{ t { \frac{ u }{ x } } }{ y } } { \frac{ x }{ u } }} { . }
Dies ist äquivalent zu
\mathdisp {I { \frac{ I(y) }{ v } } { \frac{ I { \frac{ I(y) }{ v } }( x) }{ u } } \vDash \alpha { \frac{ s { \frac{ v }{ y } } }{ x } } { \frac{ t { \frac{ u }{ x } } }{ y } }} { , }
und wegen
\mavergleichskette
{\vergleichskette
{I { \frac{ I(y) }{ v } }( x)
}
{ = }{ I(x)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
kann man dies als
\mathdisp {I { \frac{ I(y), I(x) }{ v , u } } \vDash \alpha { \frac{ s { \frac{ v }{ y } } }{ x } } { \frac{ t { \frac{ u }{ x } } }{ y } }} { }
schreiben. Wir nennen die Interpretation links $J$. Mit dem Substitutionslemma ist dies äquivalent zu
\mathdisp {J { \frac{ J(t { \frac{ u }{ x } } ) }{ y } } \vDash \alpha { \frac{ s { \frac{ v }{ y } } }{ x } }} { . }
Nach dem Substitutionslemma für Terme ist
\mavergleichskettedisp
{\vergleichskette
{ J { \left( t { \frac{ u }{ x } } \right) }
}
{ =} { J { \frac{ J(u) }{ x } } (t)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dabei ist
\mavergleichskettedisp
{\vergleichskette
{J(u)
}
{ =} { { \left( I { \frac{ I(y), I(x) }{ v , u } } \right) } (u)
}
{ =} { I(x)
}
{ } {
}
{ } {
}
}
{}{}{}
und somit ist
\mavergleichskettedisp
{\vergleichskette
{ J { \frac{ J(u) }{ x } } (t)
}
{ =} { { \left( I { \frac{ I(y), I(x) }{ v , u } } \right) } { \frac{ I(x) }{ x } } (t)
}
{ =} { { \left( I { \frac{ I(y), I(x) }{ v , u } } \right) } (t)
}
{ =} { I(t)
}
{ } {
}
}
{}{}{.}
Zusammengefasst ist also
\mathdisp {I { \frac{ I(y), I(x), I(t) }{ v , u, y } } \vDash \alpha { \frac{ s { \frac{ v }{ y } } }{ x } }} { . }
Die Interpretation links nennen wir wieder $J$. Nach dem Substitutionslemma ist
\mathdisp {J { \frac{ J { \left( s { \frac{ v }{ y } } \right) } }{ x } } \vDash \alpha} { . }
Dabei ist
\mavergleichskettedisp
{\vergleichskette
{ J { \left( s { \frac{ v }{ y } } \right) }
}
{ =} { { \left( J { \frac{ J(v) }{ y } } \right) } (s)
}
{ } {
}
{ } {
}
{ } {}
}
{}{}{}
und wir haben
\mavergleichskettedisp
{\vergleichskette
{J(v)
}
{ =} { { \left( I { \frac{ I(y), I(x), I(t) }{ v , u, y } } \right) } (v)
}
{ =} { I(y)
}
{ } {
}
{ } {
}
}
{}{}{.}
Daher ist
\mavergleichskettedisp
{\vergleichskette
{ J { \left( s { \frac{ v }{ y } } \right) }
}
{ =} { J { \frac{ I(y) }{ y } } (s)
}
{ =} { I { \frac{ I(y), I(x), I(t) }{ v , u, y } } { \frac{ I(y) }{ y } } (s)
}
{ =} { I { \frac{ I(y), I(x), I(t) }{ v , u, y } } (s)
}
{ =} { I(s)
}
}
{}{}{.}
Also ist insgesamt
\mavergleichskettedisp
{\vergleichskette
{J { \frac{ J { \left( s { \frac{ v }{ y } } \right) } }{ x } }
}
{ =} { J { \frac{ I(s) }{ x } }
}
{ =} { I { \frac{ I(y), I(x), I(t) }{ v , u, y } }{ \frac{ I(s) }{ x } }
}
{ =} { I { \frac{ I(y), I(x), I(s), I(t) }{ v , u, x, y } }
}
{ } {
}
}
{}{}{}
und
\mathdisp {I { \frac{ I(y), I(x), I(s), I(t) }{ v , u, x, y } } \vDash \alpha} { . }
Nach
dem Koinzidenzlemma
ist dies äquivalent zu
\mathdisp {I { \frac{ I(s), I(t) }{ x, y } } \vDash \alpha} { , }
da
\mathkor {} {u} {und} {v} {}
in $\alpha$ nicht vorkommen. Dies stimmt mit der eingangs erzielten Formulierung überein.
}
\inputaufgabeklausurloesung
{3}
{
Zeige
\mathdisp {\vdash \forall x \alpha \wedge \forall x \beta \rightarrow \forall x { \left( \alpha \wedge \beta \right) }} { . }
}
{
Die Alleinführung im Antezedens ergibt
\mathdisp {\vdash \forall x \alpha \rightarrow \alpha} { }
und
\mathdisp {\vdash \forall x \beta \rightarrow \beta} { }
und daraus zusammen mit
Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021)) (2)
\mathdisp {\vdash \forall x \alpha \wedge \forall x \beta \rightarrow \alpha \wedge \beta} { . }
Die Variable $x$ ist sowohl vorne als auch in
\mathl{\forall x { \left( \alpha \wedge \beta \right) }}{} gebunden. Daher ergibt die Alleinführung im Sukzedens
\mathdisp {\vdash \forall x \alpha \wedge \forall x \beta \rightarrow \forall x { \left( \alpha \wedge \beta \right) }} { . }
}
\inputaufgabeklausurloesung
{4}
{
Zeige, dass die Vorgängereigenschaft
\mathdisp {\forall x { \left( x \neq 0 \rightarrow \exists y (x = N y) \right) }} { }
aus der Menge der
\definitionsverweis {Peano-Axiome für den Nachfolger}{}{}
folgt.
}
{
Es sei $M$ eine Menge mit $0$ und einer Abbildung
\maabb {N} {M} {M
} {,}
die die erststufigen Peano-Axiome für die Nachfolgerabbildung erfüllt, und es sei
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ \defeq} { x \neq 0 \rightarrow \exists y (x = N y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir möchten
\mathl{\forall x \alpha}{} zeigen. Dabei handelt es sich um einen erststufig mit der Symbolmenge
\mathl{\{0,N\}}{} formulierten Ausdruck, so dass wir ihn durch Induktion beweisen können. Für
\mavergleichskette
{\vergleichskette
{x
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus $M$ ist der Vordersatz falsch und die Gesamtaussage richtig. Es sei nun
\mavergleichskette
{\vergleichskette
{x
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Aussage für $x$ richtig, d.h. es gelte
\mathl{\exists y (x=Ny)}{.} Dann gilt direkt
\mavergleichskettedisp
{\vergleichskette
{N(x)
}
{ =} { N(Ny))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und somit wiederum
\mathl{\exists z (Nx=Nz)}{.} Die Gesamtaussage ist also auch für $N(x)$ richtig und es ergibt sich die Gültigkeit für alle $x$.
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{10}
{
Beweise den Fixpunktsatz der Prädikatenlogik.
}
{
\teilbeweis {}{}{}
{Wir betrachten die Abbildung
\maabbeledisp {F} {\N \times \N} {\N
} {(m,n)} {F(m,n)
} {,}
die durch
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ F(m,n)
}
{ \defeq} {\begin{cases} GN( \alpha(n)),\, \text { falls } m \text{ die } GN \text{ eines } \alpha \in L^{\rm Ar}_1 \text{ ist}\, , \\ 0 \text{ sonst} \, ,\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
festgelegt ist. Bei der Berechnung von $F$ wird also zuerst geschaut, ob das erste Argument, also $m$, die Gödelnummer eines arithmetischen Ausdrucks mit genau einer freien Variablen ist. Falls nicht, so ist
\mavergleichskette
{\vergleichskette
{ F(m,n)
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
unabhängig von $n$. Falls ja, so ist also
\mavergleichskette
{\vergleichskette
{m
}
{ = }{GN(\alpha)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^{\rm Ar}_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
In diesem Ausdruck wird dann die einzige freie Variable durch das zweite Argument der Abbildung, also $n$, ersetzt, wobei man einen Satz
\mathl{\alpha(n)}{} erhält. Dessen Gödelnummer ist nach Definition der Wert der Abbildung
\mathl{F(m,n)}{.} In diesem Fall ist also
\mavergleichskette
{\vergleichskette
{ F(m,n)
}
{ = }{ GN(\alpha(n))
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Diese Erläuterungen zeigen zugleich, dass $F$
\definitionsverweis {berechenbar}{}{}
ist.}
{}\teilbeweis {}{}{}
{Da $\Gamma$ nach Voraussetzung Repräsentierungen erlaubt, gibt es einen Ausdruck
\mathl{\varphi(x,y,z)}{} mit drei freien Variablen, der diese Abbildung repräsentiert. D.h. es gilt für jede Belegung der Variablen mit natürlichen Zahlen
\mathl{m,n,k}{} die Beziehungen
\zusatzklammer {wir können annehmen, dass $\Gamma$
\definitionsverweis {widerspruchsfrei}{}{}
ist, da andernfalls das Resultat trivial ist} {} {}
\mathdisp {F(m,n)=k \text{ genau dann, wenn } \Gamma \vdash \varphi(m,n,k)} { , }
\mathdisp {F(m,n) \not = k \text{ genau dann, wenn } \Gamma \vdash \neg \varphi(m,n,k)} { }
und
\zusatzklammer {für jede Belegung $m,n$ für $x$ und $y$} {} {}
\mathdisp {\Gamma \vdash \exists ! z \varphi (m,n,z)} { . }
}
{}
\teilbeweis {}{}{}
{Den Fixpunkt zu einem vorgegebenen
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{L^{\rm Ar}_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
erhalten wir nun durch eine trickreiche Anwendung von $\varphi$. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{s
}
{ \defeq} {\forall z { \left( \varphi(x,x,z) \rightarrow \alpha(z) \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Der Ausdruck $s$ besitzt die Gödelnummer
\mathl{GN(s)}{.} Wir behaupten nun, dass der Satz
\mavergleichskettedisp
{\vergleichskette
{q
}
{ \defeq} { s \frac{ GN(s)}{x}
}
{ =} {\forall z { \left( \varphi (GN(s),GN(s),z) \rightarrow \alpha(z) \right) }
}
{ } {
}
{ } {
}
}
{}{}{}
die zu beweisende Ableitungsbeziehung
\mathl{\Gamma \vdash q \leftrightarrow \alpha ( GN(q))}{} erfüllt.}
{}
\teilbeweis {}{}{}
{Der Ausdruck $s$ besitzt die einzige freie Variable $x$, daher gilt
\mavergleichskettedisp
{\vergleichskette
{ F(GN(s),GN(s))
}
{ =} { GN { \left( s \frac{GN(s)}{x} \right) }
}
{ =} { GN(q)
}
{ } {
}
{ } {
}
}
{}{}{.}
Aufgrund der Repräsentierungseigenschaft ist daher
\mathdisp {\Gamma \vdash \varphi (GN(s),GN(s),GN(q))} { . }
Aus der Allaussage $q$ erhält man durch
\definitionsverweis {Spezialisierung}{}{}
\zusatzklammer {man ersetzt die Variable $z$ durch den Term \mathlk{GN(q)}{}} {} {}
\mathdisp {\vdash q \rightarrow { \left( \varphi(GN(s), GN(s), GN(q)) \rightarrow \alpha (GN(q)) \right) }} { . }
Da das Antezedens der rechten Implikation aus $\Gamma$ ableitbar ist, folgt
\mathdisp {\Gamma \vdash q \rightarrow \alpha(GN(q))} { . }
}
{\leerzeichen{}Dies besagt also die Ableitbarkeit der Hinrichtung.}
\teilbeweis {}{}{}
{Die aufgrund der Repräsentierbarkeit oben angeführte eindeutige Existenzaussage führt zu
\mathdisp {\Gamma \vdash \forall z { \left( \varphi(GN(s), GN(s),z) \rightarrow (z = GN(q)) \right) }} { . }
Durch
\definitionsverweis {Substitution}{}{}
ergibt sich
\mathdisp {\vdash ( z = GN(q)) \rightarrow ( \alpha (GN(q)) \rightarrow \alpha (z) )} { }
und somit nach einer prädikatenlogischen Umformulierung
\mathdisp {\Gamma \vdash \forall z { \left( \varphi(GN(s), GN(s),z) \wedge \alpha (GN(q)) \rightarrow \alpha (z) \right) }} { . }
Da hierbei
\mathl{\alpha(GN(q))}{} keine freie Variablen besitzt, ist auch
\mathdisp {\Gamma \vdash \alpha (GN(q)) \rightarrow { \left( \forall z (\varphi(GN(s), GN(s),z) \rightarrow \alpha (z)) \right) }} { , }
und das Sukzedens ist gerade $q$, so dass auch die Rückrichtung ableitbar ist.}
{}
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{4}
{
Es sei $M$ ein
$K$-\definitionsverweis {modallogisches System}{}{,}
in dem zusätzlich das
\definitionsverweis {Transitivitätsaxiom}{}{}
gelte. Ferner sei $s$ ein modallogischer Ausdruck, für den
\mathdisp {M \vdash \neg \Box s \leftrightarrow s} { }
gelte. Zeige für einen beliebigen Ausdruck $p$ die Ableitbarkeit
\mathdisp {M \vdash \neg \Box (p \wedge \neg p ) \rightarrow \neg \Box s} { . }
}
{
Aus der Fixpunkteigenschaft
\mathdisp {M \vdash \neg \Box s \leftrightarrow s} { }
ergibt sich insbesondere
\mathdisp {M \vdash \Box s \rightarrow \neg s} { . }
Mit
Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021)) (1)
folgt
\mathdisp {M \vdash \Box \Box s \rightarrow \Box \neg s} { . }
Mit dem Transitivitätsaxiom und dem Kettenschluss folgt
\mathdisp {M \vdash \Box s \rightarrow \Box \neg s} { . }
Dies zusammen mit der Tautologie
\mathdisp {\vdash \Box s \rightarrow \Box s} { }
ergibt
\mathdisp {\vdash \Box s \rightarrow \Box s \wedge \Box \neg s} { . }
Mit
Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021)) (4)
haben wir
\mathdisp {M \vdash \Box s \wedge \Box \neg s \rightarrow \Box (s \wedge \neg s)} { }
und somit
\mathdisp {M \vdash \Box s \rightarrow \Box (s \wedge \neg s)} { . }
Für ein beliebiges $p$ ist nun
\mathdisp {\vdash s \wedge \neg s \rightarrow p \wedge \neg p} { }
und somit durch
Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021)) (1)
\mathdisp {M \vdash \Box ( s \wedge \neg s ) \rightarrow \Box (p \wedge \neg p)} { }
und insgesamt
\mathdisp {M \vdash \Box s \rightarrow \Box (p \wedge \neg p)} { , }
was durch Kontraposition die Behauptung ergibt.
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}