Kurs:Einführung in die mathematische Logik/9/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}{ 1 }
\renewcommand{\avier}{ 6 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 2 }
\renewcommand{\asieben}{ 8 }
\renewcommand{\aacht}{ 0 }
\renewcommand{\aneun}{ 4 }
\renewcommand{\azehn}{ 6 }
\renewcommand{\aelf}{ 4 }
\renewcommand{\azwoelf}{ 3 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 3 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 6 }
\renewcommand{\asiebzehn}{ 52 }
\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{Eine
\stichwort {maximal widerspruchsfreie} {}
Teilmenge
\mathl{\Gamma \subseteq L^V}{} zu einer Menge $V$ an
\definitionsverweis {Aussagenvariablen}{}{.}
}{Die rekursive Definition für die \stichwort {Ausdrücke} {} in einer Sprache erster Stufe.
}{Die \stichwort {Interpretation der Terme} {} zu einem \definitionsverweis {Symbolalphabet}{}{} $S$ in einer gegebenen $S$-\definitionsverweis {Interpretation}{}{} auf einer Grundmenge $M$.
}{Ein \stichwort {atomarer} {} Ausdruck in der Prädikatenlogik.
}{Eine \stichwortpraemath {R} {berechenbare Funktion}{} \maabbdisp {F} {\N^k} {\N } {.}
}{Das modallogische \stichwort {Reflexivitätsaxiom} {.} }
}
{} {}
\inputaufgabegibtloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz über die Division mit Rest in einem Peano-Halbring.}{Der \stichwort {Vollständigkeitssatz} {} der Prädikatenlogik.}{Der \stichwort {erste Gödelsche Unvollständigkeitssatz} {.}}
}
{} {}
\inputaufgabegibtloesung
{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} {w} } {\tabellenzeiledrei {f} {w} {f} } {\tabellenzeiledrei {f} {f} {f} }
}
{} {}
\inputaufgabegibtloesung
{6 (2+1+3)}
{
Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest. \aufzaehlungvier{Ein Tag heißt \stichwort {sockenzerstreut} {,} wenn er verschiedene Socken anhat. }{Ein Tag heißt \stichwort {schuhzerstreut} {,} wenn er verschiedene Schuhe anhat. }{Ein Tag heißt \stichwort {zerstreut} {,} wenn er sockenzerstreut oder schuhzerstreut ist. }{Ein Tag heißt \stichwort {total zerstreut} {,} wenn er sowohl sockenzerstreut als auch schuhzerstreut ist. }
a) Vom Jahr
\mathl{2015}{} weiß man, dass $17$ Tage sockenzerstreut und $11$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?
b) Vom Jahr
\mathl{2013}{} weiß man, dass $270$ Tage sockenzerstreut und $120$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?
c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.
}
{} {}
\inputaufgabe
{3}
{
Erläutere das Konzept der \stichwort {Wohldefiniertheit} {} anhand eines typischen Beispiels.
}
{} {}
\inputaufgabegibtloesung
{2}
{
Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$. Begründe die folgende Regel für die
\definitionsverweis {Ableitungsbeziehung}{}{:}
Wenn
\mathl{\Gamma \vdash \alpha_1 , \ldots , \Gamma \vdash \alpha_n}{} und
\mathl{\Gamma \vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \beta}{,} dann auch
\mathl{\Gamma \vdash \beta}{.}
}
{} {}
\inputaufgabegibtloesung
{8 (3+5)}
{
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. Beweise die folgenden 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}{} (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus $U$ und auf den in $\alpha$ frei vorkommenden Variablen identisch sind).
}
}
{} {}
\inputaufgabe
{0}
{
}
{} {}
\inputaufgabegibtloesung
{4}
{
Es seien
\mathl{A,B,C}{} einstellige Relationssymbole. Zeige, dass der \stichwort {Modus Darii} {,} also die Aussage
\mathdisp {( \forall x (Ax \rightarrow Bx) \wedge \exists x (Ax \wedge Cx) ) \rightarrow ( \exists x (Bx \wedge Cx) )} { }
im Prädikatenkalkül
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{6 (3+3)}
{
Es sei $(M,0,N)$ ein
\definitionsverweis {Modell}{}{}
für die
\definitionsverweis {Peano-Axiome für den Nachfolger}{}{.}
\aufzaehlungzwei {Zeige, dass $N$
\definitionsverweis {fixpunktfrei}{}{}
ist, d.h. dass
\mavergleichskettedisp
{\vergleichskette
{N(x)
}
{ \neq} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle $x \in M$.
} {Zeige, dass $N$ periodenfrei ist. D.h. für jedes
\mathl{\ell \in \N_+}{} ist
\mavergleichskettedisp
{\vergleichskette
{N^\ell ( x)
}
{ \neq} { x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei
\mavergleichskettedisp
{\vergleichskette
{ N^\ell
}
{ =} { N \circ \cdots \circ N
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die $\ell$-fache Hintereinanderschaltung von $N$ bedeutet.
}
}
{} {}
\inputaufgabegibtloesung
{4}
{
Zeige, dass es einen
\definitionsverweis {Peano-Halbring}{}{}
$M$ mit der Eigenschaft gibt, dass es darin ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt, das größer als jede natürliche Zahl in $M$
\zusatzklammer {also Zahlen der Form
\mathl{1+1 + \cdots + 1}{}} {} {}
ist.
}
{} {}
\inputaufgabegibtloesung
{3 (1+1+1)}
{
Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze
\mathl{1,2,3,4}{} nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz $3$ bestreiten. Von einer solchen Runde seien die Mannschaften $A,B,C,D$ und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.
\aufzaehlungdrei{Welche Information über die Platzierung kann man stets aus den Daten erschließen?
}{Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
}{unter welcher nicht?
}
}
{} {}
\inputaufgabe
{0}
{
}
{} {}
\inputaufgabegibtloesung
{3}
{
Beweise den ersten Gödelschen Unvollständigkeitssatz mit dem Unvollständigkeitslemma.
}
{} {}
\inputaufgabe
{0}
{
}
{} {}
\inputaufgabegibtloesung
{6 (4+2)}
{
\aufzaehlungzwei {Skizziere ein modallogisches Modell, bei dem es verschiedene Weltpunkte $v,w$ mit
\mathdisp {v \vDash \neg \Box p} { }
und
\mathdisp {w \vDash \Box \Box p \wedge \Diamond p \wedge \Diamond \neg p} { }
gibt.
} {Was ist die minimale Anzahl von Welten in einem modallogischen Modell, in dem die Anforderungen aus 1) realisierbar sind.
}
}
{} {}