uni/fmod/ue1/fmod-ue1.md

% Formale Modellierung ue1 % 14 Mai 2020

Aufgabe 1

(a)

$x\ ist\ y$

$x\ kann\ z$

$daher,\ alle\ y\ können\ z$

$x$ ... Ich, $y$ ... Vogel, $z$ ... fliegen

Ist keine gültige Inferenzregel. Es wird versucht, mittels eines Beispiels auf alle zu schließen, was in vielen Fällen nicht korrekt ist. Um das zu zeigen, reicht ein Gegenbeispiel. Zum Beispiel gilt die Inferenzregel nicht mehr wenn:

$w$ ... Pinguin

$w\ kann\ nicht\ z$

$w\ ist \ y$

$daher,\ w\ kann\ z$

Ein Pinguin, für den wir per Definition festlegen, dass es nicht fliegen kann, ist ein Gegenbeispiel für die obige Inferenzregel.

Eine (nicht zwingend inhaltlich korrekte) richtige Inferenzregel wäre:

$alle y\ können\ z$

$x\ ist\ y$

$daher,\ x\ kann\ z$

Wenn wir wieder unser Gegenbeispiel heranziehen:

$w$ ... Pinguin

$w\ ist\ y$

$daher,\ w\ kann\ z$

Ist sie inhaltlich nicht korrekt, aber die Inferenzregel ist dennoch gültig!

(b)

$alle\ x\ machen\ y$

$z\ ist\ x$

$daher,\ z\ macht\ y$

$x$ ... Affe, $y$ ... durch den Wald rasen, $z$ ... Bobo

Ist eine korrekte Inferenzregel (bekannt als Deduktion).

Inferenzbeispiel:

$w$ ... Barbara

$w\ ist\ x$

$daher,\ w\ macht\ y$

(c)

$x\ mag\ keine\ y$

$z\ ist\ y$

$daher,\ z\ mag\ x\ nicht$

$x$ ... Gülcan, $y$ ... Junge, $z$ ... Max

Ist eine falsche Inferenzregel. Wir wissen weder ob Gülcan ein Junge ist, weder noch, ob alle Jungs keine anderen Jungs mögen. Eine für diese Auflegung richtige Inferenzregel lässt sich aber leicht aufstellen:

$x\ mag\ keine\ y$

$x\ ist\ y$

$daher,\ x\ mag\ z\ nicht$

Oder sogar:

$x\ mag\ x\ nicht$

Inferenzbeispiel:

$w$ ... Jan

$w\ ist\ y$

$daher,\ x\ mag\ w\ nicht$

Aufgabe 2

Satz 1:

$t0$ ... Zeit ist Frühjahr, $k{x:pflanze}$ ... $x$ kauft Pflanze, $k_{x:erde}$ ... $x$ kauft Erde

$$ F_1: t0 \supset (k{x:pflanze} \land k_{x:erde}) $$

oder dual dazu:

$$ F1: (k{x:pflanze} \land k_{x:erde}) \subset t_0 $$

Satz 2:

$pt$ ... Topfpflanze, $k{x:topf}$ ... $x$ kauft Topf, $k_{x:blumenkisterl}$ ... $x$ kauft Blumenkisterl

$$ F_2: (t_0 \land pt) \supset (k{x:pflanze} \land k{x:erde} \land (k{x:topf} \lor k_{x:blumenkisterl})) $$

Hier gibt es Interpretationsspielraum bei der Frage, ob nur eines von $k{x:topf}$ und $k{x:blumenkisterl}$ gelten kann, oder beides gleichzeitig.

Satz 3:

$pa$ ... $Pflanze$ ist anspruchsvoll, $k{x:dünger}$ ... $x$ kauft Dünger, $a_x$ ... $x$ hält genau sich an Anleitung

$$ F_3: (t_0 \land p_t \land pa) \supset (k{x:pflanze} \land k{x:erde} \land (k{x:topf} \lor k{x:blumenkisterl}) \land k{x:dünger} \land a_x) $$

Wie sich sehen lässt, sind Formeln $F_2$ und $F_3$ Fortführungen von $F_1$ und ließen sich eventuell kombinieren. Sprachlich wird darauf durch Verwendung von "außerdem" und "auch" gedeutet.

Satz 4:

$p{x:sellerie}$ ... $x$ pflanzt Sellerie, $p{x:salat}$ pflanz Salat

$$ F4: p{x:sellerie} \not\equiv p_{x:salat} $$

Satz 5:

$b{x:loch}$ ... $x$ bereitet Loch vor, $b{x:topf}$ bereitet Topf vor

$$ F5: b{x:loch} \not\equiv b_{x:topf} $$

Ob bei $F_5$ nicht beides gleichzeitig vorbereitet werden kann, muss hineininterpretiert werden.

Satz 6:

$bf{x:pflanze:topf}$ ... $x$ befreit Pflanze von Topf, $s{x:pflanze:loch}$ ... $x$ setzt Pflanze in Loch, $vx$ ... $x$ ist vorsichtig, $s{x:loch:erde}$ ... $x$ setzt Loch in Erde

$$ F6: bf{x:pflanze:topf} \land (s_{x:pflanze:loch} \land vx) \land s{x:loch:erde} $$

Satz 7:

$e_{pflanze:erde}$ ... Pflanze ist eingeflanzt in Erde

$$ F7: e{pflanze:erde} $$

Aufgabe 3

$R$ ... Anna verwendet rot, $B$ ... Anna verwendet blau, $G$ ... Anna verwendet gelb

(a)

$$ F_a: R \land \neg B \land \neg G $$

(b)

$$ F_b: (R \land B) \lor (R \land G) \lor (B \land G) $$

(c)

$$ F_c: ((R \land B) \lor (R \land G) \lor (B \land G)) \land \neg (R \land B \land G) $$

alternativ:

$$ F_c: F_b \land \neg (R \land B \land G) $$

(d)

$$ F_d: (R \land B \land G) $$

(e)

$$ F_e: B \equiv R $$

(f)

$$ F_f: B \not\equiv R $$

(g)

$$ F_g: B \land \neg R $$

(h)

$$ F_h: R \supset (B \land G) $$

Aufgabe 4

Eine Menge ist vollständig, wenn durch die Operatoren einer Menge alle anderen repräsentiert werden können.

(a)

${ or, xor, true }$

$$ \bot \equiv (\top \not\equiv \top) $$

$$ (x \downarrow y) \equiv ((x \lor y) \not\equiv \top) $$

x	y	|	$(x \downarrow y)$	$\equiv$	$((x$	$\lor$	$y)$	$\not\equiv$	$\top)$
1	1	|	0	1		1		0
1	0	|	0	1		1		0
0	1	|	0	1		1		0
0	0	|	1	1		0		1

Da die Menge ${ xor }$ funktional vollständig ist, und die Operatoren dieser Menge mit den ursprünglich gegebenen hergeleitet werden kann, ist auch ${ or, xor, true }$ funktional vollständig.

(b)

${ or, xor }$

Wir können durch Induktion zeigen, dass wir nie auf die unäre Funktion $false(x) = \bot$ mithilfe unserer gegebenen Menge schließen können. Es reicht auch bei binären Operationen nur darauf zu schließen, ob $false(x) = \bot$ hergeleitet werden kann, da $false(x) \equiv false(y)$.

Induktionsbasis:

$xor(...)$, $or(...)$ alleine können $false(x)$ nicht darstellen

$$ xor(x, y) \not\equiv false(x) $$

$$ or(x, y) \not\equiv false(x) $$

Induktionsschritt:

Wir unterscheiden 4 Fälle

Fall 1:

$$ xor(xor(x, y), x) \equiv y $$

$$ xor(xor(x, y), y) \equiv x $$

Fall 2:

$$ or(or(x, y), x) \equiv or(or(x, y), y) \equiv or(x, y) $$

Fall 3:

$$ or(xor(x, y), x) \equiv or(xor(x, y), y) \equiv or(x, y) $$

Fall 4:

Bisher waren die Fälle unspektakulär, aber Fall 4 zeigt sich für eine Zeit hartnäckig, wir benennen zunächst die Formeln $F{4,x}$ und $F{4,y}$.

$$ F_{4,x}: xor(or(x, y), x) $$

$$ F_{4,y}: xor(or(x, y), y) $$

Es ergeben sich folgende Wahrheitstabellen:

x	y	|	$F_{4,x}$	$F_{4,y}$
1	1	|	0	0
1	0	|	0	1
0	1	|	1	0
0	0	|	0	0

Aber bei Ausführung aller nun zur Verfügung stehender Varianten einer Verkettung der Operationen, ergibt sich folgendes:

$$ xor(x, F{4,x}) \equiv or(x, F{4,x}) \equiv or(x, y) $$

$$ xor(y, F{4,y}) \equiv or(y, F{4,y}) \equiv or(x, y) $$

$$ or(y, F_{4,x}) \equiv y $$

$$ or(x, F_{4,y}) \equiv x $$

Zu guter Letzt entsteht aus den letzten beiden Optionen ein Term, welcher bisher noch nicht abbildbar war:

$$ G{4}: xor(y, F{4,x}) \equiv xor(x, F_{4,y}) $$

Mit folgender Wahrheitstabelle:

x	y	|	$G_{4}$
1	1	|	1
1	0	|	0
0	1	|	0
0	0	|	0

Nun werden die letzten (neuen) vier Optionen ausgeschöpft:

$$ or(x, G_4) \equiv x $$

$$ or(y, G_4) \equiv y $$

$$ xor(x, G4) \equiv F{4,y} $$

$$ xor(y, G4) \equiv F{4,x} $$

Wie ersichtlich können wir funktional aus der Menge ${ or, xor }$ nur die Menge ${ or, xor, id, F{4,x}, F{4,y}, G_4 }$ schließen (wobei $id$ der Identitätsoperator ist). Jede beliebige Zusammensetzung führt uns schlussendlich wieder auf diese Menge zurück. Somit ist die Menge ${ or, xor }$ nicht funktional vollständig.

Aufgabe 5

Gegeben sei die Formel mit aussagenlogischen Variablen $A$, $B$ und $C$:

$$ F: ((((A \land \neg B) \lor (\neg B \supset C)) \supset A) \land B) $$

(a)

Um zu zeigen, dass die Syntax von $F$ korrekt ist, nehmen wir folgende Konstruktionsfunktionen zur Hand:

Konstruktionsfunktionen
$F_\neg(F) = "\neg" F$
$F_\land(F, G) = "(" F\ "\land"\ G ")"$
$F_\lor(F, G) = "(" F\ "\lor"\ G ")"$
$F_\supset(F, G) = "(" F\ "\supset"\ G ")"$

Wir können unsere Formel nun zerlegen. Dabei gibt $F_i$ immer den Teil einer Zerlegung an, den wir noch überprüfen müssen:

Zerlegungen
$F_{0\land}(F_1, B) = "(" F_1\ "\land"\ B ")"$
$F_{1\supset}(F_2, A) = "(" F_2\ "\supset"\ A ")"$
$F_{2\lor}(F_3, F_4) = "(" F_3\ "\lor"\ F_4 ")"$
$F_{3\land}(A, F_5) = "(" A\ "\land"\ F_5 ")"$
$F_{5\neg}(F_5) = "\neg" B$
$F_{4\supset}(F_6, C) = "(" F_6\ "\supset"\ C ")"$
$F_{6\neg}(F_6) = "\neg" B$

Weil mithilfe der Konstruktionsfunktionen alle Zerlegungen aufgelöst werden, handelt es sich um eine syntaktisch korrekte Formel.

(b)

Gegeben sei die Interpretation $I(A) = 1$, $I(B) = 0$ und $I(C) = 1$. Eine Evaluierung würde dann wie folgt aussehen:

Evaluierung
$val_I(F) = val_I(((A \land \neg B) \lor (\neg B \supset C)) \supset A)\ and\ val_I(B)$
$val_I(F) = (val_I((A \land \neg B) \lor (\neg B \supset C))\ implies\ val_I(A))\ and\ 0$
$val_I(F) = 0$

Bei einer lazy Evaluierung bliebe $val_I(B)$ unaufgedeckt bis zum Schluss. Bei einer non-lazy Evaluierung hingegen, ist sofort bemerkbar, dass ein Ausdruck der Form $G \land \bot$ nur auf 0 evaluieren kann. Wir wären eigentlich schon fertig. Im Sinne dieser Aufgabe, wird die Formel zur Gänze evaluiert:

Evaluierung
$val_I(F) = val_I(((A \land \neg B) \lor (\neg B \supset C)) \supset A)\ and\ val_I(B)$
$val_I(F) = (val_I((A \land \neg B) \lor (\neg B \supset C))\ implies\ val_I(A))\ and\ 0$
$val_I(F) = ((val_I(A \land \neg B)\ or\ val_I(\neg B \supset C))\ implies\ 1)\ and\ 0$
$val_I(F) = (((val_I(A)\ and\ val_I(\neg B))\ or\ (val_I(\neg B)\ implies\ val_I(C)))\ implies\ 1)\ and\ 0$
$val_I(F) = (((1\ and\ 1)\ or\ (1\ implies\ 1))\ implies\ 1)\ and\ 0$
$val_I(F) = ((1\ or\ 1)\ implies\ 1)\ and\ 0$
$val_I(F) = (1\ implies\ 1)\ and\ 0$
$val_I(F) = 1\ and\ 0$
$val_I(F) = 0$

Unüberraschenderweise kommen wir durch non-lazy Evaluierung auf das selbe Ergebnis.

(c)

A	B	C	|	$((((A$	$\land$	$\neg B$	$) \lor ($	$\neg B$	$\supset$	$C))$	$\supset$	$A)$	$\land$	$B)$
1	1	1	|		0	0	1	0	1		1		1
1	1	0	|		0	0	1	0	1		1		1
1	0	1	|		1	1	1	1	1		1		0
1	0	0	|		1	1	1	1	0		1		0
0	1	1	|		0	0	1	0	1		0		0
0	1	0	|		0	0	1	0	1		0		0
0	0	1	|		0	1	1	1	1		0		0
0	0	0	|		0	1	0	1	0		1		0

Wie sich ablesen lässt, ist die Formel erfüllbar bzw. widerlegbar. Analog ist sie nicht gültig oder unerfüllbar.

Aufgabe 6

Es ist zu zeigen, dass die Formeln $F_1$ und $F_2$ äquivalent sind.

$$ F_1: (A \downarrow C) \supset (A \supset \neg B),\ F_2: (A \supset (B \not\equiv \neg B)) \lor C $$

(a)

A	B	C	|	$(A$	$\downarrow$	$C)$	$\supset$	$(A$	$\supset$	$\neg B)$	$\ =$	$(A$	$\supset$	$(B$	$\not\equiv$	$\neg B))$	$\ \ \lor\ C$
1	1	1	|		0		1		0	0	1		1		1	0	1
1	1	0	|		0		1		0	0	1		1		1	0	1
1	0	1	|		0		1		1	1	1		1		1	1	1
1	0	0	|		0		1		1	1	1		1		1	1	1
0	1	1	|		0		1		1	0	1		1		1	0	1
0	1	0	|		1		1		1	0	1		1		1	0	1
0	0	1	|		0		1		1	1	1		1		1	1	1
0	0	0	|		1		1		1	1	1		1		1	1	1

Da $F_1$ und $F_2$ beide gültig sind, sind sie auch äquivalent.

(b)

$F_1$	$F_2$
$(A \downarrow C) \supset (A \supset \neg B)$	$(A \supset (B \not\equiv \neg B)) \lor C$
$(\neg A \land \neg C) \supset (\neg A \lor \neg B)$	$(\neg A \lor (B \not\equiv \neg B)) \lor C$
$\neg (\neg A \land \neg C) \lor (\neg A \lor \neg B)$	$(\neg A \lor ((\neg B \lor B) \land (B \lor \neg B))) \lor C$
$A \lor C \lor \neg A \lor \neg B$	$(\neg A \lor (\top \land \top)) \lor C$
$\top \lor C \lor \neg B$	$\neg A \lor \top \lor C$
$\top$	$\top$

Aufgabe 7

$o_F$ ... Otos ist Fluzis, $o_E$ ... Otos ist Ezos, $o_G$ ... Otos ist Gugis

Der Sachverhalt wird mithilfe folgender Formeln modelliert:

|| |:--| |$F_1: o_F \lor o_E$| |$F_2: \neg o_E \supset o_G$| |$F_3: o_F \not\equiv o_G$|

"Otos sind Fluzis oder Ezos" wurde nicht als exklusives oder aufgefasst, weil die Sprache hier vage ist, und auch weil beim darauffolgenden Satz "Otos sind entweder Fluzis oder Gugis, aber nicht beides" im Vergleich explizit auf die Exklusivität aufmerksam gemacht worden ist.

Zur Hilfe nehmen wir uns eine Wahrheitstabelle her:

$o_E$	$o_F$	$o_G$	|	$o_F \lor o_E$	$\neg o_E \equiv o_G$	$o_F \not\equiv o_G$
1	1	1	|	1	0	0
1	1	0	|	1	1	1
1	0	1	|	1	0	1
1	0	0	|	1	1	0
0	1	1	|	1	1	0
0	1	0	|	1	0	1
0	0	1	|	0	1	1
0	0	0	|	0	0	0

Wir sagen an diesem Punkt, alle Interpretationen die den gewünschten Sachverhalt abbilden sind Lösungen. Der gewünschte Sachverhalt ist in dem Fall die Konsequenzbeziehung "Otos sind Ezos". Formal entspricht die Konsequenzbeziehung der Formel $o_E$. Damit aus den Argumenten folgt, dass die Konsequenzbeziehung gilt, müssen alle Formeln wahr sein, wenn auch $o_E$ wahr ist.

Wir bilden daher die Konjuktion aller drei Aussagen, d.h. $F_1 \land F_2 \land F_3$. Wie sich aus der Wahrheitstabelle ablesen lässt, gibt es nur eine Interpretation die eine Lösung darstellt, nämlich $I(o_E) = 1$, $I(o_F) = 1$ und $I(o_G) = 0$. Wir versuchen nun eine logische Konsequenz festzustellen.

|$I(o_E)$|$I(o_F)$|$I(o_G)$|||$F_1 \land F_2 \land F_3$|$|=_I$|$o_E$| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |1|1|1|||0|\checkmark|1| |1|1|0|||1|\checkmark|1| |1|0|1|||0|\checkmark|1| |1|0|0|||0|\checkmark|1|

(Da das Konjunkt nur für einen Wert wahr ist, wurden restliche Einträge ausgelassen)

Unsere Prämisse ist das Konjunkt unserer drei Formeln und die Konklusion $o_E$. Wie sich erkennen lässt, ist Konklusion immer wahr, wenn auch die Prämisse wahr ist. Daher handelt es sich um eine logische Konsequenz.

Aus den drei Aussagen folgt also, dass Otos sowohl ein Fluzis ist, als auch ein Ezos, aber kein Gugis.

Aufgabe 8

x	y	z	|	$f(x, y, z)$
1	1	1	|	1
1	1	0	|	0
1	0	1	|	0
1	0	0	|	0
0	1	1	|	0
0	1	0	|	0
0	0	1	|	1
0	0	0	|	1

Es soll jeweils eine diskunktive (a) und konjunktive (b) Normalform angegeben werden. Beide Normalformeln wurde durch ablesen der Wahrheitstabelle entnommen.

(a)

Disjunktive Normalform:

$$ f(x, y, z) = (x \land y \land z) \lor (\neg x \land \neg y \land z) \lor (\neg x \land \neg y \land \neg z) $$

(b)

Konjunktive Normalform:

$$ f(x, y, z) = (D{110} \land D{101} \land D{100} \land D{011} \land D_{010}) $$

$$ f(x, y, z) = (\neg x \lor \neg y \lor z) \land (\neg x \lor y \lor \neg z) \land (\neg x \lor y \lor z) \land (x \lor \neg y \lor \neg z) \land (x \lor \neg y \lor z) $$

Aufgabe 9

Gegeben ist folgende Formel:

$$ F: A \equiv (B \lor C) $$

(a)

A	B	C	|	$A$	$\equiv$	$(B \lor C)$
1	1	1	|		1	1
1	1	0	|		1	1
1	0	1	|		1	1
1	0	0	|		0	0
0	1	1	|		0	1
0	1	0	|		0	1
0	0	1	|		0	1
0	0	0	|		1	0

Eine disjunktive Normalform erhalten wir, indem wir disjunktiv die charakteristischen Konjunkte verbinden.

$$ F{DNF}: K{111} \lor K{110} \lor K{101} \lor K_{000} $$

$$ F_{DNF} = (x \land y \land z) \lor (x \land y \land \neg z) \lor (x \land \neg y \land z) \lor (\neg x \land \neg y \land \neg z) $$

(b)

$F:$	$A \equiv (B \lor C)$
$F:$	$(\neg A \lor (B \lor C)) \land (A \lor \neg (B \lor C))$
$F:$	$(\neg A \lor B \lor C) \land (A \lor (\neg B \land \neg C))$
$F:$	$(\neg A \lor B \lor C) \land ((A \lor \neg B) \land (A \lor \neg C))$
$F:$	$(\neg A \lor B \lor C) \land (A \lor \neg B) \land (A \lor \neg C)$

$$ F_{KNF}: (\neg A \lor B \lor C) \land (A \lor \neg B) \land (A \lor \neg C) $$

Aufgabe 10

|| |:--| |"Rote Tür: Pforte in die Freiheit"| |"Blaue Tür: Pforte ins Verderben, falls Grün ins Verderben führt"| |"Grüne Tür: Pforte in die Freiheit, falls Rot ins Verderben führt"| |"Nicht alles ist wahr, nicht alles ist falsch, aber nur ein Weg führt hinaus!"|

Wir stellen zunächst 3 Variablen dafür auf, ob die jeweiligen Türen in die Freiheit führen. Türen die nicht in die Freiheit führen, führen implizit ins Verderben.

$R$ ... rote Tür führt in die Freiheit, $B$ ... blaue Tür führt in die Freiheit, $G$ ... grüne Tür führt in die Freiheit

|| |:-:| |$F_1: R \equiv \top$| |$F_2: \neg B \equiv \neg G$| |$F_3: G \equiv \neg R$| |$F_4: (R \land \neg B \land \neg G) \lor (\neg R \land B \land \neg G) \lor (\neg R \land \neg B \land G)$| |$F_5: \neg (F_1 \land F_2 \land F_3) \land \neg (\neg F_1 \land \neg F_2 \land \neg F_3)$|

Formel $F_4$ drückt aus, wie nur eines aller drei Türen ein Weg in die Freiheit sein kann. Formel $F_5$ ist die tatsächliche Komplikation, nämlich können nicht alle Formeln stimmen oder falsch sein.

Geeignete Reduktionen der ersten drei Formeln führen uns zu:

$R \equiv \top$	$\neg B \equiv \neg G$	$G \equiv \neg R$
$(R \land \top) \lor (\neg R \land \bot)$	$(\neg B \land \neg G) \lor (\neg \neg B \land \neg \neg G)$	$(G \land \neg R) \lor (\neg G \land \neg \neg R)$
$R \lor \bot$	$(\neg B \land \neg G) \lor (B \land G)$	$(G \land \neg R) \lor (\neg G \land R)$
$R$	$B \equiv G$	$G \not\equiv R$

Hat sich jetzt nicht so viel gebracht, aber damit lässt sich zumindest einmal leichter arbeiten. Das Kernstück dieses Rätsels ist jene Formel die alle anderen zusammenbringt, also $F_5$, daher beginnen wir nun diese auszuwerten:

|| |:--| |$F_5: \neg (F_1 \land F_2 \land F_3) \land \neg (\neg F_1 \land \neg F_2 \land \neg F_3)$| |$F_5: (\neg F_1 \lor \neg F_2 \lor \neg F_3) \land (\neg \neg F_1 \lor \neg \neg F_2 \lor \neg \neg F_3)$| |$F_5: (\neg F_1 \lor \neg F_2 \lor \neg F_3) \land (F_1 \lor F_2 \lor F_3)$| |$F_5: (\neg R \lor \neg (B \equiv G) \lor \neg (G \not\equiv R)) \land (R \lor (B \equiv G) \lor (G \not\equiv R))$| |$F_5: (\neg R \lor (B \not\equiv G) \lor (G \equiv R)) \land (R \lor (B \equiv G) \lor (G \not\equiv R))$| |$F_5: (\neg R \lor (B \land \neg G) \lor (\neg B \land G) \lor (G \land R) \lor (\neg G \land \neg R)) \land (R \lor (B \land G) \lor (\neg B \land \neg G) \lor (G \land \neg R) \lor (\neg G \land R))$| |$F_5: (\neg R \lor (B \land \neg G) \lor (\neg B \land G) \lor (G \land R) \lor (\neg G \land \neg R)) \land (R \lor (B \land G) \lor (\neg B \land \neg G) \lor (G \land \neg R) \lor (\neg G \land R))$|

Diese Form für $F_5$ lässt sich zumindest computerisiert leicht in eine Wahrheitstabelle bringen. Worauf es hier wirklich ankommt, ist die Menge aller Interpretationen für die sowohl $F_4$, als auch $F_5$ wahr sind zu finden (Formeln $F_1$, $F_2$ und $F_3$ haben wir ja schon in $F_5$ untergebracht. In einer Wahrheitstabelle ergibt sich:

B	G	R	|	$F_5$	$F_4$	$F_4 \land F_5$
1	1	1	|	1	0	0
1	1	0	|	1	0	0
1	0	1	|	1	0	0
1	0	0	|	0	1	0
0	1	1	|	1	0	0
0	1	0	|	1	1	1
0	0	1	|	0	1	0
0	0	0	|	1	0	0

Es gibt insgesamt nur eine Interpretation, für welche unsere Vorraussetzung, die Formel $F_4 \land F_5$ erfüllt ist, nämlich $I(B) = 0$, $I(G) = 1$ und $I(R) = 0$. Mithilfe dieser Lösung sind wir eindeutig davon überzeugt, das die grüne Tür ins freie führt.

Aufgabe 11

(a)

Zentral in dieser Aufgabe ist es, wer mitgenommen wird. Daher ist es naheliegend, als Aussagevariablen zu bestimmen, ob jeweils eine bestimmte Person mitgenommen wird oder nicht.

$m{Opa}$ ... nimmt Opa Knack mit, $m{Oma}$ ... nimmt Oma Knack mit, $m_K$ ... nimmt Karlchen Knack mit, $m_M$ ... nimmt Megabyte Knack mit, $m_S$ ... nimmt Schlabber Knack mit

|| |:--| |$F1: \neg m{Opa}$| |$F_2: m_M \not\equiv m_K$| |$F3: m{Oma} \supset m_K$| |$F_4: m_S \not\equiv m_K$| |$F_5: mM \equiv (m{Oma} \lor m_K)$|

(b)

Aus $F_1$ folgt, dass Opa Knack ausscheidet, daher müssen wir ihn gar nicht erst berücksichtigen. Klar ist auch, dass Oma Knack mitkommt, wenn Karlchen Knack mitkommt, wobei das umgekehrte nicht zwingend wahr sein muss, daher müssen wir das im Hinterkopf aufbewahren. Wie immer versuchen wir eine Situation zu finden, welche jeden Sachverhalt erfüllt, also betrachten wir die Formel $F_6: F_2 \land F_3 \land F_4 \land F_5$.

|| |:--| |$F_6: F_2 \land F_3 \land F_4 \land F_5$| |$F_6: (m_M \not\equiv mK) \land (m{Oma} \supset m_K) \land (m_S \not\equiv m_K) \land (mM \equiv (m{Oma} \lor m_K))$| |$F_6: (\neg m_M \lor \neg m_K) \land (m_M \lor mK) \land (\neg m{Oma} \lor m_K) \land (\neg m_S \lor \neg m_K) \land (m_S \lor m_K) \land (\neg mM \lor \neg (m{Oma} \lor m_K)) \land (mM \lor (m{Oma} \lor m_K))$| |$F_6: (\neg m_M \lor \neg m_K) \land (m_M \lor mK) \land (\neg m{Oma} \lor m_K) \land (\neg m_S \lor \neg m_K) \land (m_S \lor m_K) \land (\neg mM \lor (\neg m{Oma} \land \neg m_K)) \land (mM \lor m{Oma} \lor m_K)$| |$F_6: (\neg m_M \lor \neg m_K) \land (m_M \lor mK) \land (\neg m{Oma} \lor m_K) \land (\neg m_S \lor \neg m_K) \land (m_S \lor m_K) \land (\neg mM \lor \neg m{Oma}) \land (\neg m_M \lor \neg m_K) \land (mM \lor m{Oma} \lor m_K)$| |$F_6: (\neg m_M \lor \neg m_K) \land (m_M \lor mK) \land (\neg m{Oma} \lor m_K) \land (\neg m_S \lor \neg m_K) \land (m_S \lor m_K) \land (\neg mM \lor \neg m{Oma}) \land (mM \lor m{Oma} \lor m_K)$|

In diesem Stadium fällt uns auf, dass $m_K$ eine zentrale Rolle spielt. Um algebraisch fortschreiten zu können, teilen wir das Problem auf. Einmal betrachten wir die sich ergebenden Interpretationen wenn $\neg m_K$ und ein zweites mal betrachten wir die sich ergebenden Interpretationen wenn $mK$. Der erste Fall wird denotiert als $F{6,mK}$, der zweite als $F{6,\neg m_K}$.

|| |:--| |$F_{6,m_K}: (\neg m_M \lor \neg \top) \land (mM \lor \top) \land (\neg m{Oma} \lor \top) \land (\neg m_S \lor \neg \top) \land (m_S \lor \top) \land (\neg mM \lor \neg m{Oma}) \land (mM \lor m{Oma} \lor \top)$| |$F_{6,m_K}: \neg m_M \land \top \land \top \land \neg m_S \land \top \land (\neg mM \lor \neg m{Oma}) \land \top$| |$F_{6,m_K}: \neg m_M \land \neg m_S \land (\neg mM \lor \neg m{Oma})$| |$F_{6,m_K}: \neg m_M \land \neg m_S$|

Hier stellt sich heraus, dass wenn Karlchen Knack mitkommt, Megabyte Knack und Schlabber Knack keineswegs mitkommen. Das ist eigentlich keine neue Information. Interessant ist aber, dass es irrelevant ist, ob Oma Knack mitkommt oder nicht. Das bedeuted, beide Interpretationsmöglichkeiten sind Lösungen.

Im Falle das Karlchen Knack nicht mitkommt:

|| |:--| |$F_{6,\neg m_K}: (\neg m_M \lor \neg \bot) \land (mM \lor \bot) \land (\neg m{Oma} \lor \bot) \land (\neg m_S \lor \neg \bot) \land (m_S \lor \bot) \land (\neg mM \lor \neg m{Oma}) \land (mM \lor m{Oma} \lor \bot)$| |$F_{6,\neg m_K}: \top \land mM \land \neg m{Oma} \land \top \land m_S \land (\neg mM \lor \neg m{Oma}) \land (mM \lor m{Oma})$| |$F_{6,\neg m_K}: mM \land \neg m{Oma} \land m_S \land (\neg mM \lor \neg m{Oma}) \land (mM \lor m{Oma})$| |$F_{6,\neg m_K}: mM \land \neg m{Oma} \land m_S$|

In diesem Fall ist die Antwort eindeutig, wenn Karlchen Knack nicht mitkommt, kommen dafür Megabyte Knack und Schlabber Knack mit. Es gibt also insgesamt folgende Konstellationen, die sich ergeben können:

|| |:--| |$mK \land m{Oma} \land \neg m_M \land \neg m_S$| |$mK \land \neg m{Oma} \land \neg m_M \land \neg m_S$| |$\neg mK \land \neg m{Oma} \land m_M \land m_S$|

Welches dieser Konstellationen tatsächlich realisiert werden wird, wird Babyface Knack sich wohl aussuchen müssen.

Aufgabe 12

Gegeben haben wir zwei Formeln $G$ und $H$. Unser Ziel ist es herauszufinden, ob $F$ durch $G$ und $H$ subsumiert wird. Umformuliert ist unser Ziel, die Formel $F: G \land H$ auf Gültigkeit zu überprüfen.

Unser Mittel hierfür ist ein SAT-Solver. Das erste Problem, dass sich uns stellt, ist das unser SAT-Solver, wie jeder andere auch, eine Formel nur auf Erfüllbarkeit prüft und aufhört, sobald es eine Interpretation der Variablen von $G$ und $H$ gefunden hat, die $F \equiv (G \land H)$ erfüllt.

Betrachten wir alle Situationen, in denen F gültig ist, so können wir sie in einer Wahrheitstabelle festhalten:

$F$
1
$\cdot$
$\cdot$
$\cdot$
1
1

Würden wir die Wahrheitstabelle auf die potenziell sehr zahlreichen Variablen von $G$ und $H$ expandieren, müssten wir schauen, dass wenn auch immer $G$ erfüllt ist, auch $H$ erfüllt ist. Unser SAT-Solver würde aber gleich bei der ersten Interpretation, in der dies der Fall ist, aufhören.

Also müssen wir unser Problem so umgestalten, dass es auf einen SAT-Solver ausgelegt ist. Wenn unser Ziel ist, dass $F$ immer gilt, dann ist unser Ziel auch indirekt, dass $\neg F$ immer nicht gilt.

$\neg F$
0
$\cdot$
$\cdot$
$\cdot$
0
0

Wir können daher die Formel $F \equiv (G \land H)$ negiert an den SAT-Solver übergeben, also $\neg F \equiv (\neg G \lor \neg H)$. Ist die Formel $\neg F$ erfüllbar, so gibt es eine Interpretation die $\neg F$ erfüllt. Im Umkehrschluss bedeutet dass, es gibt eine (dieselbe) Interpretation, welche $F$ nicht erfüllt. Der Vorteil dieser Herangehensweise ist, dass in diesem Fall der SAT-Solver auch jene Interpretation nennt, welche $F$ nicht erfüllt.

Jetzt müssen wir nur noch darauf achten, wie die Ergebnisse des SAT-Solvers zurücktransformiert werden können. Liefert der SAT-Solver erfüllbar, so ist $\neg F$ erfüllbar und daher $F$ widerlegbar. Liefert wiederum der SAT-Solver unerfüllbar, so ist $\neg F$ unerfüllbar und daher $F$ gültig.

Wenn wir also wissen wollen, ob $F \equiv (G \land H)$ gültig ist, müssen wir den SAT-Solver fragen, ob $\neg F \equiv (\neg G \lor \neg H)$ unerfüllbar ist.

Da unser SAT-Solver aber nur Formeln in KNF entgegennimmt, müssen wir unsere Formel noch umformen:

|| |:-:| |$\neg F \equiv (\neg G \lor \neg H)$| |$F \not\equiv (\neg G \lor \neg H)$| |$(\neg F \lor \neg (\neg G \lor \neg H)) \land (F \lor (\neg G \lor \neg H))$| |$(\neg F \lor (\neg \neg G \land \neg \neg H)) \land (F \lor \neg G \lor \neg H)$| |$(\neg F \lor G) \land (\neg F \lor H) \land (F \lor \neg G \lor \neg H)$|

Aufgabe 13

(a)

Um herauszufinden, welche Wörter in $\mathcal{L}$ enthalten sein müssen, können wir eine art reverse engineering versuchen und beginnend beim Endknoten 2 den Automaten rückwärts zu traversieren. Sofort kommen wir auf zwei triviale Fälle, ${ a, b }$. Beides dieser Fälle entstehen bei einem Übergang vom Anfangsknoten 1, sind aber nicht die einzigen solchen Fälle. Nämlich ist es uns möglich, vorher beliebig oft c zu lesen. Daher bilden wir alle weiteren Kombinationen, die uns von Zustand 1 zu Zustand 2 führen, ${ ca, cb, cca, ccb }$. Jetzt wo alle zugelassenen Übergänge von 1 nach 2 ausgeschöpft sind, betrachten wir den einzigen anderen Zustand, der zu 2 führt, nämlich 3. Es gibt zwei Wege nach 3 zu kommen, einmal über 2 und einmal über 3. Zweiteres ist uns unwichtig, weil über diesen Weg keine Eingabesequenz die kurz genug ist enthalten ist. Damit der Automat also für eine Eingabesequenz bei Zustand 2 endet, muss zuletzt Zeichen c gelesen werden. Der Automat kann nur in Zustand 3 kommen, wenn er c liest, also muss das Wort mit cc enden. Wie der Automat nach 2 kommen kann, haben wir ja schon festgestellt, von Zustand 1 durch ein a oder ein b, also ergeben sich noch die Wörter ${ acc, bcc }$.

Vereinigen wir unsere Ergebnisse, kommen wir auf die gültige Sprache $\mathcal{L}$:

$$ \mathcal{L} = { a, b } \cup { ca, cb, cca, ccb } \cup { acc, bcc } = { a, b, ca, cb, cca, ccb, acc, bcc } $$

(b)

$\delta^(1, cbcac) = \delta^(\delta(1, c), bcac)$
$\delta^(\delta(1, c), bcac) = \delta^(1, bcac)$
$\delta^(\delta(1, b), cac) = \delta^(2, cac)$
$\delta^(\delta(2, c), ac) = \delta^(3, ac)$
$\delta^*(\delta(3, a), c) = \delta(3, c)$
$\delta(3, c) = 2$

(c)

Tabellarisch darstellen lässt sich der Automat $\mathcal{A}$ durch die $\delta$-Funktion:

$\delta$	1	2	3	4
a	2	4	3	4
b	2	4	4	1
c	1	3	2	4

Dadurch dass in jedem Zustand jeder Zustandsübergang eindeutig definiert ist (nur ein Wert pro Zelle), handelt es sich um einen deterministischen Automaten.

Aufgabe 14

(a)

00000010

(b)

$\delta^(1, oopopo) = \delta^(\delta(1, o), opopo)$
$\delta^(1, oopopo) = \delta^(\delta(1, o), opopo)$
$\delta^(1, opopo) = \delta^(\delta(1, o), popo)$
$\delta^(1, popo) = \delta^(\delta(1, p), opo)$
$\delta^(2, opo) = \delta^(\delta(2, o), po)$
$\delta^(3, po) = \delta^(\delta(3, p), o)$
$\delta(1, o) = 1$

$\gamma^(1, oopopo) = \gamma^(\delta(1, o), opopo)$
$\gamma^(1, oopopo) = \gamma(1, o) \cdot \gamma^(\delta(1, o), opopo)$
$0 \cdot \gamma^(1, opopo) = 0 \cdot \gamma(1, o) \cdot \gamma^(\delta(1, o), popo)$
$00 \cdot \gamma^(1, popo) = 00 \cdot \gamma(1, p) \cdot \gamma^(\delta(1, p), opo)$
$000 \cdot \gamma^(2, opo) = 000 \cdot \gamma(2, o) \cdot \gamma^(\delta(2, o), po)$
$0000 \cdot \gamma^(3, po) = 0000 \cdot \gamma(3, p) \cdot \gamma^(\delta(3, p), o)$
$00001 \cdot \gamma(1, o) = 000010$

(c)

$\mathcal{A}$ beschreibt unseren Automaten, während $[\mathcal{A}]$ unsere Übersetzungsfunktion beschreibt. Dies ergibt intuitiv auch sinn, weil ein beliebiges Wort in der Eingangssprache auf ein Wort in der Ausgangssprache abgebildet wird, quasi übersetzt wird. Folgende Definitionen sind für uns relevant.

$$ [\mathcal{A}] : \Sigma^* \to \Gamma^* $$

$$ \mathcal{A} = \gamma^*(q_0, w) $$

Abbilden lässt sich die Übersetzungsfunktion wie folgt. Um für weitere Argumentation den Ergebnissen eine Bedeutung zu verschaffen, wurde auch der jeweilige Endzustand $q_f$, in dem der Mealy-Automat nach Übersetzung des Eingangswortes $w$ verbleibt.

|$w$:|$\varepsilon$ |o|p|oo|op|pp|po|ooo|oop|opo|opp|ppp|ppo|pop|poo| |--:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$\mathcal{A}:$|$\varepsilon$|0|0|00|00|00|00|000|000|000|000|000|000|001|000| |$q_f$:|1 |1|2|1 |2 |2 |3 |1 |2 |3 |2 |2 |3 |1 |1 |

Wäre der Automat indeterministisch, hätten wir bei der Analyse der Übersetzungsfunktion keine eindeutig festgelegten Übersetzungen (d.h., Übersetzungsmengen). Aus $[\mathcal{A}]$ wird ersichtlich, dass gewisse Eingabewörter den Automaten in den Ursprungszustand 1 hinterlassen. Diese könnte man beliebig (auch beliebig oft) miteinander verketten, um Zusammensetzungen ihrer jeweiligen Übersetzungen zu bekommen (z.B., $o \to 0 \land ooo \to 000 \implies oooo \to 0000$).

Dadurch, dass der Automat nur 3 Zustände besitzt, und mit Eingabewörtern der Länge 2 bereits alle Zustände erreichen können, können wir auf interessantes schließen. Nämlich sind alle Eingabewörter der Länge 2 in der Menge an Eingabewörtern der Länge 3 enthalten, also können wir qualitativ auf das Verhalten des Automaten schließen. Eine Übersetzung endet nur in Zustand 3, wenn die Eingabefolge mit po endet. Durch Betrachtung der Eingabewörter poo und pop erfahren wir, Das die Zustände des Automaten nur zyklisch von 1 bis 3 voranschreiten können, bevor er bei Zustand 3 in Zustand 1 übergeht.

Das ist außerdem interessant, weil durch diesen Fakt die Tabelle bereits alle besonderen Übersetzungen darstellt. Bei allen längeren Wörtern können wir bereits mit Leichtigkeit vorhersagen, wie sie verlaufen müssen.

Aufgabe 15

(a)

Es ist schwierig aus der Aufgabenstellung allein zu entscheiden, welche Informationen zwecks sinnvoller Abstraktion weggelassen werden können. Beispielsweise sind höchstens 5 Minuten zur Entschärfung der Bombe für eine erfolgreiche Entschärfung gewährt. Wie lange dauert es, 1L Wassser von einer Quelle/Flasche in eine Flasche zu verschaffen? Für eine Abstraktion in der die Zeit berücksichtigt werden soll, können wir die Zustände in diskretisierten Zeitschritten von $\Delta t$ aufteilen, wobei $\Delta t$ die Zeit beschreibt, die für eine Umverteilung von 1L benötigt wird.

Ist es wichtig ob, zu modellieren, woran gerade McClane und Carver beschäftigt sind? Inwieweit können die beiden parallel arbeiten. Das könnten wir beispielsweise in Zuständen festhalten, in dem wir für einen bestimmten Zeitschritt festhalten, an welcher Flasche einer der beiden gerade werkelt, wobei diese Flasche zum Beispiel durch $f \in { \diagup, M, C }$ denotieren.

Der Brunnen ist auch ein Faktor, weil er offensichtlich nur eine Flasche gleichzeitig befüllen kann. Analog zu unseren beiden Herrschaften könnte man die Beschäftigung des Brunnens durch $b \in { \diagup, 3, 5 }$ denotieren, wobei 3 und 5 die gerade aufzufüllende Flasche denotiert.

Die Waage spielt auch einen interessanten Faktor, nämlich ist es intuitiverweise nur sinnvoll, nicht beide Flaschen gleichzeitig abzuwiegen. Hier könnte man analog wie auch beim Brunnen vorgehen.

Bevor wir unseren Traum einer perfekten Modellierung realisieren, machen wir aber eine Aufwandsabschätzung und kommen darauf, dass wir allein für die Beschäftigten, den Brunnen und die Waage $3^3 = 27$ Zustände benötigen. Hier ist noch gar nicht faktorisiert, wie sich die Flaschenmengen abbilden lassen, geschweige der Zeitdiskretisierung! Das ist leider nicht zielführend, also werden wir noch ein paar Annahmen treffen müssen.

Da es darauf ankommt, auf exakt 4 Gallonen zu kommen und wir das nur erreichen können, indem wir eine Konstellation der beiden Kanister erreichen, in denen wir uns sicher sein können, dass sie zusammen auf 4 Gallonen kommen. Wir können ja beliebig nachfüllen und müssen uns keine Gedanken über das ausschütten von exzessivem Wasser machen.

Wir denotieren daher unsere Zustände als $n|m$, wobei $n \in [0, 3] \subset \mathbb{N}$ und $m \in [0, 5] \subset \mathbb{N}$ die jeweilige Füllmenge der 3 Gallonen|5 Gallonen Kanister angeben.

Kommen wir nun zu unser Liste der Annahmen:

• wir ignorieren die Zeit, ob die Entschärfung erfolgreich stattfindet, hängt ohnehin davon ab, wie durch die Zustände gegangen wird. Wenn es Zyklen gibt, könnte all die Zeit durch traversieren der Zustände in einem dieser Zyklen verschwendet werden, auch wenn es eine Lösung gibt. Wir legen also fest, wenn es eine Lösung gibt, wird diese beim ersten Versuch erraten

• die obige Annahme ist besonders sinnvoll, wenn wir außerdem annehmen, es geht sich innerhalb der 5 Minuten aus, wenn optimal vorgegangen wird, angenommen es gibt eine Lösung

• wir nehmen an, McClane und Carver werden schon parallelisieren wo geht, uns is aber nur wichtig, wie die Füllmengen von Zustand zu Zustand transitionieren, also arbeiten die beiden einfach zusammen wenn ein Schritt nicht parallelisiert werden kann. Aus der Sicht des Automaten betrachten wir beide als eine Person die unsere Flaschen von Füllmenge zu Füllmenge transitioniert

• wir lassen nicht zu, dass bei Flascheninhalte sich gleichzeitig ändern, es sei denn, die Flaschen werden von von einer zur jeweils anderen entfüllt

• wir lassen zu, eine Flasche mit mehr Inhalt als die andere zulässt rüberzuschütten. Wenn also die 5 Gallonen Flasche in die 3 Gallonen Flasche entleert wird, gehen die überschüssigen 2 verloren. Da es äquivalent wäre, nur 3 Gallonen zu übertragen und die restlichen 2 Gallonen auszuleeren, macht das keinen Unterschied

• wir nehmen an, die Waage kann beide Flaschen gleichzeitig wiegen. Wir brauchen die Waage wirklich nur, um auf die finalen 4 Gallonen zu kommen. Wenn wir gleich zu Beginn eine winzige Menge Zeit verschwenden, wissen wir, wie schwer eine jeweilige leere Flasche sein muss, indem wir sie alleine leer auflegen. Sind z.B. beide Flaschen auf der Waage während die 5 Gallonen Flasche 4 Gallonen enthält, können wir mental das Gewicht der leeren 3 Gallonen Flasche abziehen. Das ist zulässig, weil einfach die leere Flasche entfernt werden kann und die Waage die 4 Gallonen dann akzeptiert

• die Waage ist in erster Linie nur notwendig, um die Bombe zu entschärfen. Wir gehen davon aus, McClane und Carver sind klug genug, mental zu berechnen was die jeweiligen Füllmengen zu einem Zustand sein müssen aufgrund des hervorigen Zustandübergangs und müssen sich nicht mit Messungen zwischendurch beschäftigen

• ob die Waage nun die Kombination 3 Gallonen + 1 Gallone zulässt, ist nun interessant, weil das implizieren würde, dass das Gewicht der individuellen Flaschen irrelevant ist!

(sei $F_x$ die $x$ Gallonen Flasche, $G_x$ das Gewicht von $x$ Gallonen, $G(F_x)$ das Gewicht einer $x$ Gallonen Flasche, wenn dann $3|1$, $1|3$ sowie $4|0$ alles gültige Lösungen wären, dann würde die Waage also folgende Gewichter akzeptieren: $G \in { G_3 + G(F_5) + G_1 + G(F_3), G_1 + G(F_5) + G_3 + G(F_3), G_4 + G(F_5) }$)

• der obige Punkt ist uns aber egal, weil wir im Falle der Zustände $3|1$ sowie $1|3$ einfach die Gallonen in die 5 Gallonen Flasche überfüllen können, und wir somit mit 4 Gallonen in der 5 Gallonen Flasche enden. Um die obige Komplikation zu umgehen, betrachten wir nur $4|0$ als einen gültigen Endzustand

• wir beginnen mit leeren Flaschen, d.h., der Zustand zu Beginn ist $q_0 = 0|0$

Die Menge an potenziellen Zuständen können wir abschätzen, indem wir betrachten, welche Zusammensetzungen aus $n$ und $m$ entstehen können. Wir kommen auf $4 * 6 = 24$. Da erwartet wird, dass nicht alle Zustände erreichbar sind, erachten wir das als in Ordnung.

(b)

Zu guter Letzt beschreiben wir den Mechanismus eines Zustandübergangs $\delta$ etwas genauer. Da ja ein Zustand die Füllmenge beider Flaschen berücksichtigt und nicht mehr, definieren wir einen Zustandsübergang als Änderung der Füllmengen. Nach einem Zustandsübergang kommt nach wie vor ein Zustand mit Füllmengen heraus. Selbstverständlich unterliegt diese Operation des Umfüllens gewissen zugrunde liegenden Regeln. Diese sollten ausführlich genug beschrieben sein, legal sind daher natürlich nur Zustandsübergänge, die in Umsetzung auf die reale Situation auch einen Sinn haben.

Diese Beschränken sich auf ausleeren, auffüllen und umfüllen.

Um diese Übergänge kompakt zu beschreiben, werden die Übergänge jeweils als Zeichenfolgen der Länge 2 denotiert, wobei nur Zahlen erlaubt sind. Die erste Ziffer beschreibt, wie viel Gallonen zur ersten Flasche hinzugekommen sind, die zweite analog wie viel Gallonen zur zweiten Flasche hinzugekommen sind. Wir lassen zu, diese Ziffern $n$ und $m$ auch negativ sein zu lassen, um zu repräsentieren, wann eine Flasche entleert wird. Die Menge an Zeichenfolgen für mögliche Zustandsübergänge ist daher:

$$ \Sigma = [-5, 5] \times [-3, 3] = { \pm 5, \pm3; \pm 5, \pm2; ... \pm 5, 0; ... \pm 1, 0; 0, 0 } $$

(c)

{ width=115% }

Der Automat muss zwar vollständig beschrieben werden, aber um Komplikationen zu vermeiden, wurden beim bereits sehr komplizierten grafischen Automaten aus Fig.1 zwei Kompromisse eingegangen:

• Der Endzustand $4|0$ wurde zwei mal abgebildet, weil im Grunde über zwei "Wege" auf diesen Zustand gekommen werden kann. Das wurde als sinnvoll erachtet, um die Symmetrie der Grafik und die Darstellung der zwei besonderen "Wege" nicht zu verwerfen. Beide Instanzen der Endzustände $4|0$ wurden orange markiert.

• Die Zustandsübergänge von Zustand $4|0$ werden ausgelassen, weil eine Annahme war, dass wir den optimalen Vorgang wählen und infolgedessen auch fertig sind

(d)

Eine Lösung, die sich aus der linken Hälfte des Automaten ablesen lässt, wäre die Eingabefolge 5,0;-3,3;0,-3;-2,2;5,0;-1,1;0,-3.