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

\setcounter{section}{6}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Entwerfe einen Termstammbamm für den Term
\mathdisp {f \alpha \alpha gx \alpha c_2 f \beta gy \alpha c_1 gfz \beta gc_1 fc_1} { }
wie in Beispiel 6.3.

}
{} {}

\inputaufgabe
{}
{

Wir betrachten die arithmetische Grundtermmenge, die aus den Konstanten \mathkor {} {0} {und} {1} {,} den Variablen
\mathbed {x_n} {}
{n \in \N} {}
{} {} {} {,} dem einstelligen Funktionssymbol $N$ und den beiden zweistelligen Funktionssymbolen \mathkor {} {\alpha} {und} {\mu} {} besteht. Entscheide, ob die folgenden Wörter über diesem Termalphabet Terme sind oder nicht. \aufzaehlungsechs{
\mathl{NNNNNNN01}{,} }{
\mathl{NNNNNNx_1NNNNNNNNNNNx_2}{,} }{
\mathl{\alpha NNNNNN0NNNNNNNNNNN1}{,} }{
\mathl{NNN \mu NNN\mu 0NNNNNNNNNNN1}{,} }{
\mathl{\mu \alpha \mu \alpha \mu \alpha 0101010}{,} }{
\mathl{\alpha \alpha \alpha Nx_1Nx_2x_3x_4x_3}{.} } Schreibe diejenigen Wörter, die Terme sind, mit Klammern, $\prime$, $+$ und $\cdot$.

}
{} {}

\inputaufgabe
{}
{

Erläutere den Unterschied zwischen
\mathl{G=(V,K,F_n, n \in \N_+)}{} und
\mathl{A=V \cup K \cup \bigcup_{n \in \N_+} F_n}{} in Definition 6.2.

}
{} {}

\inputaufgabe
{}
{

Es sei $G$ eine Grundtermmenge und
\mathl{t \in T(G)}{} ein $G$-\definitionsverweis {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. \aufzaehlungdrei{Wenn $u$ eine Variable oder eine Konstante ist, so ist
\mathl{t= u}{.} }{$v$ ist eine Variable oder eine Konstante. }{Wenn \mathkor {} {t_1} {und} {t_2} {} Terme sind, so ist
\mathl{t_1t_2}{} kein Term. }

}
{} {}

\inputaufgabe
{}
{

Es sei $G$ eine Grundtermmenge und $t$ ein $G$-\definitionsverweis {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. \aufzaehlungdrei{Bestimme \mathkor {} {n} {und} {k} {} im Term
\mathdisp {g gxy h fx fz g y fy} { , }
wobei $f$ einstellig, $g$ zweistellig und $h$ dreistellig sei. }{Es sei $t$ weder eine Variable noch eine Konstante. Zeige
\mathl{k \geq n}{.} }{Zeige, dass die Differenz
\mathl{n-k}{} beliebig groß sein kann. }

}
{} {}

\inputaufgabe
{}
{

Für Punkte
\mathl{A,B,C}{} in der Ebene bedeute
\mathl{R(A,B,C)}{} die Rechtwinkligkeit des durch $A,B,C$ gegebenen Dreiecks an der Ecke $A$ und
\mathl{S(A,B,C)}{} die pythagoreische Längenbeziehung. Betrachte die beiden formalen Aussagen
\mathdisp {\forall A \forall B \forall C (R(A,B,C) \longrightarrow S(A,B,C))} { }
und
\mathdisp {\forall A \forall B \forall C R(A,B,C) \longrightarrow \forall A \forall B \forall C S(A,B,C)} { . }
Welche ist (sind) eine Formalisierung des Satzes von Pythagoras, welche ist (sind) wahr?

}
{} {}

\inputaufgabe
{}
{

Es sei $T$ die \definitionsverweis {Termmenge}{}{} zur Konstantenmenge
\mathl{\{0,1\}}{,} zur Variablenmenge
\mathbed {x_i} {}
{i \in I} {}
{} {} {} {} und zur zweistelligen Funktionssymbolmenge
\mathl{\{+, \cdot\}}{.} Definiere eine natürliche Abbildung von $T$ in den Polynomring
\mathl{\Z[x_i: i \in I]}{.} Ist diese Abbildung injektiv? Ist sie surjektiv? Was ist das Bild?

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

Eine \definitionsverweis {Grundtermmenge}{}{} sei durch die Variablenmenge
\mathl{V=\{x,y,z\}}{,} eine Konstantenmenge
\mathl{K=\{c_1,c_2\}}{,} die einstelligen Funktionssymbole
\mathl{F_1=\{f,g\}}{} und die zweistelligen Funktionssymbole
\mathl{F_2=\{\alpha, \beta, \gamma\}}{} gegeben. Entwerfe einen Termstammbaum für den Term
\mathdisp {gf \beta \beta \alpha fxy \gamma c_1 z ggc_2} { . }

}
{} {}

\inputaufgabe
{}
{

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

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