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

Определение:

Булева функция от [math]n[/math] переменных — отображение [math]B_n[/math] → [math]B[/math], где [math]B = \{0, 1\}[/math] — булево множество.

Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения Bⁿ называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается P₂, а от n переменных — P₂(n). Булевы функции названы так по фамилии математика Джорджа Буля.

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

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

x1	x2	…	xn	f(x1,x2,…,xn)
0	0	…	0	f(0,0,…,0)
1	0	…	0	f(1,0,…,0)
0	1	…	0	f(0,1,…,0)
1	1	…	0	f(1,1,…,0)
[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]
0	1	…	1	f(0,1,…,1)
1	1	…	1	f(1,1,…,1)

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

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

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

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

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

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

x	0	x	¬x	1
0	0	0	1	1
1	0	1	0	1
Сохраняет 0	1	1	0	0
Сохраняет 1	0	1	0	1
Самодвойственная	0	1	1	0
Монотонная	1	1	0	1
Линейная	1	1	1	1

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

Обозначение	Название
[math]0[/math]	тождественный ноль, тождественная ложь, тождественное "НЕТ"
[math]x[/math]	тождественная функция, логическое "ДА", "YES"(англ.)
[math]\bar x,\ \neg x,\ x'[/math]	отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)
[math]1[/math]	тождественная единица, тождественная истина, тождественное "ДА", тавтология

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

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

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

x	y	0	∧	[math]\nrightarrow[/math]	x	[math]\nleftarrow[/math]	y	⊕	∨	↓	↔	¬y	←	¬x	→	∇	1
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
Сохраняет 0		1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0
Сохраняет 1		0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
Самодвойственная		0	0	0	1	0	1	0	0	0	0	1	0	1	0	0	0
Монотонная		1	1	0	1	0	1	0	1	0	0	0	0	0	0	0	1
Линейная		1	0	0	1	0	1	1	0	0	1	1	0	1	0	0	1

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

Обозначение	Другие обозначения	Название
[math]0[/math]		тождественный ноль, тождественная ложь, тождественное "НЕТ"
[math]x \wedge y[/math]	[math]x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y),[/math] x И y, И(x, y)	2И, конъюнкция
[math]x \nrightarrow y[/math]	[math]x \gt y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)[/math]	больше, инверсия прямой импликации
[math]x[/math]	[math]YES1(x,y),[/math] ДА1(x, y)	первый операнд
[math]x \nleftarrow y[/math]	[math]x \lt y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)[/math]	меньше, инверсия обратной импликации
[math]y[/math]	[math]YES2(x, y),[/math] ДА2(x, y)	второй операнд
[math]x \oplus y[/math]	[math]x + _2 y,\ x \not = y,\ x \gt \lt y,\ x \lt \gt y,\ x\ XOR\ y,\ XOR(x,y)[/math]	сложение по модулю 2, не равно, ксор, исключающее «или»
[math]x \vee y[/math]	[math]x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),[/math] x ИЛИ y, ИЛИ(x, y)	2ИЛИ, дизъюнкция
[math]x \downarrow y[/math]	[math]x\ NOR\ y,\ NOR(x,y)[/math] x ИЛИ-НЕ y, ИЛИ-НЕ(x, y)	НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса
[math]x = y[/math]	[math]x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y[/math]	равенство, эквивалентность
[math]\bar{y}[/math]	[math]NOT2(x, y),\ y',\ \neg y,[/math] НЕ2(x, y)	отрицание (негация, инверсия) второго операнда
[math]x \leftarrow y[/math]	[math]x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)[/math]	больше или равно, обратная импликация (от второго аргумента к первому)
[math]\bar{x}[/math]	[math]NOT1(x,y),\ x',\ \neg x,[/math] НЕ1(x, y)	отрицание (негация, инверсия) первого операнда
[math]x \rightarrow y[/math]	[math]x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)[/math]	меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)
[math]x \triangledown y[/math]	[math]x \mid y,\ x\ NAND\ y,\ NAND(x,y),[/math] x И-НЕ y, И-НЕ(x, y)	НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера
[math]1[/math]		тождественная единица, тождественная истина, тождественное "ДА", тавтология

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

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

[math]x[/math]	[math]y[/math]	[math]z[/math]	[math]x \downarrow y \downarrow z[/math]	[math]\neg (\geq 2(x,y,z))[/math]	[math]x \not = y \not = z[/math]	[math]x \mid y \mid z[/math]	[math]min(x,y,z)[/math]	[math]x=y=z[/math]	[math]x \oplus y \oplus z[/math]	[math]\geq 2(x,y,z)[/math]	[math]f_1[/math]	[math]f_2[/math]	[math]max(x,y,z)[/math]
0	0	0	1	1	0	1	0	1	0	0	0	0	0
0	0	1	0	1	1	1	0	0	1	0	0	0	1
0	1	0	0	1	1	1	0	0	1	0	0	0	1
0	1	1	0	0	1	1	0	0	0	1	1	1	1
1	0	0	0	1	1	1	0	0	1	0	1	0	1
1	0	1	0	0	1	1	0	0	0	1	0	1	1
1	1	0	0	0	1	1	0	0	0	1	1	1	1
1	1	1	0	0	0	0	1	1	1	1	1	1	1

Названия булевых функций трех переменных:

Обозначения	Другие обозначения	Названия
[math]x \downarrow y \downarrow z[/math]	[math]\downarrow (x,y,z) = Webb_2 (x,y,z)[/math]	3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
[math]\neg (\geq 2(x,y,z))[/math]		Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
[math]x \not = y \not = z[/math]	[math][\not =(x,y,z)] = NE(x,y,z)[/math]	Неравенство
[math]x \mid y \mid z[/math]	[math]\mid(x,y,z)[/math]	3-И-НЕ, штрих Шеффера
[math]x \wedge y \wedge z[/math]	[math]\wedge (x,y,z) = (x\ AND\ y\ AND\ z) = AND(x,y,z) = min(x,y,z)[/math] = (x И y И z) = И(x,y,z)	3-И, минимум
[math]x=y=z[/math]	[math][=(x,y,z)] = EQV(x,y,z)[/math]	Равенство
[math]x \oplus y \oplus z[/math]	[math]x +_2 y +_2 z = \oplus (x,y,z) = +_2 (x,y,z)[/math]	Тернарное сложение по модулю 2
[math]\geq 2(x,y,z)[/math]	(x И y) ИЛИ (y И z) ИЛИ (z И x)	переключатель по большинству, 3-ППБ, мажоритарный клапан
[math]f_1[/math]		Разряд займа при тернарном вычитании
[math]f_2[/math]		Разряд переноса при тернарном сложении
[math]x+y+z[/math]	[math]+(x,y,z) = max(x,y,z) = (x\ OR\ y\ OR\ z) = OR(x,y,z) =[/math] (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z)	3-ИЛИ, максимум

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

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

Определение:

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

Тождественность функций f и g можно записать, например, так:
[math]f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)[/math]

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

[math]\overline{0}=1[/math]	[math]\overline{1}=0[/math]	[math]\overline{\overline{x}}=x[/math]	[math]xy=yx\![/math]	[math]x\lor y=y \lor x[/math]
[math]0x=0\![/math]	[math]1x=x\![/math]	[math]0\lor x=x[/math]	[math]1\lor x=1[/math]	[math]xx=x\lor x=x[/math]

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

[math]x\overline{x}=0[/math]

[math]x\lor\overline{x}=1[/math]

[math]\overline{x\cdot y}=\overline{x}\lor\overline{y}[/math]

[math]\overline{x}\cdot\overline{y}=\overline{x\lor y}[/math]

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

[math]x(y\lor z)=xy\lor xz[/math]
[math]x\lor yz=(x\lor y)(x\lor z)[/math] (дистрибутивность конъюнкции и дизъюнкции)

Определение:

Функция [math]g(x_1,x_2,\dots,x_n)[/math] называется двойственной функции [math]f(x_1,x_2,\dots,x_n)[/math], если [math]f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}[/math].

Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

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

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

Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций [math]\Sigma = \{f_1,\ldots,f_n\}[/math]. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре [math]\Sigma[/math], который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:

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

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

Литература

• Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1969.
• Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
• Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов

Ссылки

• Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006
• http://psi-logic.narod.ru/bool/bool.htm
• Учебные пособия кафедры математической кибернетики ВМиК МГУ
• Булева функция — Википедия