Ein topologischer Raum im Zusammenhang mit SAT: Ist er kompakt?

18

Das Erfüllbarkeit Problem ist natürlich, ein grundsätzliches Problem in der theoretischen CS. Ich habe mit einer Version des Problems mit unendlich vielen Variablen gespielt.

Grundeinstellung. Sei eine nicht leere und möglicherweise unendliche Menge von Variablen . Ein Literal ist entweder eine Variable oder ihre Negation . Eine Klausel ist eine Disjunktion einer endlichen Anzahl von Literalen . Schließlich definieren wir eine Formel als eine Menge von Klauseln .X¬ x cxX¬xcF

Eine Zuordnung von ist eine Funktion . Ich werde die Bedingung nicht explizit definieren, wenn eine Zuweisung eine Klausel erfüllt; Es ist etwas umständlich und entspricht dem Standard-SAT. Schließlich erfüllt eine Zuweisung eine Formel, wenn sie jede konstituierende Klausel erfüllt. Sei die Menge befriedigender Zuordnungen für und sei \ unsat (F) das Komplement von \ sat (F) .σ : X { 0 , 1 } σ s a t ( F ) F u n s a t ( F ) s a t ( F )Xσ:X{0,1}σsat(F)Funsat(F)sat(F)

Ein topologischer Raum.

Unser Ziel ist es, den Raum aller Zuweisungen von X , das heißt Σ , mit einer topologischen Struktur auszustatten . Unsere geschlossenen Mengen haben die Form seint(F) wobei F eine Formel ist. Wir können überprüfen, ob dies tatsächlich eine Topologie ist:

  • Die leere Formel keine Klauseln enthält , wird von allen Aufgaben erfüllt; also ist Σ geschlossen.
  • Die Formel {x,¬x} für ein beliebiges xX ist ein Widerspruch. So ist geschlossen.
  • Schließung unter willkürlicher Überschneidung. Angenommen Fich ist eine Formel für jedes ichich . Dann ist seint(ichichFich)=ichichseint(Fich) .
  • Schließung unter endlicher Vereinigung. Angenommen, F und G sind zwei Formeln und definieren
    FG: ={cd:cF,dG}.
    Dann ist seint(FG)=seint(F)seint(G) Hierfür ist ein Argument erforderlich, das überspringe ich jedoch.

Nennen Sie diese Topologie T , die "Erfüllbarkeitstopologie" (!) In Σ . Natürlich haben die offenen Mengen dieser Topologie die Form \ unsat (F)unseint(F) . Außerdem habe ich festgestellt, dass die Sammlung offener Mengen

{unseint(c):c ist eine Klausel}
eine Grundlage für T . (Übung!)

Kompakt? Ich halte dies für eine interessante, wenn nicht sogar fürchterlich nützliche Betrachtungsweise. Ich möchte verstehen, ob dieser topologische Raum traditionelle interessante Eigenschaften wie Kompaktheit, Verbundenheit usw. besitzt. In diesem Beitrag beschränken wir uns auf Kompaktheit:

Sei eine unendlich zählbare Sammlung von Variablen. 1 Ist compact unter ?XΣT

Man kann folgendes beweisen

Vorschlag. ist kompakt, wenn und nur für alle nicht erfüllbaren Formeln eine endliche nicht erfüllbare Unterformel .TF{c1,c2,,cm}F

(Nicht so harte Übung!) Nach einigen Tagen des Nachdenkens habe ich keine großen Fortschritte bei der Beantwortung dieser Frage. Ich habe auch keine starken Beweise für oder gegen Kompaktheit. Können Sie einen Ansatz vorschlagen?

Zum Schluss als Bonusfrage:

Wurde eine solche Struktur schon einmal untersucht?

1 Die Beschränkung auf zählbares dient nur der Vereinfachung. es fühlt sich auch wie der nächste natürliche Schritt aus einer endlichen Anzahl von Variablen an.X

Srivatsan Narayanan
quelle
(1.) Basierend auf der Wiki-Zusammenfassung des Topologie- Tags ist dieses Tag hier nicht so relevant. Trotzdem habe ich es aufgenommen, da die Frage explizit mit der Punkt-Set-Topologie in Verbindung steht. (2.) Ich war mir nicht sicher, ob diese Frage besser für Math.SE oder hier geeignet ist. Ich habe beschlossen, es hier zu posten. (3.) Entschuldigen Sie die Länge der Frage. Da ich davon ausgehe, dass nicht jeder mit einem topologischen Raum vertraut sein wird, habe ich das etwas ausführlicher erklärt.
Srivatsan Narayanan
2
Ich habe eine Tag-Verbesserungsanforderung eingereicht, um die Definition des Topologie-Tags zu erweitern.
Joshua Herman
1
Kleine Bemerkung: Wenn eine Formel F (die in CNF-Form vorliegt) gegeben ist, kann man sie in DNF-Form umwandeln, sie negieren und mit De Morgan eine Formel F 'in CNF-Form erstellen, so dass sat (F) = unsat (F') und ungesättigt (F) = gesessen (F '). Dadurch wird jeder Satz geschlossen, wenn er in Ihrer Topologie geöffnet ist.
Alex ten Brink
Ist Ihr Satz nicht nur ein Sonderfall des Kompaktheitssatzes ( en.wikipedia.org/wiki/Compactness_theorem ) für die Aussagenlogik?
Travis Service
@ Travis Es könnte sein, ich bin mir nicht sicher. Mein logischer Hintergrund ist ziemlich mangelhaft, so dass ich diese Dinge nicht sehr klar sehen kann. :)
Srivatsan Narayanan

Antworten:

22

Sie leiten eine topologische Darstellung einer Booleschen Algebra ab. Das Studium der Darstellungen von Booleschen Algebren geht zumindest auf Lindenbaum und Tarski zurück, die (glaube ich) 1925 bewiesen haben, dass die vollständigen atomaren Booleschen Algebren isomorph zu Powerset-Gittern sind.

Es gibt jedoch Boolesche Algebren, die nicht vollständig und atomar sind. Beispielsweise ist die Folge eine absteigende Kette, für die in der über Formeln definierten Booleschen Algebra keine Beschränkung besteht. Die Frage, ob beliebige Boolesche Algebren, wie die von Ihnen erwähnte, auch satzbasierte Darstellungen hatten, wurde von Marshall Stone gelöst , der die Maxime "Immer topologisieren" aufstellte (Marshall H. Stone. Die Darstellung von Booleschen Algebren , 1938). .x1,x1x2,

Stones Darstellungssatz für Boolesche Algebren Jede Boolesche Algebra ist isomorph zum Gitter geschlossener Teilmengen eines topologischen Raums.

Die Hauptidee ist zu überlegen, was in Ihrem Fall die zufriedenstellenden Zuordnungen zu einer Formel sind. Im allgemeinen Fall betrachten Sie Homomorphismen aus einer Booleschen Algebra in die Boolesche Algebra mit zwei Elementen (die Wahrheitswerte). Die Inverse von Sie die Sätze von erfüllenden Belegungen gibt, oder was Ultra der Boolesche Algebra genannt. Aus diesen kann man eine Topologie erhalten, die als Spektrum oder Steinraum einer Booleschen Algebra bezeichnet wird. Stone liefert auch die Antwort auf Ihre Frage.true

Der Steinraum einer Booleschen Algebra ist ein kompakter, völlig unverbundener Hausdorff-Raum.

Es gibt mehrere Ergebnisse, die die Darstellung von Stone in verschiedene Richtungen erweitern und verallgemeinern. Eine natürliche Frage ist, ob andere Gitterfamilien solche Darstellungen haben. Stones Ergebnisse gelten auch für Verteilungsgitter. Topologische Darstellungen für beliebige Gitter wurden 1978 von Alasdair Urquhart gegeben. Verteilungsgitter weisen im Vergleich zu Booleschen Algebren eine größere Strukturvielfalt auf und sind von großem Interesse. Eine andere Darstellung für den Verteilungsfall wurde 1970 von Hilary Priestley unter Verwendung der Idee eines geordneten topologischen Raums gegeben . Anstelle von satzbasierten Darstellungen finden wir posetbasierte Darstellungen und Topologien.

Die Konstruktionen in diesen Papieren haben eine bemerkenswerte Eigenschaft. Die Konstruktion von Stone ordnet nicht nur Boolesche Algebren topologischen Räumen zu: Strukturelle Beziehungen, die Boolesche Algebren betreffen, führen zu strukturellen Eigenschaften zwischen den resultierenden Topologien. Es ist eine Dualität zwischen Kategorien. Die gesamte Bandbreite solcher Ergebnisse wird als Stone Duality bezeichnet . Inoffiziell liefern Dualitäten präzise Übersetzungen zwischen mathematischen Universen: der kombinatorischen Welt der Mengen, der algebraischen Welt der Gitter, der räumlichen Welt der Topologie und der deduktiven Welt der Logik. Hier sind einige Ansatzpunkte, die hilfreich sein können.

  1. Kapitel 11 der Einführung in Gitter und Ordnung von Davey und Priestley behandelt Stones Theorem.
  2. Die Folien von Matthew Gwynne decken den Satz ab und geben einen Beweis für die Kompaktheit. Matthäus (in den Kommentaren) schlägt auch eine Einführung in die Booleschen Algebren von Paul Halmos vor.
  3. Beim Übergang von der Aussagenlogik zur Modallogik wird die Boolesche Algebra um einen Verknüpfungserhaltungsoperator und eine Topologie mit einem Innenraum erweitert. Die Booleschen Algebren mit Operatoren aus dem Jahr 1952 von Jónsson und Tarski sind äußerst lesbar und stimmen mit der modernen Notation überein.
  4. Kapitel 5 der Modal Logic von Blackburn, de Rijke und Venema befasst sich mit Stones Theorem und seiner Erweiterung auf Boolesche Algebren mit Operatoren.
  5. Stone Spaces von Peter Johnstone überprüft solche Ergebnisse für verschiedene andere Arten von Algebren.
Vijay D
quelle
4
Stone Duality ist allgemeiner. Die Bücher von Johnstone und Vicker (siehe den Referenzteil des Wikipedia-Artikels) sind beide sehr schön, obwohl das erste ziemlich weit fortgeschritten ist.
Kaveh
1
Ja, aber ich bin mir nicht sicher, ob die OP Stone Duality in seiner ganzen Pracht kennenlernen wollte. Habe ein paar Links zu deinem Kommentar hinzugefügt. Wenn man nur den Repräsentationssatz haben will, genügt die Präsentation von Davey und Priestley.
Vijay D
2
@ Kaveh: Geschätzt. Ich gewöhne mich immer noch daran, den gewünschten Detaillierungsgrad einer Antwort zu ermitteln und den Ton der Kommentare zu lesen. Nicht, dass es mir hilft, wenn ich mich wie ein mürrischer alter Mann anhöre. (Smiley-Gesicht)
Vijay D
5
Dies wäre ein guter Ausgangspunkt für einen Blogbeitrag über Stone Duality und Verbindungen zu CS.
Suresh Venkat
3
Paul Halmos '"Einführung in die Booleschen Algebren" behandelt auch den Repräsentationssatz sowie andere Dualitätssätze.
MGwynne