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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 * Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

Diskutiere, ob es sich bei

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

um Terme handelt.

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Aufgabe 6.18 ändern

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.