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

Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от n переменных — в дискретной математике отображение Bⁿ → B, где B = {0,1} — булево множество. Элементы булева множества 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	1	0	1
1	0	0	1	1

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

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

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

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

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

x	y	0	x↓y	Шаблон:Overline	x̅	Шаблон:Overline	y̅	x⊕y	x|y	x & y	x ≡ y	y	x→y	x	x←y	x ∨ y	1
0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

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

Обозначение	Название
0	тождественный ноль, тождественная ложь, тождественное "НЕТ"
x ↓ y, x ИЛИ-НЕ y, ИЛИ-НЕ(x,y), x NOR y, NOR(x,y)	НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса
x < y, Шаблон:Overline, x LT y, LT(x,y)	меньше, инверсия обратной импликации]
x̅, НЕ1(x,y), NOT1(x,y), x', ¬x	отрицание (негация, инверсия) первого операнда
x > y, Шаблон:Overline, x GT y, GT(x,y)	больше, инверсия прямой импликации
y̅, НЕ2(x,y), NOT2(x,y), y', ¬y	отрицание (негация, инверсия) второго операнда
x ⊕ y, x +2 y, x ≠ y, x >< y, x <> y, x XOR y, XOR(x,y)	сложение по модулю 2, не равно, , исключающее «или»
x | y, x NAND y, NAND(x,y), x И-НЕ y, И-НЕ(x,y)	НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера
x & y, x · y, xy, x ∧ y, x AND y, AND(x,y), x И y, И(x,y), min(x,y)	2И, конъюнкция
x ≡ y, x = y, x EQV y, EQV(x,y), x ~ y, x ↔ y	равенство, эквивалентность
y, ДА2(x,y), YES2(x,y)	второй операнд
x → y, x ≤ y, x ⊃ y, x LE y, LE(x,y)	меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)
x, ДА1(x,y), YES1(x,y)	первый операнд
x ← y, x ≥ y, x ⊂ y, x GE y, GE(x,y)	больше или равно, обратная импликация (от второго аргумента к первому)
x ∨ y, x + y, x ИЛИ y, ИЛИ(x,y), x OR y, OR(x,y), max(x,y)	2ИЛИ, дизъюнкция
1	тождественная единица, тождественная истина, тождественное "ДА", тавтология

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

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

x	y	z	x↓y↓z	Шаблон:Overline	x≠y≠z	x|y|z	min(x,y,z)	x=y=z	x⊕y⊕z	≥2(x,y,z)	f1	f2	max(x,y,z)
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

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

Обозначения	Названия
x[math]\downarrow[/math]y[math]\downarrow[/math]z = [math]\downarrow[/math](x,y,z) = Webb2(x,y,z)	3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
[math]\neg(\gt = 2(x,y,z))[/math]	Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
x≠y≠z = [≠(x,y,z)] = NE(x,y,z,v)	Неравенство
x[math]\mid[/math]y[math]\mid[/math]z = [math]\mid[/math](x,y,z)	3-И-НЕ, штрих Шеффера
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-И, минимум
(x=y=z) = [=(x,y,z)] = EQV(x,y,z,v)	Равенство
x⊕2y⊕2z = x+2y+2z = ⊕2(x,y,z) = +2(x,y,z)	Тернарное сложение по модулю 2
[>=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x)	переключатель по большинству, 3-ППБ, мажоритарный клапан
f1	Разряд займа при тернарном вычитании
f2	Разряд переноса при тернарном сложении
(x+y+z) = +(x,y,z) = max(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z)	3-ИЛИ, максимум