Kurs:Einführung in die mathematische Logik/18/Klausur mit Lösungen/latex
%Daten zur Institution
%\input{Dozentdaten}
%\renewcommand{\fachbereich}{Fachbereich}
%\renewcommand{\dozent}{Prof. Dr. . }
%Klausurdaten
\renewcommand{\klausurgebiet}{ }
\renewcommand{\klausurtyp}{ }
\renewcommand{\klausurdatum}{ . 20}
\klausurvorspann {\fachbereich} {\klausurdatum} {\dozent} {\klausurgebiet} {\klausurtyp}
%Daten für folgende Punktetabelle
\renewcommand{\aeins}{ 3 }
\renewcommand{\azwei}{ 3 }
\renewcommand{\adrei}{ 1 }
\renewcommand{\avier}{ 3 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 2 }
\renewcommand{\asieben}{ 3 }
\renewcommand{\aacht}{ 5 }
\renewcommand{\aneun}{ 1 }
\renewcommand{\azehn}{ 5 }
\renewcommand{\aelf}{ 0 }
\renewcommand{\azwoelf}{ 0 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 0 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 4 }
\renewcommand{\aachtzehn}{ 33 }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellesiebzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Eine \stichwort {Wohlordnung} {} auf einer Menge $M$.
}{Eine \stichwortpraemath {n} {stellige Relation}{} auf einer Menge $M$.
}{Die
\stichwort {Termmenge} {}
zu einer Grundtermmenge
\mathl{(V,K,F_n)}{.}
}{Ein \stichwort {allgemeingültiger} {} prädikatenlogischer Ausdruck $\alpha \in L^S$.
}{Die \stichwort {Befehle} {} für eine Registermaschine.
}{Die \stichwort {modallogische Sprache} {} zu einer Aussagenvariablenmenge $V$. }
}
{
\aufzaehlungsechs{Eine
\definitionsverweis {totale Ordnung}{}{}
$\preccurlyeq$ auf einer Menge $M$ heißt
Wohlordnung,
wenn jede nichtleere Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {kleinstes Element}{}{}
besitzt.
}{Unter einer $n$-stelligen Relation $R$ auf $M$ versteht man eine Teilmenge der $n$-fachen Produktmenge
\mathl{M \times \cdots \times M}{.}
}{Die Termmenge ist diejenige Teilmenge
\mathl{T=T(G)}{} der Wörter $A^*$ über dem Termalphabet
\mathl{A=V \cup K \cup \bigcup_{n \in \N_+} F_n}{,} die durch die folgenden rekursiven Vorschriften festgelegt wird.
\aufzaehlungdrei{Jede Variable
\mathl{v \in V}{} ist ein Term.
}{Jede Konstante
\mathl{c \in K}{} ist ein Term.
}{Für jedes
\mathl{f \in F_n}{} und $n$ Terme
\mathl{t_1 ,t_2, \ldots , t_n}{} ist auch
\mathl{f t_1 t_2 \ldots t_n}{} ein Term.
}
}{Man nennt $\alpha$ allgemeingültig, wenn er in jeder
$S$-\definitionsverweis {Interpretation}{}{}
$I$ gilt.
}{Die Befehle für eine Registermaschine sind
\zusatzklammer {dabei bezeichnen $R_i$ Register und $B_j$ Befehlszeilen} {} {.}
\aufzaehlungfuenf{
\mathl{i +}{}
\zusatzklammer {erhöhe den Inhalt des Registers $R_i$ um $1$, d.h. um einen Strich} {} {.}
}{
\mathl{i -}{}
\zusatzklammer {reduziere den Inhalt des Registers $R_i$ um $1$, d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer} {} {.}
}{$C (i j)$
\zusatzklammer {wenn das $i$-te Register leer ist, so gehe zum Befehl $B_j$, andernfalls zum nächsten Befehl} {} {.}
}{Drucke
\zusatzklammer {drucke den Inhalt des ersten Registers} {} {.}
}{Halte an.
}
}{Die
modallogische Sprache
zu $V$ besteht aus den Aussagenvariablen, aus allen rekursiv-konstruierbaren aussagenlogischen Verknüpfungen und aus allen rekursiv-konstruierbaren Ausdrücken der Form
\mathl{\Box ( \alpha )}{.}
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen (abzählbarer Fall).}{Der \stichwort {Vollständigkeitssatz} {} der Prädikatenlogik.}{/Fakt/Name}
}
{
\aufzaehlungdrei{Es sei $V$ eine
\definitionsverweis {abzählbare}{}{}
Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mathl{\Gamma \subseteq L^V}{} eine
\definitionsverweis {widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}
Dann kann man $\Gamma$ durch sukzessive Hinzunahme von entweder
\mathl{p_n}{} oder
\mathl{\neg p_n}{} und durch Abschluss unter der
\definitionsverweis {Ableitungsbeziehung}{}{}
zu einer maximal widerspruchsfreien Teilmenge
\mathl{\Gamma' \supseteq \Gamma}{} ergänzen.}{Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{,}
$\Gamma$ eine Menge an
$S$-\definitionsverweis {Ausdrücken}{}{}
und $\alpha$ ein weiterer $S$-Ausdruck. Dann gilt
\mathl{\Gamma \vDash \alpha}{} genau dann, wenn
\mathl{\Gamma \vdash \alpha}{} gilt.}{/Fakt}
}
\inputaufgabeklausurloesung
{1}
{
Bruno liest in der Zeitung: \anfuehrung{Im letzen Jahr war bei $50 \%$ aller Autounfälle Alkohol mit im Spiel}{.} Bruno überlegt: \anfuehrung{ $50 \%$ mit Alkohol, $50 \%$ ohne Alkohol. Dann ist es also egal, ob man was trinkt oder nicht. In Zukunft werde ich das auch nicht mehr so streng sehen}{.} Beurteile diese Überlegung!
}
{Autounfall/Alkoholanteil/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{3}
{
Beweise den Satz, dass es unendlich viele Primzahlen gibt.
}
{
Angenommen, die Menge aller Primzahlen sei endlich, sagen wir
\mathl{\{p_1,p_2 , \ldots , p_r\}}{.} Man betrachtet die Zahl
\mavergleichskettedisp
{\vergleichskette
{N
}
{ =} {p_1\cdot p_2\cdot p_3 { \cdots } p_r\ + 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Zahl ist durch keine der Primzahlen $p_i$ teilbar, da bei Division von $N$ durch $p_i$ immer ein Rest $1$ verbleibt. Damit sind die Primfaktoren von $N$, die es nach
Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024))
geben muss, nicht in der Ausgangsmenge enthalten - Widerspruch.
}
\inputaufgabeklausurloesung
{3}
{
Definiere zu jeder Aussage
\mathl{\alpha \in L^V}{} die Menge
\mathl{\operatorname{ Var}_{ } ^{ } { \left( \alpha \right) }}{} der in $\alpha$ vorkommenden
\definitionsverweis {Aussagenvariablen}{}{.}
}
{
Wir legen die Abbildung
\maabbeledisp {\operatorname{Var}} {L^V} { \mathfrak {P} \, (V )
} {\alpha} { \operatorname{ Var}_{ } ^{ } { \left( \alpha \right) }
} {}
rekursiv über den Aufbau von $L^V$ fest. Wegen dem eindeutigen rekursiven Aufbau von $L^V$ ist dadurch eine wohldefinierte Abbildung gegeben. Für
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { p
}
{ \in} {V
}
{ } {
}
{ } {
}
}
{}{}{}
setzt man
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ Var}_{ } ^{ } { \left( p \right) }
}
{ =} { \{p\}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Für
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { \neg ( \beta)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
setzt man
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ Var}_{ } ^{ } { \left( \alpha \right) }
}
{ =} { \operatorname{ Var}_{ } ^{ } { \left( \beta \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Für
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { ( \beta) * ( \gamma)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{*
}
{ =} { \wedge, \vee, \rightarrow, \leftrightarrow
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
setzt man
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ Var}_{ } ^{ } { \left( ( \beta) * ( \gamma) \right) }
}
{ =} { \operatorname{ Var}_{ } ^{ } { \left( \beta \right) } \cup \operatorname{ Var}_{ } ^{ } { \left( \gamma \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{2}
{
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 (Einführung in die mathematische Logik (Osnabrück 2021))} {} {.}
}
{
Aufgrund von
Lemma 3.14 (Einführung in die mathematische Logik (Osnabrück 2021))
ist
\mathdisp {\vdash \alpha \wedge \neg \alpha \rightarrow \neg \alpha \wedge \alpha} { . }
Das Widerspruchsaxiom besagt
\mathdisp {\vdash \neg \alpha \wedge \alpha \rightarrow \beta} { . }
Das Kettenschlussaxiom liefert
\mathdisp {\vdash { \left( \alpha \wedge \neg \alpha \rightarrow \neg \alpha \wedge \alpha \right) } \wedge { \left( \neg \alpha \wedge \alpha \rightarrow \beta \right) } \rightarrow { \left( \alpha \wedge \neg \alpha \rightarrow \beta \right) }} { . }
Da die beiden Teile des Vordersatzes ableitbar sind, ist auch der Nachsatz ableitbar.
}
\inputaufgabeklausurloesung
{3}
{
Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$. Begründe die Konjunktionsregel für die
\definitionsverweis {Ableitungsbeziehung}{}{:}
Wenn
\mathl{\Gamma \vdash \alpha}{} und
\mathl{\Gamma \vdash \beta}{,} dann ist auch
\mathl{\Gamma \vdash \alpha \wedge \beta}{.}
}
{
Die Voraussetzung bedeutet, dass es Ausdrücke
\mathl{\alpha_1 , \ldots , \alpha_m, \beta_1 , \ldots , \beta_n \in \Gamma}{} mit
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_m \rightarrow \alpha} { }
und mit
\mathdisp {\vdash \beta_1 \wedge \ldots \wedge \beta_n \rightarrow \beta} { }
gibt. Daraus ergibt sich mit Hilfe
\zusatzklammer {der Regelversion} {} {}
von
Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021)) (2)
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_m \wedge \beta_1 \wedge \ldots \wedge \beta_n \rightarrow \alpha \wedge \beta} { . }
Dies bedeutet
\mathl{\Gamma \vdash \alpha \wedge \beta}{.}
}
\inputaufgabeklausurloesung
{5 (4+1)}
{
Es sei $X$ ein
\definitionsverweis {topologischer Raum}{}{}
und $F$ ein
\definitionsverweis {topologischer Filter}{}{}
auf $X$,
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{X
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {offene Teilmenge}{}{}
und
\mathl{T \notin F}{.}
\aufzaehlungzwei {Zeige, dass das Mengensystem
\mathdisp {{ \left\{ U \mid U \subseteq X \text{ offen} , \, \text{es gibt } V \in F \text{ mit }V \cap { \left( X \setminus T \right) } \subseteq U \right\} }} { }
ein Filter auf $X$ ist, der
\mathl{X \setminus T}{} enthält und $T$ nicht enthält.
} {Zeige mit Hilfe
des Lemmas von Zorn,
dass es einen
\definitionsverweis {Ultrafilter}{}{}
$G$ mit
\mavergleichskette
{\vergleichskette
{ F
}
{ \subseteq }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und mit
\mathl{T \notin G}{} gibt.
}
}
{
\aufzaehlungzwei {Sei
\mavergleichskettedisp
{\vergleichskette
{H
}
{ =} { { \left\{ U \mid U \subseteq X \text{ offen } , \, \text{es gibt } V \in F \text{ mit }V \cap X \setminus T \subseteq U \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zu
\mathl{V \in F}{} ist
\mavergleichskettedisp
{\vergleichskette
{ V \cap { \left( X \setminus T \right) }
}
{ \subseteq} { V
}
{ } {
}
{ } {
}
{ } {}
}
{}{}{}
und daher ist
\mavergleichskettedisp
{\vergleichskette
{F
}
{ \subseteq} {H
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und insbesondere ist
\mathl{X \in H}{.} Zu
\mathl{U \in H}{} gibt es
\mathl{V \in F}{} mit
\mavergleichskettedisp
{\vergleichskette
{V \cap { \left( X \setminus T \right) }
}
{ \subseteq} {U
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
und diese Bedingung wird auch von jedem
\mavergleichskette
{\vergleichskette
{U'
}
{ \supseteq }{U
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
erfüllt, also ist auch
\mathl{U' \in H}{.} Zu
\mathl{U_1,U_2 \in H}{} gibt es
\mathl{V_1,V_2 \in F}{} mit
\mavergleichskettedisp
{\vergleichskette
{V_1 \cap { \left( X \setminus T \right) }
}
{ \subseteq} {U_1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{V_2 \cap { \left( X \setminus T \right) }
}
{ \subseteq} {U_2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Daraus ergibt sich
\mavergleichskettedisp
{\vergleichskette
{ V_1 \cap V_2 \cap { \left( X \setminus T \right) }
}
{ \subseteq} { U_1 \cap U_2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und wegen
\mathl{V_1 \cap V_2 \in F}{} ist
\mathl{U_1 \cap U_2 \in H}{.} Somit ist $H$ ein Filter. Wegen
\mathl{X \in F}{} und
\mavergleichskettedisp
{\vergleichskette
{X \cap { \left( X \setminus T \right) }
}
{ =} { X \setminus T
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist
\mathl{X \setminus T \in H}{.} Angenommen
\mathl{T \in H}{.} Dann gibt es
\mathl{V \in F}{} mit
\mavergleichskettedisp
{\vergleichskette
{V \cap { \left( X \setminus T \right) }
}
{ \subseteq} { T
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und dann ist insbesondere
\mavergleichskette
{\vergleichskette
{V
}
{ \subseteq }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also
\mathl{T \in V}{} im Widerspruch zur Voraussetzung.
} {Zu dem in Teil (1) gegebenen Filter $H$ gibt es nach
Lemma 5.13 (Einführung in die mathematische Logik (Osnabrück 2021))
einen Ultrafilter $G$ mit
\mavergleichskette
{\vergleichskette
{F
}
{ \subseteq }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wegen
\mathl{X \setminus T \in F}{} ist
\mathl{T \notin G}{,} da sonst auch
\mavergleichskettedisp
{\vergleichskette
{\emptyset
}
{ =} { { \left( X \setminus T \right) } \cap T
}
{ \in} {G
}
{ } {
}
{ } {
}
}
{}{}{}
wäre.
}
}
\inputaufgabeklausurloesung
{1}
{
Man finde eine äquivalente Formulierung für die Aussage \anfuehrung{Frau Maier-Sengupta hat nicht alle Tassen im Schrank}{} mit Hilfe einer Existenzaussage.
}
{
Es gibt eine Tasse, die Frau Maier-Sengupta nicht im Schrank hat.
}
\inputaufgabeklausurloesung
{5}
{
Es seien
\mathl{s_1 , \ldots , s_n, t_1 , \ldots , t_n}{}
\definitionsverweis {Terme}{}{}
und $f$ ein $n$-stelliges Funktionssymbol. Zeige, dass die
\definitionsverweis {Ableitbarkeit}{}{}
\mathdisp {\vdash s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow fs_1 \ldots s_n =ft_1 \ldots t_n} { }
gilt.
}
{
Es sei $u$ eine Variable, die weder in einem der $s_i$ noch in einem der $t_i$ vorkommt. Für jedes
\mathl{i=1 , \ldots , n}{} setzen wir
\mavergleichskette
{\vergleichskette
{ \alpha_i
}
{ \defeq }{ f t_1 \ldots t_{i-1} s_i s_{i+1} \ldots s_n = f t_1 \ldots t_{i-1} u s_{i+1} \ldots s_n
}
{ }{
}
{ }{
}
{ }{}
}
{}{}{.}
Nach
Axiom 10.5 (Einführung in die mathematische Logik (Osnabrück 2021))
(2)
ergibt sich daraus
\mathdisp {\vdash s_i = t_i \rightarrow { \left( \alpha_i { \frac{ s_i }{ u } } \rightarrow \alpha_i { \frac{ t_i }{ u } } \right) }} { , }
also
\mathdisp {\vdash s_i = t_i \rightarrow { \left( { \left( f t_1 \ldots t_{i-1} s_i s_{i+1} \ldots s_n = f t_1 \ldots t_{i-1} s_i s_{i+1} \ldots s_n \right) } \rightarrow { \left( f t_1 \ldots t_{i-1} s_i s_{i+1} \ldots s_n = f t_1 \ldots t_{i-1} t_i s_{i+1} \ldots s_n \right) } \right) }} { . }
Da der Vordersatz in der Implikation rechts nach
Axiom 10.5 (Einführung in die mathematische Logik (Osnabrück 2021))
(1)
ableitbar ist, ergibt eine aussagenlogische Umformulierung
\mathdisp {\vdash s_i = t_i \rightarrow { \left( f t_1 \ldots t_{i-1} s_i s_{i+1} \ldots s_n = f t_1 \ldots t_{i-1} t_i s_{i+1} \ldots s_n \right) }} { . }
Diese Ableitbarkeiten gelten auch, wenn man die Vordersätze durch ihre Konjunktion
\mathdisp {(s_1=t_1) \wedge \ldots \wedge (s_n=t_n)} { }
ersetzt. Durch die Transitivität der Implikation ergibt sich daher
\mathdisp {\vdash (s_1=t_1) \wedge \ldots \wedge (s_n=t_n) \rightarrow { \left( fs_1 \ldots s_n = ft_1 \ldots t_n \right) }} { . }
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabeklausurloesung
{4}
{
Zeige, dass in einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} das modallogische
\definitionsverweis {Reflexivitätsaxiom}{}{}
genau dann gilt, wenn $R$
\definitionsverweis {reflexiv}{}{}
ist.
}
{
Es sei
\mathl{(M,R)}{} gegeben. Es sei zunächst $R$ reflexiv und sei
\mathdisp {w \vDash \Box \alpha} { . }
Wegen
\mathl{wRw}{} ist insbesondere
\mathdisp {w \vDash \alpha} { }
und damit
\mathdisp {w \vDash \Box \alpha \rightarrow \alpha} { . }
Wenn $R$ nicht reflexiv ist, so sei
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mathl{wRw}{} gelte nicht. Es sei $\mu$ die Belegung, bei der
\mathdisp {w \vDash p} { }
gelte, aber in allen anderen Welten
\mathl{v \vDash \neg p}{.} Dann ist
\mathdisp {w \vDash \neg \Diamond p} { , }
und somit ist
\mathdisp {w \not \vDash p \rightarrow \Diamond p} { . }
}