Kurs:Einführung in die mathematische Logik/15/Klausur mit Lösungen/kontrolle

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	${}\sum$
Punkte	3	3	2	2	3	5	4	3	0	0	0	2	0	0	0	4	0	31

Aufgabe (3 Punkte)

Lösung

1. Ein Wort über dem Alphabet ${}A$ ist eine beliebige endliche Zeichenkette, wobei sämtliche Einzelzeichen zu ${}A$ gehören.
2. Die Relation ${}\preccurlyeq$ heißt Ordnungsrelation, wenn folgende drei Bedingungen erfüllt sind.
   1. Es ist ${}i\preccurlyeq i$ für alle ${}i\in I$.
   2. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq k$ folgt stets ${}i\preccurlyeq k$.
   3. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq i$ folgt ${}i=j$.
3. Die ${}S$- Ausdrücke werden folgendermaßen als gültig charakterisiert (dabei seien ${}s,t,t_{1},\ldots ,t_{n}$ Terme und ${}\alpha ,\beta$ Ausdrücke).
   1. ${}I\vDash s=t$, wenn ${}I(s)=I(t)$.
   2. ${}I\vDash Rt_{1}\ldots t_{n}$, wenn ${}(I(t_{1}),\ldots ,I(t_{n}))\in R^{M}$.
   3. ${}I\vDash \neg {\left(\alpha \right)}$, wenn nicht ${}I\vDash \alpha$ gilt.
   4. ${}I\vDash {\left(\alpha \right)}\wedge {\left(\beta \right)}$, wenn ${}I\vDash \alpha$ und ${}I\vDash \beta$ gilt.
   5. ${}I\vDash {\left(\alpha \right)}\rightarrow {\left(\beta \right)}$, wenn die Gültigkeit ${}I\vDash \alpha$ die Gültigkeit ${}I\vDash \beta$ impliziert.
   6. ${}I\vDash \exists x\alpha$, wenn es ein ${}m\in M$ gibt mit ${}I{\frac {m}{x}}\vDash \alpha$.
   7. ${}I\vDash \forall x\alpha$, wenn für alle ${}m\in M$ die Beziehung ${}I{\frac {m}{x}}\vDash \alpha$ gilt.
4. Die Abbildung

   $\varphi \colon M\longrightarrow N$

   heißt ${}S$-Homomorphismus, wenn folgende Eigenschaften gelten.

   1. Für jede Konstante ${}c\in S$ ist

      ${}\varphi (c^{M})=c^{N}\,.$

   2. Für jedes ${}n$-stellige Funktionssymbol ${}f\in S$ ist

      ${}\varphi (f^{M}(m_{1},\ldots ,m_{n}))=f^{N}(\varphi (m_{1}),\ldots ,\varphi (m_{n}))\,$

      für alle ${}m_{1},\ldots ,m_{n}\in M$.

   3. Für jedes ${}n$-stellige Relationsymbol ${}R\in S$ impliziert die Gültigkeit von

      $R^{M}(m_{1},\ldots ,m_{n})$

      die Gültigkeit von

      $R^{N}(\varphi (m_{1}),\ldots ,\varphi (m_{n})).$

5. Die Multiplikation mit ${}n$ ist diejenige aufgrund von Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)) eindeutig bestimmte Abbildung

   $\mu _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \mu _{n}(k),$

   für die

   $\mu _{n}(0)=0{\text{ und }}\mu _{n}(k')=\mu _{n}(k)+n{\text{ für alle }}k\in \mathbb {N}$

   gilt.

6. Man sagt, dass ein modallogischer Ausdruck ${}\alpha$ aus dem ${}K$- System ableitbar ist, wenn sich ${}\alpha$ aus aussagenlogischen Tautologien und aus Instanzen des ${}K$- Axioms mit Hilfe des Modus ponens oder der Nezessisierungsregel ergibt.

Aufgabe (3 Punkte)

Lösung

1. Die diophantische Gleichung

   ${}x^{n}+y^{n}=z^{n}\,$

   besitzt für kein ${}n\geq 3$

   eine ganzzahlige nichttriviale Lösung.
2. Es sei ${}S$ ein Symbolalphabet und ${}\alpha \in L^{S}$ ein ${}S$-Ausdruck. Dann ist ${}\alpha$ genau dann eine ableitbare Tautologie, wenn ${}\alpha$ allgemeingültig ist.
3. Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube. Dann ist ${}\Gamma ^{\vdash }$ unvollständig.

Aufgabe (2 Punkte)

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?

Lösung

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.

Aufgabe (2 Punkte)

Erläutere das Beweisprinzip der vollständigen Induktion.

Lösung

Mit dem Beweisprinzip der vollständigen Induktion werden Aussagen ${}A(n)$ bewiesen, die von den natürlichen Zahlen ${}n\in \mathbb {N}$ abhängen. Man beweist zuerst die Aussage ${}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 ${}n\in \mathbb {N}$.

Aufgabe (3 Punkte)

Es sei ${}A$ ein Alphabet mit ${}3$ Symbolen. Wie viele Wörter über ${}A$ der Länge ${}5$ gibt es, wenn man nicht zwischen den Leserichtungen unterscheiden kann?

Lösung

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 ${}3^{3}=27$ Möglichkeiten. Somit gibt es

${}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

${}108+27=135\,$

Worttypen, wenn man die Leserichtung nicht unterscheiden kann.

Aufgabe (5 Punkte)

Es sei ${}n\in \mathbb {N} _{+}$. Man gebe ein Beispiel für eine aussagenlogische widersprüchliche Ausdrucksmenge

${}\Gamma =\{\alpha _{1},\alpha _{2},\ldots ,\alpha _{n}\}\,$

derart, dass jede echte Teilmenge davon widerspruchsfrei ist.

Lösung

Bei ${}n=1$ kann man für ${}\alpha$ jede widersprüchliche Aussage, beispielsweise ${}p\wedge \neg p$ nehmen. Es sei also ${}n\geq 2$. Es seien ${}p_{1},p_{2},\ldots ,p_{n-1}$ (verschiedene) Aussagenvariablen. Wir setzen

${}\alpha _{1}=p_{1}\,,$

${}\alpha _{i}=p_{i-1}\rightarrow p_{i}\,$

für ${}2\leq i\leq n-1$ und

${}\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

$\Gamma \vdash \neg p_{1}$

erhält, was ein Widerspruch zu ${}p_{1}\in \Gamma$ ist. Es sei nun

${}\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 ${}p_{j}$ mit ${}j\leq i$ als wahr und jede Variable ${}p_{j}$ mit ${}j>i$ als falsch belegt wird, die Menge ${}\Delta _{i}$, da für die ${}\alpha _{j}$ mit ${}j<i$ Vorder-und Nachsatz wahr belegt sind und da für die ${}\alpha _{j}$ mit ${}j>i$ der Vordersatz falsch belegt ist.

Aufgabe (4 Punkte)

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Zeige, dass für jedes ${}\alpha \in L^{V}$ entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$ gilt.

Lösung

Wegen der Widerspruchsfreiheit können nicht sowohl ${}\alpha$ als auch ${}\neg \alpha$ zu ${}\Gamma$ gehören. Wenn weder ${}\alpha$ noch ${}\neg \alpha$ zu ${}\Gamma$ gehören, so ist entweder ${}\Gamma \cup \{\alpha \}$ oder ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck ${}\beta$ sowohl

$\Gamma \cup \{\alpha \}\vdash \beta$

als auch

$\Gamma \cup \{\neg \alpha \}\vdash \beta$

gelten. Dies bedeutet nach Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021))

$\Gamma \vdash \alpha \rightarrow \beta$

und

$\Gamma \vdash \neg \alpha \rightarrow \beta ,$

woraus aufgrund der Fallunterscheidungsregel

$\Gamma \vdash \beta$

folgt. Dies bedeutet aber, dass ${}\Gamma$ widersprüchlich ist.

Aufgabe (3 Punkte)

Man erläutere durch Beispiele, dass der Aufbau der Prädikatenlogik nicht immer der mathematischen Intuition entspricht.

Lösung Prädikatenlogik/Intuitiv oder nicht/Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 (1+1) Punkte)

Wir betrachten das Symbolalphabet ${}S$, das neben Variablen aus einem einzigen zweistelligen Relationssymbol ${}R$ besteht, wobei in der abgebildeten Punktemenge das Relationssymbol ${}R$ als „(echt) rechts von“ interpretiert wird. Für zwei Punkte ${}P,Q$ bedeutet also ${}RPQ$, dass sich ${}P$ rechts von ${}Q$ befindet.

1. Welche(r) Punkt(e) erfüllt(en)

   $\exists y(Ryx\wedge \forall z(Rzx\rightarrow y=z)?$

2. Charakterisiere den Punkt ${}p_{0}$ mit einem ${}S$- Ausdruck in der einen freien Variablen ${}x$.

Lösung

1. 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}$.
2. Der Punkt ${}p_{0}$ besitzt genau drei Punkte rechts von ihm. Also ist

   $\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.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Zeige, dass ein gerichteter Graph genau dann symmetrisch ist, wenn für jede Teilmenge ${}T\subseteq M$ die Beziehung

${}T\subseteq M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}\,$

gilt.

Lösung

Wir zeigen, dass die Negationen der beiden Eigenschaften zueinander äquivalent sind.

Es sei zuerst die Relation nicht symmetrisch. Dann gibt es ${}x,y$ mit ${}xRy$, aber ${}yRx$ gilt nicht. Dann ist ${}y$ kein Vorgänger von ${}x$ und daher ist ${}y\in M\setminus \operatorname {Vorg} {\left(\{x\}\right)}$. Es ist somit ${}x\in \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(\{x\}\right)}\right)}$ und also ${}x\notin M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(\{x\}\right)}\right)}$. Daher gilt die Vorgängereigenschaft für

${}T=\{x\}\,$

nicht.

Es sei nun die Vorgängereigenschaft nicht erfüllt, es gebe also eine Teilmenge ${}T\subseteq M$ mit

${}T\not \subseteq M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}\,.$

Dann gibt es ein ${}x\in T$ mit ${}x\in \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}$. Dies bedeutet, dass es ein ${}y\in M\setminus \operatorname {Vorg} {\left(T\right)}$ mit ${}xRy$ gibt. Wegen ${}y\notin \operatorname {Vorg} {\left(T\right)}$ ist insbesondere nicht ${}yRx$, also ist die Relation nicht symmetrisch.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung