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

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

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

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

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

Таблица 2.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.

Булева функция n переменных может иметь 2ⁿ наборов. Поскольку функция принимает только два значения, общее число булевых функций n переменных равно 2²ⁿ. Таким образом, функция одной переменой может иметь четыре значения:y = x; y = Øx (отрицание х); y = 0 (константа 0); y = 1 (константа 1).

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

Таблица 2.2 – Функция отрицание

х	Øx

Булевых функций двух переменных – 16. Те из них, которые имеют специальные названия, представлены в таблице 2.3

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

x1 x2	x1Vx2	x1& x2	x1x2	x1x2	x1 Å x2	x1 x2	x1 x2
0 0 0 1 1 0 1 1

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

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

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

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

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

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

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

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

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