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

}
{} {}

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

}
{} {}

\inputaufgabegibtloesung
{}
{

Es seien
\mathl{x,y,z,w}{} Variablen und $V$ ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme? \aufzaehlungzweireihe {\itemsechs {
\mathl{VxyzVVw}{,} }{
\mathl{VVxyVzw}{,} }{
\mathl{VVxyzVw}{,} }{
\mathl{VxVyVzw}{,} }{
\mathl{xVyVzVw}{,} }{
\mathl{VVVxyzw}{,} } } {\itemsechs {
\mathl{VxyVVzw}{,} }{
\mathl{VVxVyzw}{,} }{
\mathl{VxyVzw}{,} }{
\mathl{Vx VyzVw}{,} } {
\mathl{VxVVyzw}{,} } {
\mathl{Vx yVzVw}{.} } }

}
{} {}

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

}
{} {}

\inputaufgabe
{}
{

Es sei $V$ eine Variablenmenge, $K$ eine Konstantenmenge und $F$ eine Menge aus Funktionssymbolen \zusatzklammer {mit einer gewissen Stelligkeit} {} {.} Es sei
\mavergleichskettedisp
{\vergleichskette
{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.

}
{} {}

\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
{}
{

Diskutiere, ob es sich bei
\mathdisp {n!, \, \binom { n } { k }, \, \pi,\, e^u, x^y,\, 5^x, \, \sqrt{x},\, \heartsuit} { }
um Terme handelt.

}
{} {}

\inputaufgabe
{}
{

Es sei $f$ ein zweistelliges Funktionssymbol und
\mathl{x,y}{} Variablen. Formuliere das Kommutativgesetz \zusatzklammer {für $f$} {} {} als eine Allaussage mit Hilfe der Identität von zwei Termen.

}
{} {}

\inputaufgabe
{}
{

Es sei $K$ ein \definitionsverweis {Körper}{}{} und $V=\{x_1 , \ldots , x_n \}$ eine \definitionsverweis {Variablenmenge}{}{.} Eine \definitionsverweis {Grundtermmenge}{}{} $G$ sei durch $K$ als Konstantenmenge, $V$ als Variablenmenge und den beiden zweistelligen Funktionssymbolen \mathkor {} {+} {und} {\cdot} {} festgelegt. In welcher Beziehung steht die \definitionsverweis {Termmenge}{}{} $T(G)$ zum \definitionsverweis {Polynomring}{}{}
\mathl{K[x_1 , \ldots , x_n]}{.}

}
{} {}

\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?

}
{} {}

\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
{}
{

Formuliere mit arithmetischen Grundsymbolen, Gleichheit, Quantoren und Junktoren die Eigenschaft \zusatzklammer {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
\mathl{n^2-n}{} gerade ist.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{3}
{

Es seien $M,N,L$ Mengen. Stifte eine \definitionsverweis {Bijektion}{}{} zwischen
\mathdisp {\operatorname{Abb} \, { \left( M \times N , L \right) } \text{ und } \operatorname{Abb} \, { \left( M , \operatorname{Abb} \, { \left( N , L \right) } \right) }} { . }

}
{} {}

\inputaufgabe
{2}
{

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
{2}
{

Es sei $f$ ein zweistelliges Funktionssymbol und
\mathl{x,y,z}{} Variablen. Formuliere das Assoziativgesetz \zusatzklammer {für $f$} {} {} als eine Allaussage mit Hilfe der Identität von zwei Termen.

}
{} {}

\inputaufgabe
{3}
{

Eine \definitionsverweis {Grundtermmenge}{}{} $G$ sei durch eine einelementige Konstantenmenge
\mavergleichskette
{\vergleichskette
{K }
{ = }{\{c\} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} eine leere Variablenmenge und eine einelementige einstellige Funktionssymbolmenge
\mavergleichskettedisp
{\vergleichskette
{F_1 }
{ =} { \{f\} }
{ } { }
{ } { }
{ } { }
} {}{}{} gegeben. Zeige durch Induktion, dass es eine bijektive Abbildung \maabbdisp {\varphi} {\N} { T(G) } {} mit
\mavergleichskette
{\vergleichskette
{\varphi(0) }
{ = }{c }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{\varphi(n+1) }
{ = }{ f \varphi(n) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} für alle
\mathl{n \in \N}{} gibt.

}
{} {}

\inputaufgabe
{5}
{

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