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

\setcounter{section}{3}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Beweise mittels Wahrheitstabellen, dass die folgenden Aussagen Tautologien sind.\zusatzfussnote {Wir verzichten hier und im Folgenden häufig auf Klammern, um die Lesbarkeit zu erhöhen. Gemeint sind immer die korrekt geklammerten Aussagen} {.} {} \aufzaehlungfuenf{ $(\alpha \wedge \alpha) \leftrightarrow \alpha$. }{ $\alpha \wedge \beta \rightarrow \alpha$. }{ $\alpha \rightarrow ( \beta \rightarrow \alpha)$. }{ $(\alpha \rightarrow ( \beta \rightarrow \gamma)) \rightarrow ((\alpha \rightarrow \beta) \rightarrow ( \alpha \rightarrow \gamma))$. }{ $(\alpha \rightarrow \beta) \leftrightarrow (\neg \alpha \vee \beta)$. }

}
{} {}

\inputaufgabe
{}
{

Man beweise mittels Wahrheitstabellen die \stichwort {Regeln von de Morgan} {,} nämlich dass
\mathdisp {\neg (\beta \vee \gamma) \leftrightarrow (\neg \beta \wedge \neg \gamma)} { }
und
\mathdisp {\neg (\beta \wedge \gamma) \leftrightarrow ( \neg \beta \vee \neg \gamma)} { }
\definitionsverweis {Tautologien}{}{} sind.

}
{} {}

\inputaufgabe
{}
{

Skizziere ein Entscheidungsverfahren, das für eine gegebene Aussage
\mathl{\alpha \in L^V}{} entscheidet, ob es sich um eine aussagenlogische \definitionsverweis {Tautologie}{}{} handelt oder nicht.

}
{} {}

\inputaufgabe
{}
{

Zu einer Aussage
\mathl{\alpha \in L^V}{} und
\mathl{n \in \N}{} bezeichne
\mathl{\neg^n \alpha}{} die $n$-fache Negation von $\alpha$. Zeige, dass
\mathl{\neg^n \alpha \leftrightarrow \neg^m \alpha}{} genau dann \definitionsverweis {allgemeingültig}{}{} ist, wenn
\mathl{n-m}{} ein Vielfaches von $2$ ist.

}
{} {}

\inputaufgabe
{}
{

Es seien
\mathl{p_1 , \ldots , p_n}{} \definitionsverweis {Aussagenvariablen}{}{} und
\mathl{\beta_1 , \ldots , \beta_n}{} Aussagen. Zeige, dass man, wenn man in einer allgemeingültigen Aussage $\alpha$ jedes Vorkommen von $p_i$ durch $\beta_i$ ersetzt, wieder eine allgemeingültige Aussage erhält. Zeige, dass die Umkehrung davon nicht gilt.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass eine Aussage
\mathl{\alpha \in L^V}{} genau dann eine \definitionsverweis {Kontradiktion}{}{} ist, wenn
\mathl{\neg \alpha}{} eine Tautologie ist.

}
{} {}

\inputaufgabe
{}
{

Man gebe möglichst viele Beispiele für aussagenlogische Kontradiktionen an.

}
{} {}

\inputaufgabe
{}
{

Es sei $V$ eine Menge von \definitionsverweis {Aussagenvariablen}{}{} und $\alpha$ eine Aussage in der zugehörigen formalen Sprache $L^V$. Es sei \maabbdisp {\varphi} {V} {V } {} eine \definitionsverweis {Abbildung}{}{} und es sei $\varphi(\alpha)$ diejenige Aussage, die entsteht, wenn man in $\alpha$ jede Aussagenvariable $p$ durch $\varphi(p)$ ersetzt. Zeige die folgenden Aussagen. \aufzaehlungvier{Wenn $\alpha$ eine \definitionsverweis {Tautologie}{}{} ist, so ist auch $\varphi(\alpha)$ eine Tautologie. }{Wenn $\varphi$ \definitionsverweis {injektiv}{}{} ist, so ist $\alpha$ genau dann eine Tautologie, wenn dies für $\varphi(\alpha)$ gilt. }{$\varphi(\alpha)$ kann eine Tautologie sein, auch wenn $\alpha$ keine Tautologie ist. }{Die Aussagen gelten ebenso, wenn man überall Tautologie durch \definitionsverweis {Kontradiktion}{}{} ersetzt. }

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Teilmenge, die ausschließlich aus Aussagenvariablen oder aus negierten Aussagenvariablen besteht, wobei jede Aussagenvariable höchstens direkt oder in ihrer Negation auftritt. Zeige, dass $\Gamma$ \definitionsverweis {erfüllbar}{}{} ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Wenn Karl an Susanne denkt, bekommt er feuchte Hände, einen Kloß im Hals und einen roten Kopf. Einen roten Kopf bekommt er genau dann, wenn er an Susanne denkt oder wenn er das leere Tor nicht trifft. Wenn Karl das leere Tor trifft, bekommt er feuchte Hände. Karl bekommt den Ball vor dem leeren Tor. Kurz darauf bekommt er feuchte Hände, einen roten Kopf, aber keinen Kloß im Hals. Hat er an Susanne gedacht? Hat er das leere Tor getroffen?

}
{} {}

\inputaufgabegibtloesung
{}
{

Folgende Aussagen seien bekannt. \aufzaehlungsieben{Der frühe Vogel fängt den Wurm. }{Doro wird nicht von Lilly gefangen. }{Lilly ist ein Vogel oder ein Igel. }{Für Igel ist 5 Uhr am Morgen spät. }{Doro ist ein Wurm. }{Für Vögel ist 5 Uhr am Morgen früh. }{Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs. } Beantworte folgende Fragen. \aufzaehlungdrei{Ist Lilly ein Vogel oder ein Igel? }{Ist sie ein frühes oder ein spätes Tier? }{Fängt der späte Igel den Wurm? }

}
{} {}

\inputaufgabegibtloesung
{}
{

Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest. \aufzaehlungvier{Ein Tag heißt \stichwort {sockenzerstreut} {,} wenn er verschiedene Socken anhat. }{Ein Tag heißt \stichwort {schuhzerstreut} {,} wenn er verschiedene Schuhe anhat. }{Ein Tag heißt \stichwort {zerstreut} {,} wenn er sockenzerstreut oder schuhzerstreut ist. }{Ein Tag heißt \stichwort {total zerstreut} {,} wenn er sowohl sockenzerstreut als auch schuhzerstreut ist. }

a) Vom Jahr
\mathl{2015}{} weiß man, dass $17$ Tage sockenzerstreut und $11$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?

b) Vom Jahr
\mathl{2013}{} weiß man, dass $270$ Tage sockenzerstreut und $120$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?

c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.

}
{} {}

Die folgenden Aufgaben verwenden den Begriff einer Äquivalenzrelation. Dieser ist für viele Konstruktionen in der Mathematik und in der mathematischen Logik entscheidend. Siehe den Anhang zu Äquivalenzrelationen.

Eine \definitionswort {Äquivalenzrelation}{} auf einer Menge $M$ ist eine \definitionsverweis {Relation}{}{}
\mavergleichskette
{\vergleichskette
{R }
{ \subseteq }{M \times M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} die die folgenden drei Eigenschaften besitzt \zusatzklammer {für beliebige
\mavergleichskettek
{\vergleichskettek
{x,y,z }
{ \in }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{}} {} {}. \aufzaehlungdrei{Es ist
\mavergleichskette
{\vergleichskette
{x }
{ \sim }{x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \zusatzklammer {\definitionswort {reflexiv}{}} {} {.} }{Aus
\mavergleichskette
{\vergleichskette
{x }
{ \sim }{y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} folgt
\mavergleichskette
{\vergleichskette
{y }
{ \sim }{x }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \zusatzklammer {\definitionswort {symmetrisch}{}} {} {.} }{Aus
\mavergleichskette
{\vergleichskette
{x }
{ \sim }{y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{y }
{ \sim }{z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} folgt
\mavergleichskette
{\vergleichskette
{x }
{ \sim }{z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \zusatzklammer {\definitionswort {transitiv}{}} {} {.} } Dabei bedeutet
\mavergleichskette
{\vergleichskette
{x }
{ \sim }{y }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} dass das Paar
\mathl{(x,y)}{} zu $R$ gehört.

\inputaufgabe
{}
{

Auf den ganzen Zahlen $\Z$ lebe eine Kolonie von Flöhen, und jeder Flohsprung geht fünf Einheiten weit (in beide Richtungen). Wie viele Flohpopulationen gibt es? Wie kann man einfach charakterisieren, ob zwei Flöhe zur gleichen Population gehören oder nicht?

}
{} {}

\inputaufgabe
{}
{

Wir betrachten die ganzen Zahlen $\Z$ und eine fixierte natürliche Zahl $a \geq 0$. Zeige, dass auf $\Z$ durch
\mathdisp {x \sim y, \text{ wenn die Differenz } x-y \text{ ein Vielfaches von } a \text { ist}} { , }
eine \definitionsverweis {Äquivalenzrelation}{}{} definiert wird. Wie viele \definitionsverweis {Äquivalenzklassen}{}{} gibt es?

}
{} {}

\inputaufgabe
{}
{

Es sei $K$ ein \definitionsverweis {Körper}{}{,} $V$ ein $K$-\definitionsverweis {Vektorraum}{}{} und
\mavergleichskette
{\vergleichskette
{U }
{ \subseteq }{V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ein \definitionsverweis {Untervektorraum}{}{.} Wir betrachten die \definitionsverweis {Relation}{}{} auf $V$, die durch
\mathdisp {v_1 \sim v_2 \text{ genau dann, wenn } v_1 - v_2 \in U} { }
definiert ist. Zeige, dass diese Relation eine \definitionsverweis {Äquivalenzrelation}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $K$ ein \definitionsverweis {Körper}{}{} und $V$ ein $K$-\definitionsverweis {Vektorraum}{}{.} Zeige, dass die \definitionsverweis {Relation}{}{} auf $V$, die durch
\mathdisp {v \sim w, \text{ falls es ein } \lambda \in K, \lambda \neq 0, \text{ mit } v = \lambda w \text{ gibt }} { }
eine \definitionsverweis {Äquivalenzrelation}{}{} ist. Was sind die Äquivalenzklassen?

}
{} {}

\inputaufgabe
{}
{

Wir betrachten für je zwei Teilmengen
\mavergleichskette
{\vergleichskette
{A,B }
{ \subseteq }{\N }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die \definitionsverweis {symmetrische Differenz}{}{}
\mavergleichskettedisp
{\vergleichskette
{ A \triangle B }
{ \defeq} {(A \setminus B) \cup (B \setminus A) }
{ } { }
{ } { }
{ } { }
} {}{}{.} Wir setzen
\mavergleichskette
{\vergleichskette
{A }
{ \sim }{B }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} falls
\mathl{A \triangle B}{} \definitionsverweis {endlich}{}{} ist. Zeige, dass dadurch eine \definitionsverweis {Äquivalenzrelation}{}{} auf
\mathl{\mathfrak {P} \, (\N )}{} definiert wird.

}
{} {}

\inputaufgabegibtloesung
{}
{

Betrachte auf $\Z \times (\Z \setminus \{0\})$ die \definitionsverweis {Relation}{}{}
\mathdisp {(a,b) \sim (c,d),\, \text{ falls } ad = bc \text{ ist}} { . }

a) Zeige, dass $\sim$ eine \definitionsverweis {Äquivalenzrelation}{}{} ist.

b) Zeige, dass es zu jedem $(a,b)$ ein äquivalentes Paar $(a',b')$ mit
\mavergleichskette
{\vergleichskette
{ b' }
{ > }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt.

c) Es sei $M$ die Menge der \definitionsverweis {Äquivalenzklassen}{}{} dieser Äquivalenzrelation. Wir definieren eine Abbildung \maabbeledisp {\varphi} {\Z} {M } {z} { [ (z,1)] } {.} Zeige, dass $\varphi$ \definitionsverweis {injektiv}{}{} ist.

d) Definiere auf $M$ \zusatzklammer {aus Teil c} {} {} eine \definitionsverweis {Verknüpfung}{}{} $+$ derart, dass $M$ mit dieser Verknüpfung und mit $[(0,1)]$ als neutralem Element eine \definitionsverweis {Gruppe}{}{} wird, und dass für die Abbildung $\varphi$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ \varphi(z_1 + z_2) }
{ =} {\varphi(z_1) + \varphi(z_2) }
{ } { }
{ } { }
{ } { }
} {}{}{} für alle
\mavergleichskette
{\vergleichskette
{ z_1,z_2 }
{ \in }{ \Z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt.

}
{} {}

\inputaufgabegibtloesung
{}
{

Seien \mathkor {} {M} {und} {N} {} Mengen und sei \maabb {f} {M} {N } {} eine Abbildung. Zeige, dass durch die Festlegung
\mavergleichskettedisp
{\vergleichskette
{x }
{ \sim} {y }
{ } { }
{ } { }
{ } { }
} {}{}{,} wenn
\mavergleichskettedisp
{\vergleichskette
{f(x) }
{ =} {f(y) }
{ } { }
{ } { }
{ } { }
} {}{}{,} eine \definitionsverweis {Äquivalenzrelation}{}{} auf $M$ definiert wird.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $M$ die Menge der zweimal stetig differenzierbaren Funktionen von $\R$ nach $\R$. Definiere auf $M$ eine Relation durch
\mathdisp {f \sim g \text{ falls } f(0)=g(0),\, f'(0)=g'(0) \text{ und } f^{\prime \prime}(1) = g^{\prime \prime} (1)} { . }

a) Zeige, dass dies eine \definitionsverweis {Äquivalenzrelation}{}{} ist.

b) Finde für jede Äquivalenzklasse dieser Äquivalenzrelation einen polynomialen Vertreter.

c) Zeige, dass diese Äquivalenzrelation mit der Addition von Funktionen verträglich ist.

d) Zeige, dass diese Äquivalenzrelation nicht mit der Multiplikation von Funktionen verträglich ist.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{U }
{ \subseteq }{ \R^n }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Teilmenge mit der induzierten \definitionsverweis {Metrik}{}{.} Betrachte die \definitionsverweis {Relation}{}{} $R$ auf $U$, wobei $xRy$ bedeutet, dass es eine \definitionsverweis {stetige Abbildung}{}{} \maabbeledisp {\gamma} {[0,1]} {\R^n } {t} { \gamma(t) } {,} mit \mathkor {} {\gamma(0)=x} {und} {\gamma(1)=y} {} gibt. Zeige, dass dies eine \definitionsverweis {Äquivalenzrelation}{}{} auf $U$ ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $M$ eine Menge und $\sim$ eine \definitionsverweis {Äquivalenzrelation}{}{} auf $M$ mit den \definitionsverweis {Äquivalenzklassen}{}{} $[x]$. Es sei $I$ die Menge aller Äquivalenzklassen. Zeige folgende Aussagen. \aufzaehlungzwei {Es ist $x\sim y$ genau dann, wenn $[x]=[y]$ ist, und dies gilt genau dann, wenn $[x] \cap [y] \neq \emptyset$. } {$M = \bigcup_{x\in I} [x]$ ist eine disjunkte Vereinigung.}

}
{} {}


\inputaufgabe
{}
{

Es sei $B$ ein Blatt Papier \zusatzklammer {oder ein Taschentuch} {} {.} Man versuche, sich die folgenden \definitionsverweis {Äquivalenzrelationen}{}{} auf $B$ und die zugehörige \definitionsverweis {Identifizierungsabbildungen}{}{} vorzustellen \zusatzklammer {möglichst geometrisch} {} {.} \aufzaehlungacht{Die vier Eckpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent. }{Alle Randpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent. }{Jeder Punkt des linken Randes ist äquivalent zu seinem horizontal gegenüber liegenden Punkt am rechten Rand, ansonsten sind die Punkte nur zu sich selbst äquivalent. }{Jeder Punkt des linken Randes ist äquivalent zu seinem horizontal gegenüber liegenden Punkt am rechten Rand und jeder Punkt des oberen Randes ist äquivalent zu seinem vertikal gegenüber liegenden Punkt, ansonsten sind die Punkte nur zu sich selbst äquivalent. }{Jeder Punkt des Randes ist äquivalent zu seinem punktsymmetrisch \zusatzklammer {bezüglich des Mittelpunktes des Blattes} {} {} gegenüber liegenden Punkt, ansonsten sind die Punkte nur zu sich selbst äquivalent. }{Es sei $K$ ein Kreis \zusatzklammer {d.h. eine Kreislinie} {} {} auf dem Blatt. Alle Kreispunkte seien untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent. }{Es gebe zwei Punkte $P \neq Q$, die untereinander äquivalent seien, ansonsten sind die Punkte nur zu sich selbst äquivalent. }{Es sei $H$ die horizontale Halbierungsgerade des Blattes. Zwei Punkte sind genau dann äquivalent, wenn sie achsensymmetrisch zu $H$ sind. }

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die Beziehung
\mathdisp {\alpha \sim \beta , \text{ falls } (\alpha) \leftrightarrow (\beta) \text{ allgemeingültig ist}} { , }
eine \definitionsverweis {Äquivalenzrelation}{}{} auf $L^V$ definiert. Zeige, dass sowohl alle \definitionsverweis {Tautologien}{}{} als auch alle Kontradiktionen eine \definitionsverweis {Äquivalenzklasse}{}{} bilden. Wie viele Äquivalenzklassen besitzt diese Äquivalenzrelation, falls $V$ $n$ Elemente besitzt?

}
{} {}

\inputaufgabe
{}
{

Es sei $\sim$ die in Aufgabe 3.24 diskutierte Äquivalenzrelation auf $L^V$ und sei $Q$ die zugehörige \definitionsverweis {Quotientenmenge}{}{.} Es sei $\lambda$ eine \definitionsverweis {Wahrheitsbelegung}{}{} auf $V$. Zeige, dass dies eine wohldefinierte Abbildung auf $Q$ induziert.

}
{} {}

Unter einer \definitionswort {disjunktiven Normalform}{} versteht man einen aussagenlogischen Ausdruck, der eine $\vee$-Verknüpfung von Ausdrücken der Form
\mathl{\pm p_1 \wedge \ldots \wedge \pm p_n}{} ist, wobei $\pm$ bedeutet, dass entweder die Aussagenvariable direkt oder in ihrer Negation genommen wird.

\inputaufgabegibtloesung
{}
{

Man bringe die Aussage
\mathdisp {((p\vee (r\rightarrow q)) \wedge (q\rightarrow p) ) \vee (((p \wedge \neg q) \wedge (\neg r \vee \neg p) ) \wedge ( r \rightarrow ( p \vee \neg q)))} { }
in \definitionsverweis {disjunktive Normalform}{}{.}

}
{} {}

\inputaufgabe
{}
{

Es sei $\sim$ die in Aufgabe 3.24 diskutierte Äquivalenzrelation auf $L^V$. Zeige, dass jede \definitionsverweis {Äquivalenzklasse}{}{} $[\alpha]$ einen Repräsentanten in \definitionsverweis {disjunktiver Normalform}{}{} besitzt.

}
{} {}

\inputaufgabe
{}
{

Es sei $\alpha$ ein aussagenlogischer Ausdruck in \definitionsverweis {disjunktive Normalform}{}{,} in dem die Aussagenvariablen
\mathl{p_1 , \ldots , p_n}{} vorkommen. Zeige, dass $\alpha$ genau dann eine \definitionsverweis {Tautologie}{}{} ist, wenn $\alpha$ die $\vee$-Verknüpfung von sämtlichen Kombinationen
\mathl{\pm p_1 \wedge \ldots \wedge \pm p_n}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{T}{} die Menge aller \definitionsverweis {Tautologien}{}{} in einer aussagenlogischen Sprache $L^V$. Zeige
\mavergleichskette
{\vergleichskette
{ T^{ \vDash } }
{ = }{ T }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

}
{} {}

\inputaufgabe
{}
{

Die Ausdrucksmenge
\mavergleichskette
{\vergleichskette
{ \Gamma }
{ \subseteq }{ L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} enthalte eine \definitionsverweis {Kontradiktion}{}{.} Zeige
\mavergleichskette
{\vergleichskette
{ \Gamma^{ \vDash } }
{ = }{ L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

}
{} {}

\inputaufgabe
{}
{

Interpretiere die Wahrheitstabellen zu den Junktoren $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$ als Wertetabellen von Funktionen. Was sind die Definitions-, die Werte- und die Bildmengen dieser Funktionen?

}
{} {}

\inputaufgabe
{}
{

Zeige, dass die axiomatisch fixierten syntaktischen Grund\-tautologien \definitionsverweis {allgemeingültig}{}{} sind

}
{} {}

\inputaufgabegibtloesung
{}
{

Beweise die aussagenlogische Tautologie
\mathdisp {\vdash \alpha\rightarrow (\beta \rightarrow \alpha \wedge \beta)} { }
aus den aussagenlogischen \definitionsverweis {Axiomen}{}{.}

}
{} {}

\inputaufgabe
{}
{

Zeige das Assoziativgesetz für die Konjunktion, also
\mathdisp {\vdash { \left( \alpha \wedge \beta \right) } \wedge \gamma \rightarrow \alpha \wedge { \left( \beta \wedge \gamma \right) }} { . }

}
{} {}

\inputaufgabe
{}
{

Es seien
\mathl{\alpha_1 , \ldots , \alpha_n}{} Ausdrücke und es seien
\mathl{i_1 , \ldots , i_k}{} Elemente aus
\mathl{\{1 , \ldots , n \}}{.} Zeige, dass
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \alpha_{i_1} \wedge \ldots \wedge \alpha_{i_k}} { }
gilt.

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige
\mathdisp {\vdash \alpha \wedge \neg \alpha \rightarrow \beta} { }
unter Verwendung von
\mathdisp {\vdash \gamma \wedge \delta \rightarrow \delta \wedge \gamma} { }
\zusatzklammer {Lemma 3.14} {} {.}

}
{} {}

\inputaufgabe
{}
{

Zu einer Aussage
\mathl{\alpha \in L^V}{} und
\mathl{n \in \N}{} bezeichne
\mathl{\neg^n \alpha}{} die $n$-fache Negation von $\alpha$. Zeige, dass
\mathl{\vdash \neg^n \alpha \rightarrow \neg^m \alpha}{} genau dann gilt, wenn
\mathl{n-m}{} ein Vielfaches von $2$ ist.

}
{} {}

\inputaufgabe
{}
{

Zeige die folgende Ableitungsregel für die Aussagenlogik.

Aus
\mathl{\vdash \alpha \rightarrow ( \beta \rightarrow \gamma)}{} und
\mathl{\vdash \delta \rightarrow \beta}{} folgt
\mathl{\vdash \alpha \rightarrow (\delta \rightarrow \gamma)}{.}

}
{} {}

\inputaufgabe
{}
{

Zeige, dass aus
\mathl{\vdash \alpha_1 , \ldots , \vdash \alpha_n}{} und
\mathl{\vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \beta}{} die Ableitbarkeit
\mathl{\vdash \beta}{} folgt.

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige, dass eine Regel der Form

Wenn
\mathl{\vdash \alpha}{,} dann
\mathl{\vdash \beta}{} gelten kann, ohne dass
\mathl{\vdash \alpha \rightarrow \beta}{} gilt.

}
{} {}

\inputaufgabe
{}
{

Es seien
\mathl{p_1 , \ldots , p_n}{} \definitionsverweis {Aussagenvariablen}{}{} und
\mathl{\beta_1 , \ldots , \beta_n}{} Aussagen. Zeige, dass man, wenn man in einer \definitionsverweis {syntaktischen Tautologie}{}{} $\alpha$ jedes Vorkommen von $p_i$ durch $\beta_i$ ersetzt, wieder eine Tautologie erhält.

}
{} {}

\inputaufgabe
{}
{

Es sei $\alpha$ eine ableitbare Tautologie. Zeige, dass es eine Ableitung für $\alpha$ gibt, bei der in jedem Ableitungsschritt nur Aussagenvariablen auftreten, die in $\alpha$ vorkommen.

}
{} {}

\inputaufgabe
{}
{

Skizziere ein Verfahren, wie man \zusatzklammer {bei $V$ \definitionsverweis {abzählbar}{}{}} {} {} eine Auflistung sämtlicher \definitionsverweis {syntaktischer Tautologien}{}{} aus $L^V$ erhalten kann.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{3}
{

Zeige, dass in einer aussagenlogischen \definitionsverweis {Tautologie}{}{} \zusatzklammer {und ebenso in einer aussagenlogischen \definitionsverweis {Kontradiktion}{}{}} {} {} mindestens eine \definitionsverweis {Aussagenvariable}{}{} mehrfach vorkommen muss.

}
{} {}

\inputaufgabe
{2}
{

Zeige, dass die Aussage
\mathdisp {(\alpha \rightarrow \beta) \wedge (\beta \rightarrow \gamma) \wedge ( \neg \alpha \rightarrow \beta) \rightarrow \gamma} { }
\definitionsverweis {allgemeingültig}{}{} ist.

}
{} {}

\inputaufgabe
{2}
{

Es sei
\mathl{\Gamma \subseteq L^V}{} eine \definitionsverweis {Aussagenmenge}{}{} derart, dass in keiner Aussage
\mathl{\alpha \in \Gamma}{} das Negationszeichen $\neg$ vorkommt. Zeige, dass dann die \definitionsverweis {Wahrheitsbelegung}{}{,} die jeder \definitionsverweis {Aussagenvariablen}{}{} den Wert $1$ zuweist, zu einer \definitionsverweis {Interpretation}{}{} $I$ mit
\mathl{\Gamma \subseteq I^\vDash}{} führt.

}
{} {}

\inputaufgabe
{3}
{

Zeige
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\beta \rightarrow \gamma) \wedge ( \neg \alpha \rightarrow \beta) \rightarrow \gamma} { . }

}
{} {}

\inputaufgabe
{2}
{

Begründe die folgende Ableitungsregel: Aus
\mathl{\vdash \alpha}{} und
\mathl{\vdash \alpha \wedge \beta \rightarrow \gamma}{} folgt
\mathl{\vdash \beta \rightarrow \gamma}{.}

}
{} {}

\inputaufgabe
{3}
{

Zeige, dass folgende rekursive Definition zur gleichen Menge an syntaktischen Tautologien führt:

Die Grundtautologien werden nur mit \definitionsverweis {Aussagenvariablen}{}{} formuliert.

Neben dem Modus ponens gibt es die Ersetzungsregel, d.h. wenn $\vdash \alpha$, so ist auch $\vdash \alpha'$, wobei $\alpha'$ ein Ausdruck ist, der entsteht, wenn man in $\alpha$ Aussagenvariablen durch beliebige Aussagen ersetzt.

Zeige, dass ohne diese Ersetzungsregel nicht die gleiche Menge beschrieben wird.

}
{} {}