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

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

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

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

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

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

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

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

x1 Úx2– дизъюнкция;

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

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

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

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

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

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

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