Решетка столба

Диаграмма Хассе решетки Поста.

В логике и универсальной алгебре, решетки Поста обозначает решетку всех клонов на множестве из двух элементов {0, 1}, упорядоченного по включению. Он назван в честь Эмиля Поста, который опубликовал полное описание решетки в 1941 году. Относительная простота решетки Поста резко контрастирует с решеткой клонов на трехэлементном (или большем) множестве, мощность которого равна континуум и сложная внутренняя структура. Современное изложение результатов Поста можно найти в Lau (2006).

Содержание

• 1 Базовые концепции
• 2 Именование клонов
• 3 Описание решетки
• 4 Приложения
• 5 Варианты
• 6 Ссылки

Базовые концепции

Функции булева, или логическая связка, является п - позиционной операции е: 2 ^п → 2 для некоторого п ≥ 1, где 2 обозначает два набора элементов {0, 1}. Конкретные булевы функции - это проекции

${\ displaystyle \ pi _ {k} ^ {n} (x_ {1}, \ dots, x_ {n}) = x_ {k},}$

и по m -арной функции f и n -арным функциям g 1,..., g m мы можем построить другую n -арную функцию

${\ displaystyle h (x_ {1}, \ dots, x_ {n}) = f (g_ {1} (x_ {1}, \ dots, x_ {n}), \ dots, g_ {m} (x_ { 1}, \ точки, x_ {n})),}$

назвал их состав. Набор функций, замкнутый относительно композиции и содержащий все проекции, называется клоном.

Пусть B - набор связок. Функции, которые могут быть определены с помощью формулы, используя пропозициональные переменные и связки из B образуют клон [ B ], на самом деле это самый маленький клон, который включает в себя B. Мы называем [ B ] клон созданный с помощью B, и говорят, что B является основой из [ B ]. Например, [¬, ∧] - все булевы функции, а [0, 1, ∧, ∨] - монотонные функции.

Мы используем операции ¬, N p, ( отрицание ), ∧, K pq, ( конъюнкция или встреча ), ∨, A pq, ( дизъюнкция или соединение ), →, C pq, ( импликация ), ↔, E pq, ( biconditional ), +, J pq ( исключительная дизъюнкция или сложение булевых колец ), ↛, L pq, ( неимпликация ),?: (тернарный условный оператор ) и константные унарные функции 0 и 1. Кроме того, нам нужны пороговые функции

${\ displaystyle \ mathrm {th} _ {k} ^ {n} (x_ {1}, \ dots, x_ {n}) = {\ begin {case} 1 amp; {\ text {if}} {\ bigl |} \ {i \ mid x_ {i} = 1 \} {\ bigr |} \ geq k, \\ 0 amp; {\ text {в противном случае.}} \ end {case}}}$

Например, th 1 ⁿ - это большая дизъюнкция всех переменных x i, а th n ⁿ - большая конъюнкция. Особое значение имеет функция большинства.

${\ displaystyle \ mathrm {maj} = \ mathrm {th} _ {2} ^ {3} = (x \ land y) \ lor (x \ land z) \ lor (y \ land z).}$

Обозначим элементы 2 ⁿ (т.е. назначения истинности) как векторы: a = ( a 1,..., a n). Множество 2 ⁿ содержит структуру булевой алгебры естественного произведения. То есть упорядочивание, встречи, соединения и другие операции с n -арными присвоениями истинности определяются точечно:

${\ displaystyle (a_ {1}, \ dots, a_ {n}) \ leq (b_ {1}, \ dots, b_ {n}) \ iff a_ {i} \ leq b_ {i} {\ text {для }} я = 1, \ точки, n,}$

${\ displaystyle (a_ {1}, \ dots, a_ {n}) \ land (b_ {1}, \ dots, b_ {n}) = (a_ {1} \ land b_ {1}, \ dots, a_ {n} \ land b_ {n}).}$

Именование клонов

Пересечение произвольного количества клонов снова является клоном. Пересечение клонов удобно обозначать простым сопоставлением, т. Е. Клон C 1 ∩ C 2 ∩... ∩ C k обозначается через C 1 C 2... C k. Некоторые специальные клоны представлены ниже:

• M - множество монотонных функций: f ( a) ≤ f ( b) для любого a ≤ b.
• D - это множество самодвойственных функций: ¬ f ( a) = f (¬ a).
• A - множество аффинных функций: функции, удовлетворяющие

${\ displaystyle {\ begin {align} amp; f (a_ {1}, \ dots, a_ {i-1}, c, a_ {i + 1}, \ dots, a_ {n}) = f (a_ {1}, \ точки, d, a_ {i + 1}, \ dots) \\\ Rightarrow amp; f (b_ {1}, \ dots, c, b_ {i + 1}, \ dots) = f (b_ {1}, \ dots, d, b_ {i + 1}, \ dots) \ end {выровнены}}}$

для любых i ≤ n, a, b ∈ 2 ⁿ и c, d ∈ 2. Эквивалентно, функции, выражаемые как f ( x 1,..., x n) = a 0 + a 1 x 1 +... + a n x n для некоторых a 0, a.

• U - это набор существенно унарных функций, то есть функций, которые зависят не более чем от одной входной переменной: существует i = 1,..., n такое, что f ( a) = f ( b) всякий раз, когда a i = b i.
• Λ - это множество конъюнктивных функций: f ( a ∧ b) = f ( a) ∧ f ( b). Клон Λ состоит из конъюнкций для всех подмножеств I из {1,..., n } (включая пустую конъюнкцию, т. Е. Константу 1) и константы 0.${\ displaystyle f (x_ {1}, \ dots, x_ {n}) = \ bigwedge _ {i \ in I} x_ {i}}$
• V - множество дизъюнктивных функций: f ( a ∨ b) = f ( a) ∨ f ( b). Эквивалентно V состоит из дизъюнкций для всех подмножеств I из {1,..., n } (включая пустую дизъюнкцию 0) и константы 1.${\ displaystyle f (x_ {1}, \ dots, x_ {n}) = \ bigvee _ {i \ in I} x_ {i}}$
• Для любого k ≥ 1 T 0 ^k - это множество функций f таких, что

${\ displaystyle \ mathbf {a} ^ {1} \ land \ cdots \ land \ mathbf {a} ^ {k} = \ mathbf {0} \ \ Rightarrow \ f (\ mathbf {a} ^ {1}) \ земля \ cdots \ land f (\ mathbf {a} ^ {k}) = 0.}$

Кроме того, есть набор функций, ограниченный сверху переменной: существует i = 1,..., n такое, что f ( a) ≤ a i для всех a.${\ Displaystyle \ mathrm {T} _ {0} ^ {\ infty} = \ bigcap _ {k = 1} ^ {\ infty} \ mathrm {T} _ {0} ^ {k}}$

Как частный случай, P 0 = T 0 ¹ - это набор функций, сохраняющих 0: f ( 0) = 0. Кроме того, ⊤ можно рассматривать как T 0 ^0, если принять во внимание пустую встречу.

• Для любого k ≥ 1 T 1 ^k - это множество функций f таких, что

${\ Displaystyle \ mathbf {a} ^ {1} \ lor \ cdots \ lor \ mathbf {a} ^ {k} = \ mathbf {1} \ \ Rightarrow \ f (\ mathbf {a} ^ {1}) \ lor \ cdots \ lor f (\ mathbf {a} ^ {k}) = 1,}$

и - множество функций, ограниченных снизу переменной: существует i = 1,..., n такое, что f ( a) ≥ a i для всех a.${\ Displaystyle \ mathrm {T} _ {1} ^ {\ infty} = \ bigcap _ {k = 1} ^ {\ infty} \ mathrm {T} _ {1} ^ {k}}$

Частный случай P 1 = T 1 ¹ состоит из функций, сохраняющих 1: f ( 1) = 1. Кроме того, ⊤ можно рассматривать как T 1 ^0, если принять во внимание пустое соединение.

• Самый большой клон всех функций обозначается ⊤, наименьший клон (который содержит только проекции) обозначается ⊥, а P = P 0 P 1 является клоном функций, сохраняющих константу.

Описание решетки

Набор всех клонов является замкнутой системой, следовательно, он образует полную решетку. Решетка счетно бесконечна, и все ее элементы конечно порождены. Все клоны перечислены в таблице ниже.

Диаграмма Хассе решетки Поста Центральная часть решетки

клон	одна из его баз
⊤	∨, ¬
P 0	∨, +
П 1	∧, →
п	х  ? у  : г
Т 0 к, к ≥ 2	th k k +1, ↛
Т 0 ∞	↛
PT 0 k, k ≥ 2	th k k +1, x ∧ ( y → z)
PT 0 ∞	х ∧ ( у → г)
Т 1 к, к ≥ 2	th 2 k +1, →
Т 1 ∞	→
PT 1 k, k ≥ 2	th 2 k +1, x ∨ ( y + z)
ПТ 1 ∞	х ∨ ( у + г)
M	∧, ∨, 0, 1
MP 0	∧, ∨, 0
MP 1	∧, ∨, 1
Депутат	∧, ∨
MT 0 k, k ≥ 2	th k k +1, 0
MT 0 ∞	х ∧ ( у ∨ г), 0
MPT 0 k, k ≥ 2	th k k +1 для k ≥ 3, maj, x ∧ ( y ∨ z) для k = 2
MPT 0 ∞	х ∧ ( у ∨ г)
MT 1 k, k ≥ 2	th 2 k +1, 1
MT 1 ∞	х ∨ ( у ∧ г), 1
MPT 1 k, k ≥ 2	th 2 k +1 для k ≥ 3, maj, x ∨ ( y ∧ z) для k = 2
MPT 1 ∞	х ∨ ( у ∧ г)
Λ	∧, 0, 1
ΛP 0	∧, 0
ΛP 1	∧, 1
ΛP	∧
V	∨, 0, 1
ВП 0	∨, 0
ВП 1	∨, 1
Вице-президент	∨
D	май, ¬
DP	maj, x + y + z
DM	майор
А	↔, 0
ОБЪЯВЛЕНИЕ	¬, х + у + г
AP 0	+
AP 1	↔
AP	х + у + г
U	¬, 0
UD	¬
UM	0, 1
Вверх 0	0
ВВЕРХ 1	1
⊥

Восемь бесконечных семейств на самом деле также имеют элементы с k = 1, но они появляются отдельно в таблице: T 0 ¹ = P 0, T 1 ¹ = P 1, PT 0 ¹ = PT 1 ¹ = P, MT 0 ¹ = MP 0, MT 1 ¹ = MP 1, MPT 0 ¹ = MPT 1 ¹ = MP.

Решетка имеет естественную симметрию, отображающую каждый клон C в его двойственный клон C ^d = { f ^d | f ∈ C }, где f ^d ( x 1,..., x n) = ¬ f (¬ x 1,..., ¬ x n) - двойственный де Моргану булевой функции f. Так, например, Л ^г = V, (T 0 ^K) ^D = Т 1 ^к и М ^д = M.

Приложения

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

• Осмотр решетки показывает, что максимальные клоны, отличные от ⊤ (часто называемые классами Поста), - это M, D, A, P 0, P 1, и каждый собственный подклон содержится в одном из них. Поскольку набор связок B является функционально полным тогда и только тогда, когда он порождает, мы получаем следующую характеристику: B является функционально полным, если и только если оно не входит ни в один из пяти классов Поста.
• Проблема выполнимости булевых формул NP-полна по теореме Кука. Рассмотрим ограниченную версию проблемы: для фиксированного конечного множества B связок пусть B -SAT будет алгоритмической проблемой проверки выполнимости данной B -формулы. Льюис использовал описание решетки Поста, чтобы показать, что B -SAT является NP-полным, если функция ↛ может быть сгенерирована из B (т. Е. [ B ] 0 T 0 ^∞), а во всех других случаях B -SAT полиномиально- время разрешимо.

Варианты

Изначально Пост работал не с современным определением клонов, а с так называемыми итерационными системами, которые представляют собой наборы операций, закрытых при подстановке.

${\ displaystyle h (x_ {1}, \ dots, x_ {n + m-1}) = f (x_ {1}, \ dots, x_ {n-1}, g (x_ {n}, \ dots, х_ {п + м-1})),}$

а также перестановка и идентификация переменных. Основное отличие состоит в том, что итерационные системы не обязательно содержат все прогнозы. Каждый клон - это итерационная система, и существует 20 непустых итерационных систем, которые не являются клонами. (Пост также исключил из классификации пустую итеративную систему, поэтому его диаграмма не имеет наименьшего элемента и не может быть решеткой.) В качестве другой альтернативы некоторые авторы работают с понятием замкнутого класса, который представляет собой итеративную систему, закрытую введением. фиктивных переменных. Есть четыре закрытых класса, которые не являются клонами: пустой набор, набор константных функций 0, набор константных функций 1 и набор всех константных функций.

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

Ссылки

1. ^ EL Post, Двузначные итерационные системы математической логики, Annals of Mathematics Studies, no. 5, Princeton University Press, Princeton 1941, 122 стр.
2. ^ Д. Лау, Функциональные алгебры на конечных множествах: Базовый курс многозначной логики и теории клонов, Springer, New York, 2006, 668 pp. ISBN   978-3-540-36022-3
3. ↑ Юзеф Мария Боченски (1959), ред. Альберта Менне, изд. и пер., Отто Берд, Precis of Mathematical Logic, Нью-Йорк: Гордон и нарушение, часть II, «Логика предложений», разд. 3.23, "N p ", п. 3.32, «16 диадических функторов истинности», стр. 10-11.
4. ^ HR Льюис, Проблемы выполнимости для исчислений высказываний, Математическая теория систем 13 (1979), стр. 45–53.