Kurs:Einführung in die mathematische Logik/4/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}{ 4 }
\renewcommand{\avier}{ 8 }
\renewcommand{\afuenf}{ 2 }
\renewcommand{\asechs}{ 4 }
\renewcommand{\asieben}{ 3 }
\renewcommand{\aacht}{ 5 }
\renewcommand{\aneun}{ 5 }
\renewcommand{\azehn}{ 4 }
\renewcommand{\aelf}{ 4 }
\renewcommand{\azwoelf}{ 4 }
\renewcommand{\adreizehn}{ 4 }
\renewcommand{\avierzehn}{ 6 }
\renewcommand{\afuenfzehn}{ 5 }
\renewcommand{\asechzehn}{ 64 }
\renewcommand{\asiebzehn}{ }
\renewcommand{\aachtzehn}{ }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellefuenfzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabegibtloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Eine \stichwort {Primzahl} {.}
}{Die \stichwort {Sprache der Aussagenlogik} {} $L^V$ zu einer Aussagenvariablenmenge $V$.
}{Die
\stichwort {Uminterpretation} {}
\mathl{I { \frac{ m }{ x } }}{} zu einer
$S$-\definitionsverweis {Interpretation}{}{}
$I$ in einer Menge $M$, wobei $x$ eine Variable und
\mathl{m \in M}{} ein Element der Grundmenge ist.
}{Der \stichwort {Rang} {} eines prädikatenlogischen Ausdrucks
\mathl{\alpha}{.}
}{Eine
\stichwortpraemath {R} {berechenbare Funktion}{}
\maabbdisp {F} {\N^k} {\N
} {.}
}{Eine $K$-Modallogik. }
}
{} {}
\inputaufgabegibtloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Das \stichwort {Substitutionslemma} {.}}{Der \stichwort {Satz über die induktive Definition einer Abbildung} {} auf einem Peano-Dedekind-Modell $(N,0,\prime)$.}{Der \stichwort {Vollständigkeitssatz} {} der Modallogik.}
}
{} {}
\inputaufgabegibtloesung
{4 (2+1+1)}
{
Folgende Aussagen seien bekannt. \aufzaehlungsieben{Der frühe Vogel fängt den Wurm. }{Doro wird nicht von Lilly gefangen. }{Lilly ist ein Vogel oder ein Igel. }{Für Igel ist 5 Uhr am Morgen spät. }{Doro ist ein Wurm. }{Für Vögel ist 5 Uhr am Morgen früh. }{Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs. } Beantworte folgende Fragen. \aufzaehlungdrei{Ist Lilly ein Vogel oder ein Igel? }{Ist sie ein frühes oder ein spätes Tier? }{Fängt der späte Igel den Wurm? }
}
{} {}
\inputaufgabegibtloesung
{8}
{
Es sei $\alpha$ eine aussagenlogische Aussage und es seien
\mathl{p_1 , \ldots , p_n}{} die darin vorkommenden Aussagenvariablen. Es sei
\mavergleichskettedisp
{\vergleichskette
{ \gamma
}
{ =} { \pm p_1 \wedge \ldots \wedge \pm p_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine fixierte Konjunktion dieser
\zusatzklammer {negierten} {} {}
Aussagenvariablen. Zeige, dass dann
\mathdisp {\vdash \gamma \rightarrow \alpha \text{ oder } \vdash \gamma \rightarrow \neg \alpha} { }
gilt.
}
{} {}
\inputaufgabegibtloesung
{2}
{
Es sei
\mathl{K=\{E,m,c\}}{} eine Konstantenmenge, $Q$ ein einstelliges Funktionssymbol und $P$ ein zweistelliges Funktionssymbol. Es sei $I$ die Interpretation mit
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als Grundmenge, bei der $Q$ als Quadrieren, $P$ als Multiplikation und die Konstanten als
\mavergleichskette
{\vergleichskette
{I(E)
}
{ = }{9 000 000 000
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\mavergleichskette
{\vergleichskette
{I(m)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{I(c)
}
{ = }{300 000
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
interpretiert wird. Ist der Ausdruck
\mathdisp {E = P m Q c} { }
unter dieser Interpretation gültig?
}
{} {}
\inputaufgabegibtloesung
{4 (1+2+1)}
{
\aufzaehlungdrei{Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist.
}{Beschreibe die Bedingung
\zusatzklammer {und zwar so, dass die Bedingung erkennbar ist} {} {}
aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck
\zusatzklammer {also mit dem Symbolalphabet
\mathl{+,\cdot,0,1}{} und Variablen} {} {}
in der einen freien Variablen $x$.
}{Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen $x$.
}
}
{} {}
\inputaufgabegibtloesung
{3}
{
Formuliere die \definitionsverweis {Injektivität}{}{} für eine Abbildung \maabbdisp {f} {D} {Z } {} prädikatenlogisch mit Hilfe der Verwendung von Sorten.
}
{} {}
\inputaufgabegibtloesung
{5 (3+2)}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^S$ die zugehörige Sprache und $T$ die zugehörige Termmenge. Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{ L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge.
\aufzaehlungzwei {Zeige, dass durch
\mathdisp {s \cong_\Gamma t \text{ genau dann, wenn } I(s)=I(t) \text{ für jede Interpretation } I \text{ mit } I \vDash \Gamma} { }
eine
\definitionsverweis {Äquivalenzrelation}{}{}
auf $T$ definiert wird.
} {Wenn man $\Gamma$ vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?
}
}
{} {}
\inputaufgabegibtloesung
{5 (1+1+1+1+1)}
{
In einer Wohngemeinschaft leben die Personen
\mathl{A,B,C,D,E}{.} Wir betrachten die folgenden Relationen:
\aufzaehlungdrei{
\mathl{Txy}{} bedeutet, dass $x$ und $y$ manchmal miteinander Tennis spielen,
}{
\mathl{Sxyz}{} bedeutet, dass $x,y$ und $z$ manchmal miteinander Skat spielen,
}{
\mathl{Kxyzw}{} bedeutet, dass $x,y,z$ und $w$ manchmal miteinander Doppelkopf spielen.
}
In der WG gilt
\mathdisp {TDE, SABC, SABE, KACED} { . }
\aufzaehlungfuenf{Charakterisiere umgangssprachlich die Person $D$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
}{Charakterisiere umgangssprachlich die Person $C$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $A$.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $B$.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $E$.
}
}
{} {}
\inputaufgabe
{4}
{
Entwerfe ein Programm für eine \definitionsverweis {Registermaschine}{}{,} das nach und nach alle \definitionsverweis {Quadratzahlen}{}{} ausdruckt.
}
{} {}
\inputaufgabe
{4}
{
Es seien
\mathl{T, S \subseteq \N}{} entscheidbare Mengen. Zeige, dass dann auch die Vereinigung
\mathl{T \cup S}{,} der Durchschnitt
\mathl{T \cap S}{} und auch das Komplement
\mathl{\N \setminus T}{} entscheidbar sind.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Zeige, dass die Abbildung \maabbeledisp {f} {\N^3} { \N } {(x,y,z)} {xy^2-z^2 + 2z^3 } {,} \zusatzklammer {wohldefiniert und} {} {} \definitionsverweis {arithmetisch repräsentierbar}{}{} ist.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Beweise das Unvollständigkeitslemma.
}
{} {}
\inputaufgabegibtloesung
{6 (1+1+4)}
{
Wir interpretieren den Satz von Sokrates, \anfuehrung{Ich weiß, dass ich nichts weiß}{,} als modallogisches Axiomenschema
\mathdisp {\Box \neg \Box \alpha} { . }
Zeige die folgenden Aussagen.
\aufzaehlungdrei{Dieses Axiomenschema ist
\definitionsverweis {paradox}{}{.}
}{Dieses Axiomenschema ist innerhalb der
$K$-\definitionsverweis {Modallogik}{}{}
äquivalent zu
\mathdisp {\Box \Diamond \alpha} { . }
}{Dieses Axiomenschema ist innerhalb der
$K$-\definitionsverweis {Modallogik}{}{}
äquivalent zu
\mathdisp {\Box \alpha} { , }
also zum
\definitionsverweis {Leerheitsaxiom}{}{.}
}
}
{} {}
\inputaufgabegibtloesung
{5}
{
Zeige, dass in einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} das modallogische
\definitionsverweis {Transitivitätsaxiom}{}{}
genau dann gilt, wenn $R$
\definitionsverweis {transitiv}{}{}
ist.
}
{} {}