Kurs:Einführung in die mathematische Logik/3/Klausur/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}{ 2 }
\renewcommand{\avier}{ 5 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 3 }
\renewcommand{\asieben}{ 4 }
\renewcommand{\aacht}{ 7 }
\renewcommand{\aneun}{ 6 }
\renewcommand{\azehn}{ 2 }
\renewcommand{\aelf}{ 4 }
\renewcommand{\azwoelf}{ 4 }
\renewcommand{\adreizehn}{ 3 }
\renewcommand{\avierzehn}{ 6 }
\renewcommand{\afuenfzehn}{ 4 }
\renewcommand{\asechzehn}{ 5 }
\renewcommand{\asiebzehn}{ 64 }
\renewcommand{\aachtzehn}{ }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellesechzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabegibtloesung
{3}
{
Definiere die folgenden
\zusatzklammer {kursiv gedruckten} {} {} Begriffe.
\aufzaehlungsechs{Die
\stichwort {Termmenge} {}
zu einer Grundtermmenge
\mathl{(V,K,F_n)}{.}
}{Eine \stichwort {maximal widerspruchsfreie} {} prädikatenlogische Ausdrucksmenge $\Gamma \subseteq L^S$.
}{Die
\stichwort {Multiplikation} {}
mit
\mathl{n \in \N}{} in einem
\definitionsverweis {Dedekind-Peano-Modell}{}{}
$\N$.
}{Die \stichwort {Befehle} {} für eine Registermaschine.
}{Das \definitionsverweis {modallogische}{}{} \stichwort {Löb-Axiom} {.}
}{Ein \stichwort {modallogisches Modell} {.} }
}
{} {}
\inputaufgabegibtloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Das \stichwort {Lemma von Zorn} {.}}{Der \stichwort {Vollständigkeitssatz für Tautologien} {} \zusatzklammer {Prädikatenlogik} {} {.}}{Der \stichwort {zweite Gödelsche Unvollständigkeitssatz} {.}}
}
{} {}
\inputaufgabegibtloesung
{2 (1+1)}
{
Im Pokal spielt Bayern München gegen den TSV Wildberg. Der Trainer vom TSV Wildberg, Herr Tor Acker, sagt \anfuehrung{Wir haben in dem Spiel nichts zu verlieren}{.} Die Logiklehrerin von Wildberg, Frau Loki Schummele, sagt \anfuehrung{Wenn die Wildberger in dem Spiel nichts zu verlieren haben, dann haben auch die Münchner in dem Spiel nichts zu gewinnen}{.} Der Trainer von Bayern München, Herr Roland Rollrasen, sagt \anfuehrung{Wir haben in dem Spiel etwas zu gewinnen}{.} \aufzaehlungzwei {Ist die Aussage von Frau Schummele logisch korrekt? } {Es sei vorausgesetzt, dass die Aussage des Bayerntrainers wahr ist. Welche Folgerung kann man dann für die Aussage von Herrn Acker ziehen? }
}
{} {}
\inputaufgabegibtloesung
{5 (1+1+3)}
{
\aufzaehlungdrei{Löse das folgende Minisudoku
\mathdisp {\begin{pmatrix} - & - & 2 & - \\ 3 & - & - & 4 \\ - & - & - & - \\ - & 4 & - & 1 \end{pmatrix}} { . }
}{Begründe, dass das Minisudoku aus (1) nur eine Lösung besitzt.
}{Welche mathematischen Beweisverfahren finden sich als typische Argumentationsschemata beim Lösen eines Sudokus wieder?
}
}
{} {}
\inputaufgabegibtloesung
{3}
{
Beweise durch Induktion über den rekursiven Aufbau der Sprache $L^V$, dass in jeder Aussage
\mathl{\alpha \in L^V}{} die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.
}
{} {}
\inputaufgabegibtloesung
{3}
{
Zeige, dass eine Regel der Form
Wenn
\mathl{\vdash \alpha}{,} dann
\mathl{\vdash \beta}{} gelten kann, ohne dass
\mathl{\vdash \alpha \rightarrow \beta}{} gilt.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$. Begründe die Kettenschlussregel für die
\definitionsverweis {Ableitungsbeziehung}{}{:}
Wenn
\mathl{\Gamma \vdash \alpha \rightarrow \beta}{} und
\mathl{\Gamma \vdash \beta \rightarrow \gamma}{,} dann auch
\mathl{\Gamma \vdash \alpha \rightarrow \gamma}{.}
}
{} {}
\inputaufgabegibtloesung
{7 (3+4)}
{
Es sei
\mavergleichskette
{\vergleichskette
{ V
}
{ = }{ \{x,y,z,u,v,w\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Variablenmenge, $0$ eine Konstante und
\mathl{-,+, \cdot}{} zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck
\mathl{\alpha}{,} der durch
\mathdisp {\forall x \forall y \forall z \forall u \forall v \forall w { \left( \left[ (z-x)(z-y) + (w-u)(w-v) = 0\right ] \longrightarrow \left[ (x-y)(x-y) + (u-v)(u-v) = (x-z)(x-z) +(u-w)(u-w) + (y-z)(y-z) + (v-w)(v-w) \right ] \right) }} { }
gegeben ist.
\aufzaehlungzwei {Zeige, dass $\alpha$ bei Interpretation in einem Körper $K$ wahr wird, wenn man $0$ als $0$ und
\mathl{\{-,+,\cdot\}}{} als Subtraktion, Addition und Multiplikation interpretiert.
} {Welcher wichtige mathematische Satz verbirgt sich dahinter?
}
}
{} {}
\inputaufgabegibtloesung
{6}
{
Beweise die Termaussage des Substitutionslemmas.
}
{} {}
\inputaufgabegibtloesung
{2}
{
Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet $S$, dass ein \definitionsverweis {Untervektorraum}{}{} in einem \definitionsverweis {Vektorraum}{}{} über einem \definitionsverweis {Körper}{}{} vorliegt.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Zeige, dass in einem
\definitionsverweis {Peano-Halbring}{}{}
$M$ zu
\mavergleichskette
{\vergleichskette
{d
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die
Division mit Rest
eindeutig ist.
}
{} {}
\inputaufgabe
{4}
{
Beschreibe die wesentlichen Punkte bei der Konstruktion eines Modells, mit dem man die Erfüllbarkeit einer maximal widerspruchsfreien Ausdrucksmenge, die Beispiele enthält, nachweist.
}
{} {}
\inputaufgabegibtloesung
{3}
{
Bestimme die
\definitionsverweis {Äquivalenzklassen}{}{}
zur
\definitionsverweis {elementaren Äquivalenz}{}{}
in der
\definitionsverweis {Gruppe}{}{}
\mathl{\Z/(2) \times \Z/(2)}{} zum Symbolalphabet
\mavergleichskette
{\vergleichskette
{S
}
{ = }{ \{ 0,+ \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
{} {}
\inputaufgabegibtloesung
{6}
{
Es sei
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine endliche Teilmenge. Man gebe ein Programm für eine Registermaschine an, das nur auf einen einzigen Register $R_1$ Bezug nimmt, das bei jeder Eingabe
\zusatzklammer {in $R_1$} {} {}
immer anhält und das im Anhaltezustand in
\mathl{R_1}{} genau dann den Wert $0$ besitzt, wenn die Eingabe zu $T$ gehört.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Es sei
\maabbdisp {F} {\N^r} {\N^s
} {}
eine
\definitionsverweis {arithmetisch repräsentierbare}{}{}
Abbildung. Zeige, dass zu jedem Punkt
\mathl{P \in \N^s}{} die
\definitionsverweis {Faser}{}{}
\mavergleichskettedisp
{\vergleichskette
{F^{-1}(P)
}
{ \subseteq} { \N^r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\definitionsverweis {arithmetisch repräsentierbar}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{5}
{
Zeige, dass eine aufzählbar axiomatisierbare Theorie
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auch $R$-aufzählbar ist.
}
{} {}