Булева функция

Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2ⁿ. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно 2⁽²ⁿ⁾. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции.

Практически все булевы функции низших арностей (0, 1, 2 и 3) получили исторически сложившиеся имена. Если значение функции не зависит от одной из переменных (то есть, по сути, для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная, не играя никакого «значения», называется фиктивной.

Таблицы истинности

Булева функция задаётся конечным набором значений, что позволяет представить её в виде таблицы истинности, например^[4]:

x1	x2	…	xn−1	xn	f(x1, x2, …, xn)
0	0	…	0	0	0
0	0	…	0	1	0
0	0	…	1	0	1
0	0	…	1	1	0
${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \ddots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$
1	1	…	0	0	1
1	1	…	0	1	0
1	1	…	1	0	0
1	1	…	1	1	0

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

При n = 0 количество булевых функций сводится к двум 2²⁰ = 2¹ = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.
Таблица значений и названий нульарных булевых функций:

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

При n = 1 число булевых функций равно 2²¹ = 2² = 4. Определение этих функций содержится в следующей таблице.

Таблица значений и названий булевых функций от одной переменной:

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

При n = 2 число булевых функций равно 2²² = 2⁴ = 16.

Таблица значений и названий булевых функций от двух переменных (в зависимости от области применения, функции имеют разные обозначения и разные словесные названия, но один и тот же номер):

x0=x	1	0	1	0	Обозначение функции	Название функции
x1=y	1	1	0	0
0	0	0	0	0	F2,0 = 0	тождественный ноль
1	0	0	0	1	F2,1 = x ↓ y = x † y = x NOR y = NOR(x,y) = x НЕ-ИЛИ y = НЕ-ИЛИ(x,y) = NOT(MAX(X,Y))	стрелка Пи́рса - "↓" (кинжал Куайна - "†"), функция Ве́бба - "°"[5], НЕ-ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, инверсия максимума
2	0	0	1	0	F2,2 = x > y = x GT y = GT(x,y) = x → y = x ${\displaystyle \not \rightarrow }$ y	функция сравнения "первый операнд больше второго операнда", инверсия прямой импликации, коимпликация[6]
3	0	0	1	1	F2,3 = y = y' = ¬y = NOT2(x,y) = НЕ2(x,y)	отрицание (негация, инверсия) второго операнда
4	0	1	0	0	F2,4 = x < y = x LT y = LT(x,y) = x ← y = x ${\displaystyle \not \leftarrow }$ y	функция сравнения "первый операнд меньше второго операнда", инверсия обратной импликации, обратная коимпликация[6]
5	0	1	0	1	F2,5 = x = x' = ¬x = NOT1(x,y) = НЕ1(x,y)	отрицание (негация, инверсия) первого операнда
6	0	1	1	0	F2,6 = x >< y = x <> y = x NE y = NE(x, y) = x ⊕ y = x XOR y = XOR(x,y) = XMAX(x,y) = x XMAX y	функция сравнения "операнды не равны", сложение по модулю 2, исключающее «или», сумма Жегалкина[7], исключающий max
7	0	1	1	1	F2,7 = x | y = x ↑ y = x NAND y = NAND(x,y) = x НЕ-И y = НЕ-И(x,y) = NOT(MIN(X,Y))	штрих Ше́ффера, пунктир Чулкова[8], НЕ-И, 2И-НЕ, антиконъюнкция, инверсия минимума
8	1	0	0	0	F2,8 = x ∧ y = x · y = xy = x & y = x AND y = AND(x,y) = x И y = И(x,y) = min(x,y)	конъюнкция, 2И, минимум
9	1	0	0	1	F2,9 = (x ≡ y) = x ~ y = x ↔ y = x EQV y = EQV(x,y)	функция сравнения "операнды равны", эквивалентность
10	1	0	1	0	F2,10 = YES1(x,y) = ДА1(x,y) = x	первый операнд
11	1	0	1	1	F2,11 = x ≥ y = x >= y = x GE y = GE(x,y) = x ← y = x ⊂ y	функция сравнения "первый операнд не меньше второго операнда", обратная импликация (от второго аргумента к первому)
12	1	1	0	0	F2,12 = YES2(x,y) = ДА2(x,y) = y	второй операнд
13	1	1	0	1	F2,13 = x ≤ y = x <= y = x LE y = LE(x,y) = x → y = x ⊃ y = x IMP y[9]	функция сравнения "первый операнд не больше второго операнда", прямая (материальная) импликация (от первого аргумента ко второму)
14	1	1	1	0	F2,14 = x ∨ y = x + y = x OR y = OR(x,y) = x ИЛИ y = ИЛИ(x,y) = max(x,y)	дизъюнкция, 2ИЛИ, максимум
15	1	1	1	1	F2,15 = 1	тождественная единица

При двух аргументах префиксная, инфиксная и постфиксная записи, по экономичности, почти одинаковы.

Некоторые функции, имеющие смысл в цифровой технике, например функции сравнения, минимум и максимум, не имеют смысла в логике, так как в логике, в общем случае, логические значения TRUE и FALSE не имеют жёсткой привязки к числовым значениям (например в TurboBasic'е, для упрощения некоторых вычислений, TRUE = -1, а FALSE = 0) и невозможно определить, что больше TRUE или FALSE, импликации же и др. имеют смысл и в цифровой технике и в логике.

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

При n = 3 число булевых функций равно 2⁽²³⁾ = 2⁸ = 256. Некоторые из них определены в следующей таблице:
Таблица значений и названий некоторых булевых функций от трёх переменных, имеющих собственное название:

x0=x	1	0	1	0	1	0	1	0	Обозначения	Названия
x1=y	1	1	0	0	1	1	0	0
x2=z	1	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0	1	F3,1 = x↓y↓z = ↓(x,y,z) = Webb2(x,y,z) = NOR(x,y,z)	3ИЛИ-НЕ, функция Вебба, стрелка Пирса, кинжал Куайна - "†"
23	0	0	0	1	0	1	1	1	F3,23 = ${\displaystyle \neg (>=2(x,y,z))}$ = ≥2(x,y,z)	Переключатель по большинству с инверсией, 3ППБ-НЕ, мажоритарный клапан с инверсией
31	0	0	0	1	1	1	1	1	F3,31 = x OR (y AND z) = Gi,j = Gi,j-1 OR (Pi,j-1 AND Gi-1,j-1)	Оператор Valency-2 (валентность=2) в параллельно префиксных сумматорах
126	0	1	1	1	1	1	1	0	F3,126 = (x≠y≠z) = [≠(x,y,z)] = NE(x,y,z)	Неравенство
127	0	1	1	1	1	1	1	1	F3,127 = x|y|z = |(x,y,z) = NAND(x,y,z)	3И-НЕ, штрих Шеффера
128	1	0	0	0	0	0	0	0	F3,128 = x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x И y И z) = И(x,y,z) = min(x,y,z)	3И, минимум
129	1	0	0	0	0	0	0	1	F3,129 = (x=y=z) = [=(x,y,z)] = EQV(x,y,z)	Равенство
150	1	0	0	1	0	1	1	0	F3,150 = x⊕y⊕z = x⊕2y⊕2z = ⊕2(x,y,z)	Тернарное сложение по модулю 2
184	1	0	1	1	1	0	0	0	F3,184 = ${\displaystyle [x,y,z]}$	Условная дизъюнкция
202	1	1	0	0	1	0	1	0	F3,202 = MUX(x,y)	Мультиплексор 2 в 1
216	1	1	0	1	1	0	0	0	F3,216 = f1	Разряд займа при тернарном вычитании
232	1	1	1	0	1	0	0	0	F3,232 = f2 = [>=2(x,y,z)] = ≥2(x,y,z) = (x И y) ИЛИ (y И z) ИЛИ (z И x)	Разряд переноса при тернарном сложении, переключатель по большинству, 3ППБ, мажоритарный клапан
254	1	1	1	1	1	1	1	0	F3,254 = (x+y+z) = +(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z) = max(x,y,z)	ИЛИ, максимум

При трёх и более аргументах префиксная (и постфиксная) запись экономичнее инфиксной записи.
Обычный вид записи функций — префиксный (перед операндами). При инфиксной (между операндами) записи функций функции называются операторами, а аргументы функции — операндами.

Суперпозиция и замкнутые классы функций

Результат вычисления булевой функции может быть использован в качестве одного из аргументов другой функции. Результат такой операции суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности. Например, функции ${\displaystyle f(x,y,z)={\overline {x({\overline {y}}\lor z)}}}$ (суперпозиция конъюнкции, дизъюнкции и двух отрицаний) будет соответствовать следующая таблица:

${\displaystyle x_{2}=x}$	${\displaystyle x_{1}=y}$	${\displaystyle x_{0}=z}$		${\displaystyle f(x,y,z)}$
0	0	0		1
0	0	1		1
0	1	0		1
0	1	1		1
1	0	0		0
1	0	1		0
1	1	0		1
1	1	1		0

Говорят, что множество функций замкнуто относительно операции суперпозиции, если любая суперпозиция функций из данного множества тоже входит в это же множество. Замкнутые множества функций называют также замкнутыми классами.

В качестве простейших примеров замкнутых классов булевых функций можно назвать множество ${\displaystyle \{x\}}$ , состоящее из одной тождественной функции, или множество ${\displaystyle \{0\}}$ , все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций ${\displaystyle \{x,{\overline {x}}\}}$ и множество всех унарных функций. А вот объединение замкнутых классов может таковым уже не являться. Например, объединив классы ${\displaystyle \{0\}}$ и ${\displaystyle \{x,{\overline {x}}\}}$ , мы с помощью суперпозиции ${\displaystyle {\overline {0}}}$ сможем получить константу 1, которая в исходных классах отсутствовала.

Разумеется, множество ${\displaystyle P_{2}}$ всех возможных булевых функций тоже является замкнутым.

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

Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:
${\displaystyle f(x_{1},x_{2},\dots ,x_{n})=g(x_{1},x_{2},\dots ,x_{n})}$

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

${\displaystyle {\overline {0}}=1}$	${\displaystyle {\overline {1}}=0}$	${\displaystyle {\overline {\overline {x}}}=x}$	${\displaystyle xy=yx}$	${\displaystyle x\lor y=y\lor x}$
${\displaystyle 0x=0}$	${\displaystyle 1x=x}$	${\displaystyle 0\lor x=x}$	${\displaystyle 1\lor x=1}$	${\displaystyle xx=x\lor x=x}$

А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:

${\displaystyle x{\overline {x}}=0}$

${\displaystyle x\lor {\overline {x}}=1}$

${\displaystyle {\overline {x\cdot y}}={\overline {x}}\lor {\overline {y}}}$

${\displaystyle {\overline {x}}\cdot {\overline {y}}={\overline {x\lor y}}}$

(законы де Моргана)

${\displaystyle x(y\lor z)=xy\lor xz}$
${\displaystyle x\lor yz=(x\lor y)(x\lor z)}$ (дистрибутивность конъюнкции и дизъюнкции)

Функция ${\displaystyle g(x_{1},x_{2},\dots ,x_{n})}$ называется двойственной функции ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})}$ , если ${\displaystyle f({\overline {x_{1}}},{\overline {x_{2}}},\dots ,{\overline {x_{n}}})={\overline {g(x_{1},x_{2},\dots ,x_{n})}}}$ . Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

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

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

Система булевых функций называется полной, если можно построить их суперпозицию, тождественную любой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством ${\displaystyle P_{2}}$ .

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

• Функции, сохраняющие константу ${\displaystyle P_{0}}$ и ${\displaystyle P_{1}}$ ;
• Самодвойственные функции ${\displaystyle S}$ ;
• Монотонные функции ${\displaystyle M}$ ;
• Линейные функции ${\displaystyle L}$ .

Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с ${\displaystyle P_{2}}$ , целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом, критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию.Пост доказал, что множество замкнутых классов булевых функций — счётное множество.

Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.

Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее, чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций ${\displaystyle \Sigma =\{f_{1},\ldots ,f_{n}\}}$ . Тогда каждая булева функция может быть представлена некоторым термом в сигнатуре ${\displaystyle \Sigma }$ , который в данном случае называют также формулой. Относительно выбранной системы функций полезно знать ответы на следующие вопросы:

• Как построить по данной функции представляющую её формулу?
• Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
  • В частности: существует ли способ приведения произвольной формулы к эквивалентной ей канонической форме такой, что две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
• Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?

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

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

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

• правильная, если каждая переменная входит в неё не более одного раза (включая отрицание);
• полная, если каждая переменная (или её отрицание) входит в неё ровно 1 раз;
• монотонная, если она не содержит отрицаний переменных.

Например ${\displaystyle a{\overline {b}}c\lor b{\overline {c}}\lor {\overline {a}}}$   — является ДНФ.

Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: ${\displaystyle a{\overline {b}}c\lor abc\lor {\overline {a}}b{\overline {c}}}$ .

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции, отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора ${\displaystyle b=(b_{1},b_{2},\ldots ,b_{n})}$ построить конъюнкцию ${\displaystyle x_{1}^{b_{1}}x_{2}^{b_{2}}\ldots x_{n}^{b_{n}}}$ , где ${\displaystyle x_{i}^{1}=x_{i}}$ ${\displaystyle x_{i}^{0}={\overline {x_{i}}}}$ . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации ${\displaystyle x\to y}$ результатом является ${\displaystyle {\overline {x}}y\lor {\overline {x}}\,{\overline {y}}\lor xy}$ , что можно упростить до ${\displaystyle {\overline {x}}\lor y}$ .

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

Конъюнктивная нормальная форма (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

${\displaystyle a(b\lor c)\to ab\lor ac}$

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило

${\displaystyle a\lor bc\to (a\lor b)(a\lor c)}$

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

Алгебраическая нормальная форма (АНФ или полином Жегалкина)

Алгебраическая нормальная форма (общепринятое название в зарубежной литературе) или полином Жегалкина (название, используемое в отечественной литературе) — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции («И», AND), а в качестве сложения — сложение по модулю 2 (исключающее «ИЛИ», XOR). Для получения полинома Жегалкина следует выполнить следующие действия:

1. Получить СДНФ функции
2. Все ИЛИ заменить на Исключающее ИЛИ
3. Во всех термах заменить элементы с отрицанием на конструкцию: («элемент» «исключающее ИЛИ» 1)
4. Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы

• По количеству n входных операндов, от которых зависит значение на выходе функции, различают нульарные (n = 0), унарные (n = 1), бинарные (n = 2), тернарные (n = 3) булевы функции и функции от большего числа операндов.

• По количеству единиц и нулей в таблице истинности отличают узкий класс сбалансированных булевых функций (также называемых уравновешенными или равновероятностными, поскольку при равновероятных случайных значениях на входе или при переборе всех комбинаций по таблице истинности вероятность получения на выходе значения 1 равна 1/2) от более широкого класса несбалансированных булевых функций (так же называемых неуравновешенными, поскольку вероятность получения на выходе значения 1 отлична от 1/2). Сбалансированные булевы функции в основном используются в криптографии.

• По зависимости значения функции от перестановки её входных битов различают симметричные булевы функции (значение которых зависит только от количества единиц на входе) и несимметричные булевы функции (значение которых так же зависит от перестановки её входных бит).

• По значению функции на противоположных друг другу наборах значений аргументов отличают самодвойственные функции (значение которых инвертируется при инвертировании значения всех входов) от остальных булевых функций, не обладающих таким свойством. Нижняя часть таблицы истинности для самодвойственных функций является зеркальным отражением инвертированной верхней части (если расположить входные комбинации в таблице истинности в естественном порядке).

• По алгебраической степени нелинейности отличают линейные булевы функции (АНФ которых сводится к линейной сумме по модулю 2 входных значений) и нелинейные булевы функции (АНФ которых содержит хотя бы одну нелинейную операцию конъюнкции входных значений). Примерами линейных функций являются: сложение по модулю 2 (исключающее «ИЛИ», XOR), эквивалентность, а также все булевы функции, АНФ которых содержит лишь линейные операции сложения по модулю 2 без конъюнкций. Примерами нелинейных функций являются: конъюнкция («И», AND), штрих Шеффера («НЕ-И», NAND), стрелка Пирса («НЕ-ИЛИ», NOR), а также все булевы функции, АНФ которых содержит хотя бы одну нелинейную операцию конъюнкции.

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

Две булевы функции называются равными, если множества их существенных переменных равны и на любых двух равных наборах значений существенных переменных значения функций совпадают.^[10]

• Булева алгебра
• Битовые операции
• Комбинационная логика
• Секвенциальная логика
• Троичная логика
• Троичные функции
• Логические элементы

• Алексеев В. Б. (лектор), Поспелов А.Д. (составитель). Дискретная математика (курс лекций, II семестр). — М.: Изд. отд. фак. Вычислит. математики и кибернетики МГУ им. М. В. Ломоносова, 2002. — 44 с.
• Быкова С. В., Буркатовская Ю. Б. Булевы функции: учебное пособие для студентов высших учебных заведений, обучающихся по специальности ВПО 010501 «Прикладная математика и информатика». — Томск: Томский гос. ун-т, 2010. — 190 с.
• Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. — М.: ФИЗМАТЛИТ, 2009.
• Игошин В. И. Математическая логика и теория алгоритмов. — 2-е изд., стереотип.. — М.: Издательский центр «Академия», 2008. — 448 с.
• Кузнецов О. П. Дискретная математика для инженера. — СПб.: Лань, 2007. — 394 с.
• Учебные пособия кафедры математической кибернетики ВМиК МГУ (на сайте кафедры математической кибернетики МГУ ВМК).
• Ложкин С.А. Лекции по основам кибернетики : учеб. пособие по курсам «Основы кибернетики» и «Структур. реализация дискрет. функций». — М.: Изд. отд. фак. Вычислит. математики и кибернетики МГУ им. М. В. Ломоносова, 2004. — 254 с.
• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2001. — 126 с.
• Самофалов К. Г., Романкевич А. М., Валуйский В. Н., Каневский Ю. С., Пиневич М. М. Прикладная теория цифровых автоматов. — Киев: Вища Школа, 1987. — С. 183—189. — 375 с.
• Яблонский С. В. Введение в дискретную математику. — М.: Высш. шк., 2006. — 384 с.