Kurs:Einführung in die mathematische Logik/2/Test/Klausur mit Lösungen

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	${}\sum$
Punkte	3	3	4	3	3	3	1	4	4	12	5	3	4	12	64

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Mersennesche Primzahl.
2. Eine widersprüchliche Ausdrucksmenge ${}\Gamma \subseteq L^{V}$ in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$.
3. Die Produktmenge aus zwei Mengen ${}L$ und ${}M$.
4. Die Bestandteile einer Grundtermmenge.
5. Ein allgemeingültiger prädikatenlogischer Ausdruck ${}\alpha \in L^{S}$.
6. Die Ableitbarkeit eines Ausdrucks ${}\alpha \in L^{S}$ im prädikatenlogischen Kalkül.

Lösung

1. Eine Primzahl der Form ${}2^{n}-1$ heißt Mersennesche Primzahl.
2. Die Ausdrucksmenge ${}\Gamma$ heißt widersprüchlich, wenn es einen Ausdruck ${}\alpha \in L^{V}$ mit ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \neg \alpha$ gibt.
3. Man nennt die Menge

   ${}L\times M={\left\{(x,y)\mid x\in L,\,y\in M\right\}}\,$

   die Produktmenge der Mengen ${}L$ und ${}M$.

4. Die Bestandteile einer Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.
   1. eine Variablenmenge ${}V$,
   2. eine Konstantenmenge ${}K$,
   3. zu jedem ${}n\in \mathbb {N} _{+}$ eine Menge ${}F_{n}$ von Funktionssymbolen.
5. Man nennt ${}\alpha$ allgemeingültig, wenn er in jeder ${}S$- Interpretation ${}I$ gilt.
6. Der Ausdruck ${}\alpha$ heißt ableitbar, wenn er sich aus den Grundtautologien, also
   • den aussagenlogischen syntaktischen Tautologien,
   • den Gleichheitsaxiomen,
   • der Existenzeinführung im Sukzedens,

durch sukzessive Anwendung der Ableitungsregeln Modus ponens und der Existenzeinführung im Antezedens erhalten lässt.

 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Zorn.
2. Der Satz über die Division mit Rest in einem Peano-Halbring.
3. Der Endlichkeitssatz für die Prädikatenlogik.

Lösung

1. Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge mit der Eigenschaft, dass jede total geordnete Teilmenge ${}J\subseteq I$ eine obere Schranke in ${}I$ besitzt. Dann gibt es in ${}I$ maximale Elemente.
2. Es sei ${}M$ ein Peano-Halbring und ${}d\geq 1$. Dann gibt es zu jedem ${}m\in M$ eindeutig bestimmte ${}q,r\in M$ mit ${}r$, ${}r<d$, und mit

   ${}m=qd+r\,.$

3. Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$-Ausdrücken und ${}\alpha$ ein weiterer ${}S$-Ausdruck. Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn es eine endliche Teilmenge ${}\Gamma _{e}\subseteq \Gamma$ gibt mit ${}\Gamma _{e}\vDash \alpha$.

 

Aufgabe * (4 (2+1+1) Punkte)

Folgende Aussagen seien bekannt.

1. Der frühe Vogel fängt den Wurm.
2. Doro wird nicht von Lilly gefangen.
3. Lilly ist ein Vogel oder ein Igel.
4. Für Igel ist 5 Uhr am Morgen spät.
5. Doro ist ein Wurm.
6. Für Vögel ist 5 Uhr am Morgen früh.
7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

1. Ist Lilly ein Vogel oder ein Igel?
2. Ist sie ein frühes oder ein spätes Tier?
3. Fängt der späte Igel den Wurm?

Lösung

1. Lilly ist ein Igel. Beweis durch Widerspruch. Nehmen wir an, dass Lilly kein Igel ist. Dann ist sie nach (3) ein Vogel. Da Lilly nach (7) um ${}5$ Uhr schon unterwegs ist, ist nach (6) Lilly ein früher Vogel. Nach (1) fängt Lilly also den Wurm. Da nach (5) Doro ein Wurm ist, wird er von Lilly gefangen im Widerspruch zu (2).
2. Nach dem ersten Teil ist Lilly ein Igel, und nach (7) steht sie um 5 Uhr auf. Dies ist nach (4) für Igel spät, Lilly ist also ein später Igel und somit ein spätes Tier.
3. Da nach dem zweiten Teil Lilly ein später Igel ist und sie nach (2) Doro, die nach (5) ein Wurm ist, nicht fängt, fängt der späte Igel im Allgemeinen nicht den Wurm.

 

Aufgabe * (3 Punkte)

Bei einem Zwei-Personen-Regel-Spiel (wie Schach) spielen zwei Personen (${}A$ und ${}B$) nach gewissen Regeln gegeneinander. Die Personen ziehen abwechselnd. Es ist klar, was eine Mattgewinnstellung für ${}A$ ist, da ist ${}A$ am Zug und kann ${}B$ schlagen und das Spiel ist beendet. Definiere rekursiv, was innerhalb der Menge ${}S$ aller Stellungen eine Gewinnstellung für ${}A$ (mit ${}A$ am Zug) ist.

Lösung

Wir definieren

${}G_{0}={\text{jede Mattstellung für }}A\,$

und rekursiv

${}G_{n}:={\left\{s\in S\mid {\text{ es gibt einen Zug für }}A{\text{ derart, dass für alle Züge von }}B{\text{ die entstehende Stellung zu }}G_{n-1}{\text{ gehört}}\right\}}\,.$

Eine Gewinnstellung ist dann

${}G=\bigcup _{n\in \mathbb {N} }G_{n}\,.$

 

Aufgabe (3 Punkte)

Erläutere das Konzept der Wohldefiniertheit anhand eines typischen Beispiels.

Lösung

Wohldefiniertheit/Typisches Beispiel/Aufgabe/Lösung

 

Aufgabe * (3 Punkte)

Beweise durch Induktion über den rekursiven Aufbau der Sprache ${}L^{V}$, dass in jeder Aussage ${}\alpha \in L^{V}$ die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.

Lösung

Wenn ${}p$ eine Aussagenvariable ist, so kommt darin weder eine linke noch eine rechte Klammer vor und die Anzahl stimmt überein. Zum Beweis der Rekursionsschritte sei zunächst ${}\alpha =\neg (\beta )$ und vorausgesetzt, dass die Anzahl der linken und die Anzahl der rechten Klammern in ${}\beta$ übereinstimmen. Dann besitzt ${}\alpha$ sowohl eine linke als auch eine rechte Klammer mehr als ${}\beta$, so dass die Anzahlen wieder übereinstimmen. Es sei nun ${}\alpha =(\beta )\star (\gamma )$ mit ${}\star =\wedge ,\vee ,\rightarrow ,\leftrightarrow$ und sei vorausgesetzt, dass ${}\beta$ ${}k$ linke und auch rechte Klammern und ${}\gamma$ ${}\ell$ linke und auch rechte Klammern besitzt. Dann besitzt ${}\alpha$ ${}k+l+2$ linke und auch rechte Klammern.

 

Aufgabe * (1 Punkt)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

${}p$ ${}q$ ${}?$ w w w w f f f w w f f f

Lösung

${}q$.

 

Aufgabe * (4 Punkte)

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

Lösung

Die Voraussetzung bedeutet, dass es Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{m},\beta _{1},\ldots ,\beta _{n}\in \Gamma$ mit

$\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{m}\rightarrow {\left(\alpha \rightarrow \beta \right)}$

und mit

$\vdash \beta _{1}\wedge \ldots \wedge \beta _{n}\rightarrow {\left(\beta \rightarrow \gamma \right)}$

gibt. Daraus ergibt sich mit Hilfe (der Regelversion) von Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021))  (2)

$\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{m}\wedge \beta _{1}\wedge \ldots \wedge \beta _{n}\rightarrow {\left(\alpha \rightarrow \beta \right)}\wedge {\left(\beta \rightarrow \gamma \right)}.$

Es gilt die Tautologie (Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (2),)

$\vdash {\left(\alpha \rightarrow \beta \right)}\wedge {\left(\beta \rightarrow \gamma \right)}\rightarrow {\left(\alpha \rightarrow \gamma \right)}.$

Aus der Regelversion dieses Axioms ergibt sich

$\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{m}\wedge \beta _{1}\wedge \ldots \wedge \beta _{n}\rightarrow {\left(\alpha \rightarrow \gamma \right)}.$

Dies bedeutet ${}\Gamma \vdash \alpha \rightarrow \gamma$.

 

Aufgabe * (4 (2+2) Punkte)

Es sei ${}G$ eine unendliche Menge und ${}M\subset {\mathfrak {P}}\,(G)$ die Menge, die aus sämtlichen endlichen Teilmengen von ${}G$ besteht.

1. Ist ${}(M,\subseteq )$ induktiv geordnet?
2. Besitzt ${}M$ maximale Elemente?

Lösung

1. Da ${}G$ unendlich ist, gibt es darin insbesondere verschiedene Elemente ${}x_{n}$ zu ${}n\in \mathbb {N} _{+}$. Wir betrachten die endlichen Teilmengen

   ${}G_{n}:=\{x_{1},x_{2},\ldots ,x_{n}\}\,.$

   Diese gehören zu ${}M$ und es liegen die (echten) Inklusionen ${}G_{n}\subset G_{n+1}$ vor, d.h. diese Mengen bilden eine Kette. Eine obere Schranke für diese Mengen muss aber alle Elemente ${}x_{n}$ enthalten, also unendlich sein, und eine solche gibt es nicht in ${}M$.

2. Es gibt in ${}M$ keine maximalen Elemente. Ein Element ${}N\in M$ ist eine endliche Menge von ${}G$. Da ${}G$ unendlich ist, gibt es ein Element ${}x\in G$ mit ${}x\notin N$. Dann ist ${}N\cup \{x\}$ eine ebenfalls endliche Teilmenge von ${}G$ (gehört also zu ${}M$), die ${}N$ echt umfasst, so dass ${}N$ nicht maximal ist.

 

Aufgabe * (12 (1+1+4+2+4) Punkte)

Es sei ${}G$ ein dreistelliges Relationssymbol und ${}L$ die zugehörige prädikatenlogische Sprache. Es sei ${}I$ die Interpretation, bei der die Grundmenge die euklidische Ebene ist und ${}G$ durch die dreistellige Relation interpretiert wird, bei der ${}G(A,B,C)$ zutrifft, wenn die Punkte ${}A,B,C$ auf einer Geraden liegen.

1. Zeige ${}I\vDash Gxyz\leftrightarrow Gyxz$.
2. Zeige, dass im Allgemeinen nicht ${}I\vDash \forall x\forall y\forall z{\left(Gxyz\rightarrow Gxyu\right)}$ gelten muss.
3. Es sei ${}\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 ${}\Gamma \vdash Gxyz\leftrightarrow Gyzx$.
4. Zeige, dass der Ausdruck ${}Gxyz\wedge Gxyu$ bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen ${}x,y,z,u$ belegenden Punkte auf einer Geraden liegen.
5. 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.

Lösung

1. Die Eigenschaft, ob drei Punkte auf einer Geraden liegen, hängt nicht von der Reihenfolge der Punkte ab.
2. Es seien ${}A,B$ verschiedene Punkte der Ebene, ${}C$ ein beliebiger Punkt auf der durch ${}A,B$ definierten Geraden und ${}D$ ein Punkt, der nicht auf dieser Geraden liegt. Dann ist der Vordersatz erfüllt, aber nicht der Nachsatz, und daher gilt die Implikation bei dieser Interpretation nicht.
3. Aufgrund der Alleinführung im Antezedens gilt für beliebige Variablen ${}u,v,w$ die Ableitbarkeit

   $\vdash \forall x\forall y\forall z{\left(Gxyz\leftrightarrow Gyxz\right)}\rightarrow {\left(Guvw\leftrightarrow Gvuw\right)}.$

   Daher gilt mit Modus ponens

   $\Gamma \vdash Guvw\leftrightarrow Gvuw$

   für beliebige Variablen. Insbesondere gilt

   $\Gamma \vdash Gxyz\leftrightarrow Gyxz.$

   Ebenso kann man auf

   $\Gamma \vdash Gyxz\leftrightarrow Gyzx$

   schließen. Die Transitivität der Äquivalenz liefert

   $\Gamma \vdash Gxyz\leftrightarrow Gyzx$

4. Wenn ${}x$ und ${}y$ durch den gleichen Punkt ${}A$ interpretiert werden und ${}z$ durch einen Punkt ${}C$ und ${}u$ durch einen Punkt ${}D$, derart, dass diese Punkte nicht auf einer Geraden liegen, so liegen dennoch ${}A,C$ und ${}A,D$ auf einer Geraden. Bei einer solchen Belegung sind ${}Gxyz$ und ${}Gxyu$ wahr, ohne dass alle Punkte auf einer Geraden liegen.
5. Man nimmt ${}\alpha =Gxyz\wedge Gxyu\wedge Gyzu$. Die Variablen seien durch die Punkte ${}A,B,C,D$ belegt. Wenn diese Punkte auf einer gemeinsamen Geraden liegen, so liegen insbesondere je drei von ihnen auf einer (nämlich dieser) Geraden und daher gilt ${}\alpha$ bei dieser Belegung. Zum Beweis der Umkehrung sei ${}I\vDash \alpha$. Dies bedeutet, dass sowohl ${}A,B,C$ als auch ${}A,B,D$ als auch ${}B,C,D$ jeweils auf einer Geraden liegen. Wenn unter den Punkten ${}A,B,C,D$ nur zwei verschiedene Punkte vorkommen, so liegen alle Punkte auf einer Geraden. Wir können uns also auf den Fall beschränken, wo maximal zwei Punkte identisch sind. Wenn ${}A\neq B$ ist, so definiert dies eine eindeutige Gerade, und auf dieser Geraden müssen wegen der Gültigkeit von ${}Gxyz$ bzw. ${}Gxyu$ sowohl ${}C$ als auch ${}D$ liegen. In diesem Fall liegen alle Punkte auf einer Geraden. Es sei nun ${}A=B$. Wegen ${}Gyzu$ liegen ${}B=A,C,D$ auf einer Geraden.

 

Aufgabe * (5 (2+3) Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben.

1. Zeige, dass die Substitution ${}{\frac {x}{x}}$ für die Terme die Identität ist.
2. Zeige, dass die Substitution ${}{\frac {x}{x}}$ für die Ausdrücke die Identität ist.

Lösung

1. Wir beweisen die Aussage durch Induktion über den Aufbau der Terme. Für Variablen ist bei ${}y\neq x$ direkt ${}y{\frac {x}{x}}=y$ und ferner ${}x{\frac {x}{x}}=x$. Konstanten bleiben bei jeder Substitution unverändert. Für ein ${}n$-stelliges Funktionssymbol ${}f$ und Terme ${}t_{1},\ldots ,t_{n}$ ist

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

2. 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 ${}\forall y\beta$ mit ${}y\neq x$ kommt ${}y$ nicht im substituierenden Term vor, und daher ist ${}v=y$ und

   ${}(\forall y\beta ){\frac {x}{x}}=\forall y(\beta {\frac {y}{y}})=\forall y\beta \,$

   nach Induktionsvoraussetzung. Bei ${}\forall x\beta$ ist ${}x$ nicht frei in ${}\beta$ und somit ist die relevante Termmenge leer und ${}v=x$, also

   ${}(\forall x\beta ){\frac {x}{x}}=\forall x(\beta {\frac {x}{x}})=\forall x\beta \,$

   nach Induktionsvoraussetzung.

 

Aufgabe * (3 Punkte)

Zeige

$\vdash \forall x\alpha \wedge \forall x\beta \rightarrow \forall x{\left(\alpha \wedge \beta \right)}.$

Lösung

Die Alleinführung im Antezedens ergibt

$\vdash \forall x\alpha \rightarrow \alpha$

und

$\vdash \forall x\beta \rightarrow \beta$

und daraus zusammen mit Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021))  (2)

$\vdash \forall x\alpha \wedge \forall x\beta \rightarrow \alpha \wedge \beta .$

Die Variable ${}x$ ist sowohl vorne als auch in ${}\forall x{\left(\alpha \wedge \beta \right)}$ gebunden. Daher ergibt die Alleinführung im Sukzedens

$\vdash \forall x\alpha \wedge \forall x\beta \rightarrow \forall x{\left(\alpha \wedge \beta \right)}.$

 

Aufgabe * (4 Punkte)

Beweise den Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.

Lösung

Aufgrund von Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)), angewendet auf ${}N_{1}$ und die Nachfolgerabbildung auf ${}N_{2}$, gibt es genau eine Abbildung

$\varphi \colon N_{1}\longrightarrow N_{2}$

mit den angegebenen Eigenschaften. Wenn man die Rollen vertauscht, so erhält man eine eindeutige Abbildung

$\psi \colon N_{2}\longrightarrow N_{1}$

mit den gleichen Eigenschaften. Wir betrachten nun die Verknüpfung

$\psi \circ \varphi \colon N_{1}\longrightarrow N_{1}.$

Diese erfüllt ebenfalls diese Eigenschaften. Da aber die Identität auf ${}N_{1}$ auch diese Eigenschaften erfüllt, folgt aus der Eindeutigkeitsaussage aus Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)), dass ${}\psi \circ \varphi =\operatorname {Id} _{N_{1}}$ ist. Ebenso ist ${}\varphi \circ \psi =\operatorname {Id} _{N_{2}}$ und somit sind ${}\varphi$ und ${}\psi$ invers zueinander.

 

Aufgabe * (12 (2+3+1+2+2+2) Punkte)

Es sei

${}M=\{0\}\cup \mathbb {Q} _{\geq 1}\,.$

1. Zeige, dass ${}M$ ein kommutativer Halbring ist.
2. Zeige, dass in ${}M$ die Relationen

   $a{\text{ teilt }}b{\text{ oder }}a=0$

   und

   $a\leq b{\text{ oder }}b=0$

   zueinander äquivalent sind.

3. Zeige, dass ${}{\frac {6}{5}}$ nicht irreduzibel in ${}M$ ist.
4. Zeige, dass es in ${}M$ keine irreduziblen Elemente gibt.
5. Es sei ${}\alpha$ die Aussage

   $x=0\vee \exists y(x=y+1).$

   Zeige, dass in ${}M$ die Aussage

   $\alpha {\frac {0}{x}}\wedge {\left(\alpha \rightarrow \alpha {\frac {x+1}{x}}\right)}$

   wahr ist.

6. Zeige, dass ${}M$ kein Peano-Halbring ist.

Lösung

1. Es ist lediglich zu zeigen, dass ${}M$ unter der Addition und der Multiplikation abgeschlossen sind. Dies ist für die Addition mit ${}0$ und der Multiplikation mit ${}0$ klar. Ferner ist die Summe (bzw. das Produkt) von zwei rationalen Zahlen, die beide ${}\geq 1$ sind, selbst wieder ${}\geq 1$.
2. Wenn ${}a=0$ ist, so ist wegen ${}0\leq b$ automatisch auch die rechte Seite erfüllt, und wenn ${}b=0$ ist, so ist wegen

   ${}a0=0\,$

   auch die linke Seite erfüllt. Wir können also und auf den Fall ${}a,b\neq 0$ beschränken. Wenn ${}a$ das Element ${}b$ teilt, so bedeutet dies, dass es ein ${}x\in M$ mit

   ${}ax=b\,$

   gibt. Dies bedeutet einfach, dass der in ${}\mathbb {Q}$ genommene Quoient ${}{\frac {b}{a}}$ zu ${}M$ gehört, also ${}\geq 1$ ist. Doch dies ist äquivalent zu ${}b\geq a$.

3. Es ist

   ${}{\frac {6}{5}}={\frac {12}{10}}={\frac {12}{11}}\cdot {\frac {11}{10}}\,$

   eine Darstellung in Faktoren, die beide keine Einheit sind.

4. Die ${}0$ und die (einzige) Einheit ${}1$ sind nach Definition nicht irreduzibel. Für ${}a,b\in \mathbb {N} _{+}$ mit ${}{\frac {b}{a}}>1$ ist

   ${}{\frac {b}{a}}={\frac {2b}{2a}}={\frac {2b-1}{2a}}\cdot {\frac {2b}{2b-1}}\,$

   und wegen ${}b>a$ ist auch

   ${}2b-1>2a\,,$

   also gehören die beiden Faktoren zu ${}M$.

5. Der erste Teil der Konjunktion, also ${}\alpha {\frac {0}{x}}$, ist unmittelbar wegen des ersten Teils der Disjunktion wahr. Es sei also ${}\alpha$ wahr für ein bestimmtes ${}x$. Der Nachfolger davon, also ${}x+1$, steht bereits in der Form des zweiten Teils der Disjunktion da.
6. Wir betrachten das Induktionsaxiom für die Aussage aus Teil (5). Die Voraussetzungen, also Induktionsanfang und Induktionsschritt, gelten wie in Teil (5) gezeigt. Hingegen gilt die Aussage ${}\alpha$ nicht für alle ${}x\in M$, beispielsweise gilt sie für ${}x={\frac {3}{2}}$ nicht.