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

\setcounter{section}{7}






\zwischenueberschrift{Übungsaufgaben}

\inputaufgabegibtloesung
{}
{

Wir betrachten den Satz \anfuehrung{Diese Vorlesung versteht keine Sau}{.} Negiere diesen Satz durch eine Existenzaussage.

}
{} {}

\inputaufgabe
{}
{

Man formalisiere die folgenden Aussagen, indem man geeignete Prädikate erklärt. Man gebe die Negation der Aussagen \zusatzklammer {umgangssprachlich und formal} {} {} an. \aufzaehlungneun{Alle Vögel sind schon da. }{Alle Wege führen nach Rom. }{Faulheit ist aller Laster Anfang. }{Alle Menschen werden Brüder, wo dein sanfter Flügel weilt. }{Wem der große Wurf gelungen, eines Freundes Freund zu sein, wer ein holdes Weib errungen, mische seinen Jubel ein!\zusatzfussnote {Dieser Satz ist im Konjunktiv formuliert, was eher auf eine Aufforderung hindeutet als auf eine Aussage. Man kann hier \anfuehrung{soll mischen}{} als Prädikat nehmen und damit arbeiten.} {} {} }{Freude trinken alle Wesen an den Brüsten der Natur. }{Alle Macht geht vom Volk aus. }{Alle Achtung. }{Alle Neune. }

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ das \definitionsverweis {erststufige Symbolalphabet}{}{,} das aus den Variablen
\mathl{x,y,z}{,} den Konstanten
\mathl{0,c}{,} dem einstelligen Funktionssymbol $F$, den zweistelligen Funktionssymbolen $\alpha, \beta$ und dem zweistelligen Relationssymbol
\mathl{R}{} bestehe. Überprüfe, ob die folgenden Wörter zur Sprache $L^ S$ \zusatzklammer {bei korrekter Klammerung} {} {} gehören. \aufzaehlungacht{
\mathl{Fx}{,} }{
\mathl{\forall x { \left( Fx = c \right) }}{,} }{
\mathl{x=w}{,} }{
\mathl{{ \left( Fx = c \right) } \rightarrow { \left( \alpha \right) }}{,} }{
\mathl{{ \left( Fx = c \right) } \rightarrow { \left( \neg { \left( \exists y { \left( Fx = c \right) } \right) } \right) }}{,} }{
\mathl{R0}{,} }{
\mathl{{ \left( \forall z { \left( R0x \right) } \right) } \wedge { \left( \neg { \left( \beta \alpha y z y = Rcz \right) } \right) }}{,} }{
\mathl{{ \left( \forall z { \left( R0x \right) } \right) } \wedge { \left( \neg { \left( \beta \alpha y z y = \beta cz \right) } \right) }}{.} }

}
{} {}

\inputaufgabe
{}
{

Bestimme die kleinsten Symbolmengen, mit denen die folgenden Ausdrücke formulierbar sind. \aufzaehlungdrei{ $\exists y { \left( fx = y \right) }$, }{ $\forall x { \left( fx = g yc \right) } \wedge \exists z { \left( R z x y \right) }$, }{ $\forall x \exists y S x huy$. }

}
{} {}

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.


\inputaufgabe
{}
{

Formuliere die folgenden Aussagen über die natürlichen Zahlen $\N=\{0,1,2,3, \ldots \}$ allein mittels Gleichheit, Addition, Multiplikation und unter Verwendung von aussagenlogischen Junktoren und Quantoren. \aufzaehlungzweireihe {\itemfuenf { $5 \geq 3$. }{ $5 > 3$. }{ $5 \leq 3$. }{ $7$ ist eine Primzahl. }{ $8$ ist eine Primzahl. } } {\itemfuenf { $8$ ist keine Primzahl. }{ Jede natürliche Zahl besitzt mindestens einen Primfaktor.}{ Jede natürliche Zahl größer gleich $2$ besitzt mindestens einen Primfaktor. }{ Wenn eine Primzahl ein Produkt teilt, so teilt sie auch mindestens einen der Faktoren. }{ Es gibt Zahlen, die ein Produkt teilen, obwohl sie keinen der Faktoren teilen.} }

}
{} {}

\inputaufgabe
{}
{

Formuliere die folgenden Beziehungen \zusatzklammer {ein- oder mehrstellige Prädikate} {} {} innerhalb der natürlichen Zahlen $\N=\{0,1,2,3, \ldots \}$ allein mittels Gleichheit, Addition, Multiplikation und unter Verwendung von aussagenlogischen Junktoren und Quantoren. \aufzaehlungneun{ $x \geq y$. }{ $x> y$. }{ $x$ teilt $y$. }{ $x$ teilt nicht $y$. }{ $x$ ist eine Quadratzahl. }{ $x$ ist eine Primzahl. }{ $x$ ist keine Primzahl. }{ $x$ ist das Produkt von genau zwei verschiedenen Primzahlen. }{ $x$ wird von einer Primzahl geteilt.}

}
{} {}

\inputaufgabe
{}
{

Formalisiere die folgenden mengentheoretischen Fassungen einiger aristotelischer Syllogismen in der Prädikatenlogik erster Stufe. \aufzaehlungfuenf{Modus Barbara: Aus $B \subseteq A$ und $C \subseteq B$ folgt $C \subseteq A$. }{Modus Celarent: Aus $B \cap A = \emptyset$ und $C \subseteq B$ folgt $C \cap A = \emptyset$. }{Modus Darii: Aus $B \subseteq A$ und $C \cap B \neq \emptyset$ folgt $C \cap A \neq \emptyset$. }{Modus Ferio: Aus $B \cap A = \emptyset$ und $C \cap B \neq \emptyset$ folgt $C \not \subseteq A$. }{Modus Baroco: Aus $B \subseteq A$ und $B \not \subseteq C$ folgt $A \not \subseteq C$. }

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Formalisiere in der arithmetischen Sprache (mit \mathkor {} {+} {und} {\cdot} {)} die folgenden (wahren) Aussagen. \aufzaehlungvier{Wenn $x \geq y$ und $y \geq z$, so ist
\mathl{x \geq z}{.} }{Wenn $x \geq y$ und $y \geq x$ gilt, so ist
\mathl{x= y}{.} }{Für jede natürliche Zahl gibt es eine größere natürliche Zahl. }{Eine natürliche Zahl, für die es keine kleinere natürliche Zahl gibt, ist gleich $0$. }

}
{} {}

\inputaufgabe
{}
{

Formalisiere in der arithmetischen Sprache die folgenden wahren Aussagen. \aufzaehlungzwei {Es gibt unendlich viele Primzahlen. } {Jede natürliche Zahl
\mathl{\geq 2}{} wird von einer Primzahl geteilt. }

}
{} {}

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

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{K=\{E,m,c\}}{} eine Konstantenmenge, $Q$ ein einstelliges Funktionssymbol und $P$ ein zweistelliges Funktionssymbol. Es sei $I$ die Interpretation mit
\mavergleichskette
{\vergleichskette
{M }
{ = }{\N }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} als Grundmenge, bei der $Q$ als Quadrieren, $P$ als Multiplikation und die Konstanten als
\mavergleichskette
{\vergleichskette
{I(E) }
{ = }{9 000 000 000 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{}
\mavergleichskette
{\vergleichskette
{I(m) }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{I(c) }
{ = }{300 000 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} interpretiert wird. Ist der Ausdruck
\mathdisp {E = P m Q c} { }
unter dieser Interpretation gültig?

}
{} {}

\inputaufgabe
{}
{

Es sei das arithmetische Alphabet
\mathl{\{0,1,+,\cdot\}}{} zusammen mit der Variablenmenge
\mathl{\{x,y\}}{} gegeben. Interpretiere den Term
\mathdisp {((0+1)+x) \cdot (1+(y+1))} { }
unter den folgenden Interpretationen. \aufzaehlungfuenf{
\mathl{M=\N}{} mit der Standardinterpretation und der Variablenbelegung
\mathl{I(x)=5}{} und
\mathl{I(y)=3}{.} }{
\mathl{M= \operatorname{Mat}_{ 2 } (\R)}{} mit der Standardinterpretation
\mathdisp {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
\mathl{I(x)= \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}}{} und
\mathl{I(y)=\begin{pmatrix} 3 & -2 \\ 0 & 5 \end{pmatrix}}{.} }{
\mathl{M=\N}{,} mit
\mathdisp {I(0)=1,\, I(1) =4,\, I(x)=2, \, I(y)=1} { , }
und wo $+$ als Multiplikation und $\cdot$ als Addition interpretiert wird. }{
\mathl{M=\Z}{,} mit
\mathdisp {I(0)=5,\, I(1) =-1,\, I(x)=0, \, I(y)=0} { , }
und wo sowohl $+$ als auch $\cdot$ als Subtraktion interpretiert werden. }{
\mathl{M=}{} \definitionsverweis {Potenzmenge}{}{} von
\mathl{\{1,2,3,4,5\}}{} mit
\mathdisp {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. }

}
{} {}

\inputaufgabe
{}
{

Es sei $N$ ein einstelliges Funktionssymbol, $F$ ein zweistelliges Funktionssymbol, $0$ sei eine Konstante und
\mathl{x,y}{} seien Variablen. Interpretiere den Term
\mathdisp {NFN0NFxy} { }
unter den folgenden Interpretationen, wobei $M$ die Grundmenge der Interpretation bezeichne. \aufzaehlungdrei{
\mavergleichskette
{\vergleichskette
{M }
{ = }{\N }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} $N$ ist die Nachfolgerfunktion, $F$ die Addition,
\mavergleichskette
{\vergleichskette
{I(0) }
{ = }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,}
\mavergleichskette
{\vergleichskette
{ I(x) }
{ = }{ 3 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{ I(y) }
{ = }{ 4 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{
\mavergleichskette
{\vergleichskette
{M }
{ = }{ \Q }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} $N$ ist das Quadrieren, $F$ die Multiplikation,
\mavergleichskette
{\vergleichskette
{I(0) }
{ = }{-2 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,}
\mavergleichskette
{\vergleichskette
{ I(x) }
{ = }{ 3 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{ I(y) }
{ = }{ { \frac{ 3 }{ 4 } } }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }{
\mavergleichskette
{\vergleichskette
{M }
{ = }{ C^\infty(\R,\R) }
{ = }{ { \left\{ f:\R \rightarrow \R \mid f \text{ unendlich oft differenzierbar} \right\} } }
{ }{ }
{ }{ }
} {}{}{,} $N$ ist das Differenzieren von Funktionen, $F$ die Multiplikation von Funktionen,
\mathl{I(0)}{} ist die Identität,
\mathl{I(x)}{} ist die Sinusfunktion und
\mathl{I(y)}{} ist die Exponentialfunktion zur Basis $e$. }

}
{} {}

\inputaufgabe
{}
{

Es sei das arithmetische Alphabet
\mathl{\{0,1,+,\cdot\}}{} zusammen mit der Variablenmenge
\mathl{\{x,y\}}{} gegeben. Interpretiere den Ausdruck
\mathdisp {\forall x \exists y ( x = y+y \vee x+1 = y+y )} { }
unter den in Aufgabe 7.15 angeführten Interpretationen und überprüfe die Gültigkeit.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $L^S$ die \definitionsverweis {prädikatenlogische Sprache}{}{,} die neben Variablen aus einem zweistelligen Relationssymbol $A$ und einem dreistelligen Relationssymbol $B$ bestehe. Wir betrachten $S$-\definitionsverweis {Interpretationen}{}{} $I$, wobei die Grundmenge jeweils aus einem \definitionsverweis {Vektorraum}{}{} $V$ über einem \definitionsverweis {Körper}{}{} $K$ bestehe und $A$ als die \definitionsverweis {lineare Unabhängigkeit}{}{} von zwei und $B$ als die lineare Unabhängigkeit von drei Vektoren interpretiert werde. \aufzaehlungfuenf{Zeige
\mathdisp {I \vDash Bxyz \rightarrow Axy} { . }
}{Gilt
\mathdisp {I \vDash Axy \wedge Axz \wedge Ayz \rightarrow Bxyz} { }
für einen beliebigen Vektorraum? }{Gibt es Vektorräume, für die die Aussage in Teil 2 gilt? }{Es sei
\mathl{V= \R^3}{} und
\mathl{e_1,e_2,e_3}{} sei die Standardbasis. Gilt
\mathdisp {I { \frac{ e_1,e_2,e_3 }{ x,y,z } } \vDash Bxyz} { ? }
}{Es sei
\mathl{V=\R}{} als $\Q$-Vektorraum betrachtet. Gilt
\mathdisp {I { \frac{ 1, \sqrt{2} }{ x,y } } \vDash Axy} { ? }
}

}
{} {}

\inputaufgabe
{}
{

Es sei \maabbdisp {\varphi} {\N} {\Z } {} die durch
\mavergleichskettedisp
{\vergleichskette
{\varphi(n) }
{ \defeq} { \begin{cases} { \frac{ n }{ 2 } }\, , \text{ falls } n \text { gerade}\, , \\ - { \frac{ n+1 }{ 2 } }\, , \text{ falls } n \text { ungerade}\, ,\end{cases} }
{ } { }
{ } { }
{ } { }
} {}{}{} gegebene \definitionsverweis {bijektive Abbildung}{}{} mit der \definitionsverweis {Umkehrabbildung}{}{} $\varphi^{-1}$. Auf $\Z$ seien die zweistelligen Funktionen \mathkor {} {\circ} {und} {\heartsuit} {} durch
\mavergleichskettedisp
{\vergleichskette
{m \circ n }
{ \defeq} { \varphi (\varphi^{-1} (m) + \varphi^{-1} (n)) }
{ } { }
{ } { }
{ } { }
} {}{}{} und
\mavergleichskettedisp
{\vergleichskette
{m \heartsuit n }
{ \defeq} { \varphi (\varphi^{-1} (m) \cdot \varphi^{-1} (n)) }
{ } { }
{ } { }
{ } { }
} {}{}{} gegeben, wobei \mathkor {} {+} {und} {\cdot} {} die üblichen Verknüpfungen auf $\N$ seien. Die Menge $\Z$ zusammen mit diesen Verknüpfungen nennen wir $M$.

a) Berechne in $M$
\mathdisp {( 5 \heartsuit (-2)) \circ ((-6) \heartsuit 3)} { . }

b) Es sei $S$ das Symbolalphabet, das aus den Variablen
\mathl{x,y}{,} einer Konstanten $c$ und zwei zweistelligen Funktionssymbolen
\mathl{\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
\mavergleichskettedisp
{\vergleichskette
{t }
{ =} { \beta \alpha c c \beta x c }
{ } { }
{ } { }
{ } { }
} {}{}{.}

c) Gilt bei der Interpretation $I$ der Ausdruck
\mathdisp {\forall x { \left( \exists y { \left( c \circ y = x \right) } \right) }} { ? }

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{1}
{

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

}
{} {}

\inputaufgabe
{2}
{

Es sei $S$ das \definitionsverweis {erststufige Symbolalphabet}{}{,} das aus den Variablen
\mathl{x,y,z}{,} den Konstanten
\mathl{0,1 , 2}{,} den einstelligen Funktionssymbolen $F,G$, den zweistelligen Funktionssymbolen $\alpha, \beta$, den einstelligen Relationssymbolen $P,Q$ und dem zweistelligen Relationssymbol
\mathl{R}{} bestehe. Überprüfe, ob die folgenden Wörter zur Sprache $L^S$ \zusatzklammer {bei korrekter Klammerung} {} {} gehören. \aufzaehlungacht{
\mathl{Fx=P2}{,} }{
\mathl{Fx=G1}{,} }{
\mathl{\forall x { \left( 0 = 1 \right) }}{,} }{
\mathl{{ \left( \beta 12 = 22 \right) } \rightarrow { \left( Q0 \right) }}{,} }{
\mathl{{ \left( Fx = 1 \right) } \rightarrow { \left( \neg { \left( G2 = 0 \right) } \right) }}{,} }{
\mathl{\exists 0 { \left( P0 \right) }}{,} }{
\mathl{{ \left( \exists x { \left( R0x \right) } \right) } \wedge { \left( \neg { \left( \alpha \beta 012 = Rcz \right) } \right) }}{,} }{
\mathl{{ \left( R \alpha 0x G y \right) } \wedge { \left( \neg Q1 \right) }}{.} }

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

\inputaufgabe
{2}
{

Schreibe die folgenden Aussagen mit Quantoren: \aufzaehlungvier{Für jede natürliche Zahl gibt es eine größere natürliche Zahl. }{Für jede natürliche Zahl gibt es eine kleinere natürliche Zahl. }{Es gibt eine natürliche Zahl, die größer oder gleich jeder anderen natürlichen Zahl ist. }{Es gibt eine natürliche Zahl, die kleiner oder gleich jeder anderen natürlichen Zahl ist. } Welche sind wahr, welche falsch?

}
{} {}

\inputaufgabe
{3}
{

Formalisiere in der arithmetischen Sprache die folgenden zahlentheoretischen Vermutungen. \aufzaehlungdrei{Die Goldbach-Vermutung. }{Die Vermutung über die Unendlichkeit der Primzahlzwillinge. }{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.}

\inputaufgabe
{4}
{

Es sei das arithmetische Alphabet
\mathl{\{0,1,+,\cdot\}}{} zusammen mit der Variablenmenge
\mathl{\{x,y\}}{} gegeben. Interpretiere den Term
\mathdisp {((0+x)+1) \cdot (1+( (y \cdot x) +1))} { }
unter den folgenden Interpretationen. \aufzaehlungvier{
\mathl{M=\N}{} mit der Standardinterpretation und der Variablenbelegung
\mathl{I(x)=7}{} und
\mathl{I(y)=2}{.} }{
\mathl{M= \operatorname{Mat}_{ 2 } (\R)}{} mit der Standardinterpretation
\mathdisp {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
\mathl{I(x)= \begin{pmatrix} -1 & 3 \\ 4 & 5 \end{pmatrix}}{} und
\mathl{I(y)=\begin{pmatrix} 2 & -3 \\ 2 & 0 \end{pmatrix}}{.} }{
\mathl{M=\Z}{,} mit
\mathdisp {I(0)=6,\, I(1) =-4,\, I(x)=0, \, I(y)=5} { , }
und wo sowohl $+$ als auch $\cdot$ als Subtraktion interpretiert werden. }{
\mathl{M=}{} \definitionsverweis {Potenzmenge}{}{} von
\mathl{\{1,2,3,4,5,6\}}{} mit
\mathdisp {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. }

}
{} {}