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 c
Przypisanie jest funkcją . 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 będzie zbiorem spełniających się zadań dla , a niech będzie dopełnieniem .
Przestrzeń topologiczna.
Naszym celem jest nadanie przestrzeni wszystkich przydziałów , nazywając to , strukturą topologiczną . Nasze zamknięte zestawy mają postać gdzie 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 dla dowolnego 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 )
- Zamknięcie w ramach skończonej unii. Załóżmy, że i są dwiema formułami i definiują
Następnie To wymaga argumentu, ale pominę to.
Nazwij tę topologię , „topologią satysfakcji” (!) Na . Oczywiście otwarte zestawy tej topologii mają postać . Co więcej, zaobserwowano, że zbiór zestawów otwartych
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 ?Σ T
Można udowodnić, co następuje
Propozycja. jest zwarty, jeżeli i tylko dla preparatów unsatisfiable istnieje skończona unsatisfiable podstruktura .
(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.
Odpowiedzi:
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.
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.
źródło