3.2 Булевы функции

Функция f (x₁, x₂,..., x_n), принимающая два значения: 0 и 1 и зависящая от переменных, каждая из которых может принимать значения 0 и 1, называется булевой или переключательной. Из определения следует, что область определения булевой функции – совокупность всевозможных n-мерных наборов из нулей и единиц, а для её задания достаточно указать, какие значения функции соответствуют каждому из наборов (табл. 3.3).

Таблица 3.3 – Задание булевой функции

x1	x2	...	xn-1	xn	f (x1, x2,...,xn-1, xn)
0	0	...	0	0	f (0, 0,...,0, 0)
0	0	...	0	1	f (0, 0,...,0, 1)
...	...	...	...	...	.................………
1	1	...	1	0	f (1, 1,...,1, 0)
1	1	...	1	1	f (1, 1,...1, 1)

Порядок расположения наборов, принятый в таблице, называется стандартным или естественным. При таком порядке каждому набору

= (₁,...,_n), где _i есть 0 или 1, ставится в соответствие число

N = ₁ 2^n-1 + ... + _n-1 2 + _n .

Наборам (0, 0,...,0, 0), (0, 0,...,0, 1),..., (1, 1,...,1, 1) соответствуют числа 0, 1,..., 2ⁿ-1. Естественным порядком будет расположение наборов в порядке возрастания соответствующих им чисел. Десятичное число, соответствующее входному набору, является его номером. Поэтому очевидно, что количество k входных наборов для булевой функции n переменных равно k=2ⁿ. Количество же различных функций n переменных можно определить из следующих соображений. Каждая функция задается набором своих k значений (для k входных наборов), которому также можно поставить в соответствие k-разрядное двоичное число. Располагая теперь в таблице функции в порядке возрастания соответствующих им чисел, мы получим все возможные различные функции. Количество таких функций будет равно .

Рассмотрим другие способы задания булевых функций. Сначала познакомимся с функциями одной и двух переменных, которые часто употребляются в математической логике и кибернетике, их можно считать «элементарными» функциями (табл. 3.4, 3.5).

Таблица 3.4 – Булевы функции одной переменной

x	g1(x)	g2(x)	g3(x)	g4(x)	g1(x), g4(x) – константы 0 и 1,
0	0	0	1	1	g2(x) = x,
1	0	1	0	1	g3(x) = x (отрицание x).

Таблица 3.5 – Булевы функции двух переменных

x1	x2	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15	f16
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

Следует отметить, что к функциям двух переменных относятся и такие, которые в действительности зависят от одной переменной или не зависят ни от одной.

Функции f₁, f₁₆ – константы 0 и 1. Они не зависят существенно ни от одной переменной.

Функции f₄ = х₁, f₁₁ =х₂, f₆ = х₂, f₁₃ =х₁ зависят существенно только от одной переменной.

f₂ = х₁ ٨ х₂ – конъюнкция или логическое умножение (знак «٨» можно заменять на «∙», либо опускать).

f₈ = х₁ ٧ х₂ – дизъюнкция или логическое сложение.

f₁₀ – эквивалентность, х₁  х₂.

f₇ = х₁  х₂ или х₁ + х₂ (mod 2) – сложение по модулю два.

f₁₂, f₁₄ – импликация, х₂  х₁ и х₁  х_2.

f₁₅ – штрих Шеффера, х₁ | х_2.

f₉ – стрелка Пирса, х₁  х₂ (другое название – функция Вебба).

f₃, f₅ – функции запрета х₁ и х₂ соответственно. f₃ = х₁  х₂ ,

f₅ = х₂  х₁ .

Исходя из элементарных функций можно строить формулы, т.е. рассматривать функции от функций например, (x₁  x₂)х₂)  х₃ .