Определение булевой функции

Основные сведения

Определение и арность

Булева функция от n переменных — отображение Bⁿ → B, где B = {0, 1}. Элементы 1 и 0 обычно интерпретируют как «истинно» и «ложно», хотя формально это просто символы. Элементы декартова произведения Bⁿ называют булевыми векторами. Арность функции — количество её аргументов.

Функция арности n полностью задаётся значениями на всех 2ⁿ булевых векторах, поэтому количество всех n-арных булевых функций равно 2^2ⁿ. Такое конечное представление позволяет задавать функцию таблицей истинности — списком значений f(x₁,…,xₙ) на всех наборах аргументов. Если значение функции не зависит от одной из переменных, эта переменная называется фиктивной.

Нульарные и унарные функции

При n = 0 существует 2^2⁰ = 2 функции — константы 0 и 1 (тождественный ноль и тождественная единица). При n = 1 существует 2^2¹ = 4 функции:

x — тождественная функция («ДА»); ¬x, x̄ — отрицание («НЕ»). Константа 0 сохраняет 0 и монотонна; константа 1 сохраняет 1 и монотонна; x самодвойственна, монотонна и линейна; ¬x самодвойственна и линейна.

Бинарные функции

При n = 2 существует 2^2² = 16 функций. Основные из них:

При n = 3 существует уже 2^2³ = 256 функций (например, тернарная сумма по модулю 2, «переключатель по большинству» ≥2(x,y,z), разряды суммы и займа при тернарном сложении/вычитании).

Представление функции формулой

Если выбрать некоторый набор булевых функций A, то с их использованием можно записать другие булевы функции — такая запись называется формулой. Например, при A = {∧, ¬} функция a ∨ b представляется как ¬(¬a ∧ ¬b).

Тождественность и двойственность

Две функции тождественны, если на любых одинаковых наборах аргументов они принимают равные значения. Простейшие тождества: 0̄ = 1, 1̄ = 0, x̄̄ = x, x ∧ x = x ∨ x = x, x ∧ x̄ = 0, x ∨ x̄ = 1. Законы де Моргана:

¬(x ∧ y) = ¬x ∨ ¬y     ¬(x ∨ y) = ¬x ∧ ¬y

Функция g двойственна функции f, если f(¬x₁,…,¬xₙ) = ¬g(x₁,…,xₙ). Константы 0 и 1 двойственны друг другу, конъюнкция и дизъюнкция — тоже (следствие законов де Моргана); тождественная функция и отрицание двойственны сами себе. Если в верном тождестве заменить каждую функцию на двойственную, снова получится верное тождество.

Суперпозиции

Суперпозиция (композиция) функций — новая функция, полученная из некоторого множества функций подстановкой одной функции в другую или отождествлением переменных. При подстановке g вместо i-го аргумента f получают h(x₁,…,x₍ₙ₊ₘ₋₁₎) = f(x₁,…,g(xᵢ,…),…). Множество всех неэквивалентных суперпозиций данного набора функций образует его замыкание.

Полнота системы, критерий Поста

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

• T₀ — сохраняющие 0 (f(0,…,0) = 0);
• T₁ — сохраняющие 1 (f(1,…,1) = 1);
• S — самодвойственные функции;
• M — монотонные функции;
• L — линейные функции.

Теорема Поста: набор функций K полон тогда и только тогда, когда он не содержится целиком ни в одном из классов T₀, T₁, S, M, L — то есть в K есть хотя бы одна функция, не сохраняющая 0, хотя бы одна, не сохраняющая 1, хотя бы одна несамодвойственная, хотя бы одна немонотонная и хотя бы одна нелинейная.

Представление булевых функций

Теорема Поста открывает путь к синтаксическому представлению функций: отправной точкой служит нахождение полной системы Σ = {f₁,…,fₙ}, и тогда любая булева функция представима термом (формулой) в сигнатуре Σ.

Дизъюнктивная нормальная форма (ДНФ)

ДНФ — форма, в которой функция задана как дизъюнкция простых конъюнктов. Благодаря закону двойного отрицания, законам де Моргана и дистрибутивности в ДНФ можно записать любую булеву формулу.

f(x,y,z) = (x ∧ y) ∨ (y ∧ ¬z)

Конъюнктивная нормальная форма (КНФ)

КНФ — форма, в которой функция имеет вид конъюнкции простых дизъюнктов. Так же, как и ДНФ, любая формула сводится к КНФ теми же тремя законами.

f(x,y,z) = (x ∨ y) ∧ (y ∨ ¬z)

Полином Жегалкина

Полином Жегалкина — полином с коэффициентами 0 и 1, где произведение — конъюнкция, а сложение — исключающее «или»:

P = a₀ ⊕ a₁x₁ ⊕ a₂x₂ ⊕ … ⊕ aₙxₙ ⊕ a₁₂x₁x₂ ⊕ … ⊕ a₁…ₙx₁x₂…xₙ

Строится из набора функций ⟨∧, ⊕, 1⟩, который по теореме Поста полон, поэтому полином Жегалкина позволяет выразить любую булеву функцию:

f(x₁,x₂) = 1 ⊕ x₁ ⊕ x₁x₂

Подстановка и отождествление переменных

Подстановка g в f заменяет i-й аргумент f значением g. Пример: при f(a,b) = a ∨ b и g(a) = ¬a подстановка g вместо второго аргумента даёт h(a,b) = a ∨ ¬b = a ← b.

Отождествление переменных подставляет i-й аргумент функции вместо j-го, уменьшая число аргументов на единицу. Пример: f(a,b) = a ∨ b даёт при отождествлении h(a) = a ∨ a — проектор единственного аргумента.

Схемы из функциональных элементов

Логическая схема — размеченный ориентированный граф без циклов в некотором базисе B: вершины без входящих рёбер — входы схемы, помеченные переменными; остальные вершины реализуют булевы функции из B. Отождествление переменных соответствует ветвлению проводников, подстановка — соединению выхода одного элемента со входом другого.

Стандартный базис

Стандартный базис — система {∧, ∨, ¬}. Через неё выражаются эквиваленция, импликация и константа 0:

x ↔ y = (x → y) ∧ (y → x)    x → y = ¬x ∨ y    0 = x ∧ ¬x

Стандартный базис — полная система (следствие теоремы о СДНФ: любая функция, кроме тождественного нуля, представима в виде СДНФ через ∧, ∨, ¬, а способ выражения нуля указан выше). При этом он избыточен: по закону де Моргана x∧y и x∨y выражаются друг через друга с ¬, поэтому безызбыточны уже подмножества {∧, ¬} и {∨, ¬}.

Теоремы о числе функций в базисе

Максимально возможное число функций в безызбыточном базисе — четыре (следует из теоремы Поста: любой полный набор задевает все 5 классов, но одна функция может не сохранять сразу и 0, и 1, либо быть одновременно не сохраняющей 0 и несамодвойственной, что снижает необходимое число функций до 4). Для каждого k от 1 до 4 существует свой базис:

• k = 1: X = {↓} (стрелка Пирса) или {▽} (штрих Шеффера);
• k = 2: X = {¬, ∧};
• k = 3: X = {∧, ⊕, 1};
• k = 4: X = {0, 1, x∧y, x⊕y⊕z}.