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

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

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

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

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

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

[math]x_1[/math]	[math]x_2[/math]	[math]...[/math]	[math]x_n[/math]	[math]f(x_1,x_2,...,x_n)[/math]
[math]0[/math]	[math]0[/math]	[math]...[/math]	[math]0[/math]	[math]f(0,0,...,0)[/math]
[math]1[/math]	[math]0[/math]	[math]...[/math]	[math]0[/math]	[math]f(1,0,...,0)[/math]
[math]0[/math]	[math]1[/math]	[math]...[/math]	[math]0[/math]	[math]f(0,1,...,0)[/math]
[math]1[/math]	[math]1[/math]	[math]...[/math]	[math]0[/math]	[math]f(1,1,...,0)[/math]
[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]
[math]0[/math]	[math]1[/math]	[math]...[/math]	[math]1[/math]	[math]f(0,1,...,1)[/math]
[math]1[/math]	[math]1[/math]	[math]...[/math]	[math]1[/math]	[math]f(1,1,...,1)[/math]

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

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

При [math]n = 0[/math] количество булевых функций равно [math]{2^2}^0 = 2^1 = 2[/math], первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.

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

При [math]n = 1[/math] число булевых функций равно [math]{2^2}^1 = 2^2 = 4[/math].

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

x	[math]0[/math]	[math]x[/math]	[math]\neg x[/math]	[math]1[/math]
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]	тождественная единица, тождественная истина, тождественное "ДА", тавтология

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

При [math]n = 2[/math] число булевых функций равно [math]{2^2}^2 = 2^4 = 16[/math].

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

x	y	[math]0[/math]	[math]x \land y[/math]	[math]x \nrightarrow y[/math]	[math]x[/math]	[math]x \nleftarrow y[/math]	[math]y[/math]	[math]x \oplus y[/math]	[math]x \lor y[/math]	[math]x \downarrow y[/math]	[math]x = y[/math]	[math]\neg y[/math]	[math]x \leftarrow y[/math]	[math]\neg x[/math]	[math]x \rightarrow y[/math]	[math]x \triangledown y[/math]	[math]1[/math]
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 \land 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 \lor 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]\neg y[/math]	[math]NOT2(x, y),\ y',\ \bar{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]\neg x[/math]	[math]NOT1(x,y),\ x',\ \bar{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]		тождественная единица, тождественная истина, тождественное "ДА", тавтология

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

При [math]n = 3[/math] число булевых функций равно [math]{2^2}^3 = 2^8 = 256[/math]. Некоторые из них определены в следующей таблице:

[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 \land y \land z[/math]	[math]\land (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-ИЛИ, максимум

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

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

Если выбрать некоторый набор булевых функций [math]A[/math], то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой.

Например, если [math]A = \left\{\land,\neg\right\}[/math], то функция [math]a \lor b[/math] представляется в виде [math]\neg(\neg a \land \neg b)[/math]

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

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

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

Тождественность функций 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]x \land y=y \land x\![/math]	[math]x\lor y=y \lor x[/math]
[math]0 \land x=0\![/math]	[math]1 \land x=x\![/math]	[math]0 \lor x=x[/math]	[math]1\lor x=1[/math]	[math]x \land x=x \lor x=x[/math]

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

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

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

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

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

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

[math]x \land (y\lor z)=(x \land y)\lor (x \land z)[/math]
[math]x \lor (y \land z)=(x\lor y) \land (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
• Учебные пособия кафедры математической кибернетики ВМиК МГУ
• Булева функция — Википедия