owned this note
owned this note
Published
Linked with GitHub
> "Falls es Ihnen während der Klausur schlecht geht oder Sie einen Herzinfarkt oder so haben sollten, kommen Sie zu uns vor und holen Sie sich ein Merkblatt dazu."
# GLoIn WS 17/18 Braindump
## Aufgabe 1 (Aussagenlogische Konsequenz)
Zeigen oder widerlegen Sie mittels Wahrheitstafeln die folgenden logischen Konsequenzen. Im Falle eines Widerlegs müssen Sie die entsprechende Zeile in der Wahrheitstafel deutlich markieren und argumentieren, warum dies einen Widerleg darstellt.
#### a) $(A\rightarrow B) \rightarrow C \vDash A \vee C$
#### b) $\neg(A \rightarrow \neg B) \vDash A \rightarrow B$
#### c) $A \rightarrow C \vDash \neg(C \rightarrow) A$
#### d) $(\neg A \wedge C) \vee (\neg C \wedge \neg B) \vDash (A \wedge B) \rightarrow \neg A$
## Aufgabe 2 (Formalisierung in Prädikatenlogik)
$\Sigma=\{P \diagup 1, K \diagup 1, G \diagup 1, m \diagup 1, I \diagup 2\}$
* $P(x)$ gibt an, ob $x$ ein Punkt ist
* $G(g)$ gibt an, ob $g$ eine Gerade ist
* $K(k)$ gibt an, ob $k$ ein Kreis ist
* $m(k)$ gibt den Mittelpunkt des Kreises zurück
* $I(p,x)$ ist die Inzidenzrelation (gibt $true$ zurück wenn Punkt $p$ auf Geraden $x$ bzw. auf Kreis $x$ liegt)
Nicht typrichtige Aufrufe bewirken undefiniertes Verhalten.
#### a) Zwei Kreise sind gleich wenn dieselben Punkte laut Inzidenzrelation darauf liegen.
#### b) Zwei Kreise mit dem gleichen Mitttelpunkt sind gleich oder haben keine gemeinsamen Punkte.
#### c) Je drei Punkte liegen stets auf einer gemeinsamen Geraden oder auf einem gemeinsamen Kreis.
#### d) Je zwei Kreise haben stets höchstens zwei gemeinsame Punkte oder sind gleich.
#### e) Zu jedem Kreis gibt es eine Gerade, die ihn in zwei verschiedenen Punkten schneidet.
## Aufgabe 3 (Unifikation)
Wenden Sie den Unifikationsalgorithmus aus der Vorlesung an:
$f(h(x,g(z)),y) \doteq f(h(g(y),y),g(h(w,w)))$
$w$, $x$, $y$ und $z$ sind Variablen, $f$, $g$ und $h$ Funktionen.
## Aufgabe 4 (Prädikatenlogische Normalisierung und Resolution)
### a)
Bringen Sie die Formel
$$\exists x \forall y (P(x,y) \rightarrow \forall z (Q(z) \rightarrow R(z,y))) \rightarrow \exists y (Q(y))
$$
(Achtung: die Formel selbst nicht die Negation!) in pränexe Normalform, dann in Skolemform und dann in Klauselform. Geben sie alle ggf. nötigen zwischen Schritte an.
### b)
Verwenden Sie das Resolutionsverfahren um zu zeigen, dass die Klasuelmenge unerfüllbar.
$$\{P(x, f(x))\}\\
\{\neg P(x,y), P(y,x)\}\\
\{\neg P(x,y), \neg P(y,z), P(x,z)\}\\
\{\neg P(a,a)\}
$$
a ist eine Konstante, x,y,z Variablen. Geben Sie in jedem Schritt den allgemeinsten Unifikator an.
## Aufgabe 5 (Formale Deduktion in Prädikatenlogik erster Stufe)
:::info
vergleiche Klausur WS 16/17 :wink:
:::
Folgern Sie mittels natürlicher Deduktion die Formel
$$\forall x (R(x,x))
$$
aus den Annahmen
$$\forall x \exists y (R(x,y))\\
\forall x \forall y \forall z ((R(x,y)\wedge R(y,z)) \rightarrow R(x,z))\\
\forall x \forall y (R(x,y)\rightarrow R(y,x))
$$
## Aufgabe 6 (Induktion)
$\Sigma = \{or/2, and/2, false/0, true/0\}\\
M=\{\bot, \top\}\\
\mathfrak{M}[\![false]\!]= \bot \textrm{ und } \mathfrak{M}[\![true]\!] = \top$
Für alle $a, b \in M$
$$\mathfrak{M}[\![or]\!](a,b) = \begin{cases} \bot & \textrm{falls } a=b=\bot\\ \top & \textrm{sonst}
\end{cases}
$$
sowie
$$\mathfrak{M}[\![and]\!](a,b) = \begin{cases} \top & \textrm{falls } a=b=\top\\
\bot & \textrm{sonst}
\end{cases}
$$
Zeigen Sie durch Induktion über E, dass für jeden Term E (möglicherweise mit freien Variablen), jede Variable $x$ und Umgebung $\eta$ gilt:
Wenn $\mathfrak{M}[\![E]\!] \eta[x \rightarrow \bot ]=\top$, dann auch $\mathfrak{M}[\![E]\!]\eta[x \rightarrow \top] = \top$
Wir erinnern hierbei daran
$$\eta[x \mapsto b] (v) \begin{cases} b& v = x \\
\eta(v) & \textrm{sonst}
\end{cases}
$$