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

\setcounter{section}{2}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Es sei
\mathl{S=\{A,B,C\}}{.} Betrachte die rekursiv definierte Teilmenge
\mathl{T \subseteq S^*}{,} die wie folgt festgelegt wird. \aufzaehlungzwei {Jedes Element aus $S$ gehört zu $T$. } {Wenn
\mathl{X,Y \in T}{} sind, so gehört auch
\mathl{XXY}{} zu $T$. } Bestimme, welche der folgenden Wörter zu $T$ gehören.
\mathdisp {A,\, ABABC,\, AABBB,\, AABAABA,\, AAAA,\, AABABAAB,\, AAAAAABBB} { . }
Zeige die folgenden Aussagen. \aufzaehlungvier{Jedes Element aus $T$ besitzt eine ungerade Wortlänge. }{Jede ungerade Zahl kommt als Wortlänge eines Elements aus $T$ vor. }{Es gibt Elemente in $T$, die auf mehrfache Weise generiert werden können. }{Jedes Wort
\mathl{t \in T\setminus S}{} beginnt mit zwei gleichen Buchstaben. }

}
{} {}

\inputaufgabe
{}
{

Ein Geldfälscher stellt $3$- und $7$-Euro-Scheine her. \aufzaehlungdrei{Beschreibe die Menge $M$ der vollen Eurobeträge, die er mit seinen Scheinen \zusatzklammer {exakt} {} {} begleichen kann, als eine rekursive Teilmenge von $\N$, also durch eine Startmenge und Rekursionsvorschriften. }{Zeige, dass es nur endlich viele Beträge gibt, die er nicht begleichen kann. Was ist der höchste Betrag, den er nicht begleichen kann? }{Was ist der kleinste Betrag, den er auf zwei verschiedene Weisen begleichen kann. }

}
{} {}

\inputaufgabe
{}
{

Wir betrachten die rekursiv definierte Teilmenge $M$ von
\mathl{\Z^2=\Z \times \Z}{,} die durch die Startmenge
\mavergleichskette
{\vergleichskette
{S }
{ = }{\{ (0,0)\} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und die folgenden Rekursionsvorschriften gegeben ist. \aufzaehlungdrei{Wenn
\mathl{P \in M}{} ist, so ist auch
\mathl{P + \left( 3 , \, 0 \right) \in M}{.} }{Wenn
\mathl{P \in M}{} ist, so ist auch
\mathl{P + \left( -1 , \, -2 \right) \in M}{.} }{Wenn
\mathl{P \in M}{} ist, so ist auch
\mathl{P + \left( 2 , \, 7 \right) \in M}{.} } Zeige die folgenden Aussagen. \aufzaehlungsechs{Der Punkt $\left( -3 , \, 0 \right)$ gehört zu $M$. }{Der Punkt $\left( 0 , \, 3 \right)$ gehört zu $M$. }{Der Punkt $\left( 0 , \, -3 \right)$ gehört zu $M$. }{Ein Punkt
\mathl{Q \in M}{} besitzt im Allgemeinen keine eindeutige Generierung. }{Jeder Punkt
\mathl{Q=(a,b) \in M}{} besitzt die Eigenschaft, dass
\mathl{a+b}{} ein Vielfaches von $3$ ist. }{Wenn
\mathl{Q=(a,b) \in \Z^2}{} die Eigenschaft besitzt, dass
\mathl{a+b}{} ein Vielfaches von $3$ ist, so ist
\mathl{Q \in M}{.} }

}
{} {}

\inputaufgabe
{}
{

Eine Geschenkfabrik verfügt über leere, offene Schachteln \zusatzklammer {unterschiedlicher Größe} {} {} und über Maschinen, die die beiden folgenden Abläufe durchführen können. \aufzaehlungzwei {Eine offene Schachtel schließen. } {Eine geschlossene Schachtel in eine größere offene Schachtel \zusatzklammer {in der schon andere Schachteln liegen dürfen} {} {} hineinlegen. } Ein Produkt der Fabrik ist das Ergebnis aus diesen \zusatzklammer {beliebig verschachtelten} {} {} Abläufen.




\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Rechtecke.png} }
\end{center}
\bildtext {} }

\bildlizenz { Rechtecke.png } {} {Mgausman} {Commons} {CC-by-sa 3.0} {}

\aufzaehlungsechs{Definiere \zusatzklammer {induktiv} {} {} die Schachtelanzahl eines Produkts der Fabrik. }{Definiere die Verschachtelungstiefe eines Produkts der Fabrik. }{Definiere die Arbeitsschrittanzahl eines Produkts der Fabrik. }{Bestimme die Schachtelanzahl, die Verschachtelungstiefe und die Arbeitsschrittanzahl des gezeigten Produkts \zusatzklammer {die Schachteln seien geschlossen} {} {.} }{Zeige, dass jedes Produkt der Fabrik nur maximal eine offene Schachtel enthält. }{Welche Gleichheitsbegriffe sind für die Produkte der Firma sinnvoll? Welche Produkte lassen sich auf unterschiedliche Arten generieren? Sind die unter (1), (2), (3) definierten Begriffe wohldefiniert, also unabhängig vom Generierungsprozess? }

}
{} {}

\inputaufgabe
{}
{

Erstelle eine rekursive Definition für die Menschheit.

}
{} {}

Die folgende Aufgabe verwendet den Begriff \definitionsverweis {abzählbar}{}{.}

Eine Menge $M$ heißt \definitionswort {abzählbar}{,} wenn sie leer ist oder wenn es eine \definitionsverweis {surjektive Abbildung}{}{} \maabbdisp {\varphi} {\N} {M } {} gibt.

Für diesen Begriff und das Mächtigkeitskonzept im Allgemeinen siehe den Anhang über Mächtigkeiten. Eine Menge $M$ ist genau dann abzählbar unendlich, wenn es eine bijektive Abbildung \maabbdisp {\psi} {\N} {M } {} gibt. Die Menge der rationalen Zahlen sind abzählbar unendlich, die Menge der reellen Zahlen nicht.

\inputaufgabe
{}
{

Es sei $A$ ein \definitionsverweis {abzählbares}{}{} \definitionsverweis {Alphabet}{}{.} Zeige, dass auch die Menge $A^*$ der Wörter über $A$ abzählbar ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass das erste Symbol in jeder Aussage aus $L^V$ entweder eine \definitionsverweis {Aussagenvariable}{}{}
\mathl{p \in V}{} oder das Negationszeichen $\neg$ oder eine linksseitige Klammer $($ ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Beweise durch Induktion über den rekursiven Aufbau der Sprache $L^V$, dass in jeder Aussage
\mathl{\alpha \in L^V}{} die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.

}
{} {}

\inputaufgabe
{}
{

Zeichne einen Abstammungsbaum für die Aussage
\mathdisp {((p) \wedge (\neg (q))) \wedge (\neg (r))} { . }

}
{} {}

\inputaufgabe
{}
{

Zeichne einen Abstammungsbaum für die Aussage
\mathdisp {( ( \neg(\neg(p)) ) \leftrightarrow (\neg(q)) ) \vee ( (p) \rightarrow ( ( \neg(r) ) \wedge ( \neg(q) ) ) )} { . }

}
{} {}

\inputaufgabe
{}
{

Es sei ein aussagenlogischer Ausdruck der Form
\mathdisp {( ... ) * (...)} { }
gegeben, wobei
\mathl{*= \wedge, \vee, \rightarrow, \leftrightarrow}{} ist. Es sei vorausgesetzt, dass die Klammer $)$ links von $*$ die linke öffnende Klammer abschließt \zusatzklammer {wie ist das zu definieren?} {} {.} Zeige, dass dann die Zeichenketten innerhalb der beiden Klammern Aussagen sind, und dass der Gesamtausdruck durch einen dritten Schritt im \definitionsverweis {rekursiven Aufbau}{}{} der Sprache aus diesen beiden Aussagen entstanden ist. Zeige, dass dies ohne die Klammervoraussetzung nicht der Fall sein muss.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass der letzte Konstruktionsschritt einer Aussage eindeutig bestimmt ist. Folgere, dass sich die rekursive Entstehung einer Aussage eindeutig rekonstruieren lässt.

}
{} {}

\inputaufgabegibtloesung
{}
{

Definiere zu jeder Aussage
\mathl{\alpha \in L^V}{} die Menge
\mathl{\operatorname{ Var}_{ } ^{ } { \left( \alpha \right) }}{} der in $\alpha$ vorkommenden \definitionsverweis {Aussagenvariablen}{}{.}

}
{} {}

\inputaufgabe
{}
{

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt. \wahrheitstabellezweieins{ } {\zeileunddrei {$ p $} {$ q $} {$? $} } {\zeileunddrei {w} {w} {f} } {\zeileunddrei {w} {f} {w} } {\zeileunddrei {f} {w} {f} } {\zeileunddrei {f} {f} {f} }

}
{} {}

\inputaufgabe
{}
{

Bestimme den Wahrheitswert der Aussage
\mathdisp {( ( \neg(\neg(p)) ) \leftrightarrow (\neg(q)) ) \vee ( (p) \rightarrow ( ( \neg(r) ) \wedge ( \neg(q) ) ) )} { }
bei der Belegung
\mathl{\lambda(p)=0}{} und
\mathl{\lambda(q)=\lambda(r)=1}{.}

}
{} {}

\inputaufgabe
{}
{

Bestimme zu jedem Ausdruck
\mathl{\alpha \in L^V}{} mit maximal acht Zeichen zur \definitionsverweis {Aussagenvariablenmenge}{}{}
\mathl{V=\{p,q\}}{,} ob er bei der durch
\mathl{\lambda(p)=1,\, \lambda(q)=0}{} fetgelegten Interpretation wahr oder falsch ist.

}
{} {}

\inputaufgabe
{}
{

Finde möglichst einfache aussagenlogische Ausdrücke, die die folgenden tabellarisch dargestellten Wahrheitsfunktionen ergeben. \wahrheitstabellezweieins{ } {\zeileunddrei {$ p $} {$ q $} {$? $} } {\zeileunddrei {w} {w} {w} } {\zeileunddrei {w} {f} {f} } {\zeileunddrei {f} {w} {f} } {\zeileunddrei {f} {f} {w} }\wahrheitstabellezweieins{ } {\zeileunddrei {$ p $} {$ q $} {$? $} } {\zeileunddrei {w} {w} {f} } {\zeileunddrei {w} {f} {f} } {\zeileunddrei {f} {w} {w} } {\zeileunddrei {f} {f} {f} }\wahrheitstabellezweieins{ } {\zeileunddrei {$ p $} {$ q $} {$? $} } {\zeileunddrei {w} {w} {f} } {\zeileunddrei {w} {f} {f} } {\zeileunddrei {f} {w} {f} } {\zeileunddrei {f} {f} {f} }

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die \definitionsverweis {Interpretation einer Aussage}{}{}
\mathl{\alpha \in L^V}{} nur von der \definitionsverweis {Wahrheitsbelegung}{}{} der in $\alpha$ vorkommenden \definitionsverweis {Aussagenvariablen}{}{} abhängt.

}
{} {}

\inputaufgabe
{}
{

Die Aussage
\mathl{\alpha \vee \neg \alpha}{} ist eine Tautologie. Ist somit die Frage \anfuehrung{Gilt
\mathl{\alpha}{} oder
\mathl{\neg \alpha}{?}}{} unsinnig?

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{4 (1+2+1)}
{

Ein Geldfälscher stellt $4$-, $9$- und $11$-Euro-Scheine her. \aufzaehlungdrei{Beschreibe die Menge $M$ der vollen Eurobeträge, die er mit seinen Scheinen \zusatzklammer {exakt} {} {} begleichen kann, als eine rekursive Teilmenge von $\N$, also durch eine Startmenge und Rekursionsvorschriften. }{Zeige, dass es nur endlich viele Beträge gibt, die er nicht begleichen kann. Was ist der höchste Betrag, den er nicht begleichen kann? }{Was ist der kleinste Betrag, den er auf zwei verschiedene Weisen begleichen kann. }

}
{} {}

\inputaufgabe
{2}
{

Zeichne einen Abstammungsbaum für die Aussage
\mathdisp {((( \neg (\neg (p))) \rightarrow (\neg ( q))) \vee (\neg (r))) \leftrightarrow ( (\neg (r) ) \wedge ( q ))} { . }

}
{} {}

\inputaufgabe
{2}
{

Bestimme den Wahrheitswert der Aussage
\mathdisp {((( \neg (\neg (p))) \rightarrow (\neg ( q))) \vee (\neg (r))) \leftrightarrow ( (\neg (r) ) \wedge ( q ))} { }
bei der Belegung
\mathl{\lambda(p)=\lambda(r)=0}{} und
\mathl{\lambda(q)=1}{.}

}
{} {}

\inputaufgabe
{3}
{

Es seien
\mathl{p_1 , \ldots , p_n}{} \definitionsverweis {Aussagenvariablen}{}{} und
\mathl{\beta_1 , \ldots , \beta_n}{} Aussagen. Zeige durch Induktion über den Aufbau der aussagenlogischen Sprache, dass man zu jeder Aussage $\alpha$ in den gegebenen Variablen eine Aussage erhält, wenn man jedes Vorkommen von $p_i$ in $\alpha$ durch $\beta_i$ ersetzt.

}
{} {}

\inputaufgabe
{4}
{

Beweise durch Induktion über den rekursiven Aufbau der Sprache $L^V$, dass in jeder Aussage
\mathl{\alpha \in L^V}{} und für jedes Symbol $s$ in $\alpha$, das keine Klammer ist, folgendes zutrifft: Links von $s$ ist die Anzahl der linken Klammern mindestens so groß wie die Anzahl der rechten Klammern.

}
{} {}