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

}
{} {}