[MaLo] Horn-Formel

[mani]

Hallo zusammen,

auf Übungsblatt 2, Aufgabe 1 c):

Beweisen oder widerlegen Sie für jede der folgenden Formeln, ob sie äquivalent zu einer Horn-Formel ist.
i)

Unsere Lösung war:


Es folgt: nicht logisch äquivalent zu einer Horn-Formel, da zwei positive Literale in einer Disjunktion.

Bei der Korrektur steht jetzt "Begründung nicht ausreichend". Weiss einer, wie man zufriedenstellend zeigen kann, dass es sich um keine Horn-Formel handelt?

Grüße mani

[MartinL]

Eigenschaften von Hornformeln ausnutzen. Ich glaube mich daran zu erinnern, dass für Hornformeln gibt, dass wenn es zwei Modelle für eine Horn-Formel gibt der Schnitt der Modelle (also man belegt eine Var nur dann mit 1 wenn in beiden Modellen diese mit 1 belegt ist) wieder ein Modell der Formel sein muss. Das haben wir damals in der Übung gezeigt (http://www-mgi.informatik.rwth-aachen.d ... home02.pdf).

Wenn man nun 2 Modelle der Formel findet deren Schnitt kein Modell ist, dann kann das keine Hornformel sein. Ansonsten kannst du deine Lösung eventuell ausbauen indem du mit der Eindeutigkeit der DNF Argumentierst ... Man muss halt hier irgendwie Argumentieren warum die Umformung die gemacht wurde ganz allgemeingültig ausschließt, dass keine Hornformel existiert. Das ist so auf anib nicht ganz klar, weil man ja beliebig viele weitere Umformungen machen konnte (die eventuell zu einer Hornformel führen).

Gruß,

Martin

[palle]

[...] Das ist so auf anib nicht ganz klar, weil man ja beliebig viele weitere Umformungen machen konnte (die eventuell zu einer Hornformel führen).
[...]

Sehe ich auch so.

Martin, meinst Du mit "auf anib" eigentlich "auf Anhieb" oder ist anib jetzt eine Abkürzung, für die ich zu alt bin? Das ist eine ernsthafte Frage.

[Pila]

Ja, das ist korrekt, was sie sagen.
Also du prüfst für die Anfangsformel ob sie ein kleinstes Modell hat.
Falls ja, ist sie äquivent zu einer Hornformel, falls nicht, dann eben nicht.

Kleinstes Modell heißt in diesem Fall eben minimal und klein.

[MartinL]

Eigentlich kam Martin gestern von der Seminar "Nachbesprechung" auf der Pontstraße und konnte zwar noch MaLo aber keine Rechtschreibung mehr

[palle]

Das beantwortet nicht meine Frage

[chrisblablub]

D.h. wenn die formel 2 modelle hat wo z.B. einmal X auf 0 und einma X auf 1 gesetzt wird, hat sie kein minimales Modell un is keine hornformel?

[aLee]

Nein, das kleinste Modell ist dadurch ausgezeichnet, dass die in diesem Modell auf 1 gesetzten Variablen in allen anderen Modellen auch auf 1 gesetzt sind.
Wenn eine Formel zB die Modelle 100 und 010 hat, 000 aber kein Modell ist, dann hat diese Formel kein minimales Modell, weil der Schnitt von zwei Modellen nicht wieder ein Modell ist...

Wenn aber zB 100 ein kleinstes Modell ist, und 111 ein weiteres Modell, dann darf (wie in deiner Frage) auch eine Variable mal auf 0, mal auf 1 gesetzt werden

[chrisblablub]

hm ok. Kann es auch 2 minimale modelle geben? also wenn ich z.b. 2 Modelle 11 und 01 betrachte,wäre dann 00 und 01 ein minimales modell? Oder nur eins von beiden?

[aLee]

hm ok. Kann es auch 2 minimale modelle geben?

nein (bzw die Formel ist nicht äquivalent zu ner hornformel wenn es nicht DAS kleinste Modell gibt)

also wenn ich z.b. 2 Modelle 11 und 01 betrachte,wäre dann 00 und 01 ein minimales modell? Oder nur eins von beiden?

Also wenn bei dir 00, 01 und 11 alles Modelle sind, dann ist 00 ja dein minimales Modell.

[chrisblablub]

ach hast recht, wenn 00 nen modell is kann 01 ja kein minimales modell mehr sein. danke =)

[mani]

Dankeschön, hab den Trick verstanden

[Pila]

Es kann ein 2 minimale Modelle geben, aber trz. kein kleinstes Modell, sodass es nicht äquiv. zu einer Hornformel ist.
z.B. Seien X = 0, Y = 1 ein Modell und X = 1, Y = 0 ist offensichtlich minimal, aber nicht äquiv. zu einer Hornforml.

[chrisblablub]

warum ist x = 1, y = 0 minimal? ich dachte ein modell is dann minimal, wenn alle veriablen die mit 1 belegt sind auch in allen anderen modellen mit 1 belegt sind?

[Pila]

Das ist doch kleinstes Modell dann.
Also die Begriffe klein und minimal sind nicht äquivalent.