2.1. Множества и операции над ними. Булевы функции, КНФ, ДНФ. Базисы, теорема Поста.
Множества — это объекты, которые рассматриваются в контексте двуместного отношения принадлежности. Запись «a  A» является высказыванием (истинным или ложным) и означает «a принадлежит A». Свойства отношения  устанавливаются аксиоматикой теории множеств. На основе отношения  можно строить другие конструкции.

Пример 1. «x: x  A  x  B» = «A  B» — «A содержится в B».

При рассмотрении операций над множествами часто предполагают, что фиксирован некий универсум U, содержащий любое из множеств, с которыми имеют дело.

Функция f :{0;1}ⁿ→{0;1} называется n-местной булевой. Класс всех таких функций обозначим через B. Элементы множества {0;1} называют пропозициональными переменными.

Пусть x₁, …, x_n — пропозициональные переменные. Сопоставим каждой переменной x_i высказывание «x  X_i ». Тогда про каждую булеву функцию f над переменными x₁, …, x_n можно сказать, что она задаёт операцию над множествами X₁, …, X_n. Результатом этой операции считается такое множество Y, что x  Y ↔ f (x  X₁, …, x  X_n).

Пример 2. Конъюнкция y = x₁  x₂ задаёт операцию пересечения множеств ∩ высказыванием вида x  Y ↔ x  X₁  x  X₂.

Пример 3. Функция вида f (x₁, x₂) = x₁  x₂ задаёт операцию вычитания множеств \.

Тавтология соответствует универсуму U, а противоречие — пустому множеству.

Def 1. Литерал — это формула вида x или вида x, где x — пропозициональная переменная.

Def 2. Конъюнктивная нормальная форма функции — это формула, задающая эту функцию в виде конъюнкции нескольких дизъюнкций литералов, причём операнды в дизъюнкциях и конъюнкции не повторяются. Дизъюнктивная нормальная форма функции — это формула, задающая эту функцию в виде дизъюнкции нескольких конъюнкций литералов, причём операнды в конъюнкциях и дизъюнкции не повторяются.

Def 3. Стандартная КНФ n-местной функции — это такая её КНФ, в которой каждая дизъюнкция содержит n литералов. Стандартная ДНФ n-местной функции — это такая её ДНФ, в которой каждая конъюнкция содержит n литералов.
Каждая булева функция единственным образом (с точностью до порядка операндов) представляется в виде СКНФ и в виде СДНФ. Построение выполняется по таблице истинности. Для СДНФ конъюнкции соответствуют выполняющим наборам, и в каждой конъюнкции отрицания стоят у тех переменных, которые являются ложными в наборе, которому эта конъюнкция сопоставлена. Для СКНФ наоборот: дизъюнкции соответствуют невыполняющим наборам, и в каждой из них отрицания стоят у тех переменных, которые являются истинными в наборе. ДНФ и КНФ являются двойственными друг другу относительно операции отрицания.
Def 4. Пусть P  B — некоторый класс булевых функций. Класс Q, состоящий из всех суперпозиций функций класса P, называют замыканием P и обозначают так: Q = [P]. При этом говорят, что P порождает Q. Класс называется (функционально) замкнутым или классом Поста, если он совпадает со своим замыканием. Класс P называют полным в Q, если любую функцию из Q можно выразить через суперпозиции функций из P.

Пример 4. [, , ] = B.

Def 5. Класс булевых функций P называется независимым, если ни одна функция f из класса P не содержится в [P \ {f }], т. е. не выражается через суперпозиции всех остальных. Полный независимый класс называется базисом.

Пример 5. Все эти классы: {, }, {, }, {→, }, {→, 0}, { | }, {↑}, {, +, 1}, {, +, 1} — являются базисами для класса B.

Комментарий. « | » — штрих Шеффера (a | b = (a  b)), «↑» — стрелка Пирса (a ↑ b = (a  b)).

«+» — это xor, «→» — импликация. Малая теорема Поста рассмотрит пять важнейших замкнутых классов. В ней высказывание «класс полон» будет подразумевать, что он полон в B.

Большая теорема Поста. Каждый замкнутый класс имеет конечный базис.

Доказательство теоремы состоит в том, чтобы перечислить все существующие замкнутые классы (их около 50, включая несколько бесконечных регулярных семейств), предъявить конечный базис для каждого из них и доказать, что никаких других замкнутых классов не существует.

Def 6. Замкнутый класс P называется предполным (максимальным), если P  B и P не содержится ни в каком другом замкнутом классе, отличном от B.

B₀ — класс функций, удовлетворяющих условию f (0, 0, …, 0) = 0 (сохраняющих нуль).

B₁ — класс функций, удовлетворяющих условию f (1, 1, …, 1) = 1 (сохраняющих единицу).

L — класс всех линейных функций, т. е. функций вида x₁ + … + x_n + a, где a  {0;1}.

S — класс всех самодвойственных функций, т. е. таких, что f (x₁, …, x_n) = f (x₁, …, x_n).

M — класс всех монотонных функций: x₁ ≤ y₁, …, x_n ≤ y_n  f (x₁, …, x_n) ≤ f (y₁, …, y_n).

Классы B₀, B₁, L, S, M являются замкнутыми. Это проверяется непосредственно из определений.

Малая теорема Поста. Классы B₀, B₁, L, S, M являются предполными, и никаких других предполных классов не существует. Набор булевых функций является полным тогда и только тогда, когда он не содержится целиком ни в одном из этих пяти предполных классов.

Доказательство. Пусть f (x₁, …, x_n)  B₁. Тогда f (1, …, 1) = 0 и →  B₁, а [0, →] = B (см. пример 5), т. е. B₁ — предполный класс. Далее, пусть f (x₁, …, x_n)  B₀. Тогда f (0, …, 0) = 1 и +,   B₀, а [1, +, ] = B (см. там же), т. е. B₀ — предполный. Предполнота классов L, S, M будет показана ниже.

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

У нас есть функция, не сохраняющая нуль. Подставим вместо всех аргументов одну и ту же переменную. Получится функция одного аргумента, отображающая нуль в единицу, то есть либо константа 1, либо отрицание. Сделав то же самое с функцией, не сохраняющей единицу, получим либо константу нуль, либо отрицание. Таким образом, у нас либо есть отрицание, либо обе константы 0 и 1.

Если есть обе константы, то всё равно можно получить отрицание. Возьмём немонотонную функцию. Легко понять, что она должна менять значение с единицы на нуль при изменении какого-то одного аргумента с нуля на единицу (в самом деле, будем увеличивать аргументы по одному, в какой-то момент значение функции уменьшится). Зафиксировав значения остальных аргументов (ведь мы считаем, что константы есть), получаем отрицание. Попутно заметим: мы смогли получить отрицание из произвольной немонотонной функции и констант 0, 1  М. Заметим также, что ,   М. Это означает (см. пример 4), что M — предполный класс.

Имея отрицание и несамодвойственную функцию, легко получить константы (если их не было). В самом деле, несамодвойственность означает, что f (x₁, …, x_n) = f (x₁, …, x_n) для каких-то значений x₁, …, x_n  {0;1}. Вместо нулевых значений переменных x₁, …, x_n подставим p, вместо единиц подставим p, легко видеть, что получается одна из констант. Вторая получается отрицанием. Т. е. константы можно получить из произвольной несамодвойственной функции и функции   S. Попутно заметим: функция h(x, y, z) = x y + x z + y z также принадлежит S. Тогда h (x, y, 1) = x  y. Ввиду того, что [, ] = B (пример 5), класс S является предполным.

Теперь у нас есть константы, отрицание и нелинейная функция f (x₁, …, x_n). Нелинейность означает, что в её представлении в виде многочлена (полинома Жегалкина, см. пример 5 в конце) есть моном, состоящий более чем из одной переменной. Пусть, например, этот моном содержит переменные x₁ и x₂. Сгруппируем члены по четырём группам и получим выражение: x₁ x₂ A (x₃, …, x_n) + x₁ B (x₃, …, x_n) + x₂ C (x₃, …, x_n) + D (x₃, …, x_n). Здесь A(x₃, …, x_n) не является константой 0. Фиксируем x₃, …, x_n так, чтобы A(x₃, …, x_n) = 1. Тогда g (x₁, x₂) =

= f (x₁, x₂, x₃, …, x_n) = x₁ x₂ + a x₁ + b x₂ + c для некоторых a, b, c. Тогда g(x₁ + b, x₂ + a) + a b + c = x₁  x₂. Итак, [, ] = B, и вторая часть теоремы доказана. Попутно заметим: мы получили  по   L и произвольной нелинейной функции, т. е. класс L предполон.

Если некоторый класс, отличный от B₀, B₁, L, S, M, содержится в одном из этих классов, то он не предполон (по определению), а если не содержится ни в одном из них, то он полон (по только что доказанному), следовательно, опять же, не предполон. Значит, других предполных классов (кроме B₀, B₁, L, S, M) нет, ч.т.д.

Следствие. Всякий базис для B содержит не более четырёх функций.

Доказательство. Из любого полного набора для B можно оставить не более пяти функций: f₁B₀, f₂B₁, f₃L, f₄S, f₅M. Если f₁(x, …, x) = 1, то f₁S, и можно выбросить f₁ или f₄. Если f₂(x, …, x) = 0, то f₂S, и можно выбросить f₂ или f₄. Если f₁(x, …, x) = f₂ (x, …, x) = x, то можно выбросить f₁ или f₂.