Kurs:Einführung in die mathematische Logik/1/Klausur mit Lösungen/latex

Aus Wikiversity

%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.

}
{} {}