Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 7

Übungsaufgaben

Aufgabe *

Wir betrachten den Satz „Diese Vorlesung versteht keine Sau“. Negiere diesen Satz durch eine Existenzaussage.

Aufgabe *

Negiere die Aussage „Martina findet alle Jungs im Kurs außer Markus zuckersüß“ durch eine Aussage, in der eine Existenzaussage und eine Oder-Verknüpfung vorkommen.

Aufgabe

Man formalisiere die folgenden Aussagen, indem man geeignete Prädikate erklärt. Man gebe die Negation der Aussagen (umgangssprachlich und formal) an.

1. Alle Vögel sind schon da.
2. Alle Wege führen nach Rom.
3. Faulheit ist aller Laster Anfang.
4. Alle Menschen werden Brüder, wo dein sanfter Flügel weilt.
5. Wem der große Wurf gelungen, eines Freundes Freund zu sein, wer ein holdes Weib errungen, mische seinen Jubel ein!
6. Freude trinken alle Wesen an den Brüsten der Natur.
7. Alle Macht geht vom Volk aus.
8. Alle Achtung.
9. Alle Neune.

Aufgabe

Es sei ${}S$ das erststufige Symbolalphabet, das aus den Variablen ${}x,y,z$, den Konstanten ${}0,c$, dem einstelligen Funktionssymbol ${}F$, den zweistelligen Funktionssymbolen ${}\alpha ,\beta$ und dem zweistelligen Relationssymbol ${}R$ bestehe. Überprüfe, ob die folgenden Wörter zur Sprache ${}L^{S}$ (bei korrekter Klammerung) gehören.

1. ${}Fx$,
2. ${}\forall x{\left(Fx=c\right)}$,
3. ${}x=w$,
4. ${}{\left(Fx=c\right)}\rightarrow {\left(\alpha \right)}$,
5. ${}{\left(Fx=c\right)}\rightarrow {\left(\neg {\left(\exists y{\left(Fx=c\right)}\right)}\right)}$,
6. ${}R0$,
7. ${}{\left(\forall z{\left(R0x\right)}\right)}\wedge {\left(\neg {\left(\beta \alpha yzy=Rcz\right)}\right)}$,
8. ${}{\left(\forall z{\left(R0x\right)}\right)}\wedge {\left(\neg {\left(\beta \alpha yzy=\beta cz\right)}\right)}$.

Aufgabe

Bestimme die kleinsten Symbolmengen, mit denen die folgenden Ausdrücke formulierbar sind.

1. ${}\exists y{\left(fx=y\right)}$,
2. ${}\forall x{\left(fx=gyc\right)}\wedge \exists z{\left(Rzxy\right)}$,
3. ${}\forall x\exists ySxhuy$.

Aufgabe

Man gebe für die folgenden Teilmengen der natürlichen Zahlen quantorenlogische Beschreibungen.

1. Die Menge der geraden Zahlen,
2. Die Menge der Zahlen, die durch vier teilbar sind,
3. Die Menge der ungeraden Zahlen,
4. Die Menge der Quadratzahlen,
5. Die Menge der Primzahlen,
6. Die Menge der Zahlen, die als Summe von drei Quadratzahlen geschrieben werden können.

In der folgenden Aufgabe geht es nicht um die Wahrheit der Aussagen, sondern nur um die quantorenlogische Formulierung. Man darf und soll sich natürlich trotzdem Gedanken über die Gültigkeit machen.

Aufgabe

Formuliere die folgenden Aussagen über die natürlichen Zahlen ${}\mathbb {N} =\{0,1,2,3,\ldots \}$ allein mittels Gleichheit, Addition, Multiplikation und unter Verwendung von aussagenlogischen Junktoren und Quantoren.

1. ${}5\geq 3$.
2. ${}5>3$.
3. ${}5\leq 3$.
4. ${}7$ ist eine Primzahl.
5. ${}8$ ist eine Primzahl.
6. ${}8$ ist keine Primzahl.
7. Jede natürliche Zahl besitzt mindestens einen Primfaktor.
8. Jede natürliche Zahl größer gleich ${}2$ besitzt mindestens einen Primfaktor.
9. Wenn eine Primzahl ein Produkt teilt, so teilt sie auch mindestens einen der Faktoren.
10. Es gibt Zahlen, die ein Produkt teilen, obwohl sie keinen der Faktoren teilen.

Aufgabe

Formuliere die folgenden Beziehungen (ein- oder mehrstellige Prädikate) innerhalb der natürlichen Zahlen ${}\mathbb {N} =\{0,1,2,3,\ldots \}$ allein mittels Gleichheit, Addition, Multiplikation und unter Verwendung von aussagenlogischen Junktoren und Quantoren.

1. ${}x\geq y$.
2. ${}x>y$.
3. ${}x$ teilt ${}y$.
4. ${}x$ teilt nicht ${}y$.
5. ${}x$ ist eine Quadratzahl.
6. ${}x$ ist eine Primzahl.
7. ${}x$ ist keine Primzahl.
8. ${}x$ ist das Produkt von genau zwei verschiedenen Primzahlen.
9. ${}x$ wird von einer Primzahl geteilt.

Aufgabe

Formalisiere die folgenden mengentheoretischen Fassungen einiger aristotelischer Syllogismen in der Prädikatenlogik erster Stufe.

1. Modus Barbara: Aus ${}B\subseteq A$ und ${}C\subseteq B$ folgt ${}C\subseteq A$.
2. Modus Celarent: Aus ${}B\cap A=\emptyset$ und ${}C\subseteq B$ folgt ${}C\cap A=\emptyset$.
3. Modus Darii: Aus ${}B\subseteq A$ und ${}C\cap B\neq \emptyset$ folgt ${}C\cap A\neq \emptyset$.
4. Modus Ferio: Aus ${}B\cap A=\emptyset$ und ${}C\cap B\neq \emptyset$ folgt ${}C\not \subseteq A$.
5. Modus Baroco: Aus ${}B\subseteq A$ und ${}B\not \subseteq C$ folgt ${}A\not \subseteq C$.

Aufgabe

Finde Parallelen zwischen Aussagen- und Quantorenlogik einerseits und Mengentheorie andererseits.

Aufgabe

Man mache sich den Unterschied zwischen den Aussagenvariablen in der Sprache der Aussagenlogik und den Variablen in der Sprache der Prädikatenlogik klar.

Aufgabe

Formalisiere in der arithmetischen Sprache (mit ${}+$ und ${}\cdot$) die folgenden (wahren) Aussagen.

1. Wenn ${}x\geq y$ und ${}y\geq z$, so ist ${}x\geq z$.
2. Wenn ${}x\geq y$ und ${}y\geq x$ gilt, so ist ${}x=y$.
3. Für jede natürliche Zahl gibt es eine größere natürliche Zahl.
4. Eine natürliche Zahl, für die es keine kleinere natürliche Zahl gibt, ist gleich ${}0$.

Aufgabe

Formalisiere in der arithmetischen Sprache die folgenden wahren Aussagen.

1. Es gibt unendlich viele Primzahlen.
2. Jede natürliche Zahl ${}\geq 2$ wird von einer Primzahl geteilt.

Wie sieht es mit der Aussage aus, dass jede natürliche Zahl eine Primfaktorzerlegung besitzt?

Aufgabe

Erstelle einen prädikatenlogischen Ausdruck ${}\alpha$, der in einer Struktur genau dann gilt, wenn die Grundmenge der Struktur genau ${}7$ Elemente besitzt.

Aufgabe

Das Symbolalphabet ${}S$ bestehe neben Variablen aus dem einzigen einstelligen Funktionssymbol ${}f$. Finde für die folgenden Ausdrücke aus ${}L^{S}$ jeweils Interpretationen, in denen der Ausdruck gilt, und Interpretationen, in denen er nicht gilt.

1. ${}\forall x(x=fffx)$.
2. ${}\exists x(x=fffx)$.
3. ${}\forall x(fx=fffx)$.
4. ${}\forall x(x=ffx)\wedge \forall x(\neg (x=fx))$.

Aufgabe

Formalisiere mit dem Symbolalphabet, das neben Variablen aus ${}\{f,g\}$ besteht, wobei ${}f,g$ einstellige Funktionssymbole sind, die Aussage, dass die Hintereinanderschaltung von injektiven Abbildungen auf einer Menge wieder injektiv ist.

Aufgabe *

Es sei ein Symbolalphabet ${}S$ erster Stufe mit der Variablenmenge

${}V=\{x,y,z,w\}\,$

gegeben und eine ${}S$- Interpretation ${}I$ in der Menge ${}\mathbb {R}$ mit

$I(x)=5,\,I(y)=\pi ,\,I(z)=-{\sqrt {2}},\,I(w)=-3.$

Bestimme die Werte von ${}x,y,z,w$ bei der Interpretation ${}J:=I{\frac {e,-{\sqrt {2}},{\frac {4}{7}},I(x)}{x,z,x,y}}$ auf ${}V$.

Aufgabe *

Es sei ${}K=\{E,m,c\}$ eine Konstantenmenge, ${}Q$ ein einstelliges Funktionssymbol und ${}P$ ein zweistelliges Funktionssymbol. Es sei ${}I$ die Interpretation mit ${}M=\mathbb {N}$ als Grundmenge, bei der ${}Q$ als Quadrieren, ${}P$ als Multiplikation und die Konstanten als ${}I(E)=9000000000$ ${}I(m)=1$ und ${}I(c)=300000$ interpretiert wird. Ist der Ausdruck

$E=PmQc$

unter dieser Interpretation gültig?

Aufgabe

Es sei das arithmetische Alphabet ${}\{0,1,+,\cdot \}$ zusammen mit der Variablenmenge ${}\{x,y\}$ gegeben. Interpretiere den Term

$((0+1)+x)\cdot (1+(y+1))$

unter den folgenden Interpretationen.

1. ${}M=\mathbb {N}$ mit der Standardinterpretation und der Variablenbelegung ${}I(x)=5$ und ${}I(y)=3$.
2. ${}M=\operatorname {Mat} _{2}(\mathbb {R} )$ mit der Standardinterpretation

   $I(0)={\begin{pmatrix}0&0\\0&0\end{pmatrix}},\,I(1)={\begin{pmatrix}1&0\\0&1\end{pmatrix}}$

   und der üblichen Matrizenaddition und Matrizenmultiplikation und der Variablenbelegung ${}I(x)={\begin{pmatrix}1&2\\3&4\end{pmatrix}}$ und ${}I(y)={\begin{pmatrix}3&-2\\0&5\end{pmatrix}}$.

3. ${}M=\mathbb {N}$, mit

   $I(0)=1,\,I(1)=4,\,I(x)=2,\,I(y)=1,$

   und wo ${}+$ als Multiplikation und ${}\cdot$ als Addition interpretiert wird.
4. ${}M=\mathbb {Z}$, mit

   $I(0)=5,\,I(1)=-1,\,I(x)=0,\,I(y)=0,$

   und wo sowohl ${}+$ als auch ${}\cdot$ als Subtraktion interpretiert werden.
5. ${}M=$ Potenzmenge von ${}\{1,2,3,4,5\}$ mit

   $I(0)=\emptyset ,\,I(1)=\{1,2,3,4,5\},\,I(x)=\emptyset ,\,I(y)=\{2,4\},$

   und wo ${}+$ als ${}\cup$ und ${}\cdot$ als ${}\cap$ interpretiert wird.

Aufgabe

Es sei ${}N$ ein einstelliges Funktionssymbol, ${}F$ ein zweistelliges Funktionssymbol, ${}0$ sei eine Konstante und ${}x,y$ seien Variablen. Interpretiere den Term

$NFN0NFxy$

unter den folgenden Interpretationen, wobei ${}M$ die Grundmenge der Interpretation bezeichne.

1. ${}M=\mathbb {N}$, ${}N$ ist die Nachfolgerfunktion, ${}F$ die Addition, ${}I(0)=0$, ${}I(x)=3$ und ${}I(y)=4$.
2. ${}M=\mathbb {Q}$, ${}N$ ist das Quadrieren, ${}F$ die Multiplikation, ${}I(0)=-2$, ${}I(x)=3$ und ${}I(y)={\frac {3}{4}}$.
3. ${}M=C^{\infty }(\mathbb {R} ,\mathbb {R} )={\left\{f:\mathbb {R} \rightarrow \mathbb {R} \mid f{\text{ unendlich oft differenzierbar}}\right\}}$, ${}N$ ist das Differenzieren von Funktionen, ${}F$ die Multiplikation von Funktionen, ${}I(0)$ ist die Identität, ${}I(x)$ ist die Sinusfunktion und ${}I(y)$ ist die Exponentialfunktion zur Basis ${}e$.

Aufgabe

Es sei das arithmetische Alphabet ${}\{0,1,+,\cdot \}$ zusammen mit der Variablenmenge ${}\{x,y\}$ gegeben. Interpretiere den Ausdruck

$\forall x\exists y(x=y+y\vee x+1=y+y)$

unter den in Aufgabe 7.19 angeführten Interpretationen und überprüfe die Gültigkeit.

Aufgabe *

Es sei ${}L^{S}$ die prädikatenlogische Sprache, die neben Variablen aus einem zweistelligen Relationssymbol ${}A$ und einem dreistelligen Relationssymbol ${}B$ bestehe. Wir betrachten ${}S$- Interpretationen ${}I$, wobei die Grundmenge jeweils aus einem Vektorraum ${}V$ über einem Körper ${}K$ bestehe und ${}A$ als die lineare Unabhängigkeit von zwei und ${}B$ als die lineare Unabhängigkeit von drei Vektoren interpretiert werde.

1. Zeige

   $I\vDash Bxyz\rightarrow Axy.$

2. Gilt

   $I\vDash Axy\wedge Axz\wedge Ayz\rightarrow Bxyz$

   für einen beliebigen Vektorraum?

3. Gibt es Vektorräume, für die die Aussage in Teil 2 gilt?
4. Es sei ${}V=\mathbb {R} ^{3}$ und ${}e_{1},e_{2},e_{3}$ sei die Standardbasis. Gilt

   $I{\frac {e_{1},e_{2},e_{3}}{x,y,z}}\vDash Bxyz?$

5. Es sei ${}V=\mathbb {R}$ als ${}\mathbb {Q}$-Vektorraum betrachtet. Gilt

   $I{\frac {1,{\sqrt {2}}}{x,y}}\vDash Axy?$

Aufgabe

Es sei

$\varphi \colon \mathbb {N} \longrightarrow \mathbb {Z}$

die durch

${}\varphi (n):={\begin{cases}{\frac {n}{2}}\,,{\text{ falls }}n{\text{ gerade}}\,,\\-{\frac {n+1}{2}}\,,{\text{ falls }}n{\text{ ungerade}}\,,\end{cases}}\,$

gegebene bijektive Abbildung mit der Umkehrabbildung ${}\varphi ^{-1}$. Auf ${}\mathbb {Z}$ seien die zweistelligen Funktionen ${}\circ$ und ${}\heartsuit$ durch

${}m\circ n:=\varphi (\varphi ^{-1}(m)+\varphi ^{-1}(n))\,$

und

${}m\heartsuit n:=\varphi (\varphi ^{-1}(m)\cdot \varphi ^{-1}(n))\,$

gegeben, wobei ${}+$ und ${}\cdot$ die üblichen Verknüpfungen auf ${}\mathbb {N}$ seien. Die Menge ${}\mathbb {Z}$ zusammen mit diesen Verknüpfungen nennen wir ${}M$.

a) Berechne in ${}M$

$(5\heartsuit (-2))\circ ((-6)\heartsuit 3).$

b) Es sei ${}S$ das Symbolalphabet, das aus den Variablen ${}x,y$, einer Konstanten ${}c$ und zwei zweistelligen Funktionssymbolen ${}\alpha ,\beta$ bestehe. Es sei ${}I$ die Interpretation von ${}L^{S}$ in ${}M$, die ${}\alpha$ als ${}\circ$, ${}\beta$ als ${}\heartsuit$, ${}c$ als ${}1$ und die Variablen als ${}2$ interpretiere. Berechne ${}I(t)$ für den Term

${}t=\beta \alpha cc\beta xc\,.$

c) Gilt bei der Interpretation ${}I$ der Ausdruck

$\forall x{\left(\exists y{\left(c\circ y=x\right)}\right)}?$

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Es sei ${}S$ das erststufige Symbolalphabet, das aus den Variablen ${}x,y,z$, den Konstanten ${}0,1,2$, den einstelligen Funktionssymbolen ${}F,G$, den zweistelligen Funktionssymbolen ${}\alpha ,\beta$, den einstelligen Relationssymbolen ${}P,Q$ und dem zweistelligen Relationssymbol ${}R$ bestehe. Überprüfe, ob die folgenden Wörter zur Sprache ${}L^{S}$ (bei korrekter Klammerung) gehören.

1. ${}Fx=P2$,
2. ${}Fx=G1$,
3. ${}\forall x{\left(0=1\right)}$,
4. ${}{\left(\beta 12=22\right)}\rightarrow {\left(Q0\right)}$,
5. ${}{\left(Fx=1\right)}\rightarrow {\left(\neg {\left(G2=0\right)}\right)}$,
6. ${}\exists 0{\left(P0\right)}$,
7. ${}{\left(\exists x{\left(R0x\right)}\right)}\wedge {\left(\neg {\left(\alpha \beta 012=Rcz\right)}\right)}$,
8. ${}{\left(R\alpha 0xGy\right)}\wedge {\left(\neg Q1\right)}$.

Es genügt, die korrekten Ausdrücke aufzuschreiben; Punkte gibt es nur bei einer komplett richtigen Lösung.

Aufgabe (2 Punkte)

Es sei ${}S$ ein Symbolalphabet einer Sprache erster Stufe, ${}T$ die Menge der ${}S$- Terme und ${}I$ eine ${}S$- Interpretation. Zeige, dass auf ${}T$ durch

$s\sim t,{\text{ falls }}I(s)=I(t),$

eine Äquivalenzrelation definiert wird.

Aufgabe (2 Punkte)

Schreibe die folgenden Aussagen mit Quantoren:

1. Für jede natürliche Zahl gibt es eine größere natürliche Zahl.
2. Für jede natürliche Zahl gibt es eine kleinere natürliche Zahl.
3. Es gibt eine natürliche Zahl, die größer oder gleich jeder anderen natürlichen Zahl ist.
4. Es gibt eine natürliche Zahl, die kleiner oder gleich jeder anderen natürlichen Zahl ist.

Welche sind wahr, welche falsch?

Aufgabe (1 Punkt)

Formalisiere mit dem Symbolalphabet, das neben Variablen aus ${}\{f,g\}$ besteht, wobei ${}f,g$ einstellige Funktionssymbole sind, dass die Hintereinanderschaltung von surjektiven Abbildungen auf einer Menge wieder surjektiv ist.

Aufgabe (3 Punkte)

Formalisiere in der arithmetischen Sprache die folgenden zahlentheoretischen Vermutungen.

1. Die Goldbach-Vermutung.
2. Die Vermutung über die Unendlichkeit der Primzahlzwillinge.
3. Die Vermutung über die Unendlichkeit der Mersenne-Primzahlen.

Man beachte bei (3), dass das Potenzieren mit einem unbekannten Exponenten nicht zur arithmetischen Sprache gehört.

Aufgabe (4 Punkte)

Es sei das arithmetische Alphabet ${}\{0,1,+,\cdot \}$ zusammen mit der Variablenmenge ${}\{x,y\}$ gegeben. Interpretiere den Term

$((0+x)+1)\cdot (1+((y\cdot x)+1))$

unter den folgenden Interpretationen.

1. ${}M=\mathbb {N}$ mit der Standardinterpretation und der Variablenbelegung ${}I(x)=7$ und ${}I(y)=2$.
2. ${}M=\operatorname {Mat} _{2}(\mathbb {R} )$ mit der Standardinterpretation

   $I(0)={\begin{pmatrix}0&0\\0&0\end{pmatrix}},\,I(1)={\begin{pmatrix}1&0\\0&1\end{pmatrix}}$

   und der üblichen Matrizenaddition und Matrizenmultiplikation und der Variablenbelegung ${}I(x)={\begin{pmatrix}-1&3\\4&5\end{pmatrix}}$ und ${}I(y)={\begin{pmatrix}2&-3\\2&0\end{pmatrix}}$.

3. ${}M=\mathbb {Z}$, mit

   $I(0)=6,\,I(1)=-4,\,I(x)=0,\,I(y)=5,$

   und wo sowohl ${}+$ als auch ${}\cdot$ als Subtraktion interpretiert werden.

4. ${}M=$ Potenzmenge von ${}\{1,2,3,4,5,6\}$ mit

   $I(0)=\{5,6\},\,I(1)=\{1,2,3,4,5,6\},\,I(x)=\emptyset ,\,I(y)=\{1,3,5\},$

   und wo ${}+$ als ${}\cup$ und ${}\cdot$ als ${}\cap$ interpretiert wird.

Fußnoten