решетка Поста

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

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

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

и если заданы m -арная функция f и n- арная функции g ₁ , ..., g _m , мы можем построить еще одну n -арную функцию

${\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{m}(x_{1},\dots ,x_{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. Кроме того, нам нужны пороговые функции

${\displaystyle \mathrm {th} _{k}^{n}(x_{1},\dots ,x_{n})={\begin{cases}1&{\text{если}}{\bigl |}\{i\mid x_{i}=1\}{\bigr |}\geq k,\\0&{\text{иначе.}}\end{cases}}}$

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

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

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

${\displaystyle (a_{1},\dots ,a_{n})\leq (b_{1},\dots ,b_{n})\если a_{i}\leq b_{i}{\text{ для }}i=1,\dots ,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 = [∧, ∨, 0, 1] — множество монотонных функций: f ( a ) ≤ f ( b ) для любого a ≤ b .
• D = [maj, ¬] — множество самодвойственных функций: ¬ f ( a ) = f (¬ a ) .
• A = [↔, 0] — множество аффинных функций: функции, удовлетворяющие

${\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)\\\Стрелка вправо &f(b_{1},\dots,c,b_{i+1},\dots)=f(b_{1},\dots,d,b_{i+1},\dots)\end{align}}}$

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

• U = [¬, 0] — это множество по существу унарных функций, т. е. функций, которые зависят не более чем от одной входной переменной: существует i = 1, ..., n такое, что f ( a ) = f ( b ) всякий раз, когда a _i = b _i .
• Λ = [∧, 0, 1] — множество конъюнктивных функций: 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 = [∨, 0, 1] — множество дизъюнктивных функций: 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, Т^к
  ₀= [й^к+2
  _к+1, ↛] — множество функций 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 ₀ = T¹
₀= [∨, +] — множество функций , сохраняющих 0 : f ( 0 ) = 0. Кроме того, ⊤ можно рассматривать как T⁰
₀если принять во внимание пустое место.

• Для любого k ≥ 1, Т^к
  ₁= [й^к+2
  _к+1, →] — это множество функций 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 ₁ = T¹
₁= [∧, →] состоит из 1-сохраняющих функций: f ( 1 ) = 1. Кроме того, ⊤ можно рассматривать как T⁰
₁если принять во внимание пустое соединение.

• Наибольший клон всех функций обозначается ⊤ = [∨, ¬], наименьший клон (содержащий только проекции) обозначается ⊥ = [], а P = P ₀ P ₁ = [ x  ? y  : z ] является клоном функций, сохраняющих константы .

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

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

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

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

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

Если рассматривать только клоны, которые должны содержать постоянные функции, то классификация становится намного проще: таких клонов всего 7: UM, Λ, V, U, A, M и ⊤. Хотя это можно вывести из полной классификации, есть и более простое доказательство, занимающее меньше страницы. ^[5]

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

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

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

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