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

}
{} {}

\inputaufgabegibtloesung
{}
{

Wir betrachten Wörter über dem Alphabet
\mathl{\{a,x\}}{} und den Prozess $P$, der in einem solchen Wort jedes Vorkommen von $x$ durch das Wort
\mathl{xax}{} ersetzt. \aufzaehlungzwei {Bestimme das Ergebnis von
\mathl{axxax}{} unter diesem Prozess. } {Diesen Prozess kann man iterieren. Mit
\mathl{P^n(w)}{} bezeichnen wir das Ergebnis, wenn man den Prozess $n$-mal hintereinander auf das Startwort $w$ anwendet. Bestimme die Anzahl der Buchstaben in
\mathl{P^n(w)}{} zum Startwort
\mavergleichskette
{\vergleichskette
{w }
{ = }{x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} }

}
{} {}

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

}
{} {}

\inputaufgabegibtloesung
{}
{

Bei einem Zwei-Personen-Regel-Spiel \zusatzklammer {wie Schach} {} {} spielen zwei Personen \zusatzklammer {$A$ und $B$} {} {} nach gewissen Regeln gegeneinander. Die Personen ziehen abwechselnd. Es ist klar, was eine Mattgewinnstellung für $A$ ist, da ist $A$ am Zug und kann $B$ schlagen und das Spiel ist beendet. Definiere rekursiv, was innerhalb der Menge $S$ aller Stellungen eine Gewinnstellung für $A$ \zusatzklammer {mit $A$ am Zug} {} {} ist.

}
{} {}

\inputaufgabe
{}
{

Artikuliere die beiden folgenden Brüche mit \anfuehrung{tel}{} \aufzaehlungzwei {
\mathl{{ \frac{ 5700 }{ 23 } }}{} } {
\mathl{{ \frac{ 5000 }{ 723 } }}{.} }

}
{} {}

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

Es sei $A$ ein \definitionsverweis {Alphabet}{}{} mit $5$ Symbolen. Wie viele Wörter über $A$ der Länge $7$ gibt es, wenn man nicht zwischen den Leserichtungen unterscheiden kann?

}
{} {}

\inputaufgabe
{}
{

Es sei ein DNA-Doppelstrang der Länge $n$ gegeben. Wie viele Möglichkeiten gibt es dafür bei
\mavergleichskette
{\vergleichskette
{n }
{ = }{1,2 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} wenn man weder die beiden Stränge noch die Leserichtungen unterscheiden kann.

}
{} {}

\inputaufgabegibtloesung
{}
{

Bei einer Leiter sollen die an den Holmen austretenden Sprossenenden farblich markiert werden. Es stehen drei Farben zur Verfügung, und die Leiter hat sechs Sprossen. Wie viele Färbungsmöglichkeiten gibt es, wenn die farblose Leiter weder oben/unten noch links/rechts kennt?

}
{} {}

\inputaufgabe
{}
{

Es seien \mathkor {} {A} {und} {B} {} \definitionsverweis {Alphabete}{}{} und sei \maabb {\varphi} {A} {B } {} eine \definitionsverweis {Abbildung}{}{.} Zeige, dass dies eine natürliche Abbildung \maabbdisp {\tilde{\varphi}} {A^*} {B^* } {} zwischen den Wortmengen induziert. Zeige, dass $\varphi$ genau dann \definitionsverweis {injektiv}{}{} \zusatzklammer {\definitionsverweis {surjektiv}{}{}} {} {} ist, wenn $\tilde{\varphi}$ injektiv \zusatzklammer {surjektiv} {} {} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $A$ ein \definitionsverweis {Alphabet}{}{} mit $4$ Symbolen. Wie viele Wörter der Länge $9$ gibt es über $A$, wenn man Symbole in einem Wort simultan vertauschen kann?

}
{} {}

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

Es seien $V$ und $W$ \definitionsverweis {Aussagenvariablenmengen}{}{} und \maabb {\varphi} {V} {W } {} eine \definitionsverweis {Abbildung}{}{.} Zeige, dass dies eine natürliche Abbildung \maabbdisp {L^\varphi} {L^V} {L^W } {} induziert.

}
{} {}

\inputaufgabe
{}
{

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt. \wahrheitstabellezweieins{ } {\zeileunddrei {$ p $} {$ q $} {$? $} } {\zeileunddrei {w} {w} {w} } {\zeileunddrei {w} {f} {f} } {\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
{}
{

Es seien $V$ und $W$ \definitionsverweis {Aussagenvariablenmengen}{}{,} \maabb {\varphi} {V} {W } {} eine \definitionsverweis {Abbildung}{}{} und \maabb {L^\varphi} {L^V} {L^W } {} die nach Aufgabe 2.22 zugehörige Abbildung. Es sei $\lambda$ eine \definitionsverweis {Wahrheitsbelegung}{}{} auf $W$. Zeige
\mavergleichskettedisp
{\vergleichskette
{I^{\lambda \circ \varphi} }
{ =} { I^\lambda \circ L^\varphi }
{ } { }
{ } { }
{ } { }
} {}{}{.}

}
{} {}

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

Es sei ein DNA-Doppelstrang der Länge $n$ gegeben. Wie viele Möglichkeiten gibt es dafür bei
\mavergleichskette
{\vergleichskette
{n }
{ = }{3,4 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} wenn man weder die Stränge noch die Leserichtungen unterscheiden 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.

}
{} {}