Kurs:Einführung in die mathematische Logik/1/Klausur mit Lösungen/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}{ 1 }
\renewcommand{\afuenf}{ 4 }
\renewcommand{\asechs}{ 6 }
\renewcommand{\asieben}{ 1 }
\renewcommand{\aacht}{ 4 }
\renewcommand{\aneun}{ 12 }
\renewcommand{\azehn}{ 3 }
\renewcommand{\aelf}{ 2 }
\renewcommand{\azwoelf}{ 6 }
\renewcommand{\adreizehn}{ 5 }
\renewcommand{\avierzehn}{ 6 }
\renewcommand{\afuenfzehn}{ 7 }
\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. Bei 3.-7. bedeutet $S$ ein Symbolalphabet einer prädikatenlogischen Sprache erster Stufe. \aufzaehlungsechs{Ein Primzahl\stichwort {zwilling} {.}
}{Die Bestandteile einer \stichwort {Grundtermmenge} {.}
}{Eine \stichwortpraemath {S} {Struktur}{} zu einem Symbolalphabet $S$ einer Sprache erster Stufe.
}{Ein \stichwort {allgemeingültiger} {} prädikatenlogischer Ausdruck $\alpha \in L^S$.
}{Ein \stichwortpraemath {S} {Homomorphismus}{} \maabbdisp {\varphi} {M} {N } {} zwischen zwei $S$-\definitionsverweis {Strukturen}{}{} \mathkor {} {M} {und} {N} {.}
}{Eine
\stichwort {arithmetisch repräsentierbare} {}
Relation
\mathl{R \subseteq \N^r}{.}
}
}
{} {}
\inputaufgabegibtloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der \stichwort {Isomorphiesatz} {} für \zusatzklammer {zweitstufige} {} {} Dedekind-Peano-Modelle.}{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} {f} } {\tabellenzeiledrei {w} {f} {w} } {\tabellenzeiledrei {f} {w} {f} } {\tabellenzeiledrei {f} {f} {w} }
}
{} {}
\inputaufgabegibtloesung
{1}
{
Gehört das leere Wort $\emptyset$ zur Sprache der Aussagenlogik $L^V$ zu einer Aussagenvariablenmenge $V$?
}
{} {}
\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
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
entweder
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{ \neg \alpha
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabegibtloesung
{6}
{
Man gebe ein Beispiel für eine mathematische Existenzaussage, die mit dem Lemma von Zorn bewiesen wird, und führe den Beweis durch.
}
{} {}
\inputaufgabegibtloesung
{1}
{
Erstelle einen prädikatenlogischen Ausdruck $\alpha$, der in einer Struktur genau dann gilt, wenn die Grundmenge der Struktur genau $4$ Elemente besitzt.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Es sei das arithmetische Alphabet
\mathl{\{0,1,+,\cdot\}}{} zusammen mit der Variablenmenge
\mathl{\{x,y\}}{} gegeben. Interpretiere den Term
\mathdisp {((0+1)+x) \cdot (1+(y+1))} { }
unter den folgenden Interpretationen, wobei $M$ die Grundmenge der Interpretation bezeichne.
\aufzaehlungvier{
\mathl{M=\N}{} mit der Standardinterpretation und der Variablenbelegung
\mathl{I(x)=5}{} und
\mathl{I(y)=3}{.}
}{
\mathl{M= \operatorname{Mat}_{ 2 } (\R)}{} mit der Standardinterpretation
\mathdisp {I(0)= \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, \, I(1)= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}} { }
und der üblichen Matrizenaddition und Matrizenmultiplikation und der Variablenbelegung
\mathl{I(x)= \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}}{} und
\mathl{I(y)=\begin{pmatrix} 3 & -2 \\ 0 & 5 \end{pmatrix}}{.}
}{
\mathl{M=\Z}{,} mit
\mathdisp {I(0)=5,\, I(1) =-1,\, I(x)=0, \, I(y)=0} { , }
und wo sowohl $+$ als auch $\cdot$ als Subtraktion interpretiert werden.
}{
\mathl{M=}{}
\definitionsverweis {Potenzmenge}{}{}
von
\mathl{\{1,2,3,4,5\}}{} mit
\mathdisp {I(0)=\emptyset ,\, I(1) = \{1,2,3,4,5\} ,\, I(x) = \emptyset , \, I(y)=\{2,4\}} { , }
und wo $+$ als $\cup$ und $\cdot$ als $\cap$ interpretiert wird.
}
}
{} {}
\inputaufgabegibtloesung
{12 (1+1+4+2+4)}
{
Es sei $G$ ein dreistelliges Relationssymbol und $L$ die zugehörige prädikatenlogische Sprache. Es sei $I$ die
\definitionsverweis {Interpretation}{}{,}
bei der die Grundmenge die euklidische Ebene ist und $G$ durch die dreistellige Relation interpretiert wird, bei der
\mathl{G(A,B,C)}{} zutrifft, wenn die Punkte
\mathl{A,B,C}{} auf einer Geraden liegen.
\aufzaehlungfuenf{Zeige
\mathl{I \vDash Gxyz \leftrightarrow Gyxz}{.}
}{Zeige, dass im Allgemeinen nicht
\mathl{I \vDash \forall x \forall y \forall z { \left( Gxyz \rightarrow Gxyu \right) }}{} gelten muss.
}{Es sei
\mathl{\Gamma=\{ \forall x \forall y \forall z { \left( Gxyz \leftrightarrow Gyxz \right) } , \, \forall x \forall y \forall z { \left( Gxyz \leftrightarrow Gxzy \right) } \}}{.} Erstelle eine Ableitung für
\mathl{\Gamma \vdash Gxyz \leftrightarrow Gyzx}{.}
}{Zeige, dass der Ausdruck
\mathl{Gxyz \wedge Gxyu}{} bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen
\mathl{x,y,z,u}{} belegenden Punkte auf einer Geraden liegen.
}{Formuliere einen Ausdruck aus $L$ in vier freien Variablen, der bei der gegebenen Interpretation besagt, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.
}
}
{} {}
\inputaufgabe
{3}
{
Erläutere den Begriff \stichwort {Sortenprädikat} {} an einem mathematischen Beispiel.
}
{} {}
\inputaufgabegibtloesung
{2}
{
Man gebe ein Beispiel für einen \definitionsverweis {kommutativen Halbring}{}{,} der kein \definitionsverweis {Peano-Halbring}{}{} ist.
}
{} {}
\inputaufgabe
{6 (3+3)}
{
\aufzaehlungzwei {Entwerfe ein Programm für eine
\definitionsverweis {Registermaschine}{}{,}
das die Potenz
\mathl{r_j^{r_k}}{} berechnet, wobei
\mathl{r_j}{} und
\mathl{r_k}{} die Inhalte im $j$-ten bzw. $k$-ten Register sind.
} {Entwerfe ein Programm für eine Registermaschine, das entscheidet, ob der Registerinhalt $r_i$ des Registers $R_i$ die echte Potenz einer natürlichen Zahl ist.
}
}
{} {}
\inputaufgabegibtloesung
{5}
{
Es sei
\mathl{T \subseteq \N}{} eine Teilmenge von natürlichen Zahlen. Zeige, dass $T$ genau dann
$R$-\definitionsverweis {entscheidbar}{}{}
ist, wenn sowohl $T$ als auch das Komplement
\mathl{\N \setminus T}{}
$R$-\definitionsverweis {aufzählbar}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{6}
{
Man gebe für die Abbildung
\maabbdisp {F} {\N} {\N
} {}
mit
\mavergleichskettedisp
{\vergleichskette
{F(n)
}
{ =} {\begin{cases} \sqrt{n} \, ,\text{ falls } \sqrt{n} \in \N \, ,\\ 0 \text{ sonst} \, , \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
einen Ausdruck an, der $F$
\definitionsverweis {arithmetisch repräsentiert}{}{.}
}
{} {}
\inputaufgabegibtloesung
{7}
{
Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine arithmetische Ausdrucksmenge ohne freie Variablen 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} { }
folgt, dass $\alpha$ in $\Gamma$ die Relation $R$ genau dann
\definitionsverweis {repräsentiert}{}{,}
wenn
\mathl{\beta}{} in $\Gamma$ die Relation $R$ repräsentiert.
}
{} {}