Hallo, habe mal eine Frage zur Definition dieses Graphen G(F).

Ich verstehe dass so, dass die Knotenmenge die Literale sein sollen(also negierte und nicht negierte Atome).

Bei der Kantenmenge wundere ich mich ein wenig: Sollen diese alpha und beta Atome oder Literale sein? Da die Knotenmenge ja aus Literalen besteht, müssten alpha und beta auch Literale sein.
Allerdings steht danach nur für alpha und beta falls ( negiert alpha oder beta) oder ( beta oder negiert alpha). Die Sache ist jetzt die :
Also angenommen wir haben die Klausel x V y .
Können wir dann alpha = neg x , beta = y setzen, da dann ja nach der Äquivalenzregel "Doppelnegation" gilt neg neg x V y = x V y ? Oder dürfen wir keine Äquivalenzregeln anwenden?

Kurz: Meint dieses (neg alpha V beta) bzw. ( beta V neg alpha) rein die Syntax, oder berücksichtigt es auch Äquivalenzersetzung?

Hi…

letzteres ist richtig, d.h. Äquivalenzumformungen sind erlaubt.

Jede Klausel führt zu zwei Kanten im Graphen (weil mit (a,b) auch (?1,?2) eine Kante im Graphen ist - mit ?1 und ?2 zum Selbstausfüllen ;) ), d.h. bei fünf Klauseln, solltest du nachher auf 10 Kanten kommen.

(Obiges "Jede Klausel führt zu zwei Kanten im Graphen" stimmt natürlich nur, wenn das verschiedene (im Sinne von "nicht äquivalente" Klauseln sind! Wenn ich z.B. zweimal die gleiche Klausel habe, dann "produzieren" die ja beide die gleichen Kanten im Graphen!)