Kurs:Einführung in die mathematische Logik/12/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}{ 3 }
\renewcommand{\avier}{ 2 }
\renewcommand{\afuenf}{ 2 }
\renewcommand{\asechs}{ 4 }
\renewcommand{\asieben}{ 2 }
\renewcommand{\aacht}{ 2 }
\renewcommand{\aneun}{ 0 }
\renewcommand{\azehn}{ 4 }
\renewcommand{\aelf}{ 0 }
\renewcommand{\azwoelf}{ 6 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 0 }
\renewcommand{\afuenfzehn}{ 3 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 34 }
\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 {widersprüchsfreie} {}
Ausdrucksmenge
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einer aussagenlogischen Sprache.
}{Ein
\stichwort {größtes Element} {}
\mathl{x \in I}{} in einer
\definitionsverweis {geordneten Menge}{}{}
\mathl{(I,\preccurlyeq)}{.}
}{Die Bestandteile einer \stichwort {Grundtermmenge} {.}
}{Ein \stichwort {Isomorphismus} {} \maabbdisp {\varphi} {M} {N } {} zwischen zwei $S$-Strukturen \mathkor {} {M} {und} {N} {.}
}{Die
\stichwort {Register-Entscheidbarkeit} {}
einer Teilmenge
\mathl{T \subseteq \N}{.}
}{Eine $K$-Modallogik. }
}
{
\aufzaehlungsechs{Die Menge $\Gamma$ heißt widersprüchsfrei, wenn es keinen Ausdruck
\mathl{\alpha \in L^V}{} mit
\mathkor {} {\Gamma \vdash \alpha} {und} {\Gamma \vdash \neg \alpha} {}
gibt.
}{Ein Element
\mathl{x \in I}{} heißt größtes Element von $I$, wenn
\mavergleichskette
{\vergleichskette
{y
}
{ \preccurlyeq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mathl{y \in I}{} gilt.
}{Die Bestandteile einer Grundtermmenge besteht aus den folgenden
\zusatzklammer {untereinander disjunkten} {} {}
Mengen.
\aufzaehlungdrei{eine Variablenmenge $V$,
}{eine Konstantenmenge $K$,
}{zu jedem
\mathl{n \in \N_+}{} eine Menge $F_n$ von Funktionssymbolen.
}
}{\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.
}{Die Teilmenge $T$ heißt Register-entscheidbar, wenn es ein Programm $P$ für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz
\mathdisp {n \in T \text{ genau dann, wenn } P(n) \text{ die Ausgabe } 0 \text{ besitzt}} { }
gilt.
}{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 {Lemma von Zorn} {.}}{Der Satz über die Division mit Rest in einem Peano-Halbring.}{Der Satz über die Unvollständigkeit der Peano-Arithmetik.}
}
{
\aufzaehlungdrei{Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
mit der Eigenschaft, dass jede
\definitionsverweis {total geordnete}{}{}
Teilmenge
\mathl{J \subseteq I}{} eine
\definitionsverweis {obere Schranke}{}{}
in $I$ besitzt. Dann gibt es in $I$
\definitionsverweis {maximale Elemente}{}{.}}{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
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}{Die erststufige
\definitionsverweis {Peano-Arithmetik}{}{}
ist
\definitionsverweis {unvollständig}{}{.}}
}
\inputaufgabeklausurloesung
{3}
{
Franziska möchte mit ihrem Freund Heinz Schluss machen. Sie erwägt die folgenden drei Begründungen. \aufzaehlungdrei{\anfuehrung{Du hast dich schon am ersten Tag voll daneben benommen. Seitdem ist es von jedem Tag zum nächsten Tag nur noch schlimmer geworden. Du wirst Dich also immer völlig daneben benehmen}{.} }{\anfuehrung{Wenn ich mit Dir zusammenbleiben würde, so würde ich irgendwann als eine traurige, gelangweilte, vom Leben enttäuschte Person enden, das möchte ich aber auf gar keinen Fall}{.} }{\anfuehrung{Also, wenn Du mich nicht liebst, will ich Dich sowieso nicht. Wenn Du mich aber liebst, so komme ich zu dem Schluss, dass Du dein Verhalten mit Deinen Gefühlen nicht zur Deckung bringen kannst. Dann bist Du also unreif und dann will ich Dich auch nicht}{.} } Welche mathematischen Beweisprinzipien spiegeln sich in den drei Begründungen wieder?
}
{
\aufzaehlungdrei{Induktionsbeweis. }{Beweis durch Widerspruch. }{Beweis durch Fallunterscheidung. }
}
\inputaufgabeklausurloesung
{2}
{
Entscheide, ob der aussagenlogische Ausdruck
\mathl{{ \left( \neg p \vee q \right) } \rightarrow { \left( p \vee \neg q \right) }}{}
\definitionsverweis {erfüllbar}{}{}
ist oder nicht.
}
{
Wenn die Aussagenvariable $p$ mit $1$ und die Aussagenvariable $q$ mit $0$ belegt wird, so besitzt der Vordersatz
\mathl{\neg p \vee q}{} den Wahrheitswert $0$ und somit besitzt die Gesamtimplikaton den Wahrheitswert $1$. Daher ist der Ausdruck erfüllbar.
}
\inputaufgabeklausurloesung
{2}
{
Es sei $V$ eine Menge von
\definitionsverweis {überabzählbar}{}{}
vielen
\definitionsverweis {Aussagenvariablen}{}{}
und es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {abzählbare}{}{}
Ausdrucksmenge. Ist $\Gamma^\vdash$ abzählbar oder überabzählbar?
}
{
Für jede Aussagenvariable $p$ kann man
\mathdisp {\vdash p \rightarrow p} { }
ableiten, also insbesondere
\mathdisp {\Gamma \vdash p \rightarrow p} { . }
Da $V$ überabzählbar ist, lassen sich also überabzählbar viele Ausdrücke aus $\Gamma$ ableiten.
}
\inputaufgabeklausurloesung
{4}
{
Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}
Zeige mit dem Lemma von Zorn, dass es eine
\definitionsverweis {maximal widerspruchsfreie}{}{}
Teilmenge
\mavergleichskette
{\vergleichskette
{\Gamma'
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt, die $\Gamma$ enthält.
}
{
Wir betrachten die Menge
\mavergleichskettedisp
{\vergleichskette
{M
}
{ \defeq} { { \left\{ \Delta \subseteq L^V \mid \Delta \supseteq \Gamma , \, \Delta \text{ widerspruchsfrei } \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit der durch Inklusion gegebenen
\definitionsverweis {Ordnung}{}{.}
Wegen
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist diese Menge nicht leer. Es sei
\mavergleichskette
{\vergleichskette
{N
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine nichtleere total geordnete Teilmenge. Die Vereinigung
\mavergleichskettedisp
{\vergleichskette
{ \Theta
}
{ =} { \bigcup_{\Delta \in N} \Delta
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist ebenfalls widerspruchsfrei, da ein Widerspruch schon aus einer endlichen Teilmenge ableitbar wäre, die ganz in einem der $\Delta$ enthalten wäre. Also besitzt die Kette in $M$ eine obere Schranke. Nach dem
Lemma von Zorn
gibt es also in $M$ maximale Elemente. Ein solches ist
\definitionsverweis {maximal widerspruchsfrei}{}{.}
}
\inputaufgabeklausurloesung
{2}
{
Negiere den Satz \anfuehrung{Kein Schwein ruft mich an und keine Sau interessiert sich für mich}{} durch (eine) geeignete Existenzaussage(n).
}
{
Es gibt ein Schwein, das mich anruft, oder es gibt eine Sau, die sich für mich interessiert.
}
\inputaufgabeklausurloesung
{2}
{
Formalisiere in der arithmetischen Sprache die \zusatzklammer {wahre} {} {} Aussage, dass es unendlich viele Primzahlen gibt.
}
{
Wir arbeiten mit $\geq$ und setzen
\mathdisp {\operatorname{Prim} (y) = y \geq 2 \wedge \forall t \forall s { \left( ts = y \rightarrow { \left( t= 1 \vee s = 1 \right) } \right) }} { , }
was die Primeigenschaft von $y$ bedeutet. Eine Formalisierung für die Unendlichkeit der Primzahlen ist
\mathdisp {\forall x \exists y { \left( y\geq x+1 \wedge \operatorname{Prim} (y) \right) }} { , }
da dieser Ausdruck besagt, dass es oberhalb jeder Zahl eine Primzahl gibt.
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{4}
{
Es sei
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \Q_{\geq 0}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Menge der nichtnegativen rationalen Zahlen. Zeige, dass $M$ ein
\definitionsverweis {kommutativer Halbring}{}{,}
aber kein
\definitionsverweis {Peano-Halbring}{}{}
ist.
}
{
Die Menge $\Q_{\geq 0}$ ist ein kommutativer Halbring, da $\Q$ ein Körper ist und $\Q_{\geq 0}$ unter Addition und Multiplikation abgeschlossen ist.
Wir betrachten die Aussage
\mathdisp {x = 0 \vee \exists y (x = y+1)} { , }
die wir als $\alpha$ bezeichnen. Es handelt sich um eine Ausssage mit der freien Variablen $x$. Diese Aussage ist in $\Q_{\geq 0}$ nicht gültig, wenn man $x$ beispielsweise durch
\mathl{{ \frac{ 1 }{ 2 } }}{} belegt, und insbesondere ist
\mathl{\forall x \alpha}{} nicht gültig.
Dagegen ist
\mathl{\alpha { \frac{ 0 }{ x } }}{} aufgrund des linken Teils wahr. Ferner ist die Indukltionsschrittaussage
\mathdisp {\exists y (x = y+1) \rightarrow \exists y (x +1 = y+1)} { }
ebenfalls wahr, da ja aus
\mavergleichskettedisp
{\vergleichskette
{x
}
{ =} {y+1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
direkt
\mavergleichskettedisp
{\vergleichskette
{x+1
}
{ =} { (y+1)+1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
folgt. Somit gilt die Voraussetzung im Induktionsaxiom, aber nicht die Konklusion für diese Aussage, und somit gilt das Induktionsaxiom in $\Q_{\geq 0}$ nicht.
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{6}
{
Im Aufbau der Registermaschine wurde der Druckbefehl durch einen Musiktonbefehl ersetzt, der den Inhalt von $R_1$ in einen Ton umsetzt, damit man mit der Registermaschine auch komponieren bzw. Lieder kodieren kann. Für ein Lied wurden schon Programmabschnitte
\mathl{P_1,P_2,P_3,P_4}{} geschrieben, die die folgende Bedeutung haben: $P_1$ ist das Vorspiel
\zusatzklammer {$V$} {} {,}
$P_2$ ist die Strophe
\zusatzklammer {$S$} {} {,}
$P_3$ ist der Refrain
\zusatzklammer {$R$} {} {}
und $P_4$ ist das Gitarrensolo
\zusatzklammer {$G$} {} {.}
Es soll nun aus den Programmabschnitten ein
\zusatzklammer {anhaltendes} {} {}
Programm zusammengesetzt werden, derart, dass beim Abspielen des Programms ein Lied der Form
\mathdisp {V-S-R-S-R-G-S-R-R} { }
erklingt. Dabei darf jeder der Programmabschnitte
\mathl{P_1,P_2,P_3,P_4}{} nur einmal im Programmcode auftauchen. Verwende ausschließlich die Grundbefehle.
}
{
Wir arbeiten mit den Hilfszählregistern
\mathl{R_s,R_t,R_u,R_v}{,} die am Anfang der Reihe nach mit
\mathl{1-2-3-4}{} belegt seien. Wir behaupten, dass das folgende Programm
\zusatzklammer {die Befehlszeilennummern repräsentieren teilweise ganze Programmabschnitte} {} {}
das Lied abspielt.
\mathdisp {1 \,\,\,\,\,\,\,\,\,\, P_1} { }
\mathdisp {2 \,\,\,\,\,\,\,\,\,\, P_2} { }
\mathdisp {3 \,\,\,\,\,\,\,\,\,\, P_3} { }
\mathdisp {4 \,\,\,\,\,\,\,\,\,\, s-} { }
\mathdisp {5 \,\,\,\,\,\,\,\,\,\, t-} { }
\mathdisp {6 \,\,\,\,\,\,\,\,\,\, u-} { }
\mathdisp {7 \,\,\,\,\,\,\,\,\,\, v-} { }
\mathdisp {8 \,\,\,\,\,\,\,\,\,\, C(v,14)} { }
\mathdisp {9 \,\,\,\,\,\,\,\,\,\, C(u,3)} { }
\mathdisp {10 \,\,\,\,\,\,\,\,\,\, C(t,12)} { }
\mathdisp {11 \,\,\,\,\,\,\,\,\,\, C(s,2)} { }
\mathdisp {12 \,\,\,\,\,\,\,\,\,\, P_4} { }
\mathdisp {13 \,\,\,\,\,\,\,\,\,\, C(s,2)} { }
\mathdisp {14 \,\,\,\,\,\,\,\,\,\, \text{Halte an}} { }
Wir analysieren den Programmdurchlauf. Zuerst wird das Vorspiel, die Strophe und der Refrain abgespielt. Dann werden die vier Zähler auf
\mathl{0-1-2-3}{} gesetzt. Die folgenden drei Abfragen sind negativ, im elften Befehl ist das abgefragte Register $R_s$ leer und daher geht es zu Zeile $2$. Somit wird Strophe und Refrain abgespielt und anschließend werden die Register auf
\mathl{0-0-1-2}{} gesetzt. Die folgenden zwei Abfragen sind negativ, im zehnten Befehl ist das abgefragte Register $R_t$ leer und daher geht es zu Zeile $12$. Dort wird das Gitarrensolo abgespielt und anschließend geht es, da ja $R_s$ leer ist, zur Programmzeile $2$. Es folgt Strophe und Refrain und anschließend werden die Register auf
\mathl{0-0-0-1}{} gesetzt. Die folgende Abfrage ist negativ, aber im neunten Befehl ist das abgefragte Register $R_u$ leer und daher geht es zu Zeile $3$. Es wird der Refrain abgespielt und anschließend werden die Register auf
\mathl{0-0-0-0}{} gesetzt. Im Befehl $8$ wird jetzt zum Haltebefehl umgeleitet.
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{3}
{
Zu einem
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R,\mu)}{} und einem modallogischen Ausdruck $\alpha$ setzen wir
\mavergleichskettedisp
{\vergleichskette
{M( \alpha )
}
{ =} { { \left\{ w \in M \mid w \vDash \alpha \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige
\mavergleichskettedisp
{\vergleichskette
{M( \Diamond \alpha )
}
{ =} { \operatorname{Vorg} { \left( M( \alpha ) \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
Sei
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M( \Diamond \alpha )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mathl{w \vDash \Diamond \alpha}{} und damit gibt es ein $v$ mit
\mathl{wRv}{} und mit
\mathl{v \vDash \alpha}{.} Daher ist
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{ M( \alpha )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit ist
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{ \operatorname{Vorg} { \left( M( \alpha ) \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wenn umgekehrt
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{ \operatorname{Vorg} { \left( M( \alpha ) \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, so gibt es ein
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{ M( \alpha )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{wRv}{.} Also ist
\mathl{v \vDash \alpha}{} und damit
\mathl{w \vDash \Diamond \alpha}{.} Also ist
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{ M(\Diamond \alpha)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}