Булеві функції однієї змінної

Загальна таблиця відповідності для булевих функцій однієї змінної має вигляд

				Таблиця 2
x	y1 = f1(x)	y2 = f2(x)	y3 = f3(x)	y4 = f4(x)
0	1	0	1	0
1	1	0	0	1

Тут функції y₁ та y₂ є функціями-константами, f₁(x) – абсолютно істинна, f₂(x) – абсолютно хибна, f₃(x) – логічне заперечення, або НЕ, f₄(x) – змінна x (повторює значення змінної x і тому збігається з нею).

Область визначення булевих функцій

Областю визначення булевої функції n аргументів є сукупність 2ⁿ булевих кортежів.

Булева функція двох аргументів є повністю визначеною, якщо задано її значення в кожному з чотирьох можливих наборів (2² = 4). Булева функція трьох аргументів на (2³ = 8) наборах також буде повністю визначеною.

Булева функція n аргументів є повністю визначеною, якщо задано всі її значення в кожному з 2ⁿ наборів.

Теорема 1. Число f₂(n) усіх функцій, що залежать від n змінних x₁, x₂, …, x_n, дорівнює .

Дійсно, булеву функцію n аргументів визначено в 2ⁿ наборах, в яких вона може набувати значення 0 або 1 із загальної кількості значень 2ⁿ. Тому у відповідність кожній перемикальній функції можна поставити 2ⁿ-розрядне двійкове число. Проте кількість різних 2ⁿ-розрядних чисел дорівнює , отже, f₂(n) = .

Елементарні функції алгебри логіки

Приклади елементарних функцій однієї змінної наведено в табл. 2. У таблиці 3 подано 16 функцій двох змінних, з яких шість f₁₆(a, b) = 0, f₁₁(a, b) = a, f₁₃(a, b) = b, f₁₂(a, b) = , f₁₄(a, b) = , f₁₅(a, b) = 1, є константами або функціями одного аргументу. Інші 10 функцій залежать від двох аргументів і мають свої загальноприйняті позначення та назви, зазначені в табл. 3. Розглянути всі функції, що залежать від трьох аргументів важко, оскільки їх є = 256.

Таблиця 3
Позна­чення функції	Най­ме­нуван­ня функ­ції	a				При­мітка	Зберігає 0	Зберігає 1	Само­двоїста	Монотон­на	Лінійна
		0	0	1	1
		b
		0	1	0	1
f1 = a  b = = ab	Кон’юнкція (логічне множення), f = min(a, b)	0	0	0	1					
f2 = a  b = = a + b	Диз’юнкція (логічне додавання), f = max(a, b)	0	1	1	1					
f3 = a  b	Імплікація (від a до b)	1	1	0	1			
f4 = a  b	Імплікація (від b до a)	1	0	1	1			
f5 = a ~ b	Рівно­силь­ність	1	0	0	1			
f6 = a  b = = a  b	Не­рів­но­силь­ність (сума за модулем 2)	0	1	1	0		
f7 = a b = = a / b	Функція Шеффера (ін­версія кон’юнкції)	1	1	1	0	Уні­вер­саль­на
f8 = a b = = a  b	Функція стрілка Пірса-Вебба (ін­­версія диз’юнк­ції)	1	0	0	0	Те саме
f9 = a b	Інверсія імплікації (функ­ція заборони за b)	0	0	1	0		
f10 = a b	Інверсія, обернена ім­плі­ка­ції (функ­ція за­бо­ро­ни за a)	0	1	0	0		
f11 = a	Повторення a (змінна a)	0	0	1	1	Три­ві­аль­на					
f12 =	Інверсія a (функція НЕ a)	1	1	0	0						
f13 = b	Повторення b (змінна b)	0	1	0	1	Те саме					
f14 =	Інверсія b (функція НЕ b)	1	0	1	0						
f15 = 1	Одинична функція (константа 1)	1	1	1	1	Три­віальна					
f16 = 1	Нульова функція (константа 0)	0	0	0	0	Те саме					

Функція f₁(a, b) – кон’юнкція (логічне множення) істинна тоді, коли a і b істинні. Кон’юнкцією називають також функцію 1. Умовно її позначають f₁(a, b) = a  b = a  b.

Функція f₂(a, b) – диз’юнкція (логічне додавання) істинна тоді, коли істинними є або a, або b, або обидві змінні. Диз’юнкцію часто називають також функцією АБО й умовно позначають так: f₂(a, b) = a + b = a  b.

Імплікація – це функція f₃(a, b), яка є хибною тоді й тільки тоді, коли a є істинним, а b є хибним. Позначається вона f₃(a, b) = a  b.

Функція f₆(a, b) – додавання за модулем 2 (функція нерівно­сильности) є істинною, коли істинними є a або b окремо.

f₇(a, b) – є хибною тоді й тільки тоді, коли a і b є істинними.

Функція f₈(a, b) – істинна тоді й тільки тоді, коли a і b є хибними.