Булевы функции#
«… в математике истинный смысл теоремы до конца раскрывается лишь в ходе ее доказательства, и если найдется такой болван, который будет заучивать только формулировки теорем, игнорируя доказательства, — он будет тратить время впустую.» (Л. Янг)
Главная цель изучения данной темы - не просто приобрести навыки упрощения булевых формул (эти стандартные алгоритмы реализованы в готовых пакетах, например SymPy). Мы изучаем теорию, чтобы лучше понять логику алгоритмов.
Основные понятия#
Источник: Соболева, Чечкин - Дискретная математика. Углубленный курс
Булева функция - это таблица двоичных значений \(f(x_1, x_2, \ldots, x_n)\) для всех двоичных наборов \((x_1, x_2, \ldots, x_n)\).
В разделе “Математическая индукция” мы доказали, что число всех подмножеств \(n\)-элементного множества равно \(2^n\). Аналогичным образом доказывается, что число упорядоченных кортежей из \(n\) двоичных значений составляет \(2^n\).
Следствие 1. Число двоичных наборов аргументов булевой функции от \(n\) аргументов равно \(2^n\).
Следствие 2. Число различных булевых функций от \(n\) аргументов равно \(2^{(2^n)}\).
Пример. Разных булевых функций от \(1\) переменной будет \(4\). Перечислим их:
\(f_1(x) = 0\), \(f_2(x) = x\), \(f_3(x) = \neg x\), \(f_4(x) = 1\).
Пример. Различных булевых функций от \(2\) переменных будет \(16\).
Для некоторых булевых функций от \(2\) переменных введены обозначения:
\(f_1(x_1, x_2) = x_1 \vee x_2\) - дизъюнкция
\(f_2(x_1, x_2) = x_1 \land x_2\) - конъюнкция
\(f_3(x_1, x_2) = x_1 \oplus x_2\) - сложение по модулю 2
\(f_4(x_1, x_2) = x_1 \to x_2\) - импликация
\(f_5(x_1, x_2) = x_1 \leftrightarrow x_2\) - эквиваленция
\(f_6(x_1, x_2) = x_1 \, | \, x_2\) - штрих Шеффера
\(f_7(x_1, x_2) = x_1 \downarrow x_2\) - стрелка Пирса
\(x_1\) |
\(x_2\) |
\(f_1\) |
\(f_2\) |
\(f_3\) |
\(f_4\) |
\(f_5\) |
\(f_6\) |
\(f_7\) |
|---|---|---|---|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
Аналитическое задание булевых функций#
Источники: Гашков, Фролов - Дискретная математика; Соболева, Чечкин - Дискретная математика. Углубленный курс
СДНФ#
Пусть булева функция \(f(x_1, x_2, \ldots, x_n)\) задана таблицей. Построим формулу специального вида, выражающую булеву функцию с помощью всего лишь трёх алгебраических операций \(\land, \vee, \neg\).
Определение. Пусть \(s = (s_1, s_2, \ldots, s_n)\) - двоичный кортеж параметров, \(x = (x_1, x_2, \ldots, x_n)\) - двоичный кортеж аргументов булевой функции. Булева функция \(K_s(x) = x_1^{s_1} \cdot x_2^{s_2} \cdot \ldots \cdot x_n^{s_n}\) называется полной элементарной конъюнкцией.
В полной элементарной конъюнкции участвуют все переменные или их отрицания без повторений. Обозначение “степень булевой переменной” расшифровывается так:
\(x^1 = x, \quad x^0 = \overline{x}\)
Число различных полных элементарных конъюнкций от \(n\) переменных равно \(2^n\) (см. утверждение о числе двоичных кортежей длины \(n\)).
Каждая полная элементарная конъюнкция обладает важным свойством:
Полная элементарная конъюнкция \(K_s(x)\) равна \(1\) лишь на одном наборе параметров \(s = (s_1, s_2, \ldots, s_n)\), когда \(x_i^{s_i} = 1\), т.е. \(x_i = s_i\).
Отсюда следует, что дизъюнкция \(m\) различных полных элементарных конъюнкций равна \(1\) лишь на \(m\) наборах аргументов, соответствующих параметрам полных элементарных конъюнкций.
Теорема. Если булева функция \(f(x) = f(x_1, x_2, \ldots, x_n)\) не является тождественно равной нулю и задана таблицей с \(m \geq 1\) единичными значениями, то существует единственная дизъюнкция \(m\) различных полных элементарных дизъюнкций, соответствующих этим значениям, которая задаёт булеву функцию
\(f(x_1, x_2, \ldots, x_n) = \bigvee\limits_{s \colon f(s) = 1} K_s(x)\)
и называется совершенной дизъюнктивной нормальной формой (СДНФ) данной булевой функции.
Пример. Функция голосования задается следующей таблицей истинности.
\(x_1\) |
\(x_2\) |
\(x_3\) |
\(f(x)\) |
|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
В силу теоремы эта функция представляется в виде дизъюнкции 4-х полных элементарных конъюнкций, которые соответствуют единичным значениям функции:
\(f(x) = \overline{x_1} \cdot x_2 \cdot x_3 \vee x_1 \cdot \overline{x_2} \cdot x_3 \vee x_1 \cdot x_2 \cdot \overline{x_3} \vee x_1 \cdot x_2 \cdot x_3\)
Разложение булевой функции по переменной#
Всякая булева функция \(f(x)\) реализуется формулой
\( f(x_1, x_2, \ldots, x_n) = \overline{x_1}\cdot f(0, x_2, \ldots, x_n) + x_1 \cdot f(1, x_2, \ldots, x_n) \)
Аналогично функцию можно разложить по нескольким переменным \(x_1, \ldots, x_k\). В следующей формуле \(s = (s_1, \ldots, s_k)\) - кортеж двоичных параметров, обозначающих конкретные значения переменных \(x_1, \ldots, x_k\):
\( f(x_1, \ldots, x_k, \ldots, x_n) = \bigvee\limits_{s} x_1^{s_1} \cdot \ldots \cdot x_k^{s_k} \cdot f(s_1, \ldots, s_k, x_{k+1}, \ldots, x_n). \)
Разложение булевой функции по всем переменным (т.е. в случае \(k = n\)) дает СДНФ:
\( f(x_1, \ldots, x_n) = \bigvee\limits_{s} x_1^{s_1} \cdot \ldots \cdot x_n^{s_n} \cdot f(s_1, \ldots, s_n). \)
Упражнение. Разложите функцию голосования по переменной \(x_2\).
Многочлен Жегалкина#
Представим булеву функцию \(f(x_1, x_2, \ldots, x_n)\) в виде суперпозиции операций \(\oplus, \land\) с участием константы \(1\).
Определение. Элементарная конъюнкция, не содержащая отрицаний переменных, называется монотонной конъюнкцией. В частности, монотонной конъюнкцией является “пустая конъюнкция” - константа \(1\).
Определение. Многочленом Жегалкина называется формула, являющаяся монотонной конъюнкцией или суммой по модулю два различных монотонных конъюнкций, или константой \(0\).
Общий вид многочлена Жегалкина от 2 переменных:
\( a_0 \oplus a_1x \oplus a_2y \oplus a_{12}xy \)
Каждая из 4 возможных монотонных конъюнкций либо присутствует (\(a_i = 1\)), либо отсутствует (\(a_i = 0\)) в формуле. Всего различных многочленов Жегалкина от 2 переменных столько же, сколько двоичных наборов длины 4, то есть \(2^4 = 16\). Это значит, что различных многочленов Жегалкина столько же, сколько и различных булевых функций.
Упражнение. Запишите общий вид многочлена Жегалкина от 3 переменных. Сколько всего различных многочленов Жегалкина от 3 переменных? Сколько всего различных булевых функций от 3 переменных? Почему?
Теорема. Всякая булева функция представима многочленом Жегалкина, причем единственным образом.
Доказательство. Докажем существование. Если функция - константа, то многочлен Жегалкина есть эта константа. Иначе булева функция представима в виде СДНФ.
Преобразуем СДНФ:
\( f(x_1, \ldots, x_n) = \bigvee\limits_{s} x_1^{s_1} \cdot \ldots \cdot x_n^{s_n} \cdot f(s_1, \ldots, s_n) = \)
\( = \bigoplus\limits_{s} (x_1 \oplus \overline{s_1}) \cdot \ldots \cdot (x_n \oplus \overline{s_n}) \cdot f(s_1, \ldots, s_n) = \)
\( = \bigoplus\limits_{s} (x_1 \oplus s_1 \oplus 1) \cdot \ldots \cdot (x_n \oplus s_n \oplus 1) \cdot f(s_1, \ldots, s_n). \)
Раскрывая скобки по закону дистрибутивности \(x \land (y \oplus z) = x \land y \oplus x \land z\), получаем многочлен Жегалкина. Таким образом, всякая булева функция представима многочленом Жегалкина.
Докажем единственность. Посчитаем число различных многочленов Жегалкина от \(n\) переменных. Их \(2^{(2^n)}\), столько же, сколько различных булевых функций.
Каждому многочлену Жегалкина соответствует единственная булева функция. Каждой булевой функции соответствует хотя бы один многочлен Жегалкина. Если какой-то булевой функции соответствует больше одного многочлена, то найдется многочлен, которому не соответствует никакая булева функция, что невозможно. Значит, представление булевой функции в виде многочлена Жегалкина единственно.
Замечание. Пусть \(A, B\) - конечные множества, \(f \colon A \to B\) - функция. Если \(|A| = |B|\) и \(f\) - сюръекция, то \(f\) - биекция.
Полные системы булевых функций#
Источник: лекции ВМК МГУ
Определение. Система булевых функций называется полной, если всякую булеву функцию любого числа переменных можно выразить с помощью формулы глубины не меньше 1 с участием операций из данной системы (глубина формулы - это число операций в формуле).
Примеры полных систем:
\(\text{Б}_0 = \{x_1 \land x_2, x_1 \vee x_2, \overline{x_1} \}\)
\(\text{Б}_+ = \{x_1 \oplus x_2, x_1 \land x_2, 1 \}\)
В первом случае сошлемся на возможность выразить любую функцию, не равную тождественно \(0\), в виде СДНФ (константу \(0\) тоже можно выразить с помощью системы \(\text{Б}_0\) следующим образом: \(0 = x_1 \land \neg x_1\)).
Во втором случае ссылаемся на возможность выразить всякую функцию с помощью многочлена Жегалкина (особый случай - константа \(0\), которая выражается так: \(0 = x_1 \oplus x_1\)).
Полнота одной системы через полноту другой системы#
Существует приём, который бы доказывал полноту систем на основе уже построенных полных систем.
Теорема. Пусть \(A\) - полная система булевых функций, и пусть \(A'\) - другая система булевых функций, такая, что всякая функция из \(A\) реализуется некоторой формулой над \(A'\). Тогда \(A'\) - полная система.
Примеры: \(\{x_1 \land x_2, \overline{x_1}\}\), \(\{x_1 \vee x_2, \overline{x_1}\}\), \(\{x_1 \,|\, x_2\}\), \(\{x_1 \downarrow x_2\}\) - полные системы булевых функций, поскольку каждую из этих систем можно выразить с помощью функций системы \(\text{Б}_0\).
Например, \(\overline{x_1} = x_1 \, | \, x_1\), \(x_1 \land x_2 = \neg (x_1 \, | \, x_2) = (x_1 \, | \, x_2) \, | \, (x_1 \, | \, x_2)\). Поэтому по теореме, если \(\{\overline{x_1}, x_1 \land x_2\}\) - полная система, то \(\{|\}\) - также полная система.
Упражнение. Докажите полноту системы \(\{x_1 \to x_2, 0\}\).
Замкнутые классы#
Критерий полноты#
Минимизация ДНФ#
Источники: Судоплатов, Овчинникова - Дискретная математика; Никишечкин - Дискретная математика и дискретные системы управления; Алексеев - Дискретная математика