Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 2/latex
\setcounter{section}{2}
\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 2.6.
}
{} {}
\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
{}
{
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.
}
}
{} {}
Die folgende Aufgabe verwendet den Begriff
\definitionsverweis {abzählbar}{}{.}
\inputaufgabe
{}
{
Es sei $A$ ein \definitionsverweis {abzählbares}{}{} \definitionsverweis {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) | >> |
|---|