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