Un espace topologique lié à la SAT: est-il compact?

18

Le problème de satisfaction est, bien sûr, un problème fondamental en CS théorique. Je jouais avec une version du problème avec une infinité de variables.

Configuration de base. Soit X un ensemble de variables non vide et éventuellement infini . Un littéral est soit une variable XX soit sa négation ¬X . Une clause c est une disjonction d' un nombre fini de littéraux . Enfin, nous définissons une formule F comme un ensemble de clauses .

Une affectation de X est une fonction σ:X{0,1} . Je ne définirai pas explicitement la condition à laquelle une affectation σ satisfait une clause; il est légèrement encombrant et identique à celui du SAT standard. Enfin, une affectation satisfait une formule si elle satisfait toutes les clauses constitutives. Soit sat(F) l'ensemble des affectations satisfaisantes pour F , et soit unsunet(F) le complément de sunet(F) .

Un espace topologique.

Notre objectif est de doter l'espace de toutes les affectations de X , appelons ceci Σ , d'une structure topologique . Nos ensembles fermés sont de la forme sunet(F)F est une formule. On peut vérifier qu'il s'agit bien d'une topologie:

  • La formule vide ne contenant aucune clause est satisfaite par toutes les affectations; donc Σ est fermé.
  • La formule {X,¬X} pour tout XX est une contradiction. Donc est fermé.
  • Fermeture sous intersection arbitraire. Supposons Fje est une formule pour chaque jeje . Alors sunet(jejeFje)=jejesunet(Fje) .
  • Fermeture sous union finie. Supposons que F et g sont deux formules et définissent
    Fg: ={c:cF,g}.
    Alors sunet(Fg)=sunet(F)sunet(g) . Cela nécessite un argument, mais je vais sauter ceci.

Appelez cette topologie T , la "topologie de satisfiabilité" (!) Sur Σ . Bien sûr, les ensembles ouverts de cette topologie sont de la forme \ unsat (F)unsunet(F) . De plus, je remarquai que la collection d'ensembles ouverts

{unsunet(c):c est une clause}
constitue une base pour T . (Exercice!)

Compact? Je pense que c'est une façon intéressante, sinon terriblement utile, de voir les choses. Je veux comprendre si cet espace topologique possède des propriétés traditionnelles intéressantes comme la compacité, la connectivité, etc. Dans cet article, nous nous limiterons à la compacité:

Soit une collection infiniment dénombrable de variables. 1 Est compact sous ?Σ TXΣT

On peut prouver ce qui suit

Proposition. est compact si et seulement pour toutes les formules insatisfiables , il existe une sous - formule insatisfiables finie .TF{c1,c2,,cm}F

(Exercice pas si difficile!) Après plusieurs jours de réflexion, je n'ai pas beaucoup progressé pour répondre à cette question. Je n'ai pas non plus de preuves solides pour ou contre la compacité. Pouvez-vous suggérer une approche?

Enfin, comme question bonus:

Une telle structure a-t-elle été étudiée auparavant?

1 La restriction à dénombrable est juste pour la simplicité; cela ressemble aussi à la prochaine étape naturelle à partir d'un nombre fini de variables.X

Srivatsan Narayanan
la source
(1.) Sur la base du résumé wiki de la balise de topologie , cette balise n'est pas pertinente ici. Néanmoins, je l'ai inclus car la question se connecte explicitement à la topologie par points. (2.) Je ne savais pas si cette question convenait mieux à Math.SE ou ici; J'ai décidé de le poster ici. (3.) Désolé pour la longueur de la question. Comme je présume que tout le monde ne connaît pas un espace topologique, j'ai expliqué ces choses un peu plus en détail.
Srivatsan Narayanan
2
J'ai soumis une demande d'amélioration de balise pour élargir la définition de la balise de topologie.
Joshua Herman
1
Petite remarque: étant donné une formule F (qui est sous forme CNF), on peut la convertir en forme DNF, la nier et utiliser De Morgan pour créer une formule F 'sous forme CNF telle que sat (F) = unsat (F') et unsat (F) = sat (F '). Ainsi, tout ensemble est fermé s'il est ouvert dans votre topologie.
Alex ten Brink
Votre proposition n'est-elle pas simplement un cas spécial du théorème de compacité ( en.wikipedia.org/wiki/Compactness_theorem ) pour la logique propositionnelle?
Travis Service
@Travis C'est possible, je n'en suis pas sûr. Mon expérience en logique est assez déficiente, donc je ne peux pas voir ces choses très clairement. :)
Srivatsan Narayanan

Réponses:

22

Ce que vous faites est de dériver une représentation topologique d'une algèbre booléenne. L'étude des représentations des algèbres booléennes remonte au moins à Lindenbaum et Tarski qui ont prouvé (en 1925, je pense) que les algèbres booléennes atomiques complètes sont isomorphes aux réseaux de jeux de puissance.

Il existe cependant des algèbres booléennes qui ne sont pas complètes et atomiques. Par exemple, la séquence , est une chaîne descendante qui n'a pas de limite dans l'algèbre booléenne définie sur des formules. La question de savoir si des algèbres booléennes arbitraires, comme celle que vous mentionnez, avait également des représentations basées sur des ensembles a été résolue par Marshall Stone , qui a avancé la maxime "toujours topologiser" (Marshall H. Stone. La représentation des algèbres booléennes , 1938) .X1,X1X2,

Théorème de représentation de Stone pour les algèbres booléennes Chaque algèbre booléenne est isomorphe au réseau de sous-ensembles clopen d'un espace topologique.

L'idée principale est de considérer quelles sont dans votre cas les affectations satisfaisantes d'une formule. Dans le cas général, vous considérez les homomorphismes d'une algèbre booléenne dans l'algèbre booléenne à deux éléments (les valeurs de vérité). L'inverse de vous donne les ensembles de missions satisfaisant, ou ce qu'on appelle ultrafiltres de l'algèbre booléenne. À partir de ceux-ci, on peut obtenir une topologie appelée spectre ou espace de pierre d'une algèbre booléenne. Stone répond également à votre question.true

L'espace de pierre d'une algèbre booléenne est un espace de Hausdorff compact et totalement déconnecté.

Plusieurs résultats ont étendu et généralisé la représentation de Stone dans différentes directions. Une question naturelle est de se demander si d'autres familles de réseaux ont de telles représentations. Les résultats de Stone s'appliquent également aux réseaux distributifs. Alasdair Urquhart a donné des représentations topologiques pour les réseaux arbitraires en 1978. Les réseaux distributifs jouissent d'une plus grande diversité de structure par rapport aux algèbres de Boole et présentent un grand intérêt. Hilary Priestley a donné une représentation différente du cas distributif en 1970, en utilisant l'idée d'un espace topologique ordonné . Au lieu de représentations basées sur des ensembles, nous pouvons trouver des représentations et des topologies basées sur des posets.

Les constructions de ces papiers ont une propriété remarquable. La construction de Stone ne mappe pas seulement les algèbres booléennes aux espaces topologiques: les relations structurelles reliant les algèbres booléennes se traduisent en propriétés structurelles entre les topologies résultantes. C'est une dualité entre les catégories. Toute la gamme de ces résultats s'appelle Stone Duality . Informellement, les dualités nous donnent des traductions précises entre les univers mathématiques: le monde combinatoire des ensembles, le monde algébrique des réseaux, le monde spatial de la topologie et le monde déductif de la logique. Voici quelques points de départ qui peuvent vous aider.

  1. Le chapitre 11 de Introduction to Lattices and Order , par Davey et Priestley, couvre le théorème de Stone.
  2. Les diapositives de Matthew Gwynne couvrent le théorème et donnent une preuve de compacité. Matthew (dans les commentaires) suggère également l' introduction aux algèbres booléennes par Paul Halmos.
  3. En passant de la logique propositionnelle à la logique modale, l'algèbre booléenne est étendue avec un opérateur préservant les jointures et une topologie avec un intérieur. L'article de Jónsson et Tarski, 1952, Algèbres booléennes avec opérateurs est extrêmement lisible et conforme à la notation moderne.
  4. Le chapitre 5 de Modal Logic de Blackburn, de Rijke et Venema couvre le théorème de Stone et son extension aux algèbres booléennes avec des opérateurs.
  5. Stone Spaces de Peter Johnstone examine ces résultats pour divers autres types d'algèbres.
Vijay D
la source
4
Stone Duality est plus général. Les livres de Johnstone et Vicker (voir la partie références de l'article Wikipédia) sont tous les deux assez sympas, bien que le premier soit assez avancé.
Kaveh
1
Oui, mais je ne sais pas si l'OP voulait connaître Stone Duality dans toute sa splendeur. Ont ajouté quelques liens par votre commentaire. Si l'on veut juste le théorème de représentation, la présentation de Davey et Priestley suffit.
Vijay D
2
@Kaveh: apprécié. Je m'habitue toujours à identifier le niveau de détail souhaité d'une réponse et à lire le ton des commentaires. Non pas que ma voix de vieil homme grincheux aide. (smiley)
Vijay D
5
Ce serait un excellent point de départ pour un article de blog sur Stone Duality et les connexions à CS.
Suresh Venkat
3
L'introduction aux algèbres booléennes de Paul Halmos couvre également le théorème de représentation, ainsi que d'autres théorèmes de dualité.
MGwynne