[MaLo] Malo-Blat 4

[deuper]

Hi,

eine frage zur Resolution? kann man die Klauseln mehrmals in der Resolution verwenden? kann es eine Klausel geben die gar nicht verwendet wird?

Z.B : c1,c2,c3,c4

c1-c2 = c12
c2-c3=c23
c1-c23=leere Menge => unerfüllbar

in diesem Beispiel wird also c4 und c12 nicht vewendet aber trotzdem wurde gezeigt dass die formel unerfüllbar ist.ist das so ok oder müssen alle lauseln verwendet werden

Gruss
DeuPer

[mirko]

Hi,

eine frage zur Resolution? kann man die Klauseln mehrmals in der Resolution verwenden? kann es eine Klausel geben die gar nicht verwendet wird?

ja, ja

[Fighter_MV]

Du darfst quasi alles machen um die leere Klauser zu erzeugen. Wenn du eine Resolvente erechnet hast, dann gehört sie per Definition zur gesamten Klauselmenge und aus dieser Menge darfst du jede mit jeder Klausel benutzen, egal wie oft diese schon vorher benutzt wurden

[deuper]

Danke für die Antworten

[Nyx]

Hallo,

reicht bei Aufgabe 1 b) ein Gegenbeispiel als Beweis oder sollen wir einen Beweis führen UND ein Gegenbeispiel bringen? Mich irritiert nämlich der Doppelpunkt in der Aufgabenstellung...

[Miss*Sunflower]

Prinzipiell reicht bei einem 'falsch' ein gegenbespiel und bei einem 'wahr' musst du einen richtigen beweis führen,der alle möglichkeiten abdeckt. (auch bei anderen fächern ist es meistens so)

[Nyx]

Ja, stimmt...
Thx.

Aufgabe 3 (a):
Hier sollen wir ZEIGEN, dass jede Klauselmenge ohne positive Klauseln erfüllbar ist.
Aber durch ein einfaches Gegenbeispiel, kann man das doch widerlegen:
ist unerfüllbar und hat keine positive Klausel.

Normalerweise steht doch in solchen Fällen: Beweisen oder widerlegen Sie.
Also hab ich da wohl nen Denkfehler (durch die Temperaturen?!) Oder was?!

[magicrat]

Denkfehler
Ist erfüllbar, zB durch J(X)=J(Y)=1.

[Icarus]

....
ist unerfüllbar und hat keine positive Klausel.
...

edit: falsche behauptung, deshalb gelöscht.

...
Normalerweise steht doch in solchen Fällen: Beweisen oder widerlegen Sie.
....

Darum nehme ich an, dass alle Unterpunkte der Aufgabe 3 richtig sind und man beweisen (zeigen) soll.

[Fighter_MV]

....
ist unerfüllbar und hat keine positive Klausel.
...

hat auch positive Klausel, weil positive Literale in beiden Klauseln vorkommen. Eine Klausel positiv gdw. ''alle'' Literale nicht negiert sind.

Das Ding hat keine positive Klausel, da in beiden Klausern mindestens ein negiertes Literal vorhanden ist.

Allerdings kann man die Formel doch mit X = 1 und Y = 1 erfüllen.

Die Literale in den Klauseln sind ja verodert, also

(X oder nicht Y) und (nicht X oder Y)

[Sebi]

Naja, dann nimm nun noch die Klausel {!X, !Y} hinzu, dann ist es direkt vollends klar, dass es stimmt

[Fighter_MV]

Dann ist die Belegung X = 0, Y = 0 gültig.

Ich glaube es gibt kein Gegenbeispiel. Wir sollen ja beweisen, dass es so ist und kein Gegenbeispiel finden

[Sebi]

Ja genau. Es gilt immer, dass es erfüllbar ist.

[Nyx]

Ok, das mein Beispiel für X=Y=1 erfüllbar ist, sehe ich ein.
ABER: die Resolvente C aus C1={X,!Y} und C2={!X,Y} ist doch die leere Klausel, oder?! Also nach Resolutionskalkül unerfüllbar. HÄ?!

[Sebi]

Nein, Doppelresollution ist nicht korrekt!!!!!
Also {!A,B}, {A,!B} ist NICHT die leere Klausel!!!