Определение. Переменная x называется булевой, если она способна принимать только два значения 0 и 1. В качестве примера интерпретации такого рода переменных может выступать обычный настенный выключатель света на два положения. Здесь 1 соответствует положению переключателя вверх и 0 — положению вниз.
Определение. Функция f(x₁,x₂,…,x_n) называется булевой (или логической, или функцией алгебры логики, или переключательной), если все ее аргументы x[i] являются булевыми, а сама функция также может принимать только два значения 0 и 1. Множество всех булевых функций от переменных x₁,x₂,…,x_n обозначают через P₂.

Способы задания булевых функций

Способы задания булевых функций не отличаются от способов задания обычных функций анализа. К таковым способам задания стандартно относятся:
1) табличный;
2) графический;
3) аналитический.

(1) Табличный способ задания

Пусть w=f(x₁,x₂,…,x_n) — булева функция n аргументов. Область определения данной функции можно рассматривать и как множество упорядоченных наборов (или векторов, или двоичных наборов) D={x₁,x₂,…,x_n | x_i ∈ {0,1}, i=1,2,…,n}, на каждом из которых функция принимает одно из двух значений: w ∈ {0,1}. Количество таких наборов (x₁,x₂,…,x_n), согласно правилу прямого произведения, равно |D|=

В качестве примера рассмотрим табличное представление булевой функции трех аргументов w=f(x,y,z), где w,x,y,z  ∈ {0,1}. Область определения функции — это множество двоичных наборов D={(x,y,z), |  x,y,z ∈ {0,1}}. Их число есть |D|=2^3=8, а количество таких функций равно 2^|D|=2^2^3=256. Значения функции f(x,y,z) удобно представить в виде табл. 1.3, где перечислены всевозможные наборы из нулей и единиц длины 3 и для каждогонабора указано значение функции fⁱ ∈ {0,1} на этом наборе.

В таблицах, аналогичных табл. 1.3 обычно употребляется расположение наборов, соответствующих порядку естественного роста двоичных чисел 0,1,…2^n-1, в
примере n=3.
Определение. Таблицы значений булевых функций, подобные табл. 1.3, называются таблицами истинности булевых функций. Название таблиц происходит от интерпретации значений 1 — истина (TRUE), 0 — ложь (FALSE).

(2) Графический способ задания

Рассмотрим графическое представление булевой функции трех аргументов w=f(x,y,z), заданной таблично (табл. 1.3). Заметим, что множество наборов области определения функции D={(x,y,z) , | x,y,z ∈ {0,1}} является множеством координат точек вершин единичного трехмерного куба (рис. 1.2). Очевидный способ графического представления булевой функции — это отметить каким-то образом вершины куба, в которых функция принимает значение 1. Именно так на рис. 1.2 и сделано. В соответствии с таблицей значений (табл. 1.3) отмечены вершины, в которых булева функция равна 1.

Замечание. Очевидно, что область определения булевой функции n аргументов w=f(x₁,x₂,…,x_n) составляется из наборов координат точек вершин единичного n-мерного куба.

(3) Аналитический способ задания

Приведем таблицы истинности, обозначения и названия булевых функций одного и двух аргументов. В табл. 1.4 представлены все (их 2^2^1=4) функции одного аргумента, в табл. 1.5 — все функции двух аргументов (их 2^2^2=16).

Таблица 1.4

Функции 0 и 1 называются соответственно тождественным нулем и тождественной единицей. Иногда эти функции 0 и 1 рассматривают как функции, зависящие от пустого множества переменных.

Таблица 1.5

x у	0 0 1 1 0 1 0 1	Обозначение	Название
0	0 0 0 0	0	Нуль, const 0
1	0 0 0 1	x•y,x∧y,x&y	Конъюнкция
2	0 0 1 0	yx,x•y	Запрет по x
3	0 0 1 1	x	Повторение x
4	0 1 0 0	x, x•y	Запрет по y
5	0 1 0 1	y	Повторение y
6	0 1 1 0	x⊕y	Сумма по модулю 2
7	0 1 1 1	x∨y	Дизъюнкция
8	1 0 0 0	x↓y	Стрелка Пирса
9	1 0 0 1	x~y	Эквивалентность
10	1 0 1 0	¬y, y	Отрицание y
11	1 0 1 1	y→x, y⇒x, y⊃x	Импликация от y к x
12	1 1 0 0	¬x, x	Отрицание x
13	1 1 0 1	x→y, x⇒y, x⊃y	Импликация от x к y
14	1 1 1 0	x|y	Штрих Шеффера
15	1 1 1 1	1	Единица, const 1

Функции одного и двух аргументов, представленные в таблицах 1.4 и 1.5, называются элементарными.

Символы ¬, |, ↓, ∧, , ∨, →, ⊕, ~, участвующие в обозначениях элементарных функций, называются логическими связками (операциями) или функциональными символами.