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 g{c}_{1}f{c}_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. $NNNNNN{x}_{1}NNNNNNNNNNN{x}_2$,
3. $\alpha NNNNNN0NNNNNNNNNNN1$,
4. $NNN\mu NNN\mu 0NNNNNNNNNNN1$,
5. $\mu \alpha \mu \alpha \mu \alpha 0101010$,
6. $\alpha \alpha \alpha N{x}_{1}N{x}_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\ge 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

$\mathrm{\forall }A\mathrm{\forall }B\mathrm{\forall }C(R(A,B,C)⟶S(A,B,C))$

und

$\mathrm{\forall }A\mathrm{\forall }B\mathrm{\forall }CR(A,B,C)⟶\mathrm{\forall }A\mathrm{\forall }B\mathrm{\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}zgg{c}_2.$

Aufgabe (5 Punkte)

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

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