Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/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?

Aufgaben zum Abgeben

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.