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 um conjunto de variáveis não vazio e possivelmente infinito . Um literal é uma variável ou sua negação . Uma cláusula é uma disjunção do número finito de literais . Finalmente, definimos uma fórmula como um conjunto de cláusulas .
Uma atribuição de é uma função . 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 o conjunto de atribuições satisfatórias para , e seja o complemento de .
Um espaço topológico.
Nosso objetivo é dotar o espaço de todas as atribuições de , chamado , com uma estrutura topológica . Nossos conjuntos fechados são da forma onde é 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 para qualquer é uma contradição. Então está fechado.
- Fechamento sob interseção arbitrária. Suponha é uma fórmula para cada . Então .
- Encerramento sob união finita. Suponha que e sejam duas fórmulas e defina
Então . Isso precisa de um argumento, mas vou pular isso.
Chame essa topologia , a "topologia de satisfação" (!) No . Obviamente, os conjuntos abertos dessa topologia têm o formato . Além disso, observei que a recolha de conjuntos abertos
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 ?Σ 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 .
(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.
Respostas:
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.
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.
fonte