Проблема удовлетворенности является, конечно, фундаментальной проблемой в теоретической CS. Я играл с одной версией проблемы с бесконечным количеством переменных.
Базовая настройка. Пусть непустое и, возможно, бесконечное множество переменных . Литерал - это либо переменная либо ее отрицание . Предложение - это дизъюнкция конечного числа литералов . Наконец, мы определяем формулу как набор предложений .¬ x c
Назначение - это функция . Я не буду явно определять условие, когда присваивание удовлетворяет предложению; это немного громоздко, и то же самое, что и в стандартном SAT. Наконец, присваивание удовлетворяет формуле, если оно удовлетворяет каждому составляющему предложению. Пусть будет множеством удовлетворяющих присваиваний для , и пусть будет дополнением к .σ : X → { 0 , 1 } σ s a t ( F ) F u n s a t ( F ) s a t ( F )
Топологическое пространство.
Наша цель - наделить пространство всех присваиваний , назовем это , топологической структурой . Наши замкнутые множества имеют вид где - формула. Мы можем проверить, что это действительно топология:ΣF
- Пустая формула содержащая предложений, удовлетворяется всеми присваиваниями; поэтому закрыта.Е
- Формула для любого является противоречием. Так что закрыто.x ∈ X ∅
- Замыкание при произвольном пересечении. Пусть формула для каждого . Тогда . i ∈ I s a t ( ⋃ i ∈ I F i ) = ⋂ i ∈ I s a t ( F i )
- Закрытие при конечном объединении. Предположим, что и - две формулы и определяют
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 ∨ ds a t ( F ∨ G ) = s a t ( F ) ∪ s a t ( G )
Назовите эту топологию "топологией выполнимости" (!) На . Конечно, множества этой топологии имеют вид . Кроме того, я заметил , что совокупность открытых множеств образует базис . (Упражнение!) Σ u n s a t ( F ) { u n s a t ( c )T
Компактный? Я чувствую, что это интересный, хотя и не очень полезный способ взглянуть на вещи. Я хочу понять, обладает ли это топологическое пространство традиционными интересными свойствами, такими как компактность, связность и т. Д. В этом посте мы ограничимся компактностью:
Пусть счетно бесконечный набор переменных. 1 Является ли компактным в ?Σ T
Можно доказать следующее
Предложение. компактно тогда и только для всех невыполнимых формул , существует конечная невыполнимая подформулу . F { c 1 , c 2 , … , c m } ⊆ F
(Не очень сложное упражнение!) После нескольких дней размышлений у меня не было большого прогресса в ответе на этот вопрос. У меня также нет убедительных доказательств за или против компактности. Можете ли вы предложить какой-то подход?
Напоследок в качестве бонусного вопроса:
Была ли такая структура изучена ранее?
1 Ограничение счетного только для простоты; это также похоже на следующий естественный шаг из конечного числа переменных.
Ответы:
То, что вы делаете, это получение топологического представления булевой алгебры. Изучение представлений булевых алгебр восходит, по крайней мере, к Линденбауму и Тарскому, которые доказали (я думаю, что в 1925 г.), что полные атомные булевы алгебры изоморфны решеткам powerset.
Было несколько результатов, которые расширяют и обобщают представление Стоуна в различных направлениях. Естественный вопрос - спросить, есть ли у других семейств решеток такие представления. Результаты Стоуна также применимы к распределительным решеткам. Топологические представления для произвольных решеток были даны Alasdair Urquhart в 1978 году. Распределительные решетки обладают большим разнообразием по структуре по сравнению с булевыми алгебрами и представляют большой интерес. Иное представление для распределительного случая было дано Хилари Пристли в 1970 году, используя идею упорядоченного топологического пространства . Вместо представлений на основе множеств мы можем найти представления и топологии на основе множеств.
Конструкции в этих работах обладают одним замечательным свойством. Построение Стоуна отображает не только булевы алгебры в топологические пространства: структурные отношения, относящиеся к булевым алгебрам, преобразуются в структурные свойства между полученными топологиями. Это двойственность между категориями. Вся гамма таких результатов называется каменной двойственностью . Неформально двойственности дают нам точные переводы между математическими вселенными: комбинаторный мир множеств, алгебраический мир решеток, пространственный мир топологии и дедуктивный мир логики. Вот несколько отправных точек, которые могут помочь.
источник