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

Определение 4.1. Булевой функцией f (x ₁, x ₂,..., x_n) называется произвольная функция n переменных, аргументы которой x ₁, x ₂,..., x_n и сама функция f принимают значения 0 или 1, т. е. x_i {0, 1}, i = 1, 2,..., n; f (x ₁, x ₂,..., x_n) {0, 1}.

Одной из важнейших интерпретаций теории булевых функций является теория переключательных функций. Первоначально математический аппарат теории булевых функций был применен для анализа и синтеза релейно-контактных схем с операциями последовательного и параллельного соединения контактов. Подробнее это приложение теории булевых функций будет рассмотрено в разделе 4.9.

Любая булева функция может быть представлена таблицей, в левой части которой перечислены все наборы переменных (их 2 ⁿ), а в правой части – значения функции. Пример такого задания представлен в таблице 4.1.

Таблица 4.1

x 1 x 2 x 3	f (x 1, x 2, x 3)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Для формирования столбца значений переменных удобен лексико-графический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100 = 011+ 1.

Всего существует 2² различных булевых функций n переменных.

Функций одной переменной – 4. Из них выделим функцию “отрицание x ”(обозначается Ø x). Эта функция представлена в таблице 4.2.

Таблица 4.2

x	Ø x

Булевых функций двух переменных – 16 (2² при n = 2). Те из них, которые имеют специальные названия, представлены в таблице 4.3.

Таблица 4.3

x 1 x 2	x 1V x 2	x 1& x 2	x 1 x 2	x 1~ x 2	x 1 Å x 2	x 1¯ x 2	x 1ï x 2
0 0 0 1 1 0 1 1		0	1	1

В таблице 4.3 представлены следующие функции двух переменных:

x ₁V x ₂ – дизъюнкция;

x ₁& x ₂ – конъюнкция;

x ₁É x ₂ – импликация;

x ₁~ x ₂ – эквивалентность;

x ₁Å x ₂ – сложение по модулю 2;

x ₁¯ x ₂ – стрелка Пирса;

x ₁ï x ₂ – штрих Шеффера.

Остальные функции специальных названий не имеют и могут быть выражены через перечисленные выше функции.