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

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.

${}NNNNNNN01$ ,
${}NNNNNNx_{1}NNNNNNNNNNNx_{2}$ ,
${}\alpha NNNNNN0NNNNNNNNNNN1$ ,
${}NNN\mu NNN\mu 0NNNNNNNNNNN1$ ,
${}\mu \alpha \mu \alpha \mu \alpha 0101010$ ,
${}\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

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

Wenn ${}u$ eine Variable oder eine Konstante ist, so ist ${}t=u$ .
${}v$ ist eine Variable oder eine Konstante.
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.

Bestimme ${}n$ und ${}k$ im Term
$ggxyhfxfzgyfy,$
wobei ${}f$ einstellig, ${}g$ zweistellig und ${}h$ dreistellig sei.
Es sei ${}t$ weder eine Variable noch eine Konstante. Zeige ${}k\geq n$ .
Zeige, dass die Differenz ${}n-k$ beliebig groß sein kann.

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

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