Przestrzeń topologiczna związana z SAT: czy jest zwarta?

18

Spełnialności problemem jest to, oczywiście, podstawowym problemem teoretycznym CS. Bawiłem się jedną wersją problemu z nieskończenie wieloma zmiennymi.

Podstawowe ustawienia. Niech będzie niepustym i prawdopodobnie nieskończonym zestawem zmiennych . Dosłowność to albo zmienna albo jej negacja . Klauzula jest rozróżnieniem skończonej liczby literałów . Na koniec definiujemy formułę jako zestaw klauzul .X¬ x cxX¬xcF

Przypisanie X jest funkcją σ:X{0,1} . Nie będę wyraźnie określać warunku, kiedy przypisanie σ spełnia klauzulę; jest nieco nieporęczny i jest taki sam jak w standardowym SAT. Wreszcie zadanie spełnia formułę, jeśli spełnia każdą klauzulę składową. Niech sat(F) będzie zbiorem spełniających się zadań dla F , a niech unsat(F) będzie dopełnieniem sat(F) .

Przestrzeń topologiczna.

Naszym celem jest nadanie przestrzeni wszystkich przydziałów X , nazywając to Σ , strukturą topologiczną . Nasze zamknięte zestawy mają postać sat(F) gdzie F jest wzorem. Możemy zweryfikować, że jest to rzeczywiście topologia:

  • Wszystkie formuły spełniają pustą formułę niezawierającą żadnych klauzul; więc Σ jest zamknięta.
  • Formuła {x,¬x} dla dowolnego xX jest sprzecznością. Więc jest zamknięty.
  • Zamknięcie pod arbitralnym skrzyżowaniem. Załóżmy, jest preparatem dla każdego . Następnie . i I s a t ( i I F i ) = i I s a t ( F i )FiiIsat(iIFi)=iIsat(Fi)
  • Zamknięcie w ramach skończonej unii. Załóżmy, że F i G są dwiema formułami i definiują
    FG:={cd:cF,dG}.
    Następnie sat(FG)=sat(F)sat(G) To wymaga argumentu, ale pominę to.

Nazwij tę topologię T , „topologią satysfakcji” (!) Na Σ . Oczywiście otwarte zestawy tej topologii mają postać unsat(F) . Co więcej, zaobserwowano, że zbiór zestawów otwartych

{unsat(c):c is a clause}
tworzy podstawę T . (Ćwiczenie!)

Kompaktowy? Uważam, że jest to interesujący, jeśli nie bardzo użyteczny sposób patrzenia na rzeczy. Chcę zrozumieć, czy ta przestrzeń topologiczna ma tradycyjne interesujące właściwości, takie jak zwartość, łączność itp. W tym poście ograniczymy się do zwartości:

Niech będzie niezliczoną liczbą zmiennych. 1 Czy kompaktowy pod ?Σ TXΣT

Można udowodnić, co następuje

Propozycja. jest zwarty, jeżeli i tylko dla preparatów unsatisfiable istnieje skończona unsatisfiable podstruktura .TF{c1,c2,,cm}F

(Niezbyt trudne ćwiczenie!) Po kilku dniach myślenia nie mam dużego postępu w udzielaniu odpowiedzi na to pytanie. Nie mam również silnych dowodów na zwartość lub przeciw zwartości. Czy możesz zasugerować jakieś podejście?

Wreszcie jako pytanie dodatkowe:

Czy taka struktura była wcześniej badana?

1 Ograniczenie do policzalnego ma na celu uproszczenie; wydaje się także, że jest to kolejny naturalny krok od skończonej liczby zmiennych.X

Srivatsan Narayanan
źródło
(1.) W oparciu o podsumowanie wiki znacznika topologii , ten znacznik nie jest tutaj istotny. Niemniej jednak dołączyłem go, ponieważ pytanie wyraźnie łączy się z topologią zbioru punktów. (2.) Nie byłem pewien, czy to pytanie bardziej pasuje do Math.SE czy tutaj; Postanowiłem opublikować go tutaj. (3.) Przepraszamy za długość pytania. Ponieważ przypuszczam, że nie wszyscy będą zaznajomieni z przestrzenią topologiczną, wyjaśniłem to nieco bardziej szczegółowo.
Srivatsan Narayanan
2
Wysłałem prośbę o ulepszenie znacznika w celu rozszerzenia definicji znacznika topologii.
Joshua Herman
1
Mała uwaga: biorąc pod uwagę formułę F (która jest w postaci CNF), można przekonwertować ją na postać DNF, zanegować i użyć De Morgana, aby utworzyć formułę F 'w postaci CNF, tak aby sat (F) = unsat (F') i unsat (F) = sat (F '). W ten sposób każdy zestaw jest zamknięty, jeśli jest otwarty w twojej topologii.
Alex ten Brink,
Czy twoja propozycja nie jest tylko specjalnym przypadkiem twierdzenia o zwartości ( en.wikipedia.org/wiki/Compactness_theorem ) dla logiki zdań?
Travis Service,
@Travis Może być, nie jestem pewien. Moje doświadczenie w logice jest dość słabe, więc nie widzę tych rzeczy bardzo wyraźnie. :)
Srivatsan Narayanan

Odpowiedzi:

22

To, co robisz, to uzyskiwanie topologicznej reprezentacji algebry boolowskiej. Badanie reprezentacji algeb Boolowskich sięga przynajmniej Lindenbauma i Tarskiego, którzy udowodnili (jak sądzę w 1925 r.), Że kompletne, atomowe algebry boolowskie są izomorficzne w stosunku do sieci powerset.

x1,x1x2,

Twierdzenie Stone'a o algebrach boolowskich Każda algebra boolowska jest izomorficzna z siecią kratownic podzbiorów przestrzeni topologicznej.

true

Kamienna przestrzeń algebry boolowskiej jest zwartą, całkowicie niepowiązaną przestrzenią Hausdorffa.

Było kilka wyników, które rozszerzają i uogólniają reprezentację Stone'a w różnych kierunkach. Naturalnym pytaniem jest pytanie, czy inne rodziny sieci mają takie reprezentacje. Wyniki Stone'a dotyczą również krat dystrybucyjnych. Topologiczne reprezentacje dla dowolnych sieci zostały przedstawione przez Alasdair Urquhart w 1978 roku. Sieci dystrybucyjne charakteryzują się większą różnorodnością w strukturze niż algebry logiczne i są bardzo interesujące. Inną reprezentację przypadku dystrybucyjnego podała Hilary Priestley w 1970 roku, wykorzystując ideę uporządkowanej przestrzeni topologicznej . Zamiast reprezentacji opartych na zestawach możemy znaleźć reprezentacje i topologie oparte na zestawach.

Konstrukcje w tych dokumentach mają jedną niezwykłą właściwość. Konstrukcja kamienia odwzorowuje nie tylko algebry boolowskie w przestrzeniach topologicznych: relacje strukturalne dotyczące algebry boolowskiej przekładają się na właściwości strukturalne między wynikowymi topologiami. Jest to dualność między kategoriami. Cała gama takich wyników nosi nazwę Stone Duality . Nieformalnie dualności dają nam precyzyjne tłumaczenia między wszechświatami matematycznymi: kombinatoryczny świat zbiorów, algebraiczny świat sieci, przestrzenny świat topologii i dedukcyjny świat logiki. Oto kilka punktów początkowych, które mogą pomóc.

  1. Rozdział 11 wstępu do krat i porządku autorstwa Daveya i Priestleya obejmuje twierdzenie Stone'a.
  2. Slajdy Matthew Gwynne obejmują twierdzenie i dają dowód zwartości. Matthew (w komentarzach) sugeruje również wprowadzenie do algebry logicznej Paula Halmosa.
  3. Przechodząc od logiki zdań do logiki modalnej, algebra Boolean została rozszerzona o operator zachowujący łączenie i topologię z wnętrzem. Artykuł Jónssona i Tarskiego z 1952 roku, Boolean Algebras with Operators, jest niezwykle czytelny i zgodny ze współczesną notacją.
  4. Rozdział 5 logiki modalnej autorstwa Blackburn, de Rijke i Venema omawia twierdzenie Stone'a i jego rozszerzenie na algebry logiczne wraz z operatorami.
  5. Stone Spaces autorstwa Petera Johnstone'a przegląda takie wyniki dla różnych innych rodzajów algeb.
Vijay D.
źródło
4
Kamienna dualność jest bardziej ogólna. Książki Johnstone'a i Vickera (patrz część referencyjna artykułu na Wikipedii) są całkiem miłe, choć pierwsza jest dość zaawansowana.
Kaveh
1
Tak, ale nie jestem pewien, czy OP chciał wiedzieć o Stone Duality w pełnej krasie. Dodałem kilka linków do twojego komentarza. Jeśli ktoś chce tylko twierdzenia o reprezentacji, wystarczy prezentacja Daveya i Priestleya.
Vijay D
2
@Kaveh: Doceniony. Nadal przyzwyczajam się do identyfikowania pożądanego poziomu szczegółowości odpowiedzi i czytania tonu komentarzy. Nie to, że pomaga mi to, że brzmi jak zrzędliwy starzec. (buźka)
Vijay D
5
Byłby to świetny punkt wyjścia dla postu na blogu o Stone Duality i powiązaniach z CS.
Suresh Venkat,
3
„Wprowadzenie do algebr Boolean” Paula Halmosa obejmuje również twierdzenie o reprezentacji, a także inne twierdzenia o dualności.
MGwynne,