Wie sind Prime impliziert von Horn-Formeln definiert?

Question

Ich bin verwirrt über die Definition von Prime impliziert in Hornformeln.

Beispielsweise in der Zeitung von kira 2012 auf Seite 109 wird gesagt:

jetzt in der Zeitung von boros 2010 auf Seite 82 Die folgende Definition wird eingesetzt:

Mein Ziel ist es, zu entscheiden, ob eine Hornformel Prime oder nicht in der Polynomzeit ist. Dafür möchte ich die in der Kira 2012 verwendete Definition annehmen.

Wie kann ich nachweisen, dass die beiden oben genannten Definitionen für Prime-Implikationen von Hornformeln gleichwertig sind?

edit: Was ich bisher habe, ist, dass wir, wenn wir die Definition von Kiras übernehmen und zum Beispiel eine Klausel $ C=neg x_1 \ vee \ neg x_2 \ vee x_3 $ der Formel < Span-Klasse="Math-Container"> $ F $ und $ C $ ist Prime, dann $ F \ Rightarrow C $ . Wenn man ein Literal in c vernachlässigt, erhalten wir $ c_1=neg x_1 \ vee \ neg x_2 $ und offensichtlich $ c_1 \ Rightarrow C $ . Daher ist es, da $ C $ Prime dann von kiras Definition keine andere ordnungsgemäße Sub-Klausel von $ C $ ist ein impliziter also so $ f \ nrightarrow c_1 $ . Vernachlässigung von mehr Literalen in $ C_1 $ , um $ C_2 $ zu erhalten, geben $ C_2 \ Rightarrow C_1 \ Rightsarrow C $ . Dann per Definition von $ c $ muss es sein, dass $ f \ nrightarrow c_2 \ rightarrow c_1 $ und wir Erhalten Sie, dass alle Unterklauseln von $ C_1 $ nicht prime, wenn wir überprüfen, ob $ c_1 $ nicht ist Prime. Um zu überprüfen, ob eine Formel $ F $ Prime ist, berücksichtigen wir jede Klausel $ C $ und vernachlässigen alle Literale von $ C $ Einmal und prüfen, ob die neue Klausel nicht erstklassig ist. Wenn eine Klausel primiert ist, folgt, dass f nicht primiert ist.

Ich denke, der Äquivalenz für die andere Richtung ist in ähnlicher Weise. Nehmen Sie die Definition von Boros an. Wenn wir dann die Klausel $ C $ in Betracht ziehen und ein beliebiges Literal fallen lassen, werden wir $ C_1 $ , was nicht ist Eine Implizite, wenn $ C $ Prime ist, so $ F \ Nrightarrow C_1 $ . Wieder haben wir ovisuell $ C_1 \ Rightarrow C $ und indem Sie weitere willkürliche Literale in $ C_1 $ an ablegen Holen Sie sich $ C_2 $ Wir HINWEIS $ F \ Nrightarrow C_2 \ Rightarrow C_1 $ (Ansonsten $ F \ Rightsarrow C_2 \ Rightarrow C_1 $ das ist falsch seit $ c_1 $ ist nicht impliziert). Da wir durch Ablegen von Literalen beliebige Unterklauseln herstellen können, kann man folgen, dass auch alle ordnungsgemäßen Unterklauseln von c nicht prime sein, da sonst $ F \ Rightarrow C_2 \ Rightarrow C_1 $ das ist ein Widerspruch. Und Kiras Definition folgt.

ist mein Begründen richtig?

Answer 1

Diese Äquivalenz ist eine etwas ähnliche Folklore-Idee in Papieren über Prime Implizins. Ein kleiner Beweis ist im Abschnitt „Definitionen“ präsentiert von diesem Papier . Die Idee hinter der Äquivalenz ist, dass, wenn $ C $ kein Prime-Implikaner für $ \ varphi $ ist, ist , dann gibt es eine ordnungsgemäße Subset $ C '$ von $ C $ (Identifizierung von Klauseln mit dem Satz von Literale, die sie zwingen), so dass $ C '$ ein Implikaner von $ \ varphi $ ist. Wenn dies jedoch der Fall ist, können Sie $ C '$ mit den Literalen in $ C \ SetMinus C' $ füllen bis es mit Größe $ | C | hat - 1 $ , und somit erhalten Sie einen Implikanten, der $ C $ minus genau ein wörtliches Wort ist, das Sie "fallen lassen". Die andere Richtung der Äquivalenz ist trivial: Wenn keine ordnungsgemäße Teilmenge von $ C $ ist, ist ein Implikaner, und dann das Lasten des $ C $ Gibt Ihnen etwas, das kein Implikaner ist.

Ich sehe die Beziehung nicht mit Hornformeln, da die Äquivalenz von Definitionen für Prime-Implikaner jeder Formel beträgt.