Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 2

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

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

Die folgende Aufgabe verwendet den Begriff abzählbar.

Aufgabe

Es sei ${}A$ ein abzählbares Alphabet. Zeige, dass auch die Menge ${}A^{*}$ der Wörter über ${}A$ abzählbar ist.

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieses Arbeitsblattes Zur Vorlesung (PDF)