Klauselmenge und Resolventenve < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:29 So 17.09.2006 | | Autor: | Binky |
| Aufgabe | Die Klauselmenge M sei definiert durch M{K1,K2,K3} mit K1{A,B,C} [mm] K2{\neg A, \neg B} K3{\neg C}
[/mm]
Beantworten mit ja bzw. nein
1.Die Klauselmenge M ist erfüllbar.
2. Die leere Klausel lässt sich aus M mit dem Resolventenverfahren ableiten.
3. K1 und K2 haben mindestens zwei Resolventen.
4. K1 und K2 haben mindestens eine Tautologie als Resolvente. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo, bei dieser Frage weiß ich einfach nicht weiter und finde leider auch kein gescheites Material zu Resolventen und Tautologie.
Könnte mir jemand das Resolventenverfahren erklären bzw. kurz anreißen um mir auf die Sprünge zu helfen? Ich sollte es eigentlich schon einmal in der Vorlesung gehört haben aber ich steh mal wieder aufm Schlauch.
Gruß
Alex
|
|
| |
|
Hallo und guten Morgen,
in Standard-Lehrbüchern der Logik und Theoretischen Informatik wird das Verfahren erklärt,
hinreichend informativ ist auch der Eintrag bei Wikipedia.
Wir haben allgemein eine Menge von Klauseln [mm] \{C_1,\ldots , C_m\} [/mm] gegeben und fragen nach der simultanen Erfüllbarkeit dieser.
Wenn ein Literal L in [mm] C_i [/mm] ist und [mm] \overline{L}\in C_j, [/mm] so gilt
[mm] (C_i\wedge C_j)\longrightarrow C_R [/mm]
für die Klausel [mm] C_R:= (C_i\cup C_j)\setminus\{L,\overline{L}\}
[/mm]
[mm] C_R [/mm] heisst Resolvente von [mm] C_i, C_j.
[/mm]
Wenn also [mm] C_1\wedge\ldots \wedge C_m [/mm] erfüllbar ist, so auch die Formel [mm] C_1\wedge\ldots\wedge C_m\wedge \bigwedge_{C\in Res(C_1,\ldots , C_m)\}
[/mm]
wobei
[mm] Res(C_1,\ldots [/mm] , [mm] C_m) [/mm] die Menge aller Resolventen in obigem Sinne ist.
Man kann nun das Resolventenbildungsverfahren iterieren. Erhält man dabei irgendwann die leere Klausel, so ist die ursprüngliche Formel nicht erfüllbar.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:52 Mo 18.09.2006 | | Autor: | Binky |
Hallo,
tut mir wirklich leid aber z.B. den Wiki Artikel habe ich auch gefunden. Könntest du mir diese Aussagen mal an Beispielen verdeutlichen?
Gruß
Binky
|
|
|
| |
|
Hallo Binky,
es sei [mm] C_1= A\vee [/mm] B [mm] \vee [/mm] C
und [mm] C_2 [/mm] = [mm] \neg A\vee D\vee [/mm] E,
dann ist die Resolvente der beiden gegeben durch
[mm] B\vee C\vee D\vee [/mm] E
Du siehst hier an dem Beispiel: Egal, welchen Wahrheitswert A bekommt, kann es nicht gleichzeitig [mm] C_1 [/mm] und [mm] C_2 [/mm] erfüllen, sondern wird genau eine
der beiden Klauseln erfüllen. Die andere muss dann durch eine der anderen in ihr vorkommenden Variablen erfüllt werden.
Wird umgekehrt die Resolvente erfüllt, so wird also durch die entsprechende Belegung mindestens eine der beiden Klauseln erfüllt, und die andere kann
dann in jedem Fall durch geeignete Belegung von A wahr gemacht werden.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:32 Mo 18.09.2006 | | Autor: | Binky |
| Aufgabe | Die Klauselmenge M sei definiert durch M{K1,K2,K3} mit K1{A,B,C}
Beantworten mit ja bzw. nein
1.Die Klauselmenge M ist erfüllbar.
2. Die leere Klausel lässt sich aus M mit dem Resolventenverfahren ableiten.
3. K1 und K2 haben mindestens zwei Resolventen.
4. K1 und K2 haben mindestens eine Tautologie als Resolvente. |
Danke schon mal,
wenn ich das nun richtig verstanden habe, würde ich die Fragen so beantworten:
1.Die Klauselmenge M ist erfüllbar.
Nein ist sie nicht.
2. Die leere Klausel lässt sich aus M mit dem Resolventenverfahren ableiten.
Ja, da jedes A,B,C durch [mm] \neg [/mm] A, [mm] \neg [/mm] B, [mm] \neg [/mm] C in der Klauselmenge zur leeren Klausel wird.
3. K1 und K2 haben mindestens zwei Resolventen.
Nein. Sie haben nur die gemeinsame Klauselmenge {C}
4. K1 und K2 haben mindestens eine Tautologie als Resolvente.
Ja, {C}, da C immer wahr ist (Tautologie)
Stimmt dieses soweit oder habe ich es dennoch falsch verstanden?
Gruß
Alex
|
|
|
| |
|
Hallo und guten Morgen,
>
> 1.Die Klauselmenge M ist erfüllbar.
> Nein ist sie nicht.
Doch.
ZB A=1, B=0, C=0 erfüllt [mm] K_1,K-2,K_3 [/mm]
(Beachte: Klauseln sind Disjunktionen, also Veroderungen von Literalen).
> 2. Die leere Klausel lässt sich aus M mit dem
> Resolventenverfahren ableiten.
> Ja, da jedes A,B,C durch [mm]\neg[/mm] A, [mm]\neg[/mm] B, [mm]\neg[/mm] C in der
> Klauselmenge zur leeren Klausel wird.
Die leere Klausel lässt sich nicht ableiten.
> 3. K1 und K2 haben mindestens zwei Resolventen.
> Nein. Sie haben nur die gemeinsame Klauselmenge {C}
Es ist doch [mm] K_1=A\vee B\vee [/mm] C, [mm] \: K_2= \neg A\vee \neg [/mm] B
damit sind [mm] A\vee C\vee \neg [/mm] A und [mm] B\vee C\vee\neg [/mm] B
Resolventen ,
die sich aber sofort beide als zu der Klausel 1 äquivalent erweisen.
Gruss,
Mathias
> 4. K1 und K2 haben mindestens eine Tautologie als
> Resolvente.
> Ja, {C}, da C immer wahr ist (Tautologie)
>
> Stimmt dieses soweit oder habe ich es dennoch falsch
> verstanden?
>
> Gruß
>
> Alex
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:18 Di 19.09.2006 | | Autor: | Binky |
Hallo,
also wird doch etwas schwieriger.
Ich habe also die Klauselmenge M { [mm] K_1,K_2,K_3 [/mm] } mit [mm] K_1 [/mm] { A,B,C } , [mm] K_2 [/mm] { [mm] \neg [/mm] A, [mm] \neg [/mm] B } und [mm] K_3 [/mm] mit { [mm] \neg [/mm] C }
Daraus kann ich doch die folgenden Klauseln bilden:
{C} aus {A,B,C} und { [mm] \neg [/mm] A, [mm] \neg [/mm] B }
{A,B} aus {A,B,C} und { [mm] \neg [/mm] C }
Und daraus doch jeweils auch die leere Klausel oder?
Habe dazu dieses Beispiel gefunden:
M= {{A,B, [mm] \neg [/mm] C }, { [mm] \neg [/mm] A}, {A,B,C}, {A, [mm] \neg [/mm] B }}
Daraus bilden sich die Klauseln:
{A,C} aus {A,B,C} und {A, [mm] \neg [/mm] B }
{A,B} aus {A,B, [mm] \neg [/mm] C} und {A,C}
{A} aus {A, [mm] \neg [/mm] B } und {A,B}
daher die leere Klausel aus {A} und { [mm] \neg [/mm] A}
Das ist doch soweit richtig zum Verständnis zur Klauselbildung oder?
Gruß
Alex
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:58 Mi 20.09.2006 | | Autor: | Binky |
Ich habs mitlerweile begriffen. Habe leider auch das Fach schaltwerke und rechnerorganisation und das darf man nicht vermischen.
die resolventen aus K1 und K2 sind also ( B, [mm] \neg [/mm] B , C) und (A, [mm] \neg [/mm] A, C)
das sagt auch gleichzeitig aus, dass es zwei tautologien zwischen K1 und K2 gibt.
Damit wären die Fragen 3 und 4 erledigt.
Es gibt noch eine weitere Resolvente (A,B) mit K1 und K3.
Wenn man sich dieses nun genau ansieht erkennt man auch dass M erfüllbar ist und sich nicht die leere Klausel für M aus dem Resolventenverfahren erzeugen lässt.
Danke noch mal für Mühe und Geduld mit mir.
Gruß
Binky
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:25 Do 21.09.2006 | | Autor: | mathiash |
Hallo Alex,
keine Ursache ! Na dann weiterhin frohes Lernen !
Gruss,
Mathias
|
|
|
|
