Представление булевой функции

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

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

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

Функция отрицания

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

Булевы функции двух переменных

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

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

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

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

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

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

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

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

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