TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Übungen SS12/Blatt 1 - Beispiel 1

Check using semantics whether the following statements hold.

1. $\neg p\lor q\models q\rightarrow (p\rightarrow \neg q)$
2. $p\land q\models (p\lor q)\rightarrow q$
3. $P(c)\rightarrow \forall x(Q(x)\lor R(x))\land \forall x(Q(x)\rightarrow P(a))\models (P(c)\land \neg R(b))\rightarrow P(a)$
   where $a$, $b$, and $c$ are constant symbols.

Theorie

Aus dem TIL Skriptum:

Deduktionstheorem für aussagenlogische Formeln

Deduktionstheorem für aussagenlogische Formeln

$F_{1},...,F_{n}\models G\,$ gilt genau dann, wenn $F_{1},...,F_{n-1}\models (F_{n}\rightarrow G)\,$ eine gültige Formel ist.

für n = 0 ist $\models G\,$ gleichbedeutend mit "$G\,$ ist gültig".

Folgerung: ... gilt genau dann, wenn $(F_{1}\land ...\land F_{n})\rightarrow G\,$ eine gültige Formel ist.

Lösungsvorschlag

1 und 2 sind mit Wahrheitstabellen und der Anwendung des Deduktionstheorems relativ schnell gelöst. Da wir links nur jeweils eine Formel stehen haben, müssen wir jeweils zeigen, dass $F\rightarrow G$ gültig ist (für alle Interpretationen wahr liefert).

1

${\begin{aligned}F&=\neg p\lor q\\G&=q\rightarrow (p\rightarrow \neg q)\end{aligned}}$

Ich beschränk mich hier auf das Gegenbeispiel (Wahrheitstabellen dürft ihr selber aufstellen ;))

Für die Interpretation

${\begin{aligned}I(p)&={\text{t}}\\I(q)&={\text{t}}\end{aligned}}$

ist der Wahrheitswert von F = t, und G = f

und damit der Wahrheitswert von $F\rightarrow G={\text{f}}$

somit ist unsere Interpretation ein Gegenbeispiel, und haben damit laut Deduktionstheorem gezeigt, dass die ursprüngliche Annahme $F\models G$ nicht gilt

2

Analog zu 1, nur gibt es hier kein Gegenbeispiel (wieder Wahrheitstabellen aufstellen).

Für

${\begin{aligned}F&=p\land q\\G&=(p\lor q)\rightarrow q\end{aligned}}$

ist

$F\rightarrow G$ gültig, und damit gilt laut Deduktionstheorem $F\models G$

3

${\begin{aligned}F&=P(c)\rightarrow \forall x(Q(x)\lor R(x))\land \forall x(Q(x)\rightarrow P(a))\\G&=(P(c)\land \neg R(b))\rightarrow P(a)\end{aligned}}$

Wir sollen wieder zeigen, dass $F\models G$ gilt, also wie vorher, laut Deduktionstheorem (dass auf Prädikatenlogische- wie auf Aussagenlogische Formeln anwendbar ist), dass $F\rightarrow G$ gültig ist.

Indirekt können wir das zeigen, in dem wir annehmen, dass $F\rightarrow G$ widerlegbar ist, und das ist nur möglich, wenn $F={\text{t}}\,$ und $G={\text{f}}\,$.

Mit Wahrheitstabellen (selber aufstellen) sehen wir, dass $G={\text{f}}\,$ nur dann gilt, wenn

${\begin{aligned}P(c)&={\text{t}}\\R(b)&={\text{f}}\\P(a)&={\text{f}}\end{aligned}}$

Für den linken Teil können wir mit der Spezialisierungsregel folgende Annahmen treffen:

• Gilt $\forall x(Q(x)\lor R(x))$, so gilt auch $(Q(b)\lor R(b))$
• und auch $(Q(b)\rightarrow P(a))$

Über die Junktoren können wir nun schrittweise folgendes feststellen:

• nachdem $P(c)={\text{t}}\,$ gilt, muss, damit $F={\text{t}}\,$ gelten kann, auch $(Q(b)\lor R(b))\land (Q(b)\rightarrow P(a))\,$ wahr sein.
• damit $(Q(b)\lor R(b))\land (Q(b)\rightarrow P(a))\,$ wahr werden kann, muss sowohl der linke, als auch der rechte Teil der Konjunktion wahr sein.
• weil aber $R(b)={\text{f}}\,$ und $P(a)={\text{f}}\,$ gilt, wird für $Q(b)={\text{t}}\,$ nur der linke, und für $Q(b)={\text{f}}\,$ nur der rechte teil wahr.

Es ist also hier nicht möglich $F={\text{t}}\,$ zu konstruieren. Damit kann $F\rightarrow G\,$ nicht widerlegt werden, und wir haben unseren Widerspruch.

Links

• f.thread:92958
• f.thread:92943