В логике и универсальной алгебре , решетки Поста обозначает решетку всех клонов на множестве из двух элементов {0, 1}, упорядоченного по включению . Он назван в честь Эмиля Поста , который опубликовал полное описание решетки в 1941 году. [1] Относительная простота решетки Поста резко контрастирует с решеткой клонов на трехэлементном (или более крупном) наборе, который имеет мощность континуума и сложная внутренняя структура. Современное изложение результатов Поста можно найти в Lau (2006). [2]
Основные понятия
Функции булева , или логическая связка , является п - позиционной операции е : 2 п → 2 для некоторого п ≥ 1 , где 2 обозначает два набора элементов {0, 1}. Конкретные булевы функции - это проекции
и по m -арной функции f и n -арным функциям g 1 , ..., g m мы можем построить другую n -арную функцию
назвал их состав . Набор функций, замкнутый относительно композиции и содержащий все проекции, называется клоном .
Пусть B - набор связок. Функции , которые могут быть определены с помощью формулы , используя пропозициональные переменные и связки из B образуют клон [ B ], на самом деле это самый маленький клон , который включает в себя B . Мы называем [ B ] клон созданный с помощью B , и говорят , что B является основой из [ B ]. Например, [¬, ∧] - все булевы функции, а [0, 1, ∧, ∨] - монотонные функции.
Мы используем операции ¬, N p , ( отрицание ), ∧, K pq , ( конъюнкция или встреча ), ∨, A pq , ( дизъюнкция или соединение ), →, C pq , ( импликация ), ↔, E pq , ( бикондиционный ), +, J pq ( исключительная дизъюнкция или сложение булевых колец ), ↛, L pq , [3] ( неимпликация ),?: (тернарный условный оператор ) и константные унарные функции 0 и 1. пороговые функции
Например, th 1 n - это большая дизъюнкция всех переменных x i , а th n n - большая конъюнкция. Особое значение имеет функция большинства.
Обозначим элементы 2 n (т.е. присвоения истинности) векторами: a = ( a 1 , ..., a n ) . Множество 2 n содержит структуру логической алгебры естественного произведения . То есть упорядочивание, встречи, соединения и другие операции над 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 - набор аффинных функций: функции, удовлетворяющие
- для любых i ≤ n , a , b ∈ 2 n и 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.
- V - множество дизъюнктивных функций: f ( a ∨ b ) = f ( a ) ∨ f ( b ) . Эквивалентно V состоит из дизъюнкцийдля всех подмножеств I из {1, ..., n } (включая пустую дизъюнкцию 0) и константу 1.
- Для любого k ≥ 1 T 0 k - это множество функций f таких, что
- Более того, - множество функций, ограниченных сверху переменной: существует i = 1, ..., n такое, что f ( a ) ≤ a i для всех a .
- Как частный случай, P 0 = T 0 1 представляет собой набор функций, сохраняющих 0 : f ( 0 ) = 0 . Кроме того, ⊤ можно рассматривать как T 0 0, если принять во внимание пустую встречу.
- Для любого k ≥ 1 T 1 k - это множество функций f таких, что
- а также - множество функций, ограниченных снизу переменной: существует i = 1, ..., n такое, что f ( a ) ≥ a i для всех a .
- Частный случай P 1 = T 1 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 1 = P 0 , T 1 1 = P 1 , PT 0 1 = PT 1 1 = P , MT 0 1 = MP 0 , MT 1 1 = MP 1 , MPT 0 1 = MPT 1 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- формулы. Льюис [4] использовал описание решетки Поста, чтобы показать, что B -SAT является NP-полным, если функция ↛ может быть сгенерирована из B (т. Е. [ B ] ⊇ T 0 ∞ ), и во всех остальных случаях B -SAT является полиномиально разрешима.
Варианты
Изначально Post работал не с современным определением клонов, а с так называемыми итерационными системами , которые представляют собой наборы операций, закрытых при подстановке.
а также перестановка и идентификация переменных. Основное отличие состоит в том, что итерационные системы не обязательно содержат все прогнозы. Каждый клон - это итерационная система, и существует 20 непустых итерационных систем, которые не являются клонами. (Пост также исключил из классификации пустую итеративную систему, поэтому его диаграмма не имеет наименьшего элемента и не может быть решеткой.) В качестве другой альтернативы некоторые авторы работают с понятием замкнутого класса , который является итерационной системой, закрытой введением. фиктивных переменных. Есть четыре закрытых класса, которые не являются клонами: пустой набор, набор функций-констант 0, набор функций-констант 1 и набор всех функций-констант.
Сама по себе композиция не позволяет сгенерировать нулевую функцию из соответствующей унарной константной функции, это техническая причина, по которой нулевые функции исключены из клонов в классификации Поста. Если мы снимем ограничение, мы получим больше клонов. А именно, каждый клон С в решетке Почты , которая содержит , по меньшей мере , одна постоянной функцию соответствует два клонам под менее ограничительного определение: C , и C вместе со всеми нульарными функциями, Унарные версии находятся в C .
Рекомендации
- ^ EL Post, Двузначные итерационные системы математической логики , Annals of Mathematics Studies, no. 5, Princeton University Press, Princeton 1941, 122 стр.
- ^ Д. Лау, Функциональные алгебры на конечных множествах: Базовый курс многозначной логики и теории клонов , Springer, New York, 2006, 668 pp. ISBN 978-3-540-36022-3
- ^ Бохеньский (1959), перераб., Альберт Menne, ред. и пер., Отто Берд, Precis of Mathematical Logic , Нью-Йорк: Гордон и нарушение, часть II, «Логика предложений», разд. 3.23, "N p ", п. 3.32, «16 диадических функторов истинности», стр. 10-11.
- ^ HR Льюис , Проблемы выполнимости для исчислений высказываний , Математическая теория систем 13 (1979), стр. 45–53.