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

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

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

Folgende Aussagen seien bekannt.

1. Der frühe Vogel fängt den Wurm.
2. Doro wird nicht von Lilly gefangen.
3. Lilly ist ein Vogel oder ein Igel.
4. Für Igel ist 5 Uhr am Morgen spät.
5. Doro ist ein Wurm.
6. Für Vögel ist 5 Uhr am Morgen früh.
7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

1. Ist Lilly ein Vogel oder ein Igel?
2. Ist sie ein frühes oder ein spätes Tier?
3. Fängt der späte Igel den Wurm?

Aufgabe * (8 Punkte)Referenznummer erstellen

Es sei ${}\alpha$ eine aussagenlogische Aussage und es seien ${}p_{1},\ldots ,p_{n}$ die darin vorkommenden Aussagenvariablen. Es sei

${}\gamma =\pm p_{1}\wedge \ldots \wedge \pm p_{n}\,$

eine fixierte Konjunktion dieser (negierten) Aussagenvariablen. Zeige, dass dann

$\vdash \gamma \rightarrow \alpha \,\,{\text{ oder }}\,\,\vdash \gamma \rightarrow \neg \alpha$

gilt.

Aufgabe * (2 Punkte)Referenznummer erstellen

Es sei ${}K=\{E,m,c\}$ eine Konstantenmenge, ${}Q$ ein einstelliges Funktionssymbol und ${}P$ ein zweistelliges Funktionssymbol. Es sei ${}I$ die Interpretation mit ${}M=\mathbb {N}$ als Grundmenge, bei der ${}Q$ als Quadrieren, ${}P$ als Multiplikation und die Konstanten als ${}I(E)=9000000000$ ${}I(m)=1$ und ${}I(c)=300000$ interpretiert wird. Ist der Ausdruck

$E=PmQc$

unter dieser Interpretation gültig?

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

1. Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist.
2. Beschreibe die Bedingung (und zwar so, dass die Bedingung erkennbar ist) aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck (also mit dem Symbolalphabet ${}+,\cdot ,0,1$ und Variablen) in der einen freien Variablen ${}x$.
3. Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen ${}x$.

Aufgabe * (3 Punkte)Referenznummer erstellen

Formuliere die Injektivität für eine Abbildung

$f\colon D\longrightarrow Z$

prädikatenlogisch mit Hilfe der Verwendung von Sorten.

Aufgabe * (5 (3+2) Punkte)Referenznummer erstellen

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache und ${}T$ die zugehörige Termmenge. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge.

1. Zeige, dass durch

   $s\cong _{\Gamma }t{\text{ genau dann, wenn }}I(s)=I(t){\text{ für jede Interpretation }}I{\text{ mit }}I\vDash \Gamma$

   eine Äquivalenzrelation auf ${}T$ definiert wird.

2. Wenn man ${}\Gamma$ vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?

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

In einer Wohngemeinschaft leben die Personen ${}A,B,C,D,E$. Wir betrachten die folgenden Relationen:

1. ${}Txy$ bedeutet, dass ${}x$ und ${}y$ manchmal miteinander Tennis spielen,
2. ${}Sxyz$ bedeutet, dass ${}x,y$ und ${}z$ manchmal miteinander Skat spielen,
3. ${}Kxyzw$ bedeutet, dass ${}x,y,z$ und ${}w$ manchmal miteinander Doppelkopf spielen.

In der WG gilt

$TDE,SABC,SABE,KACED.$

1. Charakterisiere umgangssprachlich die Person ${}D$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
2. Charakterisiere umgangssprachlich die Person ${}C$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
3. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}T,S,K$ die Person ${}A$.
4. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}T,S,K$ die Person ${}B$.
5. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}T,S,K$ die Person ${}E$.

Aufgabe (4 Punkte)Referenznummer erstellen

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Quadratzahlen ausdruckt.

Aufgabe (4 Punkte)Referenznummer erstellen

Es seien ${}T,S\subseteq \mathbb {N}$ entscheidbare Mengen. Zeige, dass dann auch die Vereinigung ${}T\cup S$, der Durchschnitt ${}T\cap S$ und auch das Komplement ${}\mathbb {N} \setminus T$ entscheidbar sind.

Aufgabe * (4 Punkte)Referenznummer erstellen

Zeige, dass die Abbildung

$f\colon \mathbb {N} ^{3}\longrightarrow \mathbb {N} ,\,(x,y,z)\longmapsto xy^{2}-z^{2}+2z^{3},$

(wohldefiniert und) arithmetisch repräsentierbar ist.

Aufgabe * (4 Punkte)Referenznummer erstellen

Beweise das Unvollständigkeitslemma.

Aufgabe * (6 (1+1+4) Punkte)Referenznummer erstellen

Wir interpretieren den Satz von Sokrates, „Ich weiß, dass ich nichts weiß“, als modallogisches Axiomenschema

$\Box \neg \Box \alpha .$

Zeige die folgenden Aussagen.

1. Dieses Axiomenschema ist paradox.
2. Dieses Axiomenschema ist innerhalb der ${}K$- Modallogik äquivalent zu

   $\Box \Diamond \alpha .$

3. Dieses Axiomenschema ist innerhalb der ${}K$- Modallogik äquivalent zu

   $\Box \alpha ,$

   also zum Leerheitsaxiom.

Aufgabe * (5 Punkte)Referenznummer erstellen

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische Transitivitätsaxiom genau dann gilt, wenn ${}R$ transitiv ist.