Um espaço topológico relacionado ao SAT: é compacto?

18

O problema da satisfação é, obviamente, um problema fundamental no CS teórico. Eu estava brincando com uma versão do problema com infinitas variáveis.

Configuração básica. Seja X um conjunto de variáveis não vazio e possivelmente infinito . Um literal é uma variável xX ou sua negação ¬x . Uma cláusula c é uma disjunção do número finito de literais . Finalmente, definimos uma fórmula F como um conjunto de cláusulas .

Uma atribuição de X é uma função σ:X{0,1} . Não definirei explicitamente a condição para quando uma atribuição σ satisfizer uma cláusula; é um pouco complicado e é o mesmo que no SAT padrão. Finalmente, uma atribuição satisfaz uma fórmula se satisfizer todas as cláusulas constituintes. Seja sat(F) o conjunto de atribuições satisfatórias para F , e unsat(F) seja o complemento de sat(F) .

Um espaço topológico.

Nosso objetivo é dotar o espaço de todas as atribuições de X , chamado Σ , com uma estrutura topológica . Nossos conjuntos fechados são da forma sat(F) onde F é uma fórmula. Podemos verificar se essa é realmente uma topologia:

  • A fórmula vazia que não contém cláusulas é satisfeita por todas as atribuições; assim Σ está fechado.
  • A fórmula {x,¬x} para qualquer xX é uma contradição. Então está fechado.
  • Fechamento sob interseção arbitrária. Suponha Fi é uma fórmula para cada iI . Então sat(iIFi)=iIsat(Fi) .
  • Encerramento sob união finita. Suponha que F e G sejam duas fórmulas e defina
    FG:={cd:cF,dG}.
    Então sat(FG)=sat(F)sat(G) . Isso precisa de um argumento, mas vou pular isso.

Chame essa topologia T , a "topologia de satisfação" (!) No Σ . Obviamente, os conjuntos abertos dessa topologia têm o formato unsat(F) . Além disso, observei que a recolha de conjuntos abertos

{unsat(c):c is a clause}
forma uma base para T . (Exercício!)

Compactar? Eu sinto que essa é uma maneira interessante, se não terrivelmente útil, de ver as coisas. Quero entender se esse espaço topológico possui propriedades interessantes tradicionais como compacidade, conectividade etc. Neste post, vamos nos restringir à compacidade:

Seja uma coleção infinita de variáveis. 1 Is compacto sob ?Σ TXΣT

Pode-se provar o seguinte

Proposição. é compacto e se apenas para todas as fórmulas insatisfatível , existe uma subfórmula finito insatisfatível .TF{c1 1,c2,...,cm}F

(Exercício não tão difícil!) Após vários dias de reflexão, não tenho muito progresso em responder a essa pergunta. Também não tenho fortes evidências a favor ou contra a compacidade. Você pode sugerir alguma abordagem?

Finalmente, como uma pergunta bônus:

Essa estrutura já foi estudada antes?

1 A restrição para contável é apenas por simplicidade; também parece o próximo passo natural do número finito de variáveis.X

Srivatsan Narayanan
fonte
(1.) Com base no resumo do wiki da tag de topologia , essa tag não é relevante aqui. No entanto, eu o incluí, pois a pergunta se conecta explicitamente à topologia de conjunto de pontos. (2.) Eu não tinha certeza se essa pergunta é mais adequada para Math.SE ou aqui; Eu decidi postar aqui. (3.) Desculpe o tamanho da pergunta. Como presumo que nem todos estarão familiarizados com um espaço topológico, expliquei essas coisas um pouco mais elaboradamente.
Srivatsan Narayanan
2
Enviei uma solicitação de melhoria de tag para ampliar a definição da tag de topologia.
Joshua Herman
11
Pequena observação: dada uma fórmula F (que está no formato CNF), pode-se convertê-lo para o formato DNF, negá-lo e usar De Morgan para criar uma fórmula F 'no formato CNF, de modo que sat (F) = unsat (F') e insat (F) = sat (F '). Assim, qualquer conjunto é fechado se estiver aberto em sua topologia.
Alex10 Brink
Sua proposição não é apenas um caso especial do teorema da compactação ( en.wikipedia.org/wiki/Compactness_theorem ) para lógica proposicional?
Travis Service
@ Travis Poderia ser, não tenho certeza. Minha formação em lógica é bastante deficiente, então não posso ver essas coisas com muita clareza. :)
Srivatsan Narayanan

Respostas:

22

O que você está fazendo é derivar uma representação topológica de uma álgebra booleana. O estudo das representações das álgebras booleanas remonta pelo menos a Lindenbaum e Tarski, que provaram (em 1925, eu acho) que as álgebras booleanas atômicas completas são isomórficas para as redes de conjuntos de potências.

x1 1,x1 1x2,...

Teorema da representação de Stone para álgebras booleanas Toda álgebra booleana é isomórfica à estrutura dos subconjuntos de clopen de um espaço topológico.

trvocêe

O espaço Stone de uma álgebra booleana é um espaço Hausdorff compacto e totalmente desconectado.

Houve vários resultados que ampliam e generalizam a representação de Stone em várias direções. Uma questão natural é perguntar se outras famílias de treliças têm essas representações. Os resultados de Stone também se aplicam a redes distributivas. Representações topológicas para redes arbitrárias foram dadas por Alasdair Urquhart em 1978. As redes distributivas desfrutam de maior diversidade na estrutura, em comparação com as álgebras booleanas e são de grande interesse. Uma representação diferente para o caso distributivo foi dada por Hilary Priestley em 1970, usando a idéia de um espaço topológico ordenado . Em vez de representações baseadas em conjuntos, podemos encontrar representações e topologias baseadas em posets.

As construções nestes documentos têm uma propriedade notável. A construção de Stone mapeia não apenas álgebras booleanas para espaços topológicos: relações estruturais relacionadas a álgebras booleanas se traduzem em propriedades estruturais entre as topologias resultantes. É uma dualidade entre categorias. Toda a gama de resultados é chamada Dualidade de Pedra . Informalmente, as dualidades nos dão traduções precisas entre os universos matemáticos: o mundo combinatório dos conjuntos, o mundo algébrico das redes, o mundo espacial da topologia e o mundo dedutivo da lógica. Aqui estão alguns pontos de partida que podem ajudar.

  1. O capítulo 11 da Introdução a redes e ordem , de Davey e Priestley, aborda o teorema de Stone.
  2. Os slides de Matthew Gwynne cobrem o teorema e dão uma prova de compacidade. Matthew (nos comentários) também sugere Introdução às álgebras booleanas por Paul Halmos.
  3. Ao passar da lógica proposicional para a lógica modal, a álgebra booleana é estendida com um operador de preservação de junção e a topologia com um interior. O artigo de Jónsson e Tarski, de 1952, Álgebras Booleanas com Operadores é extremamente legível e consistente com a notação moderna.
  4. O capítulo 5 da lógica modal de Blackburn, de Rijke e Venema aborda o teorema de Stone e sua extensão às álgebras booleanas com operadores.
  5. Stone Spaces, de Peter Johnstone, analisa esses resultados para vários outros tipos de álgebras.
Vijay D
fonte
4
A dualidade de pedra é mais geral. Os livros de Johnstone e Vicker (consulte a parte de referências do artigo da Wikipedia) são bastante bons, embora o primeiro seja bastante avançado.
Kaveh
11
Sim, mas não tenho certeza se o OP queria saber sobre a Dualidade da Pedra em toda a sua glória. Adicionei alguns links por seu comentário. Se alguém apenas quer o teorema da representação, a apresentação de Davey e Priestley é suficiente.
Vijay D
2
@ Kaveh: Apreciado. Ainda estou me acostumando a identificar o nível de detalhe desejado de uma resposta e a ler o tom dos comentários. Não que o meu som de um velho rabugento ajude. (smiley-face)
Vijay D
5
Este seria um ótimo ponto de partida para uma postagem no blog sobre Stone Duality e conexões com o CS.
Suresh Venkat
3
A "Introdução às Álgebras Booleanas" de Paul Halmos também abrange o teorema da representação, bem como outros teoremas da dualidade.
MGwynne