TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Prüfung 2013-01-30/Beispiel 1

Teilaufgabe a)

Gegeben seien die Folgende Formeln:

$\varphi =\mathrm{\forall }x[Film(x)\to \mathrm{\exists }y(Cinema(y)\wedge Shows(y,x))]$

$\psi =\mathrm{\exists }y\mathrm{\forall }x[Film(x)\to (Cinema(y)\wedge Shows(y,x))]$

1. Überprüfen Sie mittels Semantik, ob $\varphi \models \psi$ gilt. Zeigen Sie, dass jedes Modell von $\varphi$ auch ein Modell von $\psi$ ist, oder konstruieren Sie ein Gegenbeispiel

2. Überprüfen Sie mittels TC1, ob $\varphi \models \psi$ gilt. Falls Umformungen notwendig sind, geben Sie bitte detailliert die Zuordnung zwischen den entsprechenden Ausdrücken an.

Lösungsvorschlag

1. Konstruktion eines Gegnbeispiels:

$U=\{f1,f2,c1,c2\}$
$\Sigma =(\text{Func, Pred})$
$Func=\{\}$
$Pred=\{Film/1,Cinema/1,Shows/2\}$

$I(F)=\{(f1),(f2)\}$
$I(C)=\{(c1),(c2)\}$
$I(S)=\{(c1,f1),(c2,f2)\}$

Jetzt kann man leicht überprüfen, dass $\varphi$ zwar erfüllt wird $\psi$ jedoch nicht

($I\models \varphi$ jedoch $I\models ̸\psi$ Q.E.D.B.).

2. Wir wollen herausfinden, ob $\varphi \models \psi$ gilt. Das ist dann und nur dann der Fall, wenn $\varphi$ zu wahr und $\psi$ zu falsch evaluiert. Falls die Aussage gültig ist, darf es kein Modell für $\varphi \wedge \mathrm{\neg }\psi$ geben, TC1 wäre in diesem Fall also geschlossen.

Anmerkung: Hier ist darauf zu achten, dass ein Existenzquantor im Scope eins Allquantors nicht eliminiert werden darf.

Umformung in NNF:

$\mathrm{\forall }x[F(x)\to \mathrm{\exists }y(C(y)\wedge S(y,x))]\wedge \mathrm{\neg }\mathrm{\exists }y\mathrm{\forall }x[F(x)\to (C(y)\wedge S(y,x))]$
$\mathrm{\forall }x[\mathrm{\neg }F(x)\vee \mathrm{\exists }y(C(y)\wedge S(y,x))]\wedge \mathrm{\forall }y\mathrm{\neg }\mathrm{\forall }x[\mathrm{\neg }F(x)\vee (C(y)\wedge S(y,x))]$
$\mathrm{\forall }x[\mathrm{\neg }F(x)\vee \mathrm{\exists }y(C(y)\wedge S(y,x))]\wedge \mathrm{\forall }y\mathrm{\exists }x\mathrm{\neg }[\mathrm{\neg }F(x)\vee (C(y)\wedge S(y,x))]$
$\mathrm{\forall }x[\mathrm{\neg }F(x)\vee \mathrm{\exists }y(C(y)\wedge S(y,x))]\wedge \mathrm{\forall }y\mathrm{\exists }x[F(x)\wedge \mathrm{\neg }(C(y)\wedge S(y,x))]$
$\mathrm{\forall }x[\mathrm{\neg }F(x)\vee \mathrm{\exists }y(C(y)\wedge S(y,x))]\wedge \mathrm{\forall }y\mathrm{\exists }x[F(x)\wedge (\mathrm{\neg }C(y)\vee \mathrm{\neg }S(y,x))]$

TC1 (VORSICHT: nicht ganz richtig):

$\mathrm{\forall }x[\mathrm{\neg }F(x)\vee \mathrm{\exists }y(C(y)\wedge S(y,x))]\wedge \mathrm{\forall }y\mathrm{\exists }x[F(x)\wedge (\mathrm{\neg }C(y)\vee \mathrm{\neg }S(y,x))]$
$\mathrm{\forall }x[\mathrm{\neg }F(x)\vee \mathrm{\exists }y(C(y)\wedge S(y,x))]$ $\mathrm{\forall }y\mathrm{\exists }x[F(x)\wedge (\mathrm{\neg }C(y)\vee \mathrm{\neg }S(y,x))]$
$\mathrm{\exists }x[F(x)\wedge (\mathrm{\neg }C(a)\vee \mathrm{\neg }S(a,x))]$ $F(b)\wedge (\mathrm{\neg }C(a)\vee \mathrm{\neg }S(a,b))$ $\mathrm{\neg }F(b)\vee \mathrm{\exists }y(C(y)\wedge S(y,b))$ $F(c)\wedge (\mathrm{\neg }C(a)\vee \mathrm{\neg }S(a,c))$
$F(c)$ $\mathrm{\neg }C(a)\vee \mathrm{\neg }S(a,c)$ $F(b)$ $\mathrm{\neg }C(a)\vee \mathrm{\neg }S(a,b)$
$\mathrm{\neg }F(b)$	$\mathrm{\exists }y(C(y)\wedge S(y,b))$
✘ clash	$C(d)\wedge S(d,b)$ $C(d)$ $S(d,b)$
	$\mathrm{\neg }C(a)$		$\mathrm{\neg }S(a,c)$
	$\mathrm{\neg }C(a)$	$\mathrm{\neg }S(a,b)$	$\mathrm{\neg }C(a)$	$\mathrm{\neg }S(a,b)$

Teilaufgabe b)

1) $p\vee q$ ist eine logische Konsequenz von $\mathrm{\neg }(p\to q)$.

2) Die Aussage $(p\to q)\to \mathrm{\neg }q\models \mathrm{\neg }p$ gilt.

3) Zwei syntaktisch unterschiedliche Formeln können niemals dieselben Modelle haben.

4) $W\cup \{\varphi \}\models \mathrm{\neg }\psi$ gilt genau dann, wenn $W\cup \{\psi \}\models \mathrm{\neg }\varphi$.

Lösungsvorschlag:

1) RICHTIG, weil:

$\mathrm{\neg }(p\to q)\models p\vee q$

$\Rightarrow p\wedge \mathrm{\neg }q\models p\vee q$

or similar:
-(p -> q) |= p v q
|= -(p -> q) -> (p v q)
|= --(-p v q) v (p v q)
|= (-p v q) v (p v q)
|= -p v q v p v q
|= T
so it's tautology
2) FALSCH, weil:

$(p\to q)\to \mathrm{\neg }q\models \mathrm{\neg }p$

$\Rightarrow (\mathrm{\neg }p\vee q)\to \mathrm{\neg }q\models \mathrm{\neg }p$

$\Rightarrow (p\wedge \mathrm{\neg }q)\vee \mathrm{\neg }q\models \mathrm{\neg }p$

$\Rightarrow \mathrm{\neg }q\models \mathrm{\neg }p$

3) FALSCH, weil äquivalente Formeln syntaktisch unterschiedlich sein können aber trotzdem dieselben Modelle besitzen.

4) RICHTIG, weil es sich um das Kontrapositionstheorem handelt.

Teilaufgabe c)

Ist die folgende Aussage korrekt? Wenn ja begründen Sie Ihre Antwort; wenn nein, geben Sie ein Gegenbeispiel an.

Seien $\alpha ,\beta ,\gamma$ aussagenloische Formeln, sodass $\gamma$ logisch aus $\alpha \wedge \beta$ folgt; dann gilt, dass $\gamma$ aus $\alpha$ folgt oder $\gamma$ aus $\beta$ folgt.

Lösungsvorschlag

Die Aussage gilt nicht.

Gegenbeispiel:

Sei:
$\alpha =a\to b$
$\beta =a$
$\gamma =b$

Dann folgt $\gamma$ zwar aus $\alpha \wedge \beta$ aber weder aus $\alpha$ nocht aus $\beta$ alleine.

Anmerkung: Meiner Meinung nach gilt das sehr wohl.
Gegenbeispiel zu deinem Gegenbeispiel:
$I(a)=0,I(b)=1$
$\alpha \wedge \beta ⟹\gamma \leftrightarrow ((a\to b)\wedge a)⟹\gamma \leftrightarrow (1\wedge 0)\to 1\leftrightarrow 0\to 1$

Anmerkung: Einspruch. Die Aussage soll allgemein gelten. Natürlich kann es sein, dass man eine Interpretation findet, für die die Aussage gilt, aber das heißt noch lange nicht, dass sie allgemein gilt.

Anmerkung: Finde das Beispiel nicht gut, aber wie sieht es hiermit aus?

Sei:
$\alpha =a$
$\beta =b$
$\gamma =a\wedge b$

Dann ist offensichtlich, dass $\alpha \vee \beta$ nicht zu $\gamma$ führen kann.

Teilaufgabe d)

Untersuchen Sie, ob die folgenden zwei Formeln logisch äquivalent sind:

$(({\wedge }_{i=1}^{1000}{p}_i)\to r)\wedge (\mathrm{\neg }({\wedge }_{i=1}^{1000}{p}_i)\vee q)$ and $({\wedge }_{i=1}^{1000}{p}_i)\to (r\vee q)$

Lösungsvorschlag:

Ersetzung von $({\wedge }_{i=1}^{1000}{p}_i)$ durch A um die Übersichtlichkeit zu erhöhen.

$\Rightarrow (A\to r)\wedge (\mathrm{\neg }A\vee q)$ and $A\to (r\vee q)$

$\Rightarrow (\mathrm{\neg }A\vee r)\wedge (\mathrm{\neg }A\vee q)$ and $\mathrm{\neg }A\vee (r\vee q)$

$\mathrm{\neg }A\vee (r\wedge q)$ and $\mathrm{\neg }A\vee (r\vee q)$

Gegenbeispiel:

Wähle eine Interpretation I, sodass folgendes gilt:

$I(A)=1$

$I(r)=1$

$I(q)=0$

$\Rightarrow I\in ̸Mod(\mathrm{\neg }A\vee (r\wedge q))$

aber $I\in Mod(\mathrm{\neg }A\vee (r\vee q))$

Anmerkung ( Czechnology (Diskussion) 13:47, 25. Apr. 2016 (CEST) ): Man sollte die Interpretation für die ursprüngliche Formel (vor Ersetzung) geben, also statt der ersten Zeile wäre das

$I(p_i)=1\mathrm{\forall }i\in \{1,\dots ,1000\}$