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

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (2 Punkte)Referenznummer erstellen

Ein Mann steht mit einem Wolf, einer Ziege und einem Kohl am Ufer eines Flusses und möchte diesen überqueren. Es steht ein Boot zur Verfügung, in dem neben ihm nur ein weiterer Passagier Platz hat. Wie kann er den Fluss überqueren, ohne dass dabei der Wolf die Ziege oder die Ziege den Kohl frisst?

Aufgabe * (1 Punkt)Referenznummer erstellen

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

${}p$	${}q$	${}?$
w	w	w
w	f	f
f	w	w
f	f	f

Aufgabe * (2 Punkte)Referenznummer erstellen

Beweise die aussagenlogische Tautologie

\vdash \alpha \rightarrow (\beta \rightarrow \alpha \wedge \beta )

aus den aussagenlogischen Axiomen.

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 * (1 Punkt)Referenznummer erstellen

Wir betrachten den Satz „Lucy Sonnenschein tanzt auf allen Hochzeiten“. Negiere diesen Satz durch eine Existenzaussage.

Aufgabe * (2 Punkte)Referenznummer erstellen

Es seien ${}x,y,z,w$ Variablen und ${}V$ ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?

${}VxyzVVw$ ,
${}VVxyVzw$ ,
${}VVxyzVw$ ,
${}VxVyVzw$ ,
${}xVyVzVw$ ,
${}VVVxyzw$ ,
${}VxyVVzw$ ,
${}VVxVyzw$ ,
${}VxyVzw$ ,
${}VxVyzVw$ ,
${}VxVVyzw$ ,
${}VxyVzVw$ .

Aufgabe (2 Punkte)Referenznummer erstellen

Man erläutere für einen Ableitungskalkül den Unterschied zwischen einer syntaktischen Grundtautologie und einer Ableitungsregel.

Aufgabe * (8 Punkte)Referenznummer erstellen

Es seien ${}x,y$ Variablen, ${}s,t$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Es seien ${}u,v$ neue Variablen, die weder in ${}s$ noch in ${}t$ noch in ${}\alpha$ vorkommen. Zeige, dass

\alpha {\frac {s,t}{x,y}}\leftrightarrow \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}{\frac {x}{u}}{\frac {y}{v}}

allgemeingültig ist, wobei der Ausdruck rechts als die Hintereinanderausführung von vier Einzelsubstitutionen (von links nach rechts) zu lesen ist.

Aufgabe * (3 Punkte)Referenznummer erstellen

Zeige

\vdash \forall x\alpha \wedge \forall x\beta \rightarrow \forall x{\left(\alpha \wedge \beta \right)}.

Aufgabe * (4 Punkte)Referenznummer erstellen

Zeige, dass die Vorgängereigenschaft

\forall x{\left(x\neq 0\rightarrow \exists y(x=Ny)\right)}

aus der Menge der Peano-Axiome für den Nachfolger folgt.

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (10 Punkte)Referenznummer erstellen

Beweise den Fixpunktsatz der Prädikatenlogik.

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (4 Punkte)Referenznummer erstellen

Es sei ${}M$ ein ${}K$ - modallogisches System, in dem zusätzlich das Transitivitätsaxiom gelte. Ferner sei ${}s$ ein modallogischer Ausdruck, für den

M\vdash \neg \Box s\leftrightarrow s

gelte. Zeige für einen beliebigen Ausdruck ${}p$ die Ableitbarkeit

M\vdash \neg \Box (p\wedge \neg p)\rightarrow \neg \Box s.