Решетка сообщений - Википедия - Posts lattice

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

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

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

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

и учитывая м-арная функция ж, и п-арные функции грамм₁, ..., грамм_м, мы можем построить еще один п-арная функция

{ 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п, (отрицание ), ∧, Kpq, (соединение или же встретить ), ∨, Apq, (дизъюнкция или же присоединиться ), →, Cpq, (значение ), ↔, Epq, (двухусловный ), +, Jpq (исключительная дизъюнкция или же Логическое кольцо добавление ), ↛, Lpq,^[3] (неимпликация ),?: (троичный условный оператор ) и постоянные унарные функции 0 и 1. Кроме того, нам потребуются пороговые функции

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

Например, th₁^п - большая дизъюнкция всех переменных Икс_я, и th_п^п это большое соединение. Особое значение имеет функция большинства

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

Обозначим элементы 2^п (т.е. присвоения истинности) как векторы: а = (а₁, ..., а_п). Набор 2^п несет естественный товар Булева алгебра структура. То есть упорядочивание, встреча, присоединение и другие операции на п-арные присвоения истинности определяются точечно:

{ 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₁ ∩ C₂ ∩ ... ∩ C_k обозначается C₁C₂...C_k. Некоторые специальные клоны представлены ниже:

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

{ displaystyle { begin {align} & f (a_ {1}, dots, a_ {i-1}, c, a_ {i + 1}, dots, a_ {n}) = f (a_ {1} , dots, d, a_ {i + 1}, dots) Rightarrow & f (b_ {1}, dots, c, b_ {i + 1}, dots) = f (b_ {1}, dots, d, b_ {i + 1}, dots) end {выровнены}}}

для каждого я ≤ п, а, б ∈ 2^п, и c, d ∈ 2. Эквивалентно функции, выражаемые как ж(Икс₁, ..., Икс_п) = а₀ + а₁Икс₁ + ... + а_пИкс_п для некоторых а₀, а.

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

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

Более того,

{ Displaystyle mathrm {T} _ {0} ^ { infty} = bigcap _ {k = 1} ^ { infty} mathrm {T} _ {0} ^ {k}}

- множество функций, ограниченных сверху переменной: существует я = 1, ..., п такой, что ж(а) ≤ а_я для всех а.

В частном случае п₀ = Т₀¹ это набор 0-сохранение функции: ж(0) = 0. Кроме того, ⊤ можно считать Т₀⁰ если принять во внимание пустую встречу.

Для любого k ≥ 1, Т₁^k это набор функций ж такой, что

{ 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,}

и

{ Displaystyle mathrm {T} _ {1} ^ { infty} = bigcap _ {k = 1} ^ { infty} mathrm {T} _ {1} ^ {k}}

- множество функций, ограниченное снизу переменной: существует я = 1, ..., п такой, что ж(а) ≥ а_я для всех а.

Особый случай п₁ = Т₁¹ состоит из 1-консервирующий функции: ж(1) = 1. Кроме того, ⊤ можно считать Т₁⁰ если принять во внимание пустое соединение.

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

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

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

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

Центральная часть решетки

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

Восемь бесконечных семейств на самом деле также имеют членов с k = 1, но они появляются отдельно в таблице: Т₀¹ = P₀, Т₁¹ = P₁, PT₀¹ = PT₁¹ = P, MT₀¹ = МП₀, MT₁¹ = МП₁, MPT₀¹ = MPT₁¹ = МП.

Решетка имеет естественную симметрию, отображающую каждый клон C к своему двойному клону C^d = {ж^d | ж ∈ C}, куда ж^d(Икс₁, ..., Икс_п) = ¬ж(¬Икс₁, ..., ¬Икс_п) это де Морган двойственный булевой функции ж. Например, Λ^d = V, (Т₀^k)^d = T₁^k, и M^d = M.

Приложения

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

Осмотр решетки показывает, что максимальные клоны, отличные от (часто называемые Классы поста) суть M, D, A, P₀, П₁, и каждый собственный подклон содержится в одном из них. Как набор B связок это функционально полный тогда и только тогда, когда он порождает, мы получаем следующую характеристику: B является функционально полным, если и только если он не входит ни в один из пяти классов Post.
В проблема выполнимости для булевых формул НП-полный к Теорема Кука. Рассмотрим ограниченный вариант задачи: для фиксированного конечного множества B связок, пусть B-SAT - алгоритмическая проблема проверки того, B-формула выполнима. Льюис^[4] использовал описание решетки Поста, чтобы показать, что B-SAT является NP-полным, если функция ↛ может быть сгенерирована из B (т.е. [B] ⊇ T₀^∞), а во всех остальных случаях 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 вместе со всеми нулевыми функциями, унарные версии которых находятся в C.