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

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

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

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

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

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?

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