0 Daumen
837 Aufrufe

ich soll zeigen, dass:

Ri ⊆ Resi(K(F)

gilt.


Also dass die i-te Menge der Resolutionsklauseln eine Teilmenge der Resolutionsmenge von der Klauselmenge von F ist.


Ist das nicht beides das gleiche? Wie beweise ich das am besten?


Danke und Grüße!

Avatar von

Bitte erläutere noch mal, was Ri sein soll, am besten durch die wörtliche Definition, die ihr verwendet habt.

Hallo oswald,


danke für deine Antwort. Im Anhang ist der Teil, wo Ri  vorkommt.

Nach meinem Verständnis ist das die Menge der Klauseln von Resi(K(F)), oder?Bild Mathematik

1 Antwort

0 Daumen

Laut meiner Definition von Resi(K(F)) wird Resi(K(F)) aus Resi-1(K(F)) gebildet indem die Resolventen von jedem Klauselpaar aus Resi-1(K(F)) hinzugefügt werden.

Laut deiner Definition von Ri wird Ri aus Ri-1 gebildet, indem die Resolvente von einem Klauselpaar aus Ri-1 hinzugefügt wird.

Damit sollte die genannte Teilmengenbeziehung offensichtlich sein. Beweis geht mit vollständiger Induktion.

Avatar von 105 k 🚀

Ahh ok danke, da liegt also der Clue.

Ich habe damit angefangen, aber komme nicht so wirklich weiter... kannst du mir vielleicht noch einen Tipp geben?

Beweis durch Induktion


Induktionsbehauptung:

Ri ⊆ Resi(K(F)) mit R0 = K(F)

Induktionsanfang:

Sei i = 1, dann

        R1 ⊆ Res1 (K(F))

<=>  K(F) ∪ X ⊆ Res1(K(F))

In der Resolventen von K(F) sind alle Klauseln von K(F) sowie ihre zugehörigen Resolutionen enthalten. Da X eine dieser Resolutionen darstellt, und diese mit K(F) verbunden wird, muss R1 eine Teilmenge von K(F) sein.

Induktionsvoraussetzung:

Ri ⊆ Resi(K(F)) 


Induktionsschritt:

Sei i = i+1

       Ri+1 ⊆ Resi+1(K(F))

<=> Ri ∪ X ⊆ Res(Res1(K(F)))


Hier stockts jetzt..

Als Induktionsanfang würde ich i=0 nehmen: es ist R0 = K(F) und Res0(K(F)) = K(F). Wegen K(F) ⊆ K(F) ist also R0 ⊆ Res0(K(F)).

Für den Induktionsschritt sei 0 < n ∈ ℕ und für jedes i < n gelte Ri ⊆ Resi(K(F)). Ferner sei K eine Klausel aus Rn.

Fall 1: K ∈ Rn-1. Wegen Rn-1 ⊆ Resn-1(K(F)) ist dann K ∈ Resn-1(K(F)). Wegen Resn-1(K(F)) ⊆ Resn(K(F)) ist dann auch K ∈ Resn(K(F)).

Fall 2: K ∉ Rn-1. Seien dann K1, K2 zwei Klauseln aus Rn-1, so dass K Resolvente von K1, K2 ist (solche Klauseln existieren aufgrund der Definition von Rn). Wegen Rn-1 ⊆ Resn-1(K(F)) sind dann K1 und K2 auch in Resn-1(K(F)) enthalten. Aufgrund der Definition von Resn(K(F)) ist dann auch K ∈ Resn(K(F)).

> Sei i = i+1

Es gibt kein i, dass diese Bedingung erfüllt.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community