Булева функция - NiNa.Az

Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от ${\displaystyle n}$ аргументов — в дискретной математике — отображение ${\displaystyle f\colon E_{2}^{n}\to E_{2}}$, где ${\displaystyle E_{2}=\{0,1\}}$ — булево множество. Элементы булева множества ${\displaystyle \{1,0\}}$ обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число ${\displaystyle n}$, обозначающее количество аргументов, называется арностью или местностью функции, в случае ${\displaystyle n=0}$ булева функция превращается в булеву константу. Элементы декартова произведения (${\displaystyle n}$-я прямая степень) ${\displaystyle E_{2}^{n}}$ называют булевыми векторами или булевыми наборами. Множество всех булевых функций от любого числа аргументов часто обозначается ${\displaystyle P_{2}}$, а от ${\displaystyle n}$ аргументов — ${\displaystyle P_{2}^{n}}$. Переменные, принимающие значения из булева множества, называются булевыми переменными. Булевы функции названы по фамилии математика Джорджа Буля.

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

• установить взаимно-однозначное соответствие между булевыми и пропозициональными переменными;
• установить связь между булевыми функциями и логическими связками;
• оставить приоритет операций без изменений.

Раздел математики, изучающий булевы функции, называется теория булевых функций. Он является подразделом теории функций k-значной логики.

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

Каждая булева функция арности ${\displaystyle n}$ полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины ${\displaystyle n}$. Число таких векторов равно ${\displaystyle 2^{n}}$. Поскольку на каждом векторе булева функция может принимать значение либо ${\displaystyle 0}$, либо ${\displaystyle 1}$, то количество всех n-арных булевых функций равно ${\displaystyle 2^{2^{n}}}$. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции.

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

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

Основная статья: Таблица истинности

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

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

Иногда, для краткости, таблицу истинности представляют в виде строки значений функции:

${\displaystyle f=(0010\ldots 1000)}$

Значения функции в этой строке идут в лексикографическом порядке векторов аргументов.

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

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

Значение	Обозначение	Название
0	F0,0 = 0	тождественный ноль
1	F0,1 = 1	тождественная единица

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

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

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

x0=x	1	0	Обозначение	Название
0	0	0	F1,0 = 0	тождественный ноль
1	0	1	F1,1 = NOT(x) = x = ¬x = x'	отрицание, логическое «НЕТ», «НЕ», инвертор, SWAP (обмен)
2	1	0	F1,2 = YES(x) = x	логическое "ДА", повторитель, тавтология
3	1	1	F1,3 = 1	тождественная единица

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

При 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))	стрелка Пи́рса - "↓" (кинжал Куайна - "†"), функция Ве́бба - "°", НЕ-ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, инверсия максимума
2	0	0	1	0	F2,2 = x > y = x GT y = GT(x,y) = x → y = x ${\displaystyle \not \rightarrow }$ y	функция сравнения "первый операнд больше второго операнда", инверсия прямой импликации, коимпликация
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	функция сравнения "первый операнд меньше второго операнда", инверсия обратной импликации, обратная коимпликация
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, исключающее «или», сумма Жегалкина, исключающий 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))	штрих Ше́ффера, пунктир Чулкова, НЕ-И, 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	функция сравнения "первый операнд не больше второго операнда", прямая (материальная) импликация (от первого аргумента ко второму)
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ППБ-НЕ, мажоритарный клапан с инверсией
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ППБ, мажоритарный клапан
248	1	1	1	1	1	0	0	0	F3,248 = x OR (y AND z) = Gi+1,j+1 = Gi+1,j OR (Pi+1,j AND Gi,j)	Оператор G (Genarate) Valency-2 (валентность=2) в параллельно префиксных сумматорах
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)	ИЛИ, максимум

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

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

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

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

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

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

Основная статья: Дизъюнктивная нормальная форма

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

• правильная, если каждая переменная входит в неё не более одного раза (включая отрицание);
• полная, если каждая переменная (или её отрицание) входит в неё ровно 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. Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы

Переменная булевой функции входит в её полином Жегалкина тогда и только тогда, когда она существенна.

Полные системы булевых функций

Основная статья: Замкнутые классы булевых функций

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

Результат вычисления булевой функции может быть использован в качестве одного из аргументов другой функции. Результат такой операции суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности. Например, функции ${\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}}$, целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом, критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию. Пост доказал, что множество замкнутых классов булевых функций — счётное множество.

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

Классификация булевых функций

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

Геометрическая интерпретация

Элементы множества ${\displaystyle E_{2}^{n}}$ можно представлять себе как координаты вершин единичного гиперкуба. На этом основывается геометрическая интерпретация булевых функций. В геометрической терминологии подмножества булева гиперкуба отождествляют с подмножествами вершин, например под гранью гиперкуба понимают её множество вершин, а под самим гиперкубом — множество ${\displaystyle E_{2}^{n}}$.

Само понятие булев гиперкуб (или для краткости говорят просто булев куб) формально могут определять по-разному: как единичный куб в евклидовом пространстве, как граф, вершины которого наборы из ${\displaystyle E_{n}^{2}}$, а рёбра соединяют соседние наборы или прямо так определяют как ${\displaystyle E_{2}^{n}}$. При этом при работе с этим понятием его просто используют как синоним к ${\displaystyle E_{2}^{n}}$, подмножество булева куба — синоним к понятию подмножество ${\displaystyle E_{2}^{n}}$, вершина булева куба — синоним к понятию набор, ребро — синоним к понятию пара соседних вершин, а k-мерную грань булева куба определяют как подмножество ${\displaystyle E_{2}^{n}}$, имеющее вид:

${\displaystyle \{(x_{1},\ldots ,x_{n})\in E_{2}^{n}|x_{i_{1}}=\alpha _{1},\ldots ,x_{i_{n-k}}=\alpha _{n-k}\}}$.

${\displaystyle \alpha _{1},\ldots ,\alpha _{n-k}}$ здесь булевы константы, фиксированные для определённой грани. Таким образом, грань булева куба — множество всех булевых векторов, в которых определённые ${\displaystyle n-k}$ координат имеют заданные значения. Число ${\displaystyle m=n-k}$ называется коразмерностью грани булева куба. По сути все эти термины — просто другая терминология, для объектов теории булевых функций; просто в некоторых случаях она оказывается удобнее обычной терминологии, например при изучении ДНФ и КНФ.

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

Для булевых функций есть три различных способов интерпретации на булевом кубе. Множеством единиц булевой функции ${\displaystyle f}$ называется множество:

${\displaystyle N_{f}=\{(x_{1},\ldots ,x_{n})\in E_{2}^{n}|f(x_{1},\ldots ,x_{n})=1\}}$

Множеством нулей булевой функции ${\displaystyle f}$ называется множество:

${\displaystyle M_{f}=\{(x_{1},\ldots ,x_{n})\in E_{2}^{n}|f(x_{1},\ldots ,x_{n})=0\}}$

Множество единиц, как и множество нулей, однозначно определяет свою функцию. Две геометрических интерпретации булевых функций на этом и основаны: одна отождествляет функцию с её множеством единиц, а другая — с множеством нулей. Интерпретация через множество единиц удобнее при изучении ДНФ, а через множество нулей — КНФ.

Третья интерпретация есть просто раскраска вершин графа. Используется две краски: ${\displaystyle 0}$ и ${\displaystyle 1}$; соответственно в ${\displaystyle 0}$ окрашиваются те вершины, на которых функция принимает ${\displaystyle 0}$, а в ${\displaystyle 1}$ — на которой ${\displaystyle 1}$ (можно также представлять это как взвешенный граф). Такая интерпретация бывает удобна для представления линейных и монотонных функций: для линейных функций без фиктивных переменных такая раскраска будет правильной и куб обладает тем свойством, что соседние слои имеют противоположные значения функции. Для монотонной функции в такой интерпоетации все вершины, до которых можно дойти от нулевой сверху вниз, имеют значение ${\displaystyle 0}$, а все вершины, до которых можно дойти снизу вверх от единичной, имеют значение ${\displaystyle 1}$.

Интерпретация множеством единиц

При интерпретации функции множеством её единиц происходит следующее соответствие:

• булева функция — подмножество булева куба;
• дизъюнкция булевых функций — объединение подмножеств булева куба;
• конъюнкция булевых функций — пересечение подмножеств булева куба;
• элементарная конъюнкция — грань булева куба;
• ДНФ — множество граней булева куба;
• совершенная ДНФ — множество 0-мерных граней булева куба (то есть множество синглтонов вершин булева куба);
• функция, задаваемая ДНФ — объединение множества граней булева куба;
• импликанта функции — подмножество подмножества булева куба;
• простая импликанта функции — максимальная грань, входящая в подмножество булева куба (то есть такая грань, которая не является собственным подмножеством никакой другой грани, входящей в подмножество булева куба)
• сокращённая ДНФ функции — множество всех максимальных граней подмножества булева куба;

Интерпретация множеством нулей

При интерпретации функции множеством её нулей происходит следующее соответствие:

• булева функция — подмножество булева куба;
• дизъюнкция булевых функций — пересечение подмножеств булева куба;
• конъюнкция булевых функций — объединение подмножеств булева куба;
• элементарная дизъюнкция — грань булева куба;
• КНФ — множество граней булева куба;
• совершенная КНФ — множество 0-мерных граней булева куба;
• функция, задаваемая КНФ — объединение множества граней булева куба;
• следствие функции — подмножество подмножества булева куба;
• простое следствие функции — максимальная грань, входящая в подмножество булева куба
• сокращённая КНФ функции — множество всех максимальных граней подмножества булева куба;

См. также

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

Литература

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

Ссылки

1. Игошин, 2008, Глава 2. Булевы функции.
2. Игошин, 2008, с. 94.
3. Игошин, 2008, с. 104-105.
4. Самофалов, 1987.
5. Рагимханов, 2019, с. 30.
6. Номера логических функций https://dzen.ru/a/Zn5r7J4wYEgC3ubl
7. Элементарные булевы функции  (неопр.). Дата обращения: 9 ноября 2016. Архивировано 10 ноября 2016 года.
8. Избранные вопросы теории булевых функций. // А. С. Балюк и др. Под ред. С. Ф. Винокурова и Н. А. Перязева. — М.: ФИЗМАТЛИТ, 2001. — 192 с. — С. 13.
9. Игошин, 2008, с. 96.
10. И.А. Насыров. учебно-методическое пособие  (неопр.). Дата обращения: 20 ноября 2020. Архивировано 22 декабря 2019 года.
11. Borland Turbo BASIC Owners Handbook 1987, p.80
12. Яблонский, 2006, с. 307.
13. Нурлыбаев, 1991, с. 88.