Kurs:Einführung in die mathematische Logik/2/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}{ 4 }
\renewcommand{\afuenf}{ 9 }
\renewcommand{\asechs}{ 4 }
\renewcommand{\asieben}{ 6 }
\renewcommand{\aacht}{ 7 }
\renewcommand{\aneun}{ 7 }
\renewcommand{\azehn}{ 2 }
\renewcommand{\aelf}{ 3 }
\renewcommand{\azwoelf}{ 3 }
\renewcommand{\adreizehn}{ 12 }
\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}
\inputaufgabegibtloesung
{3}
{
Definiere die folgenden
\zusatzklammer {kursiv gedruckten} {} {} Begriffe.
\aufzaehlungsechs{Die
\stichwort {Ableitbarkeit} {}
eines Aussage
\mathl{\alpha \in L^V}{} aus einer Aussagenmenge
\mathl{\Gamma \subseteq L^V}{} in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagevariablenmenge $V$.
}{Eine \stichwortpraemath {n} {stellige Relation}{} auf einer Menge $M$.
}{Die
\stichwort {Folgerungsbeziehung} {}
\mathl{\Gamma \vDash \alpha}{,} wobei $\Gamma$ eine Menge von
$S$-\definitionsverweis {Ausdrücken}{}{}
und $\alpha$ ein $S$-Ausdruck ist
\zusatzklammer {und $S$ ein
\definitionsverweis {Symbolalphabet}{}{.}} {} {}
}{Die
\stichwort {Termsubstitution} {}
\mathl{s { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} für $S$-Terme $s$
\zusatzklammer {dabei sei $S$ ein Symbolalphabet einer
\definitionsverweis {Sprache erster Stufe}{}{,}
\mathl{x_1 , \ldots , x_k}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k}{} fixierte
$S$-\definitionsverweis {Terme}{}{}} {} {.}
}{Die \stichwort {Addition} {} in einem \definitionsverweis {Dedekind-Peano-Modell}{}{} $\N$.
}{Die
\stichwort {Register-Entscheidbarkeit} {}
einer Teilmenge
\mathl{T \subseteq \N}{.}
}
}
{} {}
\inputaufgabegibtloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Das \stichwort {Substitutionslemma} {.}}{Der Satz über das \stichwort {Halteproblem} {.}}{Der \stichwort {Fixpunktsatz} {} für arithmetische Ausdrücke.}
}
{} {}
\inputaufgabegibtloesung
{1}
{
Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt. \wahrheitstabellezweieins{ } {\tabellenzeiledrei {$ p $} {$ q $} {$? $} } {\tabellenzeiledrei {w} {w} {f} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {w} } {\tabellenzeiledrei {f} {f} {f} }
}
{} {}
\inputaufgabegibtloesung
{4 (2+2)}
{
Es sei
\mathl{G}{} eine unendliche Menge und
\mavergleichskette
{\vergleichskette
{M
}
{ \subset }{ \mathfrak {P} \, (G )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Menge, die aus sämtlichen endlichen Teilmengen von $G$ besteht.
\aufzaehlungzwei {Ist $(M, \subseteq)$
\definitionsverweis {induktiv geordnet}{}{?}
} {Besitzt $M$
\definitionsverweis {maximale Elemente}{}{?}
}
}
{} {}
\inputaufgabegibtloesung
{9 (1+3+2+1+2)}
{
Es sei $L^S$ die
\definitionsverweis {prädikatenlogische Sprache}{}{,}
die neben Variablen aus einem zweistelligen Relationssymbol $A$ und einem dreistelligen Relationssymbol $B$ bestehe. Wir betrachten
$S$-\definitionsverweis {Interpretationen}{}{}
$I$, wobei die Grundmenge jeweils aus einem
\definitionsverweis {Vektorraum}{}{} $V$ über einem
\definitionsverweis {Körper}{}{}
$K$ bestehe und $A$ als die
\definitionsverweis {lineare Unabhängigkeit}{}{}
von zwei und $B$ als die lineare Unabhängigkeit von drei Vektoren interpretiert werde.
\aufzaehlungfuenf{Zeige
\mathdisp {I \vDash Bxyz \rightarrow Axy} { . }
}{Gilt
\mathdisp {I \vDash Axy \wedge Axz \wedge Ayz \rightarrow Bxyz} { }
für einen beliebigen Vektorraum?
}{Gibt es Vektorräume, für die die Aussage in Teil 2 gilt?
}{Es sei
\mathl{V= \R^3}{} und
\mathl{e_1,e_2,e_3}{} sei die Standardbasis. Gilt
\mathdisp {I { \frac{ e_1,e_2,e_3 }{ x,y,z } } \vDash Bxyz} { ? }
}{Es sei
\mathl{V=\R}{} als $\Q$-Vektorraum betrachtet. Gilt
\mathdisp {I { \frac{ 1, \sqrt{2} }{ x,y } } \vDash Axy} { ? }
}
}
{} {}
\inputaufgabegibtloesung
{4}
{
Zeige durch ein Beispiel, dass für Terme $r_1,r_2,s$ und eine Variable
\mathl{x}{} einer
\definitionsverweis {prädikatenlogischen Sprache}{}{}
$L^S$ der Ausdruck
\mathdisp {r_1 = r_2 \rightarrow r_1 { \frac{ s }{ x } } =r_2 { \frac{ s }{ x } }} { }
nicht
\definitionsverweis {ableitbar}{}{}
sein muss.
}
{} {}
\inputaufgabegibtloesung
{6 (3+1+2)}
{
Es seien
\mathl{x,y,u,v}{} Variablen und
\mathl{\Gamma =\{ \forall x \forall y { \left( x = y \right) } \}}{} und
\mathl{\Delta = \{ x = y \}}{.}
\aufzaehlungdrei{Zeige
\zusatzklammer {ohne Bezug auf den Vollständigkeitssatz} {} {}
\mathl{\Gamma \vdash u=v}{.}
}{Charakterisiere die
\definitionsverweis {Modelle}{}{}
$M$ mit
\mathl{M \vDash \Gamma}{.}
}{Zeige
\mathl{\Delta \not\vdash u=v}{.}
}
}
{} {}
\inputaufgabegibtloesung
{7}
{
Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.
}
{} {}
\inputaufgabegibtloesung
{7}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $I$ eine
$S$-\definitionsverweis {Interpretation}{}{}
auf einer Menge $M$, wobei die
\definitionsverweis {Terminterpretation}{}{} \definitionsverweis {surjektiv}{}{}
sei. Zeige, dass die Gültigkeitsmenge
\mathl{\Gamma =I^\vDash}{}
\definitionsverweis {maximal widerspruchsfrei}{}{}
ist und
\definitionsverweis {Beispiele enthält}{}{.}
}
{} {}
\inputaufgabe
{2}
{
Man gebe ein Beispiel für eine mathematische Begriffsbildung, die als $S$-\definitionsverweis {Homomorphismus}{}{} zu einem geeigneten Symbolalphabet $S$ verstanden werden kann.
}
{} {}
\inputaufgabegibtloesung
{3}
{
Entwerfe ein Programm für eine \definitionsverweis {Registermaschine}{}{,} das nach und nach alle \definitionsverweis {Primzahlen}{}{} ausdruckt.
}
{} {}
\inputaufgabe
{3}
{
Erläutere die \stichwort {Churchsche These} {.}
}
{} {}
\inputaufgabegibtloesung
{12}
{
Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine arithmetische Ausdrucksmenge und
\mathl{R \subseteq \N}{} eine Relation. Es seien
\mathl{\alpha, \beta \in L^{\rm Ar}}{} Ausdrücke in einer freien Variablen $x$. Zeige, dass aus
\mathdisp {\Gamma \vdash \alpha \leftrightarrow \beta} { }
\betonung{nicht}{} folgt, dass $\alpha$ in $\Gamma$ die Relation $R$ genau dann
\definitionsverweis {repräsentiert}{}{,}
wenn
\mathl{\beta}{} in $\Gamma$ die Relation $R$ repräsentiert.
}
{} {}