Aussagenlogik - Begriff: "Erfüllbarkeitsäquivalent"

29.05.2005, 14:21

Sh0rty

Aussagenlogik - Begriff: "Erfüllbarkeitsäquivalent"

Hi Leudz,

bin im moment dabei mein Aussagenlogik-Skript durchzuarbeiten und mich irritiert dabei folgende Aussage:

"Zu beachten ist, dass für erfüllbarkeitsäquivalente Formeln a und b im allgemeinen NICHT die Erfüllbarkeitsäquivalenz zwischen (NICHT a) und (NICHT b) gilt!"

Nach der folgenden Definition von Erfüllbarkeitsäquivalenz würd ich das eher andersrum sehen:

"Zwei Formeln heissen erfüllbarkeitsäquivalent, wenn sie beide erfüllbar sind bzw. beide nicht erfüllbar sind. Der Unterschied zur "üblichen" Äquivalenz ist, dass es reicht, wenn es für jede Formel eine Belegung gibt, die sie erfüllt. Das müssen nicht die gleichen Belegungen sein. Bei der "üblichen" Äquivalenz müssen alle Belegungen für beide Formeln den gleichen Wert liefern."

D.h. nur im (eher nicht allgemeinen) Fall das eine Formel a oder b tautologisch ist würde die Erfüllbarkeitsäquivalenz zwischen (NICHT a) und (NICHT b) nicht gelten.
(Denn ist a tautologisch ist (NICHT a) widerspruchsvoll und damit nicht erfüllbar !)

Vielleicht kann mir das einer von euch erklären?

P.S: Die Definition von Erfüllbarkeitsäquivalenz oben ist nicht aus dem selben Skript wie die Aussage.

MfG
Shoddy

29.05.2005, 16:01

phi

Auf diesen Beitrag antworten »

Hallo Shoddy,

Ich kann dir nix versprechen, bin selber noch nicht so weit, aber boolsche Algebra ist eins meiner Lieblingsthemen; Grundlagen sind also klar und ich bin neugierig zu erfahren was

a) Erfüllbarkeit,

b) Eine Formel mit/ohne Belegung

sind, und

c) Ob du vllt. formale Beispiele dazu angeben magst.

Manchmal kommen einem ja während man es jemandem erklärt neue Einsichten. Mir geht das oft so. Augenzwinkern

29.05.2005, 21:45

Sh0rty

Auf diesen Beitrag antworten »

Hey Phi,

das freut mich zu hören Augenzwinkern

. Dann gemma das mal an:

(Ich benutze hier mal + für ODER und * für UND und - für NICHT)

Also wenn du z.B. die aussagenlogische Formel a = (A + B) hast, dann ist eine Belegung (oder auch Bewertung) genannt, eine Abbildung der Variablen(also hier A und B) auf die Wahrheitswerte 0 und 1.
A=1, B=0 wäre also z.B. eine Belegung für welche a = 1 ergibt.
Damit ist also eine Belegung einer aussagenlogischen Formel nichts anderes als eine Zeile der Wahrheitstabelle der Formel. Man "belegt" also wortwörtlich die Variablen mit 0 oder 1 Augenzwinkern

(Statt Belegung wird manchmal glaub ich auch der Begriff "Modell" verwendet)

Jetzt gibt es noch 4 Begriffe die vllt. noch wichtig wären:
Das sind erfüllbar, widersruchsvoll, tautologisch/allgemeingültig und falsifizierbar:

- Eine aussagenlogische Formel a heisst "erfüllbar" genau dann, wenn es (mindestens) eine Belegung gibt für welche sich a = 1 ergibt.
(Also unsere Formel oben a = (A + B) ist erfüllbar)

- Eine Formel a heisst "falsifizierbar" genau dann, wenn es mindestens eine Belegung gibt für die sich a = 0 ergibt.
(Also ist unsere Formel oben a = (A + B) auch falsifizierbar.)

- Eine Formel a heisst "widerspruchsvoll" genau dann, wenn für alle Belegungen gilt: a = 0
(Simples Beispiel: a = (A * -A))

- Eine Formel a heisst "tautologisch" oder "allgemeingültig" genau dann, wenn für alle Belegungen gilt: a = 1
(Simples Beispiel: a = (A + -A))

(Es gilt also: a ist widerspruchsvoll <=>a ist nicht erfüllbar <=> -a ist Tautologie )

So nun kommen wir mal zum Knackpunkt dem Begriff der Erfüllbarkeitsäquivalenz:

Also die Erfüllbarkeitsäquivalenz wird in meinem Skript der Aussagenlogik wie folgt definiert:

Zitat:

Zwei Formeln a und b heissen erfüllbarkeitsäquivalent genau dann, wenn gilt:
a ist erfüllbar <=> b ist erfüllbar

Da ich daraus nicht ganz schlau geworden bin, bzw. mir nach der Def. nicht ganz klar war ob die Formlen a und b auch für die selben Belegungen erfüllbar sein müssen um erfüllbarkeitsäquivalent zu sein habe ich noch eine 2. Definition aus dem Web herausgesucht, welche ich etwas besser finde:

Zitat:

Zwei Formeln heissen erfüllbarkeitsäquivalent, wenn sie beide erfüllbar sind bzw. beide nicht erfüllbar sind. Der Unterschied zur "üblichen" Aquivalenz ist, dass es reicht, wenn es für jede Formel eine Belegung gibt, die sie erfüllt. Das müssen nicht die gleichen Belegungen sein. Bei der "üblichen" Äquivalenz müssen alle Belegungen für beide Formeln den gleichen Wert liefern.

Was mich jetzt, wie oben schon gesagt, stört ist der folgende Satz in meinem Skript:

Zitat:

Zu beachten ist, dass für erfüllbarkeitsäquivalente Formeln a und b im allgemeinen NICHT die Erfüllbarkeitsäquivalenz zwischen -a und -b gilt.

Wenn ich das richtig verstanden und interpretiert habe, dann gilt die erfüllbarkeitsäquivalenz zwischen zwei negierten erfüllbarkeitsäquivalenten Formeln a und b doch nur dann nicht wenn eine der beiden Formeln a oder b tautologisch ist, was aber doch eher NICHT der allgemeine Fall ist.

Um das mal zu verdeutlichen:
Seien a und b zwei erfüllbarkeitsäquivalente Formeln mit je 3 Variablen:

D.h. es gibt jeweil 8 Belegungen für a und b.
Sagen wir es gibt für a 3 Belegungen für die gilt a = 1(und 5 Belegungen für die gilt a=0) und für b 2 Belegungen für die gilt b = 1(und 6 Belegungen für die gilt b=0). Also sind a und b erfüllbarkeitsäquivalent.
Für -a gibt es also dann 5 Belegungen für die gilt -a = 1 (die für die vorher a = 0 galt) und für -b gibt es dann 6 Belegungen für die gilt -b = 1. Also ist auch -a und -b erfüllbarkeitsäquivalent.

-a und - b wären nur in dem Fall nicht erfüllbarkeitsäquivalent wenn es für -a oder -b KEINE Belegungen gibt für die -a=1 oder -b=1 gilt.
D.h. für alle Belegungen gelte dann -a=0 (oder halt -b=0) was heisst a=1 für alle Belegungen. Also a (oder b) tautologisch.

Also ich hab das jetz nochmal haarkein zerpflückt und ich hab auch gehofft das mir wie du schon sagtest, evtl bei der Erklärung nochmal neue Einscihten kommen.....aber nix Forum Kloppe

Vllt. hab ich ja auch ne falsche Def. für den Begriff erfüllbarkeitsäquivalenz??

Naja vllt. fällt dir was auf Phi wenn du mit frischem Geist an die Sache rangehst. Ich hab mich hier schon zu festgefahn glaub ich Hammer

Mfg
Shoddy

30.05.2005, 11:42

phi

Auf diesen Beitrag antworten »

Moin ShOrty,

kam Gestern nicht mehr dazu. Les es mir jetzt aber gespannt durch!

Danke für´s Entgegenkommen, bis Später. Augenzwinkern

Edit:

Okay, verstehe jetzt worum es geht.

Du warst schon auf den richtigen Weg, die Tautologie eines der Beiden ist zwar nur ein spezieller Fall, aber ein noch so spezielles Gegenbeispiel reicht aus um die Verallgemeinerung : Aus "a und b sind Erfüllbarkeitsäquivalent ( EÄ.)" folgt "-a und -b sind Erfüllbarkeitsäquivalent ( EÄ.)" zu Fall zu bringen.

Nur wenn Beide nicht erfüllbar sind, also Beide Negationen von Tautologien sind sind sie EÄ.

Die Belegungen spielen keine Rolle, da´s ja dann keine gibt.

Jetzt klarer geworden ? Freude

(Hab´direkt was dazu gelernt Augenzwinkern

)

30.05.2005, 15:28

Sh0rty

Auf diesen Beitrag antworten »

Hi Phi,

ich glaube wir kommen der Sache schon etwas näher. Augenzwinkern

Aber mich stört immer noch etwas:

Zitat:

Du warst schon auf den richtigen Weg, die Tautologie eines der Beiden ist zwar nur ein spezieller Fall, aber ein noch so spezielles Gegenbeispiel reicht aus um die Verallgemeinerung : Aus "a und b sind Erfüllbarkeitsäquivalent ( EÄ.)" folgt "-a und -b sind Erfüllbarkeitsäquivalent ( EÄ.)" zu Fall zu bringen.

Das ist mir schon klar, das ich das so nicht generell sagen kann wenn es auch nur ein gegenbeispiel dazu gibt.
Was mich stört ist der Begriff im allegemeinen:
Wenn a,b EÄ sind, dann sind -a und -b im allgemeinen NICHT EÄ.

Ich interpretiere "im allgemeinen" mit "in den meisten Fällen" (vllt. liegt ja da der Fehler?):
Wenn a,b EÄ sind, dann sind -a und -b in den meisten Fällen NICHT EÄ.
Was aber in den meisten Fällen (meiner bescheidenen Meinung nach) eben doch der Fall ist:
Ein Beispiel mit Wahrheitstafeln:
Sei a=(A+B) und b=(A+(-B)), dann gilt:

code:

1:
2:
3:
4:
5:
6:
7:

| A | B | A+B | A+(-B) | -(A+B) | -(A+(-B)) |
|---|---|-----|--------|--------|-----------|
| 0 | 0 |  0  |   1    |    1   |     0     |
| 0 | 1 |  1  |   0    |    0   |     1     |
| 1 | 0 |  1  |   1    |    0   |     0     |
| 1 | 1 |  1  |   1    |    0   |     0     |

Daraus folgt also, dass a,b EÄ und -a, -b EA.
Und in den meisten Fällen ist es doch so, dass es für eine Formel a sowohl Belegungen gibt für die gilt a=1 als auch welche für die gilt a=0, so wie oben im fall a und b.
Und damit gilt in den meisten Fällen: a,b EÄ und -a,-b EÄ

Oder hänge ich mich da zu sehr am Begriff "im allgemeinen" auf oder interpretiere ihn sogar falsch??

Mfg
Shoddy

30.05.2005, 16:16

Tobias

Auf diesen Beitrag antworten »

Das wird es wohl sein

Erstmal kurz zu "Statt Belegung wird manchmal glaub ich auch der Begriff "Modell" verwendet": Ein Modell ist eine Belegung, welche die aussagenlogische Formel wahr macht. Also ist nicht jede Belegung ist auch Modell.

Eine Formel, welche sowohl erfüllbar als auch falsifizierbar ist nennt man kontingent.

Wenn die aussagenlogischen Formeln $\begin{eqnarray*} \varphi \end{eqnarray*}$ und $\begin{eqnarray*} \psi \end{eqnarray*}$ kontingent sind folgt automatisch, dass sie auch erfüllbarkeitsäquivalent sind. Die Negate der Formeln sind dann aber auch kontingent und somit auch eä. (In vielen Fällen gilt also die Negation).

Da du aber schon ein Gegenbeispiel gefunden hast, wissen wir, dass dies nicht überall gilt (nämlich wenn eine Formel kontingent und eine tautologisch bzw. widerspruchsvoll ist). Ich würde mich an deiner Stelle also nicht so sehr an der Formulierung aufhängen und einfach die Dinge so betrachten, wie sie nunmal sind. smile

30.05.2005, 16:20

phi

Auf diesen Beitrag antworten »

Moin ShOrty, Wink

"Im Allgemeinen" darf man nur sagen, wenn etwas in jedem Fall stimmt.

Das ist wie mit den Dominosteinen, wenn nur ein einziges an der falschen Stelle steht, kann man nicht sagen das wenn der erste umfällt, dann auch alle anderen umfallen. Sonst wären Induktionsbeweise nicht zuverlässig.

"In den meisten Fällen" drückt man mit "mindestens" oder "größer-gleich" aus.

Man kann "Im Allgemeinen" und "In den meisten Fällen" nur dann gleichsetzen, wenn man alle Ausnahmen mit angibt.

Also : ...mit Ausnahme von .... und ... ist i.A. ....

Ich glaub´jetzt wird´s klarer. smile

30.05.2005, 16:54

Sh0rty

Auf diesen Beitrag antworten »

Hi again..

tja hätt ich den Begriff "kontingent" gekannt hätt ich mir viele umständliche Erklärungen sparen können. Augenzwinkern

Also Phi wenn ich das jetzt richtig verstanden habe ist der Satz so also gar nicht richtig, wenn man mit "im allgemeinen" "in jedem Fall" meint.

Mönsch dann liegts ja gar nich bei mir, sondern beim Prof.
Rock

...hehehe

(Sry nochmal wegen der Haarspalterei bei den Begriffen, aber ich komme aus der Informatik und da ist so eine scheisspräzise Ausrucksweise Pflicht Augenzwinkern

)

Thx nochmal euch beiden (vor allem Phi, das der mein Text oben nachvollziehen konnte...also Respect..das konnte nichmal ich nach nochmaligen Durchlesen Augenzwinkern

)

cya
Shoddy

30.05.2005, 17:53

phi

Auf diesen Beitrag antworten »

RE: Aussagenlogik - Begriff: "Erfüllbarkeitsäquivalent"

Zitat:

Original von Sh0rty

"Zu beachten ist, dass für erfüllbarkeitsäquivalente Formeln a und b im allgemeinen NICHT die Erfüllbarkeitsäquivalenz zwischen (NICHT a) und (NICHT b) gilt!"

Die Aussage vom Prof. stimmt aber! Er sagt ja das wenn a und b EÄ. sind, nicht in jedem Fall, also nicht i.A. -a und -b EÄ. gilt.

Sobald man sich an die Präzision gewöhnt hat, macht sie vieles sogar leichter. Es gibt dann sogar weniger Mißverständnisse...

Also, toi, toi! Augenzwinkern

30.05.2005, 19:06

Sh0rty

Auf diesen Beitrag antworten »

Jau ...mensch ich hab das so interpretiert:
Wenn a und b EÄ. sind,sind in jedem Fall(also i.A.) -a und -b NICHT EÄ.

Da is wohl mein Fehler....alda Spalter soviel Lärm um nischts ...aber dafür werd ich mein Leben nimma vergessen was erfüllbarkeitsäquivalnz bedeutet Freude

...

Nochmals herzlichen dank Phi für deine Zeit Augenzwinkern

...

cya
Shoddy

30.05.2005, 19:30

phi

Auf diesen Beitrag antworten »

Jo, kannst jederzeit neue Fragen stellen. Bei mir hat sich EÄ. jetzt auch auf die Festplatte gebrannt. Was neues gelernt.

Ciau Wink

Neue Frage »

Antworten »

Aussagenlogik - Begriff: "Erfüllbarkeitsäquivalent"

Verwandte Themen