Kurs:Einführung in die mathematische Logik/10/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}{ 2 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 3 }
\renewcommand{\asieben}{ 6 }
\renewcommand{\aacht}{ 4 }
\renewcommand{\aneun}{ 3 }
\renewcommand{\azehn}{ 1 }
\renewcommand{\aelf}{ 2 }
\renewcommand{\azwoelf}{ 4 }
\renewcommand{\adreizehn}{ 3 }
\renewcommand{\avierzehn}{ 3 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 4 }
\renewcommand{\aachtzehn}{ 0 }
\renewcommand{\aneunzehn}{ 5 }
\renewcommand{\azwanzig}{ 4 }
\renewcommand{\aeinundzwanzig}{ 54 }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellezwanzig
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabegibtloesung
{3}
{
Definiere die folgenden
\zusatzklammer {kursiv gedruckten} {} {} Begriffe.
\aufzaehlungsechs{Die
\stichwort {Ableitbarkeit} {}
\mathl{\Gamma \vdash \alpha}{} eines $S$-Ausdrucks $\alpha$ aus einer Menge $\Gamma$ an
$S$-\definitionsverweis {Ausdrücken}{}{.}
}{Eine \stichwort {Abbildung} {} $F$ von einer Menge $L$ in eine Menge $M$.
}{Die \stichwort {endliche Axiomatisierbarkeit} {} einer
\definitionsverweis {Theorie}{}{}
\mathl{T \subseteq L^S_0}{.}
}{Ein \stichwort {reell-abgeschlossener} {} \definitionsverweis {Körper}{}{.}
}{Die Eigenschaft einer Menge $\Gamma$ von \definitionsverweis {arithmetischen Ausdrücken}{}{,} \stichwort {Repräsentierungen zu erlauben} {.}
}{Das \definitionsverweis {modallogische}{}{} \stichwort {Symmetrieaxiom} {.} }
}
{} {}
\inputaufgabegibtloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz von Wiles (Großer Fermat).}{Der Satz von Henkin.}{Der \stichwort {Fixpunktsatz} {} für arithmetische Ausdrücke.}
}
{} {}
\inputaufgabegibtloesung
{1}
{
Petra fliegt zu ihrer ersten internationalen Konferenz. Als sie auf dem Weg zum Flughafen ihre Wohnung \zusatzklammer {sie wohnt allein} {} {} verlässt und gerade die Wohnungstür zugemacht hat, merkt sie \zusatzklammer {eine der drei Möglichkeiten} {} {} \aufzaehlungdrei{Sie hat ihr Flugticket auf dem Schreibtisch vergessen. }{Sie hat ihre Schlüssel auf dem Schreibtisch vergessen. }{Sie hat ihren Reisepass auf dem Schreibtisch vergessen. } Was ist am schlimmsten?
}
{} {}
\inputaufgabegibtloesung
{2}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Mercedes Benz Atego 1624 container truck.JPG} }
\end{center}
\bildtext {} }
\bildlizenz { Mercedes Benz Atego 1624 container truck.JPG } {} {High Contrast} {Commons} {CC-ba-sa 3.0} {}
Die Absetzmulde ist voll mit Schutt und soll durch eine leere Mulde ersetzt werden, die das Absetzkipperfahrzeug bringt, das auch die volle Mulde mitnehmen soll. Auf dem Fahrzeug und auf dem Garagenvorplatz, wo die volle Mulde steht, ist nur Platz für eine Mulde. Dafür kann die Straße als Zwischenablage genutzt werden. Wie viele Ladevorgänge sind vor Ort nötig, bis der Gesamtaustausch vollständig abgeschlossen ist?
}
{} {}
\inputaufgabegibtloesung
{3}
{
Beweise den Satz, dass es unendlich viele Primzahlen gibt.
}
{} {}
\inputaufgabegibtloesung
{3}
{
Zeige, dass der aussagenlogische Ausdruck
\mathdisp {{ \left( r \rightarrow { \left( p \wedge \neg q \right) } \right) } \rightarrow { \left( \neg p \rightarrow { \left( \neg r \vee q \right) } \right) }} { }
\definitionsverweis {allgemeingültig}{}{}
ist
}
{} {}
\inputaufgabegibtloesung
{6 (2+4)}
{
Es seien
\mathkor {} {\alpha} {und} {\beta} {}
Aussagen.
\aufzaehlungzwei {Zeige
\mathdisp {\vdash { \left( \alpha \rightarrow \beta \right) } \rightarrow \neg { \left( \alpha \wedge \neg \beta \right) }} { . }
} {Zeige
\mathdisp {\vdash \neg { \left( \alpha \wedge \neg \beta \right) } \rightarrow { \left( \alpha \rightarrow \beta \right) }} { . }
}
}
{} {}
\inputaufgabegibtloesung
{4}
{
Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {maximal widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}
Zeige, dass für jedes
\mathl{\alpha \in L^V}{} entweder
\mathl{\alpha \in \Gamma}{} oder
\mathl{\neg \alpha \in \Gamma}{} gilt.
}
{} {}
\inputaufgabegibtloesung
{3 (2+1)}
{
Es sei
\mathl{G}{} eine Menge und
\mavergleichskette
{\vergleichskette
{M
}
{ \subseteq }{ \mathfrak {P} \, (G )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge der Potenzmenge, die unter beliebigen Vereinigungen abgeschlossen ist.
\aufzaehlungzwei {Zeige, dass $(M, \subseteq)$
\definitionsverweis {induktiv geordnet}{}{}
ist.
} {Zeige, dass $M$ ein
\definitionsverweis {größtes Element}{}{}
besitzt.
}
}
{} {}
\inputaufgabegibtloesung
{1}
{
Wir betrachten den Satz \anfuehrung{Diese Vorlesung versteht keine Sau}{.} Negiere diesen Satz durch eine Existenzaussage.
}
{} {}
\inputaufgabegibtloesung
{2}
{
Zeige, dass der
\definitionsverweis {prädikatenlogische Ausdruck}{}{}
\mathdisp {\exists x \exists y ( \neg (x=y) \wedge \forall z ( (z=x) \vee (z=y) ))} { }
\definitionsverweis {erfüllbar}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Beweise den Satz über die Vorgängereigenschaft in einem Peano-Halbring.
}
{} {}
\inputaufgabegibtloesung
{3}
{
Es sei
\mathl{(\N,0,^\prime)}{} ein
\definitionsverweis {Dedekind-Peano-Modell}{}{}
der natürlichen Zahlen. Zeige, dass die Addition die Abziehregel erfüllt, also die Aussage, dass aus einer Gleichung
\mavergleichskette
{\vergleichskette
{n+k
}
{ = }{m+k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Gleichheit
\mavergleichskette
{\vergleichskette
{n
}
{ = }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\zusatzklammer {dabei dürfen grundlegendere Regeln wie die Assoziativität der Addition und ähnliches verwendet werden} {} {.}
}
{} {}
\inputaufgabe
{3 (1+1+1)}
{
In einem Zugabteil sitzen die sechs Personen
\mathl{A,B,C,D,E,F}{.} Wir betrachten die folgenden Relationen:
\aufzaehlungdrei{$Mx$ bedeutet, dass $x$ über die deutsche Bahn motzt.
}{$Px$ bedeutet, dass $x$ einen Fensterplatz hat.
}{$Sxy$ bedeutet, dass $x$ der Person $y$ die Fahrkarte klaut.
}
Es gelten ausschließlich die Beziehungen
\mathdisp {MA,MB,MC,MD,ME,MF, PA,PD, SAD,SBE,SFB} { . }
\aufzaehlungdrei{Charakterisiere umgangssprachlich die Person $A$ allein unter Bezugnahme auf die gegebenen Relationen.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{M,P,S}{} die Person $B$.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{M,P,S}{} die Person $E$.
}
}
{} {}
\inputaufgabe
{0}
{
}
{} {}
\inputaufgabe
{0}
{
}
{} {}
\inputaufgabegibtloesung
{4}
{
Zeige, dass die erststufige Peano-Arithmetik $PA$ eine vollständige widerspruchsfreie erststufige Erweiterung $M$, also
\mavergleichskette
{\vergleichskette
{PA
}
{ \subseteq }{M
}
{ \subseteq }{L^{\rm Ar}_0
}
{ }{
}
{ }{
}
}
{}{}{,}
besitzt, die von $\N^\vDash_0$ verschieden ist.
}
{} {}
\inputaufgabe
{0}
{
}
{} {}
\inputaufgabegibtloesung
{5}
{
Zeige, dass in einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} das modallogische
\definitionsverweis {Symmetrieaxiom}{}{}
genau dann gilt, wenn $R$
\definitionsverweis {symmetrisch}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Es sei $\Gamma$ die durch das
\definitionsverweis {Löb-Axiom}{}{}
gegebene
$K$-\definitionsverweis {Modallogik}{}{,}
also die Beweisbarkeitslogik. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ \bot
}
{ \defeq} { p \wedge \neg p
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {als Abkürzung für einen Widerspruch} {} {.}
Zeige, dass
\mathdisp {\Gamma \vdash \neg \Box \neg \Box \bot \leftrightarrow \neg \Box \bot} { }
ableitbar ist.
}
{} {}