Hornformeln: Minimale Belegung, Beispiel 5.14

pinanta
Neuling
Neuling
Beiträge: 4
Registriert: 30. Jul 2017 10:37

Hornformeln: Minimale Belegung, Beispiel 5.14

Beitrag von pinanta » 30. Jul 2017 10:53

Hi, ich habe momentan ein kleines Verständnisproblem bei Beispiel 5.14 des AL-Skripts:

Betrachte einen Graphen G = (V, E) mit abzählbarer Knotenmenge V und Kantenrelation E, als Teilmenge von V x V.
Zu V* := {pv: v aus V} und u aus V sei Cu die zu
(Konjunktion über {pv: v aus E(u)}) -> pu

äquivalente Hornklausel, und H0 := {Cu: u aus V}. Beachte, dass Cu (logisch) äquivalent ist zu pu für Knoten u ohne E-Nachfolger.

Man überlegt sich, dass pu von der minimalen Interpretation für H0 wahr gemacht wird, gdw. es von u aus keine unendlichen Pfade gibt.

Mein bisheriges Verständnis:
pu ist für einen Knoten u genau dann wahr, wenn pv für alle Nachfolgerknoten v aus E(u) ebenfalls wahr ist. Da ein Knoten u ohne Nachfolger diese Bedingung erfüllt, da alle, nämlich keine, Nachfolgerknoten nicht falsch sind, ist in diesem Fall Cu logisch äquivalent zu pu.
Soweit so gut:
Wäre dann aber nicht die minimale Interpretation, dass alle pu mit u aus V mit 0 belegt werden. Das ginge doch auch für unendliche, aber endlich verzweigte, Bäume, oder übersehe ich etwas?

Bitte um einen Denkanstoß, mfg

pinanta
Neuling
Neuling
Beiträge: 4
Registriert: 30. Jul 2017 10:37

Re: Hornformeln: Minimale Belegung, Beispiel 5.14

Beitrag von pinanta » 30. Jul 2017 12:33

Okay, mir ist mein Fehler denke ich aufgefallen: Die leere Konjunktion (für Blätter) ist wahr, und impliziert damit, dass zumindest alle für alle Blätter u die Variable pu durch die minimale Belegung auf 1 gesetzt wird. Der Rest ergibt sich dann von da aus ...

Antworten

Zurück zu „Archiv“