Kurs:Einführung in die mathematische Logik/2/Test/Klausur

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.

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.

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?

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.

Aufgabe (3 Punkte)

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

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.

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

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

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?

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.

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.

Aufgabe * (3 Punkte)

Zeige

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

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.