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

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (1 Punkt)Referenznummer erstellen

Beurteile die Snookerweisheit „Ein Snookerspiel kann man in der ersten Session nicht gewinnen, aber verlieren“ vom logischen Standpunkt aus.

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

Es sei ${}p_{i}$, ${}i\in I$, eine Familie von Aussagenvariablen und ${}L$ die zugehörige aussagenlogische Sprache. Es sei ${}S$ ein Symbolalphabet bestehend aus den Variablen ${}x_{i}$, ${}i\in I$, und dem einen Konstantensymbol ${}c$ und es sei ${}L^{S}$ die zugehörige prädikatenlogische Sprache. Es sei

${}\beta _{i}:=x_{i}=c\in L^{S}\,.$

1. Definiere rekursiv eine natürliche Abbildung

   $\Psi \colon L\longrightarrow L^{S},$

   die ${}p_{i}$ auf ${}\beta _{i}$ abbildet.

2. Ist ${}\Psi$ injektiv?
3. Ist ${}\Psi$ surjektiv?
4. Zeige für alle ${}\alpha \in L$, dass ${}\vdash \alpha$ (im Ableitungskalkül der Aussagenlogik) genau dann gilt, wenn ${}\vdash \Psi (\alpha )$ (im Ableitungskalkül der Prädikatenlogik) gilt.

Aufgabe * (5 Punkte)Referenznummer erstellen

Es seien ${}A,B,C$ einstellige Relationssymbole. Zeige, dass der Modus Barbara, also die Aussage

$(\forall x(Ax\rightarrow Bx)\wedge \forall x(Bx\rightarrow Cx))\rightarrow (\forall x(Ax\rightarrow Cx))$

im Prädikatenkalkül ableitbar ist.

Aufgabe * (8 Punkte)Referenznummer erstellen

Beweise den Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell ${}(N,0,\prime )$.

Aufgabe * (4 Punkte)Referenznummer erstellen

Es sei ${}S$ ein Symbolalphabet und ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge. Begründe, warum man im Allgemeinen bei der Hinzunahme von Beispielen (innerhalb des Beweises des Vollständigkeitssatzes) nicht für alle Existenzaussagen ${}\exists x\alpha \in L^{S}$ mit einer einzigen neuen Variablen ${}z$ arbeiten kann.

Aufgabe * (5 Punkte)Referenznummer erstellen

In einem Zugabteil sitzen die sechs Personen ${}A,B,C,D,E,F$. Wir betrachten die folgenden Relationen:

1. ${}Mx$ bedeutet, dass ${}x$ über die deutsche Bahn motzt.
2. ${}Px$ bedeutet, dass ${}x$ einen Fensterplatz hat.
3. ${}Sxy$ bedeutet, dass ${}x$ der Person ${}y$ die Fahrkarte klaut.

Es gelten die Beziehungen

$MA,MB,MC,MD,ME,MF,PA,PD,SAD,SBE.$

1. Für welche Personen ist die Äquivalenzklasse zur elementaren Äquivalenz einelementig, für welche nicht?
2. Bestimme die Automorphismengruppe des Zugabteils.
3. Charakterisiere umgangssprachlich die Person ${}A$ allein unter Bezugnahme auf die gegebenen Relationen.
4. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}M,P,S$ die Person ${}E$.
5. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}M,P,S$ diejenigen Äquivalenzklassen, die aus mindestens zwei Personen bestehen.

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

Die Registerabteilung des VW-Konzerns hat - ohne Wissen des Vorstandes und am Aufsichtsrat vorbei - in jedes real existierende Registerprogramm ${}P$ an einer willkürlich gewählten Stelle die aufeinanderfolgenden Befehlszeilen eingebaut (und dabei die Zeilennummern und die Sprungbefehlsnummern angepasst, ${}k$ ist die Nummer eines in ${}P$ nicht verwendeten Registers und ${}h'$ ist die neue Haltebefehlsnummer)

$k+$

$k+$

${\text{Drucke}}$

$C(k,h').$

1. Ändert sich durch diese Manipulation die Halteeigenschaft des Programms?
2. Ändert sich durch diese Manipulation die Programmabbildung?
3. Nachdem der Skandal herauskommt und die Öffentlichkeit eine Erklärung fordert, diskutieren Vorstand, Aufsichtsrat und Abteilungsleiter die folgenden möglichen Stellungsnahmen für die anstehende Pressekonferenz:
   a) Man wollte Speicherplatz sparen.
   
   b) Man wollte aus Werbezwecken erreichen, dass jedes Registerprogramm mindestens einmal „VW“ ausdruckt.
   
   c) Man wollte einen Beitrag zur Entschleunigung leisten, indem man manche Programme etwas langsamer macht.
   
   d) Man wollte einen Beitrag zur Entschleunigung leisten, indem man alle Programme etwas langsamer macht.
   Welche dieser Erklärungen passen inhaltlich zu den Manipulationen?

Aufgabe (4 Punkte)Referenznummer erstellen

Erläutere die Unentscheidbarkeit der Arithmetik und skizziere in Grundzügen, wie man sie beweisen kann.

Aufgabe * (4 Punkte)Referenznummer erstellen

Es sei ${}n\in \mathbb {N}$ eine fixierte natürliche Zahl und

${}\alpha (x):=x=n\,,$

wobei ${}n$ durch die ${}n$-fache Summe der ${}1$ mit sich selbst realisiert werde. Zeige direkt, dass es Sätze ${}p,q\in L_{0}^{\rm {Ar}}$ mit

$\mathbb {N} \vDash \alpha (GN(p))\leftrightarrow p$

und mit

$\mathbb {N} \vDash \neg \alpha (GN(q))\leftrightarrow q$

gibt.

Aufgabe * (3 Punkte)Referenznummer erstellen

Zeige, dass im ${}K$- System der Ausdruck

$\Box (\alpha \rightarrow \beta )\rightarrow (\Diamond \alpha \rightarrow \Diamond \beta )$

ableitbar ist.

Aufgabe * (7 Punkte)Referenznummer erstellen

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische Löb-Axiom genau dann gilt, wenn ${}R$ transitiv ist und es in ${}M$ keine unendlichen Ketten gibt.