Logikübungen SoSe 2014
Gruppe Mo 10-12 (WSP3 R.1) (Oliver Woizekowski)
Pierre Röglin, Thure Dührsen
Serie 1
Aufgabe 421695400
Es bezeichne $\varphi$ die Aussage, dass alle ein Bier wollen.
Im Original steht geschrieben:
\[
K_\mathrm{S} \left(P_\mathrm{P}\varphi\land
P_\mathrm{W}\varphi\right) \rightarrow K_\mathrm{S}\varphi \lor
K_\mathrm{S} \lnot\varphi \\
\]
Wenn Schnoor weiß, dass Preugschat und Wilke es für möglich
halten, dass alle ein Bier wollen, dann weiß er, ob alle ein Bier wollen.
Die gefragte Aussage
„Wenn Schnoor weiß, ob Preugschat und Wilke
es für möglich halten, dass alle ein Bier wollen, dann weiß Schnoor,
ob alle ein Bier wollen.“
lässt sich nun folgendermaßen
formalisieren:
\[
\left(K_\mathrm S \left(P_\mathrm{P}\varphi\land
P_\mathrm{W}\varphi\right)\right) \lor \left(K_\mathrm S \lnot
\left(P_\mathrm{P}\varphi\land
P_\mathrm{W}\varphi\right)\right) \rightarrow K_\mathrm S \varphi \lor
K_\mathrm S \lnot\varphi
\]
Aufgabe 471095800
-
Schon die Annahme, dass (a)
jede Aussage entweder wahr oder falsch ist und (b) der Wahrheitswert
einer zusammengesetzten Aussage durch die Wahrheitswerte eindeutig zu
bestimmen ist -- eine Annahme, ohne die die Digitaltechnik undenkbar
wäre --, wird nicht in allen Teilgebieten der Informatik als wahr
betrachtet. In der Fuzzy-Logik etwa untersucht man die Zugehörigkeit
von Objekten zu unscharfen Mengen; eine Aussage ist dort zu einem
gewissen Grad wahr. Ein weiteres Beispiel ist der Konstruktivismus,
der davon ausgeht, dass nur solche Objekte existieren, für die eine
Konstruktionsvorschrift angegeben werden kann. Nun ist eine
Konstruktionsvorschrift notwendig endlich, d.h. sie besteht aus einer
endlichen Anzahl von Anweisungen, deren jede nur endlich oft
durchzuführen ist, und damit ist die Menge der konstruierbaren Objekte
abzählbar.
Außerdem gibt es die epistemische Logik, die auch
Wissenslogik genannt wird und dazu dient, ein Modell der Veränderung
des Wissens und der Überzeugungen von sog. Agenten (Menschen, Gruppen,
vielleicht auch Maschinen, Rechnernetze, ...) zu bilden. Allgmeiner
befasst sich die Modallogik mit Aussagen der Form „Es
ist möglich, dass $P$“, in Zeichen „$\Diamond P$“,
und „Es ist notwendig, dass $P$“, in Zeichen
„$\square P$“. Ein Beispiel eines Satzes in dieser Logik
ist etwa
\[
\Diamond P \leftrightarrow \lnot\square\lnot P
\]
$P$ ist genau dann möglich, wenn nicht notwendig ist, dass $P$ nicht
gilt.
$P$ ist genau dann möglich, wenn nicht gilt, dass $P$ nicht
ausgeschlossen ist.
- [entfällt krankheitsbedingt]
Aufgabe 239669680
Das nullstellige $\mathrm{or}$ ist definiert durch
$\mathrm{or}^{(0)}():= 0$, denn $\mathrm{or}(b,\,0)=b$ für alle
$b\in\set{0,\,1}$.
Ist $k\in\N_{>0}$, so ist das $k$-stellige $\mathrm{or}$ definiert
durch
\[
\mathrm{or}^{(k)} (X_1,\,\ldots,\,X_k) :=
\mathrm{or}\left(\mathrm{or^{(k-1)}}(x_1,\,\ldots x_{k-1}),\,
x_k\right)
\]
für alle $x_i\in\set{0,\,1}$.
Die zweistellige Funktion $\mathrm{xor}$ ist genau dann gleich $1$,
wenn die beiden Eingänge ungleich belegt sind, d.h. wenn genau einer
der Eingänge mit $1$ belegt ist, d.h. wenn eine ungerade Anzahl von
Eingängen mit $1$ belegt sind. Diese letzte Eigenschaft benutzen wir zur
Verallgemeinerung:
Das $k$-stellige $\mathrm{xor}$ soll für jedes
$k\in\N_{0}$ genau dann
gleich $1$ sein, wenn eine ungerade Anzahl von
Eingängen mit $1$ belegt sind. Also muss das nullstellige \mathrm{xor}
durch $\mathrm{xor}^{(0)}() := 0$ definiert werden, denn die Anzahl
der mit $1$ belegten Eingänge ist gleich Null, also nicht ungerade.
Ist $k\in\N_{>0}$, so ist das $k$-stellige $\mathrm{xor}$ definiert
durch
\[
\mathrm{xor}^{(k)} (x_1,\,\ldots,\,x_k) :=
\mathrm{xor}\left(\mathrm{xor^{(k-1)}}(x_1,\,\ldots x_{k-1}),\,
x_k\right)
\]
für alle $x_i\in\set{0,\,1}$.
Die Funktionen $\mathrm{or}$ und $\mathrm{xor}$ unterscheiden sich in
den Distributivgesetzen: Während $\mathrm{or}$ distributiv sowohl
bezüglich $\mathrm{or}$ als auch bezüglich $\mathrm{and}$ ist,
d.h. für alle $x_1,\,x_2,\,x_3\in\set{0,\,1}$ gelten (vgl. Vorlesung
Digitale Systeme):
\[
\begin{array}{rcl}
\OR(x_1,\, \OR(x_2,\,x_3)) &=&\OR(\OR(x_1,\,x_2),\,\OR(x_1,\,x_3))\quad\text{und}\\
\AND(x_1,\, \OR(x_2,\,x_3)) &=& \OR(\AND(x_1,\,x_2),\,\AND(x_1,\,x_3))\quad,\\
\end{array}
\]
ist $\XOR$ nicht distributiv bezüglich $\OR$: Es gilt
\[
\begin{array}{ccccccccccc}
1 = \OR(1,\,0) = \OR(1,\,\XOR(1,1)) &\neq&
\XOR(\OR(1,\,1),\,\OR(1,\,1)) = \XOR(1,\,1) = 0\quad.
\end{array}
\]
Aufgabe 130213474
Wir definieren die folgenden aussagenlogischen Variablen:
\[
\begin{array}{rcl}
X_1 = \top &:\iff& \text{Ein Glas ist eine Kanone}\quad;\\
X_2 = \top &:\iff& \text{Die Sonne dreht sich}\quad;\\
X_3 = \top &:\iff& \text{Viele Menschen sind klein}\quad;\\
X_4 = \top &:\iff& \text{Hochhäuser sind höher als 300 m}\quad;\\
X_5 = \top &:\iff& \text{Der Mond ist viereckig}\quad;\\
X_6 = \top &:\iff& \text{Die Sonne ist quadratisch}\quad;\\
X_7 = \top &:\iff& \text{Der Himmel ist blau}\quad;\\
X_8 = \top &:\iff& \text{Tulpen sind blau}\quad;\\
X_9 = \top &:\iff& \text{Poster sind aus Papier}\quad;\\
X_{10} = \top &:\iff& \text{freitags ist es warm}\quad.\\
\end{array}
\]
Dann gelten:
- Die Aussage „Ein Glas ist eine Kanone genau dann, wenn eine Glas keine Kanone ist und sich die Sonne dreht.“ entspricht der Formel
$X_1 \leftrightarrow \lnot X_1 \land X_2$.
- Die Aussage „Entweder sind viele Menschen klein oder Hochhäuser sind höher als 300 m.“ entspricht der Formel
$X_3 \xor X_4$.
- Die Aussage „Wenn der Mond viereckig ist, dann ist die Sonne quadratisch; wenn der Mond nicht viereckig ist, dann ist der Himmel blau.“ entspricht der Formel
$(X_5 \rightarrow X_6) \land (\lnot X_5 \rightarrow X_7)$.
- Die Aussage „Tulpen sind blau und Poster sind aus Papier und freitags ist es nicht warm.“ entspricht der Formel
$X_8 \land X_9 \land \lnot X_{10}$.
Aufgabe 467096690
In der Formel
\[
(X_3 \leftrightarrow (\bot \lor (X_0 \land X_2) \rightarrow ((X_0
\land X_2) \leftrightarrow (X_1 \nor \lnot X_3))))
\]
ist das am weitesten außen stehende Klammerpaar nicht nötig, weil es
keine Teilformel gibt, die von der eingeklammerten Formel abgegrenzt
werden müsste. Alle verbleibenden Klammern nummerieren wir nun von
links nach rechts durch.
Dann ist das Klammerpaar $(7,\,8)$ unnötig, denn der
$\leftrightarrow$-Operator
links von Klammer 7 hat niedrigere Präzedenz als der $\nor$-Operator
zwischen Klammer 7 und 8.
Ebenso ist das Klammerpaar $(5,\,6)$ unnötig, denn der
$\leftrightarrow$-Operator
rechts von Klammer 6 hat niedrigere Präzedenz als der $\land$-Operator
zwischen Klammer 5 und 6.
Das Klammerpaar $(4,\,9)$ ist notwendig, denn der
$\rightarrow$-Operator links von Klammer 4 hat die gleiche Präzedenz
wie der $\leftrightarrow$-Operator zwischen Klammer 6 und 7. Würde man
das Klammerpaar $(4,\,9)$ weglassen, so würde sich die Semantik der
Formel ändern.
Das Klammerpaar $(2,\,3)$ ist nötig, denn der $\lor$-Operator links
von Klammer 2 und der $\land$-Operator zwischen Klammer 2 und 3 haben
die gleiche Präzedenz.
Das Klammerpaar $(1,\,10)$ ist nötig, denn der
$\leftrightarrow$-Operator links von Klammer 1 hat niedrigere
Präzedenz als der $\lor$-Operator links
von Klammer 2.
Die klammerbereinigte Formel lautet also
\[
X_3 \leftrightarrow (\bot \lor (X_0 \land X_2) \rightarrow (X_0\land
X_2 \leftrightarrow X_1 \nor \lnot X_3))\quad.
\]
andere Serien
Last modified: Mon May 5 08:34:38 CEST 2014