Kurs:Einführung in die mathematische Logik/15/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}{ 2 }
\renewcommand{\avier}{ 2 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 5 }
\renewcommand{\asieben}{ 4 }
\renewcommand{\aacht}{ 3 }
\renewcommand{\aneun}{ 0 }
\renewcommand{\azehn}{ 0 }
\renewcommand{\aelf}{ 0 }
\renewcommand{\azwoelf}{ 2 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 0 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 4 }
\renewcommand{\asiebzehn}{ 0 }
\renewcommand{\aachtzehn}{ 31 }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellesiebzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Ein \stichwort {Wort} {} über einem Alphabet $A$.
}{Eine \stichwort {Ordnungs} {}relation $\preccurlyeq$ auf einer Menge $I$.
}{Die \zusatzklammer {rekursiv definierte} {} {} \stichwort {Gültigkeit} {} eines prädikatenlogischen $S$-Ausdruckes $\alpha$ bei einer $S$-\definitionsverweis {Interpretation}{}{} auf einer Menge $M$.
}{Ein \stichwortpraemath {S} {Homomorphismus}{} \maabbdisp {\varphi} {M} {N } {} zwischen zwei $S$-\definitionsverweis {Strukturen}{}{} \mathkor {} {M} {und} {N} {.}
}{Die
\stichwort {Multiplikation} {}
mit
\mathl{n \in \N}{} in einem
\definitionsverweis {Dedekind-Peano-Modell}{}{}
$\N$.
}{Die \stichwort {Ableitbarkeit} {} eines \definitionsverweis {modallogischen Ausdrucks}{}{} $\alpha$ im $K$-System. }
}
{
\aufzaehlungsechs{Ein Wort über dem Alphabet $A$ ist eine beliebige endliche Zeichenkette, wobei sämtliche Einzelzeichen zu $A$ gehören.
}{Die
\definitionsverweis {Relation}{}{}
$\preccurlyeq$ heißt Ordnungsrelation, wenn folgende drei Bedingungen erfüllt sind.
\aufzaehlungdrei{Es ist $i\preccurlyeq i$ für alle $i \in I$.
}{Aus $i\preccurlyeq j$ und $j\preccurlyeq k$ folgt stets $i\preccurlyeq k$.
}{Aus $i\preccurlyeq j$ und $j\preccurlyeq i$ folgt $i=j$.
}
}{Die
$S$-\definitionsverweis {Ausdrücke}{}{}
werden folgendermaßen als gültig charakterisiert
\zusatzklammer {dabei seien
\mathl{s,t,t_1 , \ldots , t_n}{} Terme und $\alpha,\beta$ Ausdrücke} {} {.}
\aufzaehlungsieben{
\mathl{I \vDash s = t}{,} wenn
\mathl{I(s)=I(t)}{.}
}{
\mathl{I \vDash Rt_1 \ldots t_n}{,} wenn
\mathl{(I(t_1) , \ldots , I(t_n)) \in R^M}{.}
}{
\mathl{I \vDash \neg { \left( \alpha \right) }}{,} wenn nicht
\mathl{I \vDash \alpha}{} gilt.
}{
\mathl{I \vDash { \left( \alpha \right) } \wedge { \left( \beta \right) }}{,} wenn
\mathl{I \vDash \alpha}{} und
\mathl{I \vDash \beta}{} gilt.
}{
\mathl{I \vDash { \left( \alpha \right) } \rightarrow { \left( \beta \right) }}{,} wenn die Gültigkeit
\mathl{I \vDash \alpha}{} die Gültigkeit
\mathl{I \vDash \beta}{} impliziert.
}{
\mathl{I \vDash \exists x \alpha}{,} wenn es ein
\mathl{m \in M}{} gibt mit
\mathl{I \frac{m}{x} \vDash \alpha}{.}
}{
\mathl{I \vDash \forall x \alpha}{,} wenn für alle
\mathl{m \in M}{} die Beziehung
\mathl{I \frac{m}{x} \vDash \alpha}{} gilt.
}
}{Die Abbildung
\maabbdisp {\varphi} {M} {N
} {}
heißt $S$-Homomorphismus, wenn folgende Eigenschaften gelten.
\aufzaehlungdrei{Für jede Konstante
\mathl{c \in S}{} ist
\mavergleichskettedisp
{\vergleichskette
{\varphi ( c^M )
}
{ =} { c^N
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Für jedes $n$-stellige Funktionssymbol
\mathl{f \in S}{} ist
\mavergleichskettedisp
{\vergleichskette
{\varphi ( f^M (m_1 , \ldots , m_n ) )
}
{ =} { f^N ( \varphi ( m_1) , \ldots , \varphi( m_n ))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mathl{m_1 , \ldots , m_n \in M}{.}
}{Für jedes $n$-stellige Relationsymbol
\mathl{R \in S}{} impliziert die Gültigkeit von
\mathdisp {R^M (m_1 , \ldots , m_n )} { }
die Gültigkeit von
\mathdisp {R^N ( \varphi ( m_1) , \ldots , \varphi( m_n ))} { . }
}
}{Die Multiplikation mit $n$ ist diejenige aufgrund von
Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021))
eindeutig bestimmte Abbildung
\maabbeledisp {\mu_n} {\N} {\N
} {k} { \mu_n(k)
} {,}
für die
\mathdisp {\mu_n (0)=0 \text{ und } \mu_n(k') = \mu_n(k) +n \text { für alle } k \in \N} { }
gilt.
}{Man sagt, dass ein
\definitionsverweis {modallogischer Ausdruck}{}{}
$\alpha$ aus dem
$K$-\definitionsverweis {System}{}{}
ableitbar
ist, wenn sich $\alpha$ aus
\definitionsverweis {aussagenlogischen Tautologien}{}{}
und aus Instanzen des
$K$-\definitionsverweis {Axioms}{}{}
mit Hilfe des Modus ponens oder der Nezessisierungsregel ergibt.
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz von Wiles (Großer Fermat).}{Der \stichwort {Vollständigkeitssatz für Tautologien} {} \zusatzklammer {Prädikatenlogik} {} {.}}{Der \stichwort {erste Gödelsche Unvollständigkeitssatz} {.}}
}
{
\aufzaehlungdrei{Die diophantische Gleichung
\mavergleichskettedisp
{\vergleichskette
{ x^n+y^n
}
{ =} { z^n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besitzt für kein
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine ganzzahlige nichttriviale Lösung.}{Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und
\mathl{\alpha \in L^ S}{} ein $S$-Ausdruck. Dann ist $\alpha$ genau dann eine
\definitionsverweis {ableitbare Tautologie}{}{,}
wenn $\alpha$
\definitionsverweis {allgemeingültig}{}{}
ist.}{Es sei
\mathl{\Gamma \subseteq L^{\rm Ar}}{} eine arithmetische Ausdrucksmenge, die
\definitionsverweis {widerspruchsfrei}{}{}
und
\definitionsverweis {aufzählbar}{}{}
sei und
\definitionsverweis {Repräsentierungen erlaube}{}{.}
Dann ist
\mathl{\Gamma^\vdash}{}
\definitionsverweis {unvollständig}{}{.}}
}
\inputaufgabeklausurloesung
{2}
{
Wenn Karl an Susanne denkt, bekommt er feuchte Hände, einen Kloß im Hals und einen roten Kopf. Einen roten Kopf bekommt er genau dann, wenn er an Susanne denkt oder wenn er das leere Tor nicht trifft. Wenn Karl das leere Tor trifft, bekommt er feuchte Hände. Karl bekommt den Ball vor dem leeren Tor. Kurz darauf bekommt er feuchte Hände, einen roten Kopf, aber keinen Kloß im Hals. Hat er an Susanne gedacht? Hat er das leere Tor getroffen?
}
{
Karl hat nicht an Susanne gedacht, da er sonst einen Kloß im Hals bekommen hätte, was er nicht hat. Andererseits bekommt er einen roten Kopf, was bedeutet, dass er das leere Tor nicht getroffen hat oder an Susanne gedacht hat. Da letzteres nicht der Fall ist, hat er das leere Tor nicht getroffen.
}
\inputaufgabeklausurloesung
{2}
{
Erläutere das Beweisprinzip der vollständigen Induktion.
}
{
Mit dem Beweisprinzip der vollständigen Induktion werden Aussagen
\mathl{A(n)}{} bewiesen, die von den natürlichen Zahlen
\mathl{n \in \N}{} abhängen. Man beweist zuerst die Aussage
\mathl{A(0)}{.} Ferner zeigt man, dass man für alle $n$ aus der Gültigkeit von $A(n)$ auf die Gültigkeit von $A(n+1)$ schließen kann. Daraus folgt die Gültigkeit von $A(n)$ für alle
\mathl{n \in \N}{.}
}
\inputaufgabeklausurloesung
{3}
{
Es sei $A$ ein \definitionsverweis {Alphabet}{}{} mit $3$ Symbolen. Wie viele Wörter über $A$ der Länge $5$ gibt es, wenn man nicht zwischen den Leserichtungen unterscheiden kann?
}
{
Es gibt $3^5=243$ Wörter der Länge $5$ über einem Alphabet mit $3$ Symbolen. Bei einem solchen Wort kommt es auf die Leserichtung genau dann nicht an, wenn der erste mit dem fünften und der zweite mit dem vierten Symbol übereinstimmt. Dafür gibt es
\mathl{3^3=27}{} Möglichkeiten.
Somit gibt es
\mavergleichskettedisp
{\vergleichskette
{243 -27
}
{ =} {216
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Wörter, bei denen es auf die Leserichtung ankommt. Diese sind mit ihrer umgekehrten Reihenfolge zu identifizieren, wenn man die Leserichtungen nicht unterscheiden kann. Somit gibt es
\mavergleichskettedisp
{\vergleichskette
{ 108+27
}
{ =} { 135
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Worttypen, wenn man die Leserichtung nicht unterscheiden kann.
}
\inputaufgabeklausurloesung
{5}
{
Es sei
\mathl{n\in \N_+}{.} Man gebe ein Beispiel für eine aussagenlogische
\definitionsverweis {widersprüchliche}{}{}
Ausdrucksmenge
\mavergleichskettedisp
{\vergleichskette
{\Gamma
}
{ =} {\{ \alpha_1,\alpha_2 , \ldots , \alpha_n \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
derart, dass jede echte Teilmenge davon
\definitionsverweis {widerspruchsfrei}{}{}
ist.
}
{
Bei
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
kann man für $\alpha$ jede widersprüchliche Aussage, beispielsweise
\mathl{p \wedge \neg p}{} nehmen. Es sei also
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es seien
\mathl{p_1,p_2 , \ldots , p_{n-1}}{}
\zusatzklammer {verschiedene} {} {}
Aussagenvariablen. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ \alpha_1
}
{ =} { p_1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{ \alpha_i
}
{ =} { p_{i-1} \rightarrow p_{i}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für
\mavergleichskette
{\vergleichskette
{2
}
{ \leq }{i
}
{ \leq }{n-1
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{ \alpha_n
}
{ =} { p_{n-1} \rightarrow \neg p_1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Menge $\Gamma$ ist widersprüchlich, da man aus $\Gamma$ durch mehrfache Anwendung der Kettenschlussregel und des Modus ponens
\mathdisp {\Gamma \vdash \neg p_1} { }
erhält, was ein Widerspruch zu $p_1 \in \Gamma$ ist. Es sei nun
\mavergleichskettedisp
{\vergleichskette
{\Delta
}
{ =} {\Gamma_i \setminus \{ \alpha_i \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir müssen zeigen, dass $\Delta_i$ widerspruchsfrei ist, wofür es genügt, eine erfüllende Wahrheitsbelegung anzugeben. Es sei $i$ fixiert. Dann erfüllt die Wahrheitsbelegung, bei der jede Variable
\mathl{p_j}{} mit
\mavergleichskette
{\vergleichskette
{j
}
{ \leq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als wahr und jede Variable
\mathl{p_j}{} mit
\mavergleichskette
{\vergleichskette
{j
}
{ > }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als falsch belegt wird, die Menge
\mathl{\Delta_i}{,} da für die
\mathl{\alpha_j}{} mit
\mavergleichskette
{\vergleichskette
{j
}
{ < }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Vorder-und Nachsatz wahr belegt sind und da für die
\mathl{\alpha_j}{} mit
\mavergleichskette
{\vergleichskette
{j
}
{ > }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
der Vordersatz falsch belegt ist.
}
\inputaufgabeklausurloesung
{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.
}
{
Wegen der Widerspruchsfreiheit können nicht sowohl $\alpha$ als auch
\mathl{\neg \alpha}{} zu $\Gamma$ gehören. Wenn weder $\alpha$ noch
\mathl{\neg \alpha}{} zu $\Gamma$ gehören, so ist entweder
\mathl{\Gamma \cup \{ \alpha \}}{} oder
\mathl{\Gamma \cup \{ \neg \alpha \}}{} widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck $\beta$ sowohl
\mathdisp {\Gamma \cup \{ \alpha \} \vdash \beta} { }
als auch
\mathdisp {\Gamma \cup \{ \neg \alpha \} \vdash \beta} { }
gelten. Dies bedeutet
nach Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021))
\mathdisp {\Gamma \vdash \alpha \rightarrow \beta} { }
und
\mathdisp {\Gamma \vdash \neg \alpha \rightarrow \beta} { , }
woraus aufgrund der
Fallunterscheidungsregel
\mathdisp {\Gamma \vdash \beta} { }
folgt. Dies bedeutet aber, dass $\Gamma$ widersprüchlich ist.
}
\inputaufgabeklausurloesung
{3}
{
Man erläutere durch Beispiele, dass der Aufbau der Prädikatenlogik nicht immer der mathematischen Intuition entspricht.
}
{Prädikatenlogik/Intuitiv oder nicht/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{2 (1+1)}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {PuntosAfín.svg} }
\end{center}
\bildtext {} }
\bildlizenz { PuntosAfín.svg } {} {Marianov} {Commons} {CC-by-sa 1.0} {}
Wir betrachten das Symbolalphabet $S$, das neben Variablen aus einem einzigen zweistelligen Relationssymbol $R$ besteht, wobei in der abgebildeten Punktemenge das Relationssymbol $R$ als \anfuehrung{(echt) rechts von}{} interpretiert wird. Für zwei Punkte
\mathl{P,Q}{} bedeutet also
\mathl{RPQ}{,} dass sich $P$ rechts von $Q$ befindet.
\aufzaehlungzwei {Welche(r) Punkt(e) erfüllt(en)
\mathdisp {\exists y (Ryx \wedge \forall z (Rzx \rightarrow y=z)} { ? }
} {Charakterisiere den Punkt
\mathl{p_0}{} mit einem
$S$-\definitionsverweis {Ausdruck}{}{}
in der einen freien Variablen $x$.
}
}
{
\aufzaehlungzwei {Die Aussage trifft für $x$ genau dann zu, wenn es rechts von $x$ genau einen Punkt gibt. Dies gilt nur für $P_1$.
} {Der Punkt $p_0$ besitzt genau drei Punkte rechts von ihm. Also ist
\mathdisp {\exists u \exists v \exists w (Rux \wedge Rvx \wedge Rwx \wedge u \neq v \wedge u \neq w \wedge v \neq w \wedge \forall z (Rzx \rightarrow z=u \vee z=v \vee z=w) )} { }
ein charakterisierender Ausdruck.
}
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{4}
{
Zeige, dass ein
\definitionsverweis {gerichteter Graph}{}{}
genau dann
\definitionsverweis {symmetrisch}{}{}
ist, wenn für jede Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Beziehung
\mavergleichskettedisp
{\vergleichskette
{T
}
{ \subseteq} { M \setminus \operatorname{Vorg} { \left( M \setminus \operatorname{Vorg} { \left( T \right) } \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{
Wir zeigen, dass die Negationen der beiden Eigenschaften zueinander äquivalent sind.
Es sei zuerst die Relation nicht symmetrisch. Dann gibt es $x,y$ mit
\mathl{xRy}{,} aber
\mathl{yRx}{} gilt nicht. Dann ist $y$ kein Vorgänger von $x$ und daher ist
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{ M \setminus \operatorname{Vorg} { \left( \{x\} \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es ist somit
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{ \operatorname{Vorg} { \left( M \setminus \operatorname{Vorg} { \left( \{x\} \right) } \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und also
\mavergleichskette
{\vergleichskette
{x
}
{ \notin }{ M \setminus \operatorname{Vorg} { \left( M \setminus \operatorname{Vorg} { \left( \{x\} \right) } \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Daher gilt die Vorgängereigenschaft für
\mavergleichskettedisp
{\vergleichskette
{T
}
{ =} { \{x\}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
nicht.
Es sei nun die Vorgängereigenschaft nicht erfüllt, es gebe also eine Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{T
}
{ \not \subseteq} {M \setminus \operatorname{Vorg} { \left( M \setminus \operatorname{Vorg} { \left( T \right) } \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dann gibt es ein
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{ \operatorname{Vorg} { \left( M \setminus \operatorname{Vorg} { \left( T \right) } \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dies bedeutet, dass es ein
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{M \setminus \operatorname{Vorg} { \left( T \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{xRy}{} gibt. Wegen
\mavergleichskette
{\vergleichskette
{y
}
{ \notin }{ \operatorname{Vorg} { \left( T \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist insbesondere nicht
\mathl{yRx}{,} also ist die Relation nicht symmetrisch.
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}