Link zur Web Version dieser Notion page: https://www.notion.so/AB-1-816446f762064cb382bc9c13113cb248

✅ Aufgabe 1

Verlangt:

1. Zugrundeliegende Inferenzregel angeben → Gültigkeit bestimmen
   • "Falls in der Wahrheitsbelegung $I$ alle Prämissen wahr sind, dann ist auch die Konklusion wahr in $I$ ." (Kriterium für die Gültigkeit von Inferenzregeln)

     (Wahrheitsbelegung = Interpretation)

     • gültig wenn für alle Wahrheitsb. immer $\textsf{val}_I(F) = 1$
     • erfüllbar wenn für mindestens eine Wahrheitsb. $\textsf{val}_I(F) = 1$
     • widerlegbar wenn für mindestens eine Wahrheitsb. $\textsf{val}_I(F) = 0$
     • unerfüllbar wenn für alle Wahrheitsb. immer $\textsf{val}_I(F) = 0$

2. Weiteres Beispiel / Gegenbeispiel

a)

Es gibt Menschen die kriminell sind (wahr)
Alle Asylanten sind Menschen (wahr)
------------------------------------------
Alle Asylanten sind kriminell (falsch

Formel der Inferenzregel: ungültig (Generalisierung)

$(\forall x \in Y) \wedge (z \in Y) \not\Rightarrow (\forall z = x)$

Alle x sind y								Prämisse
z ist ein y									Prämisse
------------------------------------------
z ist ein x									Konklusion

Weiteres Gegenbeispiel:

Alle Bälle sind rund (wahr)
Die Sonne ist rund (wahr)
-----------------------------------------
Die Sonne ist ein Ball (falsch)		

b)

Wenn alle Tober xetig sind
und ein Hituch ein Tober ist
------------------------------------------
Dann ist Hituch xetig

Inferenzregel: (gültig)

$(\forall T \sube X) \wedge (h \in T) \Rightarrow (\forall h \in X)$

Alle t sind x
h ist ein t
------------------------------------------
h ist ein x	

Weiteres Beispiel aus dem Alltag:

Wenn alle Urgroßmütter Großmütter sind
und eine Großmutter eine Mutter ist
------------------------------------------
Dann ist eine Urgroßmutter eine Mutter

c)

Alle Katzen miauen
Bello ist keine Katze
------------------------------------------
Also miaut Bello nicht

Inferenzregel: (ungültig)

$(\forall K \sube M) \wedge (b \not\in K) \not\Rightarrow (\forall b \not\in M)$

Alle k sind m
b ist kein k
------------------------------------------
b ist kein m

Gegen-Beispiel aus dem Alltag:

Alle Männer sind Menschen
Frauen sind keine Männer
------------------------------------------
Frauen sind keine Menschen

✅ Aufgabe 2

Jeden Satz einzeln Modellieren:

Legen Sie Hammer und Schraubenzieher oder Akkuschrauber bereit. Packen Sie die Plastikteile aus, aber beschädigen Sie dabei die Beschichtung nicht.

Nur wenn Sie die Version 2.0 des Modells erworben haben, stecken Sie nun alle Teile zusammen. Falls nicht, müssen Sie alle Teile verleimen.

Falls Sie beim Aufbau Probleme haben oder Teile fehlen, wenden Sie sich bitte an unsere Service-Hotline.

✅ Aufgabe 3

$M$ Maria kommt mit ins Kino

$C$ Clara kommt mit ins Kino

$P$ Peter kommt mit ins Kino

a)

Maria kommt mit ins Kino.

$M$

b)

Peter kommt vielleicht mit.

$P$Das Wort vielleicht lässt sich nicht modellieren.

c)

Clara kommt mit, Peter aber nicht.

$C\wedge(\neg P)$

d)

Wenn Maria mitkommt, dann kommt Peter nicht mit.

$M \uparrow P$

e)

Nur wenn Maria mitkommt und Peter nicht, dann kommt Clara.

$\bigl(M \wedge (\neg P)\bigl) \equiv C$

f)

Wenn Peter nicht kommt, dann kommt Clara nicht, und wenn Clara nicht kommt, dann kommt Peter nicht.

$P \equiv C$

g)

Mindestens eine(r) der drei kommt mit.

$M \vee C \vee P$

h)

Genau zwei kommen mit.

$(M \wedge C) \vee (M \wedge P) \vee (C \wedge P)$

i)

Höchstens zwei kommen mit.

$\neg (M \wedge C\wedge P)$

✅ Aufgabe 4

a)

Zeigen Sie, dass die Menge{iff, xor}vollständig ist für die Klasse der aussagenlogischen Funktionen.

Eine Menge von Funktionen heißt vollständig (für eine Funktionsklasse), wenn damit alle Funktionen (der Klasse) ausgedrückt werden können.

Beispiele

Man kann keine anderen Funktionen erzeugen, diese Menge ist nicht funktional vollständig .

Beweis: iff ist dual zu xor und man kann mit der Menge {xor} alleine beispielsweise nicht die Funktionen and sowie or bilden.

b)

Zeigen Sie, dass die Menge {iff, or} nicht vollständig ist.

Es reicht anzugeben dass eine einzige Funktion nicht darstellbar ist. - Ich nehme mir vor zu beweisen, dass die not Funktion nicht darstellbar ist, weil sie nur ein Argument beansprucht und ich intuitiv weiß, dass sie nicht mit iff oder or darstellbar ist.

Wir nutzen nur das Argument x (weil die not Funktion nur mit einem einzigen Argument arbeitet).

Hypothese

Induktiver Beweis (wobei n = # der Anwendungen eines Operators)

Alternativerweise:

Dadurch, dass iff die duale funktion zu xor ist: $\neg(\neg a \space \mathsf{ xor } \space \neg b) \equiv \textsf{iff}(a,b)$

✅ Aufgabe 5

Sei die Formel

a)

Syntaktische Korrektheit

Die Menge $\mathcal{A}$ der aussagenlogischen Formeln $\textsf{F}_i$ ist die kleinste für die gilt:

Ich kürze jede gültige Variable mit $V$ ab und beweise die Gültigkeit von innen nach außen mit Hinweisen auf die jeweiligen Bedingungen die dabei erfüllt werden

b)

Schrittweise Berechnung des Wertes $\textsf{val}_I(F)$

Ich berechne erneut nach dem oberen Muster von innen nach außen:

$\textsf{val}_I(F) = \textsf{val}_I(((A \vee \neg B) \supset C) \equiv((B \supset C) \vee \neg A))$

c)

Wahrheitstafel der Formel

https://tuwien2020.github.io/tgi-pages/#/truth-table?input=((a+or+!b)+=>+c )+%3C=%3E+((b+=%3E+c)+or+!a)

(Wahrheitsbelegung = Interpretation)

Diese Formel ist erfüllbar und widerlegbar, dadurch aber ungültig und unerfüllbar.

✅ Aufgabe 6

Zeigen Sie, dass die beiden Formeln äqvalent sind.

$F_1 := \neg((P \wedge Q) \supset(\neg P \equiv Q))$

$F_2 :=((Q \equiv R) \supset P) \wedge \neg(P \uparrow Q)$

a)

Wahrheitstafel

https://tuwien2020.github.io/tgi-pages/#/truth-table?input=(!((P+and+Q)+=>+(not+P+<=>+Q) ))+%3C=%3E+(((Q+%3C=%3E+R)+=%3E+P)+and+not(P+nand+Q))

b)

Algebraische Umformungen

Wir wollen algebraisch beweisen, dass dieser Ausdruck immer $true$ bzw $\top$ ergibt.

$\neg((P \wedge Q) \supset(\neg P \equiv Q)) \equiv (((Q \equiv R) \supset P) \wedge \neg(P \uparrow Q))$

$\neg((P \wedge Q) \supset(\neg P \equiv Q)) \equiv (((Q \equiv R) \supset P) \wedge P \wedge Q)$

Kontrolle: https://tuwien2020.github.io/tgi-pages/#/truth-table?input=(!((P+and+Q)+=>+(not+P+<=>+Q) ))+%3C=%3E+(((Q+%3C=%3E+R)+=%3E+P)+and+P+and+Q)

$\neg \bigl(\neg((P \wedge Q) \supset(\neg P \equiv Q))\bigl) \vee \bigl(((Q \equiv R) \supset P) \wedge P \wedge Q \bigl)$weil$a \Rightarrow b \Leftrightarrow \neg a \vee b$

$((P \wedge Q) \supset(\neg P \equiv Q)) \vee (((Q \equiv R) \supset P) \wedge P \wedge Q)$

Kontrolle: https://tuwien2020.github.io/tgi-pages/#/truth-table?input=((P+and+Q)+=>+(not+P+<=>+Q) )+or+(((Q+%3C=%3E+R)+=%3E+P)+and+P+and+Q)

Jetzt müsste nur eines der beiden Teile der $\vee$ Funktion $true$ sein damit die gesamte Gleichtung immer $true$ liefert.

Teil 1:

Teil 2:

✅ Aufgabe 7

Wenn ich schuldig bin, muss ich bestraft werden. [...]

$S$ Sokrates ist schuldig.

$B$ Sokrates muss bestraft werden.

Wenn Äqiuvalenz gemeint ist ( $S \equiv B$ )

Wenn Implikation gemeint ist ( $S \supset B$ )

$\begin{array}{cc|ccc}S & B & S\equiv B & S \supset B \\\hline 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{array}$

a)

... Ich bin schuldig.

Wenn $S = 1$

• dann ist $S \equiv B$ nur wahr wenn $B = 1$ also muss Sokrates bestraft werden

• dann kann $S \supset B$ auch wahr sein wenn $B \not= 1$ also ist es unklar ob Sokrates bestraft werden muss.

b)

... Ich muss bestraft werden

Wenn $B = 1$

• dann ist $S \equiv B$ nur wahr wenn $S = 1$ also ist er schuldig.

• dann kann $S \supset B$ auch wahr sein wenn $S \not= 1$ also ist es unklar ob er schuldig ist oder nicht.

Konsequenzbeziehung (logische Konseqzenz)

In diesem Fall würde die Gültigkeit / Ungültigkeit der Formel ( $S \equiv B$ ) bzw ( $S \supset B$ ) wenn man alle möglichen Fälle kennt und Wissen über die Realität von Sokrates hat ermitteln können ob Sokrates' Schlussfolgerungen per se Gültigkeit haben oder nicht.

✅ Aufgabe 8

Definition von DNF und KNF der Funktion $f: \mathbb{B}^{n} \mapsto \mathbb{B}$ .

Konj. / Disj. einer Menge von Variablen:

$\begin{array}{ll}\bigwedge\{F, G, H, \ldots\}=F \wedge G \wedge H \wedge \cdots & \bigwedge\{\}=\top \\\bigvee \{F, G, H, \ldots\}=F \vee G \vee H \vee \cdots & \bigvee\{\}=\perp\end{array}$

Wir haben eine Funktion $f$ mit

Definition DNF

Definition KNF

$\begin{array}{ccc|c} x & y & z & f(x,y,z) \\\hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array}$

Disjunktive Normalform

Konjunktive Normalform

✅ Aufgabe 9

$X : = (((G \vee \neg F) \supset H) \vee(\neg F \supset G))$

https://tuwien2020.github.io/tgi-pages/#/truth-table?input=(((G+or+!F)+=>+H )+or+(!F+=%3E+G))

Semantisch zur DNF gelangen:

https://www.wolframalpha.com/input/?i=DNF+(((G+||+~F)+implies+H)+||+(~F+implies+G))

Minimale Form:

Algebraisch zur KNF gelangen:

$(((G \vee \neg F) \supset H) \vee(\neg F \supset G))$

$((G \vee \neg F) \supset H) \vee F \vee G$weil$a \Rightarrow b \Leftrightarrow \neg a \vee b$

$(\neg G \wedge F) \vee H\vee F\vee G$weil$a \Rightarrow b \Leftrightarrow \neg a \vee b$

$F \vee G \vee H$weil$(\neg G \wedge F) \equiv F$

$\operatorname{KNF}_{X}= D_{000} = F \vee G \vee H$

✅ Aufgabe 10

"Mein lieber Watson, meine intensiven Nachforschungen gestatten mir, folgende Schlüsse zu ziehen:

• Wenn sich Brown oder Cooper als Täter herausstellen sollte, dann ist Adams unschuldig.

• Ist aber Adams oder Cooper unschuldig, dann muss Brown ein Täter sein.

• Ist Cooper schuldig, dann wäre Adams Mittäter."

$A$ Adam ist schuldig / der Täter

$B$ Brown ist schuldig / der Täter

$C$ Cooper ist schuldig / der Täter

Deklarierte Constraints die alle gültig sein müssen:

• $F_1:=(B \vee C) \supset \neg A$

• $F_2:=\neg (A \vee C) \supset B = (\neg A \wedge \neg C) \supset B$

• $F_3:=C \equiv A$

Wir suchen eine Interpretation für die $F_1 \wedge F_2 \wedge F_3$ gültig ist.

Wir vereinfachen $F_1$ und $F_2$ dadurch dass $A$ äquivalent zu $C$ ist.

• $G_{1}:=(B \vee A) \supset \neg A = B \wedge \neg A$

• $G_2:=\neg (A \vee A) \supset B = \neg A \supset B = A \vee B$weil$a \Rightarrow b \Leftrightarrow \neg a \vee b$

Wir suchen also dadurch eine Interpretation für die $B \wedge \neg A \wedge (A \vee B)$ immer gültig ist.

Dadurch, dass $A$ und $\neg A$ nicht gleichzeitig $true$ sein können, folgt, daraus:

es kann nur $B \wedge \neg A$ gültig sein.

Wir erinnern uns an $F_3:=C \equiv A$ .

Also lautet die Lösung $\neg A \wedge B \wedge \neg C$

Das bedeutet auf die "Wirklichkeit" übertragen:

Überprüfung mit Wahrheitstabelle:

https://tuwien2020.github.io/tgi-pages/#/truth-table?input=((B+or+C)+implies+!A )+and+(!(A+or+C)+implies+B)+and+(C+%3C=%3E+A)

✅ Aufgabe 11

Professor John Frink organisiert eine internationale Konferenz und sucht zur Unterstützung Student Volunteers.

Nach zahlreichen Vorstellungsgesprächen schränkt er die Auswahl auf Bart, Janey, Lisa, Milhouse und Richard ein,

wobei allerdings nur Lisa und Richard auch Fremdsprachen beherrschen.

Er stellt folgende Überlegungen an:

• Janey möchte ich auf jeden Fall, sie hat bei der letzten Konferenz schon erfolgreich mitgearbeitet.

• Ich kann höchstens drei Volunteers anstellen.

• Ich brauche jedenfalls mindestens einen Volunteer, der Fremdsprachen spricht.

• Richard und Milhouse kennen die Räume, in denen die Konferenz stattfinden soll. Einen der beiden sollte ich auf jeden Fall nehmen, aber beide zu nehmen ist nicht notwendig.

• Richard will nur mitmachen, wenn ich auch Bart anstelle.

• Milhouse und Lisa wollen nur gemeinsam genommen werden, da sie andernfalls zusammen auf Urlaub fahren wollen.

Variablen

$B$ Bart wird vom Professor angestellt.

$J$ Janey wird vom Professor angestellt.

$L$ Lisa wird vom Professor angestellt.

$M$ Milhouse wird vom Professor angestellt.

$R$ Richart wird vom Professor angestellt.

Formeln

Die folgenden contraints müssen in unserer deklarativen Modellierung eingehalten werden - also alle diese Formeln müssen bei der Interpretation nach der wir suchen $true$ sein.

• $F_1:=J$Janey muss mit

• $F_2:=\neg(\bigwedge\left\{B,J,L,M,R\right\}) \vee \neg(\bigwedge\left\{J,L,M,R\right\}) \vee \neg(\bigwedge\left\{L,M,R,B\right\}) \vee \neg(\bigwedge\left\{M,R,B,J\right\}) \vee \neg(\bigwedge\left\{R,B,J,L\right\}) \vee \neg(\bigwedge\left\{B,J,L,M\right\})$Höchstens 3

• $F_3:=L \vee R$Min. 1 Fremdsprachler

• $F_4:=R\uparrow M$Entweder Richard oder Milhouse

• $F_4:=R \equiv B$Richard nur mit Bart

• $F_5:= M \equiv L$Milhouse nur mit Lisa

Algebraische Lösung

Zuerst lösen nutzen wir die Äquivalenzen um alle Formeln zu vereinfachen und setzen $J$ überall auf $true$ .

$J = 1$

$RB$ steht für Richard und Bart zugleich

$ML$ steht für Milhouse und Lisa zugleich

• $F_2:=\neg(\bigwedge\left\{ML,RB\right\}) \vee \neg(\bigwedge\left\{ML,RB\right\}) \vee \neg(\bigwedge\left\{ML,RB\right\}) \vee \neg(\bigwedge\left\{ML,RB\right\}) \vee \neg(\bigwedge\left\{RB,ML\right\}) \vee \neg(\bigwedge\left\{RB,ML\right\})$Höchstens 3

• $F_3:= ML \vee RB$Min. 1 Fremdsprachler

• $F_4:=RB\uparrow ML$Entweder Richard oder Milhouse

wir vereinfachen weiter

• $F_2:=\neg(ML \wedge RB) = \neg ML \vee \neg RB$

• $F_3:= ML \vee RB$Min. 1 Fremdsprachler

• $F_4:=RB\uparrow ML$Entweder Richard oder Milhouse

Alle deklarierten constraints gemeinsam:

$(\neg ML \vee \neg RB) \wedge (ML \vee RB) \wedge (RB\uparrow ML)$

Das lässt sich weiter vereinfachen da: $(\neg ML \vee \neg RB) \wedge (ML \vee RB) \equiv (RB\uparrow ML)$

Es gibt 2 mögliche Interpretationen die alle constraints erfüllen.

Lösung übertragen auf die "Wirklichkeit"

Daraus folgt, dass der Professor unbedingt Lisa mitnimmt und zwischen Team $ML$ und Team $RB$ entscheiden muss.

Er könnte dafür beispielsweise eine faire Münze werfen.

✅ Aufgabe 12

Eine Kollegin und ich modellieren das gleiche Problem.

• Sie hat die Formel $H$

• Ich habe die Formeln $F,G$

• Unsere Formeln sehen unterschiedlich aus.

Überprüfung der semantischen Äquivalenz mit SAT-Solver

Was bedeutet es, wenn der SAT-Solver eine erfüllende Variablenbelegung findet?

Eine erfüllende Variablenbelegung für $\text{DNF}_H$ oder $\text{DNF}_X$ wäre eine Lösung unseres Problems → Eine Lösung die sich an alle deklarierten constraints hält.

✅ Aufgabe 13

Gegeben sei:

Dieser Automat ist ein DEA: von jedem Zustand gibt es einen eindeutigen Nachfolger mit jeder Eingabe aus dem Alphabet

$\sum =\{a,b,c\}$

$Q=\{1,2,3,4\}$

$q_0 = 1$

$F = \{0\}$

a)

Alle Wörter aus maximal 3 Zeichen die akzeptiert werden (mit denen der Automat in einem final state ) endet.

$\mathcal{L}_{|3|}(\mathcal{A})=\left\{w \in \Sigma^{*} \mid \delta^{*}\left(q_{0}, w\right) \in F, |w|\leq3\right\}$

1. $\epsilon$

2. $ac$

3. $abc$

4. $aab$

5. $bab$

6. $cab$

b)

Erweiterte Übergangsfunktion (auch für Sätze)

$\delta^{*}(1, bbacbc)$

$\delta^{*}( \delta^{*}(1,b),bacbc)$

$\delta^{*}( \delta^{*}(\delta^{*}(1,b),b),acbc)$

$...$

$\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(1,b),b),a),c),b),c)$

$\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(3,b),a),c),b),c)$

$\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(3,a),c),b),c)$

$\delta^{*}(\delta^{*}(\delta^{*}(4,c),b),c)$

$\delta^{*}(\delta^{*}(2,b),c)$

$\delta^{*}(2,c) = 1 \in F$

Dieses Wort ist Teil der akzeptierten Sprache

c)

Dieser Automat ist ein DEA: von jedem Zustand gibt es einen eindeutigen Nachfolger mit jeder Eingabe aus dem Alphabet

$\delta: Q \times \Sigma \mapsto Q$transition function

$\begin{array}{c|c} \delta & a & b & c \\\hline 1 & 2 & 3 & 3 \\ 2 & 4 & 2 & 1 \\ 3 & 4 & 3 & 3 \\ 4 & 2 & 1 & 2 \end{array}$

✅ Aufgabe 14

a)

$[\mathcal{A}](11001)= 000000$

$[\mathcal{A}](01011)= 000010$

$[\mathcal{A}](10101)=000100$

b)

$\delta^{*}(Z_{0}, 01010)$

$\delta^{*}(\delta^{*}(Z_{0},0),1010)$

$\dots$

$\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(Z_0,0),1),0),1),0)$

$\delta^{*}(\delta^{*}(\delta^{*}(\delta^{*}(Z_0,1),0),1),0)$

$\delta^{*}(\delta^{*}(\delta^{*}(Z_1,0),1),0)$

$\delta^{*}(\delta^{*}(Z_3,1),0)$

$\delta^*(Z_2,0) = Z_0$

Erweiterte Ausgabefunktion (auch für Sätze)

$\gamma^{*}\left(Z_{0}, 01010\right)$

$\gamma^{*}\left(Z_{0}, 01010\right) = \gamma(Z_0) \cdot \gamma^{*}(\delta(Z_0, 0), 1010) = 0\cdot \gamma^{*}(Z_0, 1010)$

$0\cdot \gamma^{*}(Z_0, 1010) = 0\cdot\gamma(Z_0) \cdot \gamma^{*}(\delta(Z_0, 1), 010) = 00\cdot \gamma^{*}(Z_1, 010)$

$00\cdot \gamma^{*}(Z_1, 010) = 00 \cdot\gamma(Z_1) \cdot \gamma^{*}(\delta(Z_1, 0), 10) = 000\cdot \gamma^{*}(Z_3,10)$

$000\cdot \gamma^{*}(Z_3,10) = 000\cdot \gamma(Z_3) \cdot \gamma^{*}(\delta(Z_3,1),0) = 0000 \cdot \gamma^{*}(Z_2,0)$

$0000 \cdot \gamma^{*}(Z_2,0) = 0000\cdot \gamma(Z_2) \cdot \gamma^*(\delta(Z_2,0)) = 00001 \cdot \gamma^*(Z_0) = 000010$

c)

Übersetzungsfunktion (gleich wie Mealy)

✅ Aufgabe 15

Elektronisches Tresorschloss

Display:

darstellbar $:= \{0,1,2\}$

2 Stellen

Tasten:

Es gibt immer eine aktive Stelle

$+$ inkrementiert aktive Ziffer (ab 2 → 0)

$L$ aktive Stelle ist links (looped nicht im kreis)

$R$ aktive Stelle ist rechts (looped nicht im kreis)

$OK$

$RESET$

Modellierung eines endlichen Automaten

a)

Welche Informationen sind notwendig um den Zustand des Schlosses zu beschreiben?

Notwendige Informationen / Zustände:

• Zahlen am Display (also ein Wert für jede Stelle)