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

\setcounter{section}{2}

\zwischenueberschrift{Übungsaufgaben}

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

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

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

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Finde möglichst einfache aussagenlogische Ausdrücke, die die folgenden tabellarisch dargestellten Wahrheitsfunktionen ergeben. \wahrheitstabellezweieins{ } {\tabellenzeiledrei {$ p $} {$ q $} {$? $} } {\tabellenzeiledrei {w} {w} {w} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {f} } {\tabellenzeiledrei {f} {f} {w} }\wahrheitstabellezweieins{ } {\tabellenzeiledrei {$ p $} {$ q $} {$? $} } {\tabellenzeiledrei {w} {w} {f} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {w} } {\tabellenzeiledrei {f} {f} {f} }\wahrheitstabellezweieins{ } {\tabellenzeiledrei {$ p $} {$ q $} {$? $} } {\tabellenzeiledrei {w} {w} {f} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {f} } {\tabellenzeiledrei {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.

}
{} {}

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.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

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

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.

}
{} {}