Kurs:Einführung in die mathematische Logik/11/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Ableitbarkeit eines Aussage ${}\alpha \in L^{V}$ aus einer Aussagenmenge ${}\Gamma \subseteq L^{V}$ in der Sprache der Aussagenlogik zu einer Aussagevariablenmenge ${}V$.
2. Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$.
3. Die Erfüllbarkeit eines ${}S$-Ausdruckes ${}\alpha \in L^{S}$, wobei ${}S$ ein Symbolalphabet bezeichnet.
4. Die elementare Äquivalenz für Elemente ${}m,n\in M$ für eine ${}S$-Struktur ${}M$.
5. Die aufzählbare Axiomatisierbarkeit einer Theorie ${}T\subseteq L_{0}^{S}$ zu einem Symbolalphabet ${}S$.
6. Die Gültigkeit eines modallogischen Ausdrucks ${}\alpha$ in einem modallogischen Rahmen ${}(M,R)$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Substitutionslemma.
2. Der Vollständigkeitssatz der Aussagenlogik.
3. Der zweite Gödelsche Unvollständigkeitssatz.

Aufgabe * (1 Punkt)

Formuliere die Kontraposition zu folgender Aussage von Professor Knopfloch: „Wenn Sie mein Schreiben vollständig gelesen und verstanden haben, dann antworten Sie mit Ihrer Uni-email“.

Aufgabe * (1 Punkt)

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

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

Aufgabe (3 Punkte)

Die Klasse 8c hat an jedem Wochentag eine Stunde mathematische Logik. Der Lehrer sagt am Freitag: „nächste Woche werden wir eine Klassenarbeit schreiben, und das wird eine Überraschung sein“. Begründe, dass der Lehrer lügt.

Aufgabe * (2 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Begründe die Fallunterscheidungsregel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \neg \alpha \rightarrow \beta$, dann ist auch ${}\Gamma \vdash \beta$.

Aufgabe * (3 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge ${}V$ und es seien ${}\alpha ,\beta \in L^{V}$. Zeige, dass

$\Gamma \cup \{\alpha \}\vdash \beta$

zu

$\Gamma \vdash \alpha \rightarrow \beta$

äquivalent ist.

Aufgabe * (7 Punkte)

Beweise den Satz von Hamel mit dem Lemma von Zorn.

Aufgabe * (1 Punkt)

Wir betrachten den Satz „Kein Mensch ist illegal“. Negiere diesen Satz durch eine Existenzaussage.

Aufgabe (3 Punkte)

Erläutere Vor- und Nachteile des axiomatischen Aufbaus der Mathematik.

Aufgabe * (5 (2+3) Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben.

1. Zeige, dass die Substitution ${}{\frac {x}{x}}$ für die Terme die Identität ist.
2. Zeige, dass die Substitution ${}{\frac {x}{x}}$ für die Ausdrücke die Identität ist.

Aufgabe * (6 Punkte)

Es sei ${}S$ ein Symbolalphabet erster Stufe, ${}\alpha$ ein ${}S$- Ausdruck und ${}x$ eine Variable. Zeige, dass ${}\vdash \alpha$ genau dann gilt, wenn ${}\vdash \forall x\alpha$ gilt.

Aufgabe * (4 (2+2) Punkte)

Es sei ${}M$ ein kommutativer Halbring und ${}x,y\in M$. Es sei

${}I:={\left\{u\in M\mid \exists a\exists b\exists c\exists d{\text{ mit }}u+ax+by=cx+dy\right\}}\,.$

1. Zeige, dass ${}I$ die folgenden drei Eigenschaften erfüllt.
   1. ${}0\in I$.
   2. Wenn ${}u,v\in I$ sind, so ist auch ${}u+v\in I$.
   3. Wenn ${}u\in I$ und ${}r\in M$ ist, so ist auch ${}ru\in I$.
2. ${}M$ erfülle nun die Abziehregel. Zeige, dass aus ${}u,v\in I$ mit ${}u=v+z$ auch ${}z\in I$ folgt.

Aufgabe * (3 Punkte)

Charakterisiere den Punkt ${}d$ im skizzierten Graphen mit einem Ausdruck in einer freien Variablen ${}x$ über dem Symbolalphabet, das neben Variablen aus einem einzigen zweistelligen Relationssymbol ${}R$ besteht, das im angegebenen Modell durch einen Pfeil wiedergegeben wird.