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

Übungsaufgaben

Aufgabe

Entwerfe einen Termstammbamm für den Term

$f\alpha \alpha gx\alpha c_{2}f\beta gy\alpha c_{1}gfz\beta gc_{1}fc_{1}$

wie in Beispiel 6.7.

Aufgabe

Wir betrachten die arithmetische Grundtermmenge, die aus den Konstanten ${}0$ und ${}1$, den Variablen ${}x_{n}$, ${}n\in \mathbb {N}$, dem einstelligen Funktionssymbol ${}N$ und den beiden zweistelligen Funktionssymbolen ${}\alpha$ und ${}\mu$ besteht. Entscheide, ob die folgenden Wörter über diesem Termalphabet Terme sind oder nicht.

1. ${}NNNNNNN01$,
2. ${}NNNNNNx_{1}NNNNNNNNNNNx_{2}$,
3. ${}\alpha NNNNNN0NNNNNNNNNNN1$,
4. ${}NNN\mu NNN\mu 0NNNNNNNNNNN1$,
5. ${}\mu \alpha \mu \alpha \mu \alpha 0101010$,
6. ${}\alpha \alpha \alpha Nx_{1}Nx_{2}x_{3}x_{4}x_{3}$.

Schreibe diejenigen Wörter, die Terme sind, mit Klammern, ${}\prime$, ${}+$ und ${}\cdot$.

Aufgabe *

Es seien ${}x,y,z,w$ Variablen und ${}V$ ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?

1. ${}VxyzVVw$,
2. ${}VVxyVzw$,
3. ${}VVxyzVw$,
4. ${}VxVyVzw$,
5. ${}xVyVzVw$,
6. ${}VVVxyzw$,
7. ${}VxyVVzw$,
8. ${}VVxVyzw$,
9. ${}VxyVzw$,
10. ${}VxVyzVw$,
11. ${}VxVVyzw$,
12. ${}VxyVzVw$.

Aufgabe

Erläutere den Unterschied zwischen ${}G=(V,K,F_{n},n\in \mathbb {N} _{+})$ und ${}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}$ in Definition 6.6.

Aufgabe

Es sei ${}V$ eine Variablenmenge, ${}K$ eine Konstantenmenge und ${}F$ eine Menge aus Funktionssymbolen (mit einer gewissen Stelligkeit). Es sei

${}A=V\cup K\cup F\,$

das zugehörige Alphabet. Es sei vorausgesetzt, dass dieses Alphabet nicht leer sei. Zeige, dass es nichtleere Wörter über ${}A$ gibt, die keine Terme sind.

Aufgabe

Es sei ${}G$ eine Grundtermmenge und ${}t\in T(G)$ ein ${}G$- Term. Es sei ${}u$ das am weitesten links stehende Symbol von ${}t$ und ${}v$ das am weitesten rechts stehende Symbol von ${}t$. Zeige die folgenden Eigenschaften.

1. Wenn ${}u$ eine Variable oder eine Konstante ist, so ist ${}t=u$.
2. ${}v$ ist eine Variable oder eine Konstante.
3. Wenn ${}t_{1}$ und ${}t_{2}$ Terme sind, so ist ${}t_{1}t_{2}$ kein Term.

Aufgabe

Es sei ${}G$ eine Grundtermmenge und ${}t$ ein ${}G$- Term. Es sei ${}n$ die Gesamtzahl der Variablen und Konstanten in ${}t$, wobei mehrfaches Vorkommen auch mehrfach gezählt wird. Es sei ${}k$ die Summe über alle Stelligkeiten der in ${}t$ vorkommenden Funktionssymbole, wobei wiederum mehrfach auftretende Symbole auch mehrfach gezählt werden.

1. Bestimme ${}n$ und ${}k$ im Term

   $ggxyhfxfzgyfy,$

   wobei ${}f$ einstellig, ${}g$ zweistellig und ${}h$ dreistellig sei.
2. Es sei ${}t$ weder eine Variable noch eine Konstante. Zeige ${}k\geq n$.
3. Zeige, dass die Differenz ${}n-k$ beliebig groß sein kann.

Aufgabe

Diskutiere, ob es sich bei

$n!,\,{\binom {n}{k}},\,\pi ,\,e^{u},x^{y},\,5^{x},\,{\sqrt {x}},\,\heartsuit$

um Terme handelt.

Aufgabe

Es sei ${}f$ ein zweistelliges Funktionssymbol und ${}x,y$ Variablen. Formuliere das Kommutativgesetz (für ${}f$) als eine Allaussage mit Hilfe der Identität von zwei Termen.

Aufgabe

Es sei ${}K$ ein Körper und ${}V=\{x_{1},\ldots ,x_{n}\}$ eine Variablenmenge. Eine Grundtermmenge ${}G$ sei durch ${}K$ als Konstantenmenge, ${}V$ als Variablenmenge und den beiden zweistelligen Funktionssymbolen ${}+$ und ${}\cdot$ festgelegt. In welcher Beziehung steht die Termmenge ${}T(G)$ zum Polynomring ${}K[x_{1},\ldots ,x_{n}]$.

Aufgabe

Es sei ${}T$ die Termmenge zur Konstantenmenge ${}\{0,1\}$, zur Variablenmenge ${}x_{i}$, ${}i\in I$ und zur zweistelligen Funktionssymbolmenge ${}\{+,\cdot \}$. Definiere eine natürliche Abbildung von ${}T$ in den Polynomring ${}\mathbb {Z} [x_{i}:i\in I]$. Ist diese Abbildung injektiv? Ist sie surjektiv? Was ist das Bild?

Aufgabe

Für Punkte ${}A,B,C$ in der Ebene bedeute ${}R(A,B,C)$ die Rechtwinkligkeit des durch ${}A,B,C$ gegebenen Dreiecks an der Ecke ${}A$ und ${}S(A,B,C)$ die pythagoreische Längenbeziehung. Betrachte die beiden formalen Aussagen

$\forall A\forall B\forall C(R(A,B,C)\longrightarrow S(A,B,C))$

und

$\forall A\forall B\forall CR(A,B,C)\longrightarrow \forall A\forall B\forall CS(A,B,C).$

Welche ist (sind) eine Formalisierung des Satzes von Pythagoras, welche ist (sind) wahr?

Aufgabe

Formuliere mit arithmetischen Grundsymbolen, Gleichheit, Quantoren und Junktoren die Eigenschaft (das Prädikat) einer natürlichen Zahl, gerade oder ungerade zu sein. Formuliere ebenso die Aussage, dass jede natürliche Zahl entweder gerade oder ungerade ist. Formuliere ferner die Aussage, dass zu jeder natürlichen Zahl ${}n$ die Zahl ${}n^{2}-n$ gerade ist.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es seien ${}M,N,L$ Mengen. Stifte eine Bijektion zwischen

$\operatorname {Abb} \,{\left(M\times N,L\right)}\,\,{\text{ und }}\,\,\operatorname {Abb} \,{\left(M,\operatorname {Abb} \,{\left(N,L\right)}\right)}.$

Aufgabe (2 Punkte)

Eine Grundtermmenge sei durch die Variablenmenge ${}V=\{x,y,z\}$, eine Konstantenmenge ${}K=\{c_{1},c_{2}\}$, die einstelligen Funktionssymbole ${}F_{1}=\{f,g\}$ und die zweistelligen Funktionssymbole ${}F_{2}=\{\alpha ,\beta ,\gamma \}$ gegeben. Entwerfe einen Termstammbaum für den Term

$gf\beta \beta \alpha fxy\gamma c_{1}zggc_{2}.$

Aufgabe (2 Punkte)

Es sei ${}f$ ein zweistelliges Funktionssymbol und ${}x,y,z$ Variablen. Formuliere das Assoziativgesetz (für ${}f$) als eine Allaussage mit Hilfe der Identität von zwei Termen.

Aufgabe (3 Punkte)

Eine Grundtermmenge ${}G$ sei durch eine einelementige Konstantenmenge ${}K=\{c\}$, eine leere Variablenmenge und eine einelementige einstellige Funktionssymbolmenge

${}F_{1}=\{f\}\,$

gegeben. Zeige durch Induktion, dass es eine bijektive Abbildung

$\varphi \colon \mathbb {N} \longrightarrow T(G)$

mit ${}\varphi (0)=c$ und ${}\varphi (n+1)=f\varphi (n)$ für alle ${}n\in \mathbb {N}$ gibt.

Aufgabe (5 Punkte)

Zeige, dass es kein nichtausgeartetes gleichseitiges Dreieck im ${}\mathbb {R} ^{2}$ gibt, dessen sämtliche Ecken rationale Koordinaten besitzen.

Tipp: Verwende, dass ${}{\sqrt {3}}$ irrational ist und den Satz des Pythagoras.