Kurs:Einführung in die mathematische Logik/14/Klausur/kontrolle

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	${}\sum$
Punkte	3	3	2	2	2	2	5	2	4	4	12	0	0	0	0	0	2	43

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (2 Punkte)Referenznummer erstellen

Erläutere das Prinzip Beweis durch Widerspruch.

Aufgabe * (2 Punkte)Referenznummer erstellen

Anna kann sich nicht zwischen Heinrich und Konrad entscheiden, deshalb lässt sie sich vom Zufall leiten. Sie wohnt an einer U-Bahn-Station der Linie ${}5$ , die von Heinsheim nach Konsau fährt. Heinrich wohnt in Heinsheim und Konrad in Konsau. Wenn Anna Lust auf ein Date hat, geht sie einfach zu ihrer Station und nimmt die erstbeste U-Bahn, die gerade kommt. Die U-Bahnen fahren in beide Richtungen im Zehn-Minuten-Takt und die U-Bahnen nach Heinsheim fahren ${}:\!01,:\!11,:\!21$ etc. Nach einiger Zeit stellt Anna fest, dass sie Konrad viermal so häufig besucht wie Heinrich. Wann fahren die U-Bahnen nach Konsau ab?

Aufgabe * (2 Punkte)Referenznummer erstellen

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ . Begründe die folgende Regel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha _{1},\ldots ,\Gamma \vdash \alpha _{n}$ und ${}\Gamma \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \beta$ , dann auch ${}\Gamma \vdash \beta$ .

Aufgabe * (2 Punkte)Referenznummer erstellen

Es sei ${}M$ eine endliche Menge. Betrachte die Relation auf der Potenzmenge ${}{\mathfrak {P}}\,(M)$ , die durch

S\preccurlyeq T,{\text{ falls }}{\#\left(S\right)}\leq {\#\left(T\right)},

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?

Aufgabe * (5 Punkte)Referenznummer erstellen

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ . Es sei ${}\Gamma$ widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable ${}p\in V$ gelte ${}p\in \Gamma$ oder ${}\neg p\in \Gamma$ . Zeige, dass dann ${}\Gamma$ maximal widerspruchsfrei ist.

Aufgabe * (2 (1+1) Punkte)Referenznummer erstellen

Wir betrachten den Satz „Nachts sind alle Katzen grau“.

Negiere diesen Satz durch eine Existenzausssage, wenn der Satz sich auf eine bestimmte Nacht bezieht.
Negiere diesen Satz durch eine Existenzausssage, wenn der Satz sich auf jede Nacht bezieht.

Aufgabe * (4 Punkte)Referenznummer erstellen

Es seien ${}x_{1},\ldots ,x_{n}$ Variablen, ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache ${}L^{S}$ . Zeige, dass

s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow {\left(\alpha {\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}\rightarrow \alpha {\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}\right)}

allgemeingültig ist.

Aufgabe * (4 Punkte)Referenznummer erstellen

Zeige, dass

\vdash \exists x\exists y\alpha \rightarrow \exists y\exists x\alpha

im Kalkül der Prädikatenlogik ableitbar ist.

Aufgabe * (12 (2+3+1+2+2+2) Punkte)Referenznummer erstellen

Es sei

{}M=\{0\}\cup \mathbb {Q} _{\geq 1}\,.

Zeige, dass ${}M$ ein kommutativer Halbring ist.
Zeige, dass in ${}M$ die Relationen
$a{\text{ teilt }}b{\text{ oder }}a=0$

und

$a\leq b{\text{ oder }}b=0$

zueinander äquivalent sind.
Zeige, dass ${}{\frac {6}{5}}$ nicht irreduzibel in ${}M$ ist.
Zeige, dass es in ${}M$ keine irreduziblen Elemente gibt.
Es sei ${}\alpha$ die Aussage
$x=0\vee \exists y(x=y+1).$

Zeige, dass in ${}M$ die Aussage

$\alpha {\frac {0}{x}}\wedge {\left(\alpha \rightarrow \alpha {\frac {x+1}{x}}\right)}$

wahr ist.
Zeige, dass ${}M$ kein Peano-Halbring ist.

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (2 Punkte)Referenznummer erstellen

Zeige durch Angabe eines modallogischen Modelles, dass im ${}K$ - System der Ausdruck

\Box (p\vee q)\rightarrow \Box p\vee \Box q

nicht ableitbar ist (dabei seien ${}p,q$ Aussagenvariablen).