Топологическое пространство, связанное с SAT: оно компактно?

18

Проблема удовлетворенности является, конечно, фундаментальной проблемой в теоретической CS. Я играл с одной версией проблемы с бесконечным количеством переменных.

Базовая настройка. Пусть непустое и, возможно, бесконечное множество переменных . Литерал - это либо переменная либо ее отрицание . Предложение - это дизъюнкция конечного числа литералов . Наконец, мы определяем формулу как набор предложений .Икс¬ x cИксИкс¬ИкссF

Назначение - это функция . Я не буду явно определять условие, когда присваивание удовлетворяет предложению; это немного громоздко, и то же самое, что и в стандартном SAT. Наконец, присваивание удовлетворяет формуле, если оно удовлетворяет каждому составляющему предложению. Пусть будет множеством удовлетворяющих присваиваний для , и пусть будет дополнением к .σ : X { 0 , 1 } σ s a t ( F ) F u n s a t ( F ) s a t ( F )Иксσ:Икс{0,1}σsaT(F)FUNsaT(F)saT(F)

Топологическое пространство.

Наша цель - наделить пространство всех присваиваний , назовем это , топологической структурой . Наши замкнутые множества имеют вид где - формула. Мы можем проверить, что это действительно топология:ΣИксΣFsaT(F)F

  • Пустая формула содержащая предложений, удовлетворяется всеми присваиваниями; поэтому закрыта.ЕΣ
  • Формула для любого является противоречием. Так что закрыто.x X {Икс,¬Икс}ИксИкс
  • Замыкание при произвольном пересечении. Пусть формула для каждого . Тогда . i I s a t ( i I F i ) = i I s a t ( F i )FяяяsaT(яяFя)знак равнояяsaT(Fя)
  • Закрытие при конечном объединении. Предположим, что и - две формулы и определяют F \ vee G: = \ {c \ vee d \,: \, c \ in F, d \ in G \}. Тогда \ sat (F \ vee G) = \ sat (F) \ cup \ sat (G). Это требует аргументации, но я пропущу это.G F G : = { c dFграммs a t ( F G ) = s a t ( F ) s a t ( G )
    Fграммзнак равно{сd:сF,dграмм},
    saT(Fграмм)знак равноsaT(F)saT(грамм)

Назовите эту топологию "топологией выполнимости" (!) На . Конечно, множества этой топологии имеют вид . Кроме того, я заметил , что совокупность открытых множеств образует базис . (Упражнение!) Σ u n s a t ( F ) { u n s a t ( c )TΣUNsaT(F)T

{UNsaT(с):с это пункт}
T

Компактный? Я чувствую, что это интересный, хотя и не очень полезный способ взглянуть на вещи. Я хочу понять, обладает ли это топологическое пространство традиционными интересными свойствами, такими как компактность, связность и т. Д. В этом посте мы ограничимся компактностью:

Пусть счетно бесконечный набор переменных. 1 Является ли компактным в ?Σ TИксΣT

Можно доказать следующее

Предложение. компактно тогда и только для всех невыполнимых формул , существует конечная невыполнимая подформулу . F { c 1 , c 2 , , c m } FTF{с1,с2,...,см}F

(Не очень сложное упражнение!) После нескольких дней размышлений у меня не было большого прогресса в ответе на этот вопрос. У меня также нет убедительных доказательств за или против компактности. Можете ли вы предложить какой-то подход?

Напоследок в качестве бонусного вопроса:

Была ли такая структура изучена ранее?

1 Ограничение счетного только для простоты; это также похоже на следующий естественный шаг из конечного числа переменных.Икс

Шриватсан Нараянан
источник
(1.) Судя по вики-сводке тега топологии , этот тег здесь не так важен. Тем не менее, я включил его, так как вопрос явно связан с топологией множества точек. (2.) Я не был уверен, подходит ли этот вопрос для Math.SE или здесь; Я решил опубликовать это здесь. (3.) Извините за длину вопроса. Так как я предполагаю, что не все будут знакомы с топологическим пространством, я объяснил это более детально.
Шриватсан Нараянан
2
Я отправил запрос на улучшение тега, чтобы расширить определение тега топологии.
Джошуа Герман
1
Небольшое замечание: учитывая формулу F (которая находится в форме CNF), можно преобразовать ее в форму DNF, отрицать ее и использовать Де Морган для создания формулы F 'в форме CNF, такой что sat (F) = unsat (F') и несат (F) = сб (F '). Таким образом, любой набор закрыт, если он открыт в вашей топологии.
Алекс тен Бринк
Разве ваше предложение не является частным случаем теоремы компактности ( en.wikipedia.org/wiki/Compactness_theorem ) для логики высказываний?
Трэвис Сервис
@ Travis Может быть, я не уверен. Мои знания в области логики весьма недостаточны, поэтому я не могу видеть эти вещи очень четко. :)
Шриватсан Нараянан

Ответы:

22

То, что вы делаете, это получение топологического представления булевой алгебры. Изучение представлений булевых алгебр восходит, по крайней мере, к Линденбауму и Тарскому, которые доказали (я думаю, что в 1925 г.), что полные атомные булевы алгебры изоморфны решеткам powerset.

Икс1,Икс1Икс2,...

Теорема Стоуна о представлении булевых алгебр Каждая булева алгебра изоморфна решетке замкнутых подмножеств топологического пространства.

TрUе

Пространство Стоуна булевой алгебры является компактным, полностью несвязным хаусдорфовым пространством.

Было несколько результатов, которые расширяют и обобщают представление Стоуна в различных направлениях. Естественный вопрос - спросить, есть ли у других семейств решеток такие представления. Результаты Стоуна также применимы к распределительным решеткам. Топологические представления для произвольных решеток были даны Alasdair Urquhart в 1978 году. Распределительные решетки обладают большим разнообразием по структуре по сравнению с булевыми алгебрами и представляют большой интерес. Иное представление для распределительного случая было дано Хилари Пристли в 1970 году, используя идею упорядоченного топологического пространства . Вместо представлений на основе множеств мы можем найти представления и топологии на основе множеств.

Конструкции в этих работах обладают одним замечательным свойством. Построение Стоуна отображает не только булевы алгебры в топологические пространства: структурные отношения, относящиеся к булевым алгебрам, преобразуются в структурные свойства между полученными топологиями. Это двойственность между категориями. Вся гамма таких результатов называется каменной двойственностью . Неформально двойственности дают нам точные переводы между математическими вселенными: комбинаторный мир множеств, алгебраический мир решеток, пространственный мир топологии и дедуктивный мир логики. Вот несколько отправных точек, которые могут помочь.

  1. Глава 11 « Введение в решетки и порядок » Дэйви и Пристли охватывает теорему Стоуна.
  2. Слайды Мэтью Гвинна охватывают теорему и дают доказательство компактности. Мэтью (в комментариях) также предлагает введение в булевы алгебры Пола Халмоса.
  3. При переходе от логики высказываний к модальной логике булева алгебра расширяется с помощью оператора, сохраняющего соединение, и топологии с внутренностью. Работа Йонсона и Тарского 1952 года « Булевы алгебры с операторами» чрезвычайно удобна для чтения и согласуется с современными обозначениями.
  4. Глава 5 « Модальной логики » Блэкберна, де Рийке и Венемы охватывает теорему Стоуна и ее расширение на булевы алгебры с операторами.
  5. Stone Spaces Питера Джонстона рассматривает такие результаты для различных других видов алгебр.
Виджай Д
источник
4
Каменная двойственность носит более общий характер. Книги Джонстона и Викера (см. Справочную часть статьи Википедии) довольно хороши, хотя первая довольно продвинутая.
Каве
1
Да, но я не уверен, что ОП хотел знать о Каменной Двойственности во всей ее красе. Добавили несколько ссылок на ваш комментарий. Если кто-то просто хочет теорему о представлении, достаточно представления Дэйви и Пристли.
Виджай Д
2
@Kaveh: ценится. Я все еще привыкаю к ​​определению желаемого уровня детализации ответа и читаю тон комментариев. Не то чтобы мое звучание как сварливый старик помогает. (смайлик)
Виджай Д
5
Это было бы отличной отправной точкой для сообщения в блоге о Каменной Двойственности и связей с CS.
Суреш Венкат
3
«Введение в булевы алгебры» Пола Халмоса также охватывает теорему о представлении и другие теоремы двойственности.
MGwynne