Kurs:Einführung in die mathematische Logik/11/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}{ 3 }

\renewcommand{\asechs}{ 2 }

\renewcommand{\asieben}{ 3 }

\renewcommand{\aacht}{ 7 }

\renewcommand{\aneun}{ 1 }

\renewcommand{\azehn}{ 3 }

\renewcommand{\aelf}{ 5 }

\renewcommand{\azwoelf}{ 6 }

\renewcommand{\adreizehn}{ 4 }

\renewcommand{\avierzehn}{ 3 }

\renewcommand{\afuenfzehn}{ 45 }

\renewcommand{\asechzehn}{ }

\renewcommand{\asiebzehn}{ }

\renewcommand{\aachtzehn}{ }

\renewcommand{\aneunzehn}{ }

\renewcommand{\azwanzig}{ }

\renewcommand{\aeinundzwanzig}{ }

\renewcommand{\azweiundzwanzig}{ }

\renewcommand{\adreiundzwanzig}{ }

\renewcommand{\avierundzwanzig}{ }

\renewcommand{\afuenfundzwanzig}{ }

\renewcommand{\asechsundzwanzig}{ }

\punktetabellevierzehn

\klausurnote

\newpage


\setcounter{section}{0}





\inputaufgabeklausurloesung
{3}
{

Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Die \stichwort {Ableitbarkeit} {} eines Aussage
\mathl{\alpha \in L^V}{} aus einer Aussagenmenge
\mathl{\Gamma \subseteq L^V}{} in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer Aussagevariablenmenge $V$.

}{Eine \stichwort {Ordnungs} {}relation $\preccurlyeq$ auf einer Menge $I$.

}{Die \stichwort {Erfüllbarkeit} {} eines $S$-Ausdruckes $\alpha \in L^S$, wobei $S$ ein \definitionsverweis {Symbolalphabet}{}{} bezeichnet.

}{Die \stichwort {elementare Äquivalenz für Elemente} {}
\mathl{m,n \in M}{} für eine $S$-Struktur $M$.

}{Die \stichwort {aufzählbare Axiomatisierbarkeit} {} einer Theorie
\mathl{T \subseteq L^S_0}{} zu einem Symbolalphabet $S$.

}{Die \stichwort {Gültigkeit} {} eines modallogischen Ausdrucks $\alpha$ in einem modallogischen Rahmen $(M, R)$. }

}
{

\aufzaehlungsechs{Man sagt, dass $\alpha$ aus $\Gamma$ ableitbar ist, wenn es endlich viele Ausdrücke
\mathl{\alpha_1 , \ldots , \alpha_n \in \Gamma}{} derart gibt, dass
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \alpha} { }
gilt. }{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$. } }{Man nennt $\alpha$ erfüllbar, wenn es eine $S$-\definitionsverweis {Interpretation}{}{} $I$ mit
\mathl{I \vDash \alpha}{} gibt. }{Zwei Elemente
\mathl{m,n \in M}{} heißen elementar äquivalent, wenn für jeden Ausdruck
\mathl{\alpha \in L_1^ S}{} in der einen freien Variablen $x$ und jede Variablenbelegung $\lambda$ auf $M$ die Beziehung
\mathdisp {I \frac{m}{x} \vDash \alpha \text{ genau dann, wenn } I \frac{n}{x} \vDash \alpha} { }
gilt. }{Eine \definitionsverweis {Theorie}{}{}
\mathl{T \subseteq L^S_0}{} heißt aufzählbar axiomatisierbar, wenn es eine $R$-\definitionsverweis {aufzählbare}{}{} Satzmenge
\mathl{\Gamma \subseteq L^S_0}{} mit
\mathl{T = \Gamma^\vdash}{} gibt. }{Die Gültigkeit in einem modallogischen Rahmen bedeutet, dass für jede \definitionsverweis {Wahrheitsbelegung}{}{} $\mu$
\mathdisp {(M,R, \mu) \vDash \alpha} { }
\definitionsverweis {gilt}{}{.} }


}





\inputaufgabeklausurloesung
{3}
{

Formuliere die folgenden Sätze. \aufzaehlungdrei{Das \stichwort {Substitutionslemma} {.}}{Der \stichwort {Vollständigkeitssatz der Aussagenlogik} {.}}{Der \stichwort {zweite Gödelsche Unvollständigkeitssatz} {.}}

}
{

\aufzaehlungdrei{Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben und es seien
\mathl{x_1 , \ldots , x_k}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k}{} fixierte $S$-Terme. Es sei eine $S$-Interpretation $I$ gegeben. Dann gelten folgende Aussagen. \aufzaehlungzwei {Für jeden $S$-Term $s$ gilt
\mavergleichskettedisp
{\vergleichskette
{ I \left( s { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) }
{ =} { \left( I { \frac{ I(t_1) , \ldots , I(t_k) }{ x_1 , \ldots , x_k } } \right) (s) }
{ } { }
{ } { }
{ } { }
} {}{}{.} } {Für jeden $S$-Ausdruck $\alpha$ gilt
\mathdisp {I \vDash \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \text{ genau dann, wenn } { \left( I { \frac{ I(t_1) , \ldots , I(t_k) }{ x_1 , \ldots , x_k } } \right) } \vDash \alpha} { . }
}}{Es sei $V$ eine Menge an \definitionsverweis {Aussagenvariablen}{}{} und
\mathl{\Gamma \subseteq L^V}{} eine Teilmenge der zugehörigen \definitionsverweis {Sprache der Aussagenlogik}{}{.} Es sei
\mathl{\alpha \in L^V}{.} Dann ist
\mathdisp {\Gamma \vdash \alpha \text{ genau dann, wenn } \Gamma \vDash \alpha} { . }
}{Es sei $\Gamma$ eine arithmetische Ausdrucksmenge, die \definitionsverweis {widerspruchsfrei}{}{} und \definitionsverweis {entscheidbar}{}{} sei und die \definitionsverweis {Peano-Arithmetik}{}{} umfasse. Dann ist die Widerspruchsfreiheit
\mathl{WF(\Gamma)}{} nicht aus $\Gamma$ ableitbar, d.h. es ist
\mathdisp {\Gamma \not\vdash WF(\Gamma)} { . }
}


}





\inputaufgabeklausurloesung
{1}
{

Formuliere die Kontraposition zu folgender Aussage von Professor Knopfloch: \anfuehrung{Wenn Sie mein Schreiben vollständig gelesen und verstanden haben, dann antworten Sie mit Ihrer Uni-email}{.}

}
{

Wenn Sie nicht mit Ihrer Uni-email antworten, dann haben Sie mein Schreiben nicht vollständig gelesen oder nicht verstanden.


}





\inputaufgabeklausurloesung
{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} {f} } {\tabellenzeiledrei {f} {w} {w} } {\tabellenzeiledrei {f} {f} {w} }

}
{


\mathl{\neg p}{.}


}





\inputaufgabeklausurloesung
{3}
{

Die Klasse 8c hat an jedem Wochentag eine Stunde mathematische Logik. Der Lehrer sagt am Freitag: \anfuehrung{nächste Woche werden wir eine Klassenarbeit schreiben, und das wird eine Überraschung sein}{.} Begründe, dass der Lehrer lügt.

}
{Woche/Klassenarbeit/Überraschung/Aufgabe/Lösung }





\inputaufgabeklausurloesung
{2}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer Aussagenvariablenmenge $V$. Begründe die Fallunterscheidungsregel für die \definitionsverweis {Ableitungsbeziehung}{}{:} Wenn
\mathl{\Gamma \vdash \alpha \rightarrow \beta}{} und
\mathl{\Gamma \vdash \neg \alpha \rightarrow \beta}{,} dann ist auch
\mathl{\Gamma \vdash \beta}{.}

}
{

Es gilt
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\neg \alpha \rightarrow \beta) \rightarrow \beta} { }
nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (6). Nach Voraussetzung und Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (5) ergibt sich daraus
\mathl{\vdash \beta}{.}


}





\inputaufgabeklausurloesung
{3}
{

Es sei
\mathl{\Gamma \subseteq L^V}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} über einer Aussagenvariablenmenge $V$ und es seien
\mathl{\alpha, \beta \in L^V}{.} Zeige, dass
\mathdisp {\Gamma \cup \{ \alpha \} \vdash \beta} { }
zu
\mathdisp {\Gamma \vdash \alpha \rightarrow \beta} { }
äquivalent ist.

}
{

Die Ableitungsbeziehung
\mathdisp {\Gamma \vdash \alpha \rightarrow \beta} { }
bedeutet, dass es Ausdrücke
\mathl{\gamma_1 , \ldots , \gamma_n \in \Gamma}{} mit
\mathdisp {\vdash \gamma_1 \wedge \ldots \wedge \gamma_n \rightarrow { \left( \alpha \rightarrow \beta \right) }} { }
gibt. Aufgrund der aussagenlogischen Tautologie
\mathdisp {\vdash { \left( \varphi \rightarrow { \left( \psi \rightarrow \theta \right) } \right) } \leftrightarrow { \left( \varphi \wedge \psi \rightarrow \theta \right) }} { }
ist dies äquivalent zu
\mathdisp {\vdash \gamma_1 \wedge \ldots \wedge \gamma_n \wedge \alpha \rightarrow \beta} { . }
Dies bedeutet gerade
\mathdisp {\Gamma \cup \{ \alpha \} \vdash \beta} { . }


}





\inputaufgabeklausurloesung
{7}
{

Beweise den Satz von Hamel mit dem Lemma von Zorn.

}
{

Es sei $V$ ein Vektorraum über einem Körper $K$. Es sei
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{M }
{ =} { { \left\{ T \subseteq V \mid \text{ Die Elemente aus } T \text{ sind linear unabhängig} \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Die leere Menge gehört zu $M$, also ist $M$ nicht leer. Es sei
\mavergleichskette
{\vergleichskette
{N }
{ \subseteq }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine total geordnete Teilmenge. Wir behaupten, dass
\mavergleichskettedisp
{\vergleichskette
{S }
{ =} { \bigcup_{T \in N} T }
{ } { }
{ } { }
{ } { }
} {}{}{} ebenfalls linear unabhängig ist und daher eine obere Schranke von $N$ in $M$ bildet. Andernfalls gäbe es nämlich eine endliche Teilmenge
\mavergleichskette
{\vergleichskette
{E }
{ \subseteq }{S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} deren Elemente linear abhängig sind, und es gäbe auch ein
\mavergleichskette
{\vergleichskette
{T }
{ \in }{N }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} das $E$ umfasst und daher selbst linear abhängig wäre. Nach dem Lemma von Zorn besitzt $M$ also maximale Elemente, d.h. es gibt eine Teilmenge
\mavergleichskette
{\vergleichskette
{T }
{ \subseteq }{V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} die linear unabhängig ist und derart, dass es keine echt größere linear unabhängige Teilmenge von $V$ gibt. Wir behaupten, dass $T$ auch ein \definitionsverweis {Erzeugendensystem}{}{} von $V$ ist. Es sei dazu
\mavergleichskette
{\vergleichskette
{v }
{ \in }{V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Bei
\mavergleichskette
{\vergleichskette
{v }
{ \in }{T }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} sind wir fertig. Bei
\mavergleichskette
{\vergleichskette
{v }
{ \notin }{T }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist
\mathl{T \cup \{v\}}{} linear abhängig, d.h. es gibt eine Linearkombination
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i=1}^n c_i t_i +cv }
{ =} { 0 }
{ } { }
{ } { }
{ } { }
} {}{}{} mit Elementen
\mavergleichskette
{\vergleichskette
{t_i }
{ \in }{T }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und Koeffizienten
\mavergleichskette
{\vergleichskette
{c_i,c }
{ \in }{K }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} die nicht alle $0$ sind. Dabei kann $c$ nicht $0$ sein, da sonst eine lineare Abhängigkeit zwischen Elementen aus $T$ vorliegen würde. Also kann man $v$ als Linearkombination der
\mathl{t_1 , \ldots , t_n}{} ausdrücken.


}





\inputaufgabeklausurloesung
{1}
{

Wir betrachten den Satz \anfuehrung{Kein Mensch ist illegal}{.} Negiere diesen Satz durch eine Existenzaussage.

}
{

Es gibt einen Menschen, der nicht legal ist.


}





\inputaufgabeklausurloesung
{3}
{

Erläutere Vor- und Nachteile des axiomatischen Aufbaus der Mathematik.

}
{Axiomatischer Aufbau/Vor- und Nachteile/Aufgabe/Lösung }





\inputaufgabeklausurloesung
{5 (2+3)}
{

Es sei ein Symbolalphabet $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. \aufzaehlungzwei {Zeige, dass die \definitionsverweis {Substitution}{}{}
\mathl{{ \frac{ x }{ x } }}{} für die Terme die Identität ist. } {Zeige, dass die \definitionsverweis {Substitution}{}{}
\mathl{{ \frac{ x }{ x } }}{} für die Ausdrücke die Identität ist. }

}
{

\aufzaehlungzwei {Wir beweisen die Aussage durch Induktion über den Aufbau der Terme. Für Variablen ist bei
\mavergleichskette
{\vergleichskette
{y }
{ \neq }{x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} direkt
\mavergleichskette
{\vergleichskette
{y { \frac{ x }{ x } } }
{ = }{ y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und ferner
\mavergleichskette
{\vergleichskette
{x { \frac{ x }{ x } } }
{ = }{ x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Konstanten bleiben bei jeder Substitution unverändert. Für ein $n$-stelliges Funktionssymbol $f$ und Terme
\mathl{t_1 , \ldots , t_n}{} ist
\mavergleichskettedisp
{\vergleichskette
{ (ft_1 \ldots t_n) { \frac{ x }{ x } } }
{ =} { ft_1{ \frac{ x }{ x } } \ldots t_n { \frac{ x }{ x } } }
{ =} { ft_1 \ldots t_n }
{ } { }
{ } { }
} {}{}{} nach Induktionsvoraussetzung. } {Wir beweisen die Aussage durch Induktion über den Aufbau der Sprache für alle Variablen gleichzeitig. Wenn $\alpha$ eine Identität von Termen oder eine Relationsaussage ist, so ergibt sich die Behauptung unmittelbar aus Teil (1). Der Induktionsschritt für die aussagenlogischen Junktoren ergibt sich unmittelbar aus der Definition der Substitution.

Bei
\mathl{\forall y \beta}{} mit
\mavergleichskette
{\vergleichskette
{y }
{ \neq }{x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} kommt $y$ nicht im substituierenden Term vor, und daher ist
\mavergleichskette
{\vergleichskette
{v }
{ = }{y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskettedisp
{\vergleichskette
{( \forall y \beta ) { \frac{ x }{ x } } }
{ =} { \forall y (\beta { \frac{ y }{ y } } ) }
{ =} { \forall y \beta }
{ } { }
{ } { }
} {}{}{} nach Induktionsvoraussetzung. Bei
\mathl{\forall x \beta}{} ist $x$ nicht frei in $\beta$ und somit ist die relevante Termmenge leer und
\mavergleichskette
{\vergleichskette
{v }
{ = }{x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} also
\mavergleichskettedisp
{\vergleichskette
{( \forall x \beta ) { \frac{ x }{ x } } }
{ =} { \forall x (\beta { \frac{ x }{ x } } ) }
{ =} { \forall x \beta }
{ } { }
{ } { }
} {}{}{} nach Induktionsvoraussetzung. }


}





\inputaufgabeklausurloesung
{6}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet erster Stufe}{}{,} $\alpha$ ein $S$-\definitionsverweis {Ausdruck}{}{} und $x$ eine Variable. Zeige, dass
\mathl{\vdash \alpha}{} genau dann gilt, wenn
\mathl{\vdash \forall x \alpha}{} gilt.

}
{

\teilbeweis {}{}{}
{Nach der Allquantorversion von Axiom 11.1 (Einführung in die mathematische Logik (Osnabrück 2021)) ist
\mathdisp {\vdash \forall x \alpha \rightarrow \alpha \frac{x}{x}} { , }
also
\mathdisp {\vdash \forall x \alpha \rightarrow \alpha} { . }
Daher folgt aus
\mathdisp {\vdash \forall x \alpha} { }
mittels \definitionsverweis {Modus ponens}{}{} direkt
\mathdisp {\vdash \alpha} { . }
}
{} \teilbeweis {}{}{}
{Es sei umgekehrt
\mathl{\vdash \alpha}{} gegeben. Es sei $\beta$ ein beliebiger Ausdruck, in dem $x$ nicht vorkomme. Nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) und Modus ponens ergibt sich
\mathdisp {\vdash \beta \rightarrow \alpha} { }
und
\mathdisp {\vdash \neg \beta \rightarrow \alpha} { . }
Auf diese beiden abgeleiteten Ausdrücke wird nun die Allquantorversion der Existenzeinführung im Antezedens \zusatzklammer {also die Alleinführung im Sukzedens} {} {} angewendet. Dies ist möglich, da $x$ in $\beta$ überhaupt nicht und in
\mathl{\forall x \alpha}{} nicht frei vorkommt. Man erhält
\mathdisp {\vdash \beta \rightarrow \forall x \alpha} { }
und
\mathdisp {\vdash \neg \beta \rightarrow \forall x \alpha} { . }
Daraus ergibt sich mit der Fallunterscheidungsregel
\mathdisp {\vdash \forall x \alpha} { . }
}
{}


}





\inputaufgabeklausurloesung
{4 (2+2)}
{

Es sei $M$ ein \definitionsverweis {kommutativer Halbring}{}{} und
\mathl{x,y \in M}{.} Es sei
\mavergleichskettedisp
{\vergleichskette
{I }
{ \defeq} { { \left\{ u \in M \mid \exists a \exists b \exists c \exists d \text{ mit } u+ ax+by= cx+dy \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} \aufzaehlungzwei {Zeige, dass $I$ die folgenden drei Eigenschaften erfüllt. \aufzaehlungdrei{
\mathl{0 \in I}{.} }{Wenn
\mathl{u,v \in I}{} sind, so ist auch
\mathl{u+v \in I}{.} }{Wenn
\mathl{u \in I}{} und
\mathl{r \in M}{} ist, so ist auch
\mathl{ru \in I}{.} } } {$M$ erfülle nun die Abziehregel. Zeige, dass aus
\mathl{u,v \in I}{} mit
\mavergleichskette
{\vergleichskette
{u }
{ = }{v+z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} auch
\mathl{z \in I}{} folgt. }

}
{

Es sei $M$ ein \definitionsverweis {kommutativer Halbring}{}{} und
\mathl{x,y \in M}{.} Es sei
\mavergleichskettedisp
{\vergleichskette
{I }
{ \defeq} { { \left\{ u \in M \mid \exists a \exists b \exists c \exists d , \, u+ ax+by= cx+dy \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} \aufzaehlungzwei { \aufzaehlungdrei{Die Zugehörigkeit
\mathl{0 \in I}{} ergibt sich aus
\mavergleichskette
{\vergleichskette
{a }
{ = }{b }
{ = }{c }
{ = }{d }
{ = }{0 }
} {}{}{.} }{Sei
\mavergleichskette
{\vergleichskette
{ u+ ax+by }
{ = }{ cx+dy }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{ v+ a'x+b'y }
{ = }{ c'x+d'y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Dann ist durch Addition der beiden Gleichungen direkt
\mavergleichskettedisp
{\vergleichskette
{ u+v +(a+a')x+(b+b')y }
{ =} { u+v +ax+by+ a'x+b'y }
{ =} { cx+dy + c'x+d'y }
{ =} { (c+c')x +(d+d')y }
{ } { }
} {}{}{.} }{Sei
\mavergleichskette
{\vergleichskette
{ u+ ax+by }
{ = }{ cx+dy }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Durch Multiplikation mit $r$ ergibt sich direkt
\mavergleichskettedisp
{\vergleichskette
{ru+ rax+rby }
{ =} { rcx+rcy }
{ } { }
{ } { }
{ } { }
} {}{}{.} } } {Sei
\mavergleichskette
{\vergleichskette
{u }
{ = }{v+z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{ u+ ax+by }
{ = }{ cx+dy }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{ v+ a'x+b'y }
{ = }{ c'x+d'y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Durch Addition der beiden Gleichungen über Kreuz erhält man
\mavergleichskettedisp
{\vergleichskette
{ v+ cx+dy + a'x+b'y }
{ =} { u+ ax+by + c'x+d'y }
{ =} { v+z+ ax+by + c'x+d'y }
{ } { }
{ } { }
} {}{}{.} Aufgrund der Abziehregel gilt
\mavergleichskettedisp
{\vergleichskette
{ cx+dy + a'x+b'y }
{ =} {z+ ax+by + c'x+d'y }
{ } { }
{ } { }
{ } { }
} {}{}{,} was die Zugehörigkeit
\mathl{z \in I}{} bedeutet. }


}





\inputaufgabeklausurloesung
{3}
{






\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Tred-G.svg} }
\end{center}
\bildtext {} }

\bildlizenz { Tred-G.svg } {} {Dmitry_Dzhus} {Commons} {gemeinfrei} {}

Charakterisiere den Punkt $d$ im skizzierten Graphen mit einem Ausdruck in einer freien Variablen $x$ über dem Symbolalphabet, das neben Variablen aus einem einzigen zweistelligen Relationssymbol $R$ besteht, das im angegebenen Modell durch einen Pfeil wiedergegeben wird.

}
{

Den Ausdruck
\mathdisp {\exists u \exists v \exists w (u \neq v \wedge u \neq w \wedge v \neq w \wedge Rux \wedge Rvx \wedge Rwx)} { }
erfüllen genau die beiden Punkte \mathkor {} {d} {und} {e} {,} da diese für drei Pfeile die Endpunkte sind. Ein Unterschied zwischen \mathkor {} {d} {und} {e} {} ist, dass bei $d$ nur Pfeile von Punkten ankommen, an denen jeweils höchstens ein Pfeil ankommt, während in $e$ ein Pfeil, nämlich der von $d$ ankommt, auf dem mehr als ein Pfeil ankommt. Daher ist
\mathdisp {\exists u \exists v \exists w (u \neq v \wedge u \neq w \wedge v \neq w \wedge Rux \wedge Rvx \wedge Rwx) \wedge \forall y \forall z \forall s (yRx \wedge zRy \wedge sRy \rightarrow z = s)} { . }


}