Theorie Der Informatik: Lösungen Zu Übungsblatt 1.pdf

Theorie der Informatik - Übungsblatt 1

Dieses Übungsblatt aus dem Frühjahrssemester 2020 an der Universität Basel behandelt verschiedene Konzepte aus der Theorie der Informatik, insbesondere strukturelle Induktion, Aussagenlogik und ihre Semantik.

Aufgabe 1.1: Strukturelle Induktion

Es wird bewiesen, dass für jeden Binärbaum $B$ die Anzahl seiner Blätter ($bl(B)$) immer kleiner oder gleich der doppelten Höhe ($h(B)$) ist. Dies wird durch strukturelle Induktion gezeigt:

- Basisfall: Für den leeren Baum ($B = \emptyset$) gilt $bl(\emptyset) = 1 = 2 \cdot 0$.
- Induktionsvoraussetzung: Angenommen, die Aussage gilt für alle Unterbäume $BL$ und $BR$ von $B$.
- Induktionsschritt: Für den Knotenbaum $B = (BL, \oplus, BR)$ ist:
$bl(B) = bl(BL) + bl(BR) \leq 2h(BL) + 2h(BR) \leq 2\max(h(BL), h(BR)) + 2\max(h(BL), h(BR)) = 2h(B)$

Aufgabe 1.2: Formalisierung in Aussagenlogik

Die folgenden Aussagen werden als logische Formeln formuliert:

- (a) Wenn es nicht regnet, dann ist es warm: $(\neg \text{Regen} \rightarrow \text{warm})$
- (b) Wenn Bob schwimmen geht, dann isst er ein Eis und es regnet nicht: $(\text{BobSchwimmt} \rightarrow (\text{BobIsstEis} \land \neg \text{Regen}))$
- (c) Bob schwimmt genau dann, wenn er Eis isst oder es warm ist oder es nicht regnet: Zwei mögliche Formulierungen:
- $(\text{BobSchwimmt} \leftrightarrow (\text{BobIsstEis} \land (\text{warm} \lor \neg \text{Regen})))$
- $(\text{BobSchwimmt} \leftrightarrow ((\text{BobIsstEis} \land \text{warm}) \lor \neg \text{Regen}))$
- (d) Entweder die Sonne scheint oder es regnet (aber nicht beides): $((\text{Sonne} \lor \text{Regen}) \land \neg (\text{Sonne} \land \text{Regen}))$

Aufgabe 1.3: Semantik der Aussagenlogik

- (a) Modell und Beweis für $\phi = ((A \land \neg B) \rightarrow (\neg A \lor \neg C))$ über {A, B, C}:
- Ein Modell $I = \{A \mapsto 0, B \mapsto 0, C \mapsto 0\}$ erfüllt $\phi$, da $I \models \neg (A \land \neg B)$ und daher $I \models (\neg A \lor \neg C)$.
- (b) Modell für den Fall, dass $\phi$ falsch ist:
- Ein Modell $I = \{A \mapsto 1, B \mapsto 0, C \mapsto 1\}$ zeigt, dass $\phi$ falsch ist, da $I \not\models \neg (A \land \neg B)$ und somit $I \not\models (\neg A \lor \neg C)$.

Aufgabe 1.4: Semantik der Aussagenlogik - Implikation

Es wird gezeigt, dass in einer Interpretation $I$ über dieselben atomaren Aussagen $A$, wenn $I \not\models \phi$, dann entweder $I \not\models \phi$ oder $I \models \psi$. Dies folgt aus der Definition von Implikationen in der Aussagenlogik.