Semantische Folgerung und Unerfüllbarkeit

11.09.2019, 03:08

Pippen

Semantische Folgerung und Unerfüllbarkeit

Es gilt ja folgender Satz: F |= x gdw. F $\begin{eqnarray*} \cup \end{eqnarray*}$ {~x} = unerfüllbar.

Das leuchtet mir aber nicht so recht ein. Wenn F |= x, dann kann auch der Fall eintreiten, dass F = falsch und x = falsch, womit aber F $\begin{eqnarray*} \cup \end{eqnarray*}$ ~x erfüllbar wäre, obwohl ja weiterhin gilt: F |= x, so dass nach o.g. Satz folgen müsste: F $\begin{eqnarray*} \cup \end{eqnarray*}$ ~x unerfüllbar. Oder anders ausgedrückt: der o.g. Satz läßt sich auch schreiben als (F -> x = wahr) <-> ~(F v ~x) und diese Formel gilt einfach nicht. Aus der Wahrheit von F -> x folgt nicht zwangsläufig die Wahrheit von ~(F v ~x), eben zB im Fall F = falsch und x = falsch.

Wo verstehe ich da was falsch bzw. mache einen Denkfehler?

11.09.2019, 08:03

Finn_

Auf diesen Beitrag antworten »

Kurz zum Satz.
Betrachte die folgende Umformung:
$\begin{eqnarray*} x\equiv (x\lor 0)\equiv (\neg x\rightarrow 0) \end{eqnarray*}$ .
Gemäß Deduktionstheorem ist $\begin{eqnarray*} F\models(\neg x\rightarrow 0) \end{eqnarray*}$ äquivalent zu $\begin{eqnarray*} F\cup\{\neg x\}\models 0 \end{eqnarray*}$ . Diese Aussage besagt nun, dass 0 relativ tautologisch unter den Voraussetzungen $\begin{eqnarray*} F\cup\{\neg x\} \end{eqnarray*}$ ist. Da 0 aber niemals tautologisch sein kann, dürfen die Vorraussetzungen niemals erfüllt sein. D.h. $\begin{eqnarray*} F\cup\{\neg x\}\models 0 \end{eqnarray*}$ ist gleichbedeutend damit, dass $\begin{eqnarray*} F\cup\{\neg x\} \end{eqnarray*}$ unerfüllbar ist.

Erklärung deines Denkfehlers.
Dein Denkfehler beruht auf der Annahme, eine Formelmenge sei erfüllt, wenn eine ihrer Formeln erfüllt ist. Eine Formelmenge ist jedoch nur dann erfüllt, wenn alle ihre Formeln erfüllt sind. Die Vereinigung suggeriert dir ein logisches ODER, was dich in die Irre geführt hat.

11.09.2019, 21:48

Pippen

Auf diesen Beitrag antworten »

RE: Semantische Folgerung und Unerfüllbarkeit

Zitat:

Original von Finn_
Erklärung deines Denkfehlers.
Dein Denkfehler beruht auf der Annahme, eine Formelmenge sei erfüllt, wenn eine ihrer Formeln erfüllt ist. Eine Formelmenge ist jedoch nur dann erfüllt, wenn alle ihre Formeln erfüllt sind. Die Vereinigung suggeriert dir ein logisches ODER, was dich in die Irre geführt hat.

Hm...ich kann dich noch nicht so recht verstehen. Die Aussage F $\begin{eqnarray*} \cup \end{eqnarray*}$ {~x} ist doch nichts anderes als F v {~x} und diese Formel ist unerfüllbar nur, wenn und soweit F und {~x} immer falsch sind. Richtig?

Der o.g. Äquivalenzsatz sagt nun, dass x aus F logisch folgt (F |=x) gdw. F v {~x} nie wahr ist. Nun sei einmal F |=x gegeben und dort der spezielle Fall, dass sowohl F wie x falsch seien. Dann müsste also F v {~x} unerfüllbar sein, was aber nicht der Fall ist, weil {~x} gerade wahr wird, was ausreicht, um dieser Formel ein Modell zu geben. Deswegen folgt eben aus F |= x nicht unbedingt F v {~x}, was den Satz falsifizieren würde.

Meine Vermutung ist folgende: Bei dem Satz "(F |= x) gdw. F v {~x} = F" setzt man F als immer wahr voraus und betrachtet quasi nur noch x. Kann das sein?

12.09.2019, 09:53

Finn_

Auf diesen Beitrag antworten »

[attach]49678[/attach]

Eine Formelmenge ist erfüllt, wenn alle ihre Formeln erfüllt sind:
$\begin{eqnarray*} I\models F \end{eqnarray*}$ gdw. $\begin{eqnarray*} \forall\varphi\in F\colon I(\varphi). \end{eqnarray*}$

Eine Formelmenge heißt erfüllbar, wenn es eine Belegung gibt, die die Formelmenge erfüllt:
$\begin{eqnarray*} \operatorname{erf}(F) \end{eqnarray*}$ gdw. $\begin{eqnarray*} \exists I\colon (I\models F). \end{eqnarray*}$

Eine Formelmenge ist schon dann unerfüllt, wenn eine ihrer Formeln unerfüllt ist. Infolge schon dann unerfüllbar, wenn bei jeder Belegung eine ihrer Formeln unerfüllt ist, das kann aber je Belegung eine andere Formel sein. Der Ausdruck $\begin{eqnarray*} F\cup\{\neg x\} \end{eqnarray*}$ ist keine Aussage, sondern eine Formelmenge. Wenn diese unerfüllt sein soll, dann genügt es, wenn $\begin{eqnarray*} F \end{eqnarray*}$ unerfüllt ist oder $\begin{eqnarray*} \neg x \end{eqnarray*}$ . Es muss nicht beides gleichzeitig unerfüllt sein. Unter manchen Belegungen kann $\begin{eqnarray*} F \end{eqnarray*}$ unerfüllt sein, aber $\begin{eqnarray*} \neg x \end{eqnarray*}$ erfüllt, unter anderen $\begin{eqnarray*} \neg x \end{eqnarray*}$ unerfüllt, aber $\begin{eqnarray*} F \end{eqnarray*}$ erfüllt.

Gemäß Definition ergibt sich:
$\begin{eqnarray*} \neg\operatorname{erf}(F\cup\{\neg x\}) \equiv \neg \exists I\colon (\forall \varphi\in F\cup\{\neg x\}\colon I(\varphi)) \end{eqnarray*}$
$\begin{eqnarray*} \equiv \neg\exists I\colon ([\forall \varphi\in F\colon I(\varphi)]\land I(\neg x)) \end{eqnarray*}$
$\begin{eqnarray*} \equiv \forall I\colon (\neg[\forall \varphi\in F\colon I(\varphi)]\lor \neg I(\neg x)) \end{eqnarray*}$
$\begin{eqnarray*} \equiv \forall I\colon ([\forall \varphi\in F\colon I(\varphi)]\rightarrow \neg I(\neg x)) \end{eqnarray*}$
$\begin{eqnarray*} \equiv \forall I\colon ([\forall \varphi\in F\colon I(\varphi)]\rightarrow I(x)) \end{eqnarray*}$
$\begin{eqnarray*} \equiv (F\models x). \end{eqnarray*}$
Benutzt wurden dabei nur die De Morgan'schen Gesetze und $\begin{eqnarray*} I(\neg x)=\neg I(x) \end{eqnarray*}$ . Und, dass bei der aussagenlogischen Interpretation die doppelte Negation gekürzt werden darf.

22.09.2019, 00:43

Pippen

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_
Der Ausdruck $\begin{eqnarray*} F\cup\{\neg x\} \end{eqnarray*}$ ist keine Aussage, sondern eine Formelmenge. Wenn diese unerfüllt sein soll, dann genügt es, wenn $\begin{eqnarray*} F \end{eqnarray*}$ unerfüllt ist oder $\begin{eqnarray*} \neg x \end{eqnarray*}$ . Es muss nicht beides gleichzeitig unerfüllt sein. Unter manchen Belegungen kann $\begin{eqnarray*} F \end{eqnarray*}$ unerfüllt sein, aber $\begin{eqnarray*} \neg x \end{eqnarray*}$ erfüllt, unter anderen $\begin{eqnarray*} \neg x \end{eqnarray*}$ unerfüllt, aber $\begin{eqnarray*} F \end{eqnarray*}$ erfüllt.

Da liegt mein Problem und ich werde es mal ausführlich ausführen, weil ich glaube, dass die Symbolik ziemlich böse

ist: der Ausdruck $\begin{eqnarray*} F\cup\{\neg x\} \end{eqnarray*}$ steht für die Vereinigung zweier Mengen, hier aus Formeln, nämlich der Mengen F und der Menge mit nur einer Formel: ~x. Da Erfüllbarkeit vorliegt, wenn eine Formel in mind. einer möglichen Interpretation wahr ist, so liegt Unerfüllbarkeit vor, wenn eine Formel nie wahr ist. Wenn also $\begin{eqnarray*} F\cup\{\neg x\} \end{eqnarray*}$ unerfüllbar sein soll, dann darf - so wie eine Vereinigung definiert ist - weder F noch {~x} je wahr sein. Doch in diesem Fall würde gerade ~x aus F logisch folgen, weil alle Formeln in F ja falsch wären und aus Falschem immer alles logisch folgt.

Aus verschiedenen Skripten gewinne ich den Eindruck, dass die Formel $\begin{eqnarray*} F\cup\{\neg x\} \end{eqnarray*}$ eigentlich steht für die Formel: $\begin{eqnarray*} F=wahr\cup\{\neg x\} \end{eqnarray*}$ , d.h. die Formelmenge F wird einfach als wahr gesetzt und nur noch auf ~x geschaut, dann klappt alles. Kann das sein?

22.09.2019, 10:32

zweiundvierzig

Auf diesen Beitrag antworten »

$\begin{eqnarray*} I \models \Phi \end{eqnarray*}$ genau dann, wenn $\begin{eqnarray*} I \models \varphi \end{eqnarray*}$ für alle $\begin{eqnarray*} \varphi \in \Phi \end{eqnarray*}$ .

Eine Formel ist nicht wahr oder falsch, sondern erfüllbar oder unerfüllbar.

24.09.2019, 00:52

Pippen

Auf diesen Beitrag antworten »

Zitat:

Original von zweiundvierzig
Eine Formel ist nicht wahr oder falsch, sondern erfüllbar oder unerfüllbar.

Natürlich kann eine Formel wahr oder falsch sein. Erfüllbar meint, dass die Formel wahr sein kann, unerfüllbar meint, dass sie falsch sein muss, also nie wahr sein kann. Die Formel F $\begin{eqnarray*} \cup \end{eqnarray*}$ {~x} ist daher nur dann unerfüllbar, wenn beide Teile - F und ~x - nie wahr sein können, also immer falsch sein müssen. Dann ist F |= x auch gegeben, leider auch F |= ~x wg. EFQ und damit widerspricht sich alles. Deshalb verstehe ich nicht, warum gilt: F |= x <=> ~erfüllbar(F $\begin{eqnarray*} \cup \end{eqnarray*}$ {~x}). Zur Klarstellung: verstehen würde ich, wenn gilt: F |= x <=> ~erfüllbar (F & ~x), denn das würde bedeuten, dass F & ~x nie gemeinsam wahr sein können und das hieße insbesondere, dass wenn F wahr wäre, dann ~x immer falsch und damit x immer wahr wäre und genau das ist ja die Quintessenz der log. Folgerung.

24.09.2019, 07:58

Elvis

Auf diesen Beitrag antworten »

Eine Formel ist eine Zeichenkette eines formalen Systems, sie ist, aber sie ist nicht wahr und nicht falsch. Aussagen sind wahr oder falsch. Deine Aussagen sind also falsch, da helfen auch so schöne Worte wie Quintessenz nicht, trotzdem danke dafür, dass du dem schönen Wort ein Biotop bereitest.

24.09.2019, 09:46

Finn_

Auf diesen Beitrag antworten »

Zitat:

Original von Pippen
Die Formel F $\begin{eqnarray*} \cup \end{eqnarray*}$ {~x} ist daher nur dann unerfüllbar, wenn beide Teile - F und ~x - nie wahr sein können, also immer falsch sein müssen.

Diese Überlegung ist nicht richtig, das ist dein Denkfehler.

Betrachten wir mal eine Formelmenge aus zwei Formeln,
$\begin{eqnarray*} F:=\{\varphi,\psi\} = \{\varphi\}\cup\{\psi\} \end{eqnarray*}$ .

Nach dir wäre $\begin{eqnarray*} F \end{eqnarray*}$ nur dann unerfüllbar, wenn sowohl $\begin{eqnarray*} \varphi \end{eqnarray*}$ als auch $\begin{eqnarray*} \psi \end{eqnarray*}$ unerfüllbar sind, d.h.

$\begin{eqnarray*} \neg\operatorname{erf}(F) \stackrel{\mathrm{Pippen}}\iff\neg\operatorname{erf}(\varphi)\land\neg\operatorname{erf}(\psi)\iff\neg(\exists I\colon I(\varphi))\land\neg(\exists I\colon I(\psi)) \end{eqnarray*}$
$\begin{eqnarray*} \iff \neg[(\exists I\colon I(\varphi))\lor(\exists I\colon I(\psi))] \iff \neg[\exists I\colon (I(\varphi)\lor I(\psi))]\iff \neg[\exists I\colon I(\varphi\lor\psi)] \end{eqnarray*}$
$\begin{eqnarray*} \iff\neg\operatorname{erf}(\varphi\lor\psi). \end{eqnarray*}$

Laut Definition ist jedoch
$\begin{eqnarray*} \operatorname{erf}(F) \iff [\exists I\colon (I(\varphi)\land I(\psi))] \iff [\exists I\colon I(\varphi\land\psi)] \iff \operatorname{erf}(\varphi\land\psi), \end{eqnarray*}$
und daher
$\begin{eqnarray*} \neg\operatorname{erf}(F) \iff \neg\operatorname{erf}(\varphi\land\psi). \end{eqnarray*}$

25.09.2019, 00:30

Pippen

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_
Betrachten wir mal eine Formelmenge aus zwei Formeln,
$\begin{eqnarray*} F:= \{\varphi\}\cup\{\psi\} \end{eqnarray*}$ .

...

Laut Definition ist jedoch
$\begin{eqnarray*} \operatorname{erf}(F) \iff [\exists I\colon (I(\varphi)\land I(\psi))] \iff [\exists I\colon I(\varphi\land\psi)] \iff \operatorname{erf}(\varphi\land\psi), \end{eqnarray*}$
und daher
$\begin{eqnarray*} \neg\operatorname{erf}(F) \iff \neg\operatorname{erf}(\varphi\land\psi). \end{eqnarray*}$

Und wie definierst du dann die Erfüllbarkeit von F, wenn gilt: $\begin{eqnarray*} F:= \{\varphi\}\cap\{\psi\} \end{eqnarray*}$ ?

25.09.2019, 11:24

Elvis

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \varphi=\psi\Rightarrow \{\varphi\}\cap\{\psi\}=\{\varphi\}\Rightarrow erf (\{\varphi\}\cap\{\psi\})=erf(\{\varphi\}) \end{eqnarray*}$

$\begin{eqnarray*} \varphi\ne\psi\Rightarrow \{\varphi\}\cap\{\psi\}=\emptyset\Rightarrow erf (\{\varphi\}\cap\{\psi\})=erf(\emptyset) \end{eqnarray*}$ , und die leere Menge ist erfüllbar.

25.09.2019, 22:12

Pippen

Auf diesen Beitrag antworten »

Ich glaube, langsam verstehe ich es. Machen wir mal ein konkretes Beispiel:

Seien die Formeln p, p & q, z die Formelmenge a.
Seien die Formeln p, z die Formelmenge b.

Die Formelmenge b $\begin{eqnarray*} \cup \end{eqnarray*}$ a wären die Formeln: p, p & q und z.
Die Formelmenge b $\begin{eqnarray*} \cap \end{eqnarray*}$ a wären die Formeln p und z.

Finn sagt nun, dass die Erfüllbarkeit der Formelmenge b $\begin{eqnarray*} \cup \end{eqnarray*}$ a definiert wird als: es gibt eine Interpretation, in der - gleich mal konkret gemacht - die Formeln p, p & q und z alle wahr sind bzw. unerfüllbar, wenn's keine solche Interpretation gibt. Das wirkte für mich komisch, weil die Vereinigung auf einer Disjunktion basiert, wo bereits die Wahrheit eines Teiles ausreicht, hier aber, eher "konjunktivistisch", alle Teile wahr sein müssen. Macht aber doch auch wieder Sinn, wenn man bedenkt, dass ja die gesamte Vereinigung der Formeln eine wahre Interpretation haben soll und daher auch alle Formeln die dort drin sind (gleichzeitig) eine wahre Interpretation haben müssen.

Jetzt wird auch klar, warum gilt: F |=x gdw. ~erf(F $\begin{eqnarray*} \cup \end{eqnarray*}$ {~x}). Denn wenn F $\begin{eqnarray*} \cup \end{eqnarray*}$ {~x} unerfüllbar ist, dann heißt es, dass es keine Interpretation gibt, in der F wahr und ~x wahr sind. Und nur so eine Interpretation könnte die logische Folgerung F |= x verhindern.

Bleibt noch die Frage, wie die Erfüllbarkeit für b $\begin{eqnarray*} \cap \end{eqnarray*}$ a konkret definiert aussähe?

@elivs: Wieso ist die leere Menge erfüllbar? Kannst du das erläutern bzw. sogar beweisen?

25.09.2019, 23:25

Finn_

Auf diesen Beitrag antworten »

Durch welche Interpretation eine Formelmenge erfüllt wird, kannst du z.B. wissen, wenn konkrete Formeln angegeben sind. Über $\begin{eqnarray*} \{p,z\} \end{eqnarray*}$ kannst du keine Aussage machen, da $\begin{eqnarray*} p \end{eqnarray*}$ und $\begin{eqnarray*} z \end{eqnarray*}$ für feste aber beliebige Formeln stehen.

Die leere Menge ist erfüllbar, weil diese durch jede beliebige Interpretation erfüllt wird:
$\begin{eqnarray*} (I\models\emptyset) \iff (\forall\varphi\in\emptyset: I(\varphi)) \iff 1 \end{eqnarray*}$ .
Die leere Konjunktion haben wir ja schon geklärt.

Neue Frage »

Antworten »

Semantische Folgerung und Unerfüllbarkeit

Verwandte Themen