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

ТЕМА 4. БУЛЕВЫ ФУНКЦИИ

 

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

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

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

Таблица 4.1

x1 x2 x3 f(x1, x2, x3)
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.

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

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

 

 

Таблица 4.2

x Øx

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

Таблица 4.3

x1 x2 x1Vx2 x1& x2 x1 x2 x1~x2 x1 Å x2 x1¯ x2 x1ï x2
0 0 0 1 1 0 1 1 0 1 1

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

x1Vx2 – дизъюнкция;

x1& x2 – конъюнкция;

x1Éx2 – импликация;

x1~x2 – эквивалентность;

x1Å x2 – сложение по модулю 2;

x1¯x2 – стрелка Пирса;

x1ï x2 – штрих Шеффера.

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