Булевы функции и их свойства

Напомним два фактора:

1. Всякая булева функция может быть представлена в виде композиции дизъюнкции, конъюнкции и отрицания.

2. Всякая булева функция может быть представлена в виде композиции сложения, умножения и константы.

Определение. Система булевых функций {j₁,…, j_n} называется полной, если любая булева функция может быть представлена в виде их композиций.

Булева функция имеет следующие свойства:

1. Свойство сохранения нуля Р₀. Булева функция сохраняет ноль, если на нулевом наборе значений она принимает значение 0.

2. Свойство сохранения единицы Р₁. Булева функция сохраняет единицу, если на единичном наборе значений она принимает значение 1.

3. Линейность L. Булева функция является линейной, если ее можно представить в виде f(x ₁… x _n)= a ₀+ a ₁ x ₁+…+ a _n x _n, то есть в виде многочлена Жегалкина степени не выше первой.

4. Монотонность М. Булева функция является монотонной, если для любых произвольных наборов a и b следует, что f( a)£ f (b).

Введем соотношение предшествования двух наборов:

a(a₁…a_n);

b(b₁… b_n).

a£b (a предшествует b), если все элементы набора a находятся в соотношении a₁£b₁… a_n£b_n

Сравнение наборов и значение функций удобно проверить на гиперкубе.

Для функции двух переменных сравнимые наборы можно рассмотреть на квадрате

(1;1)

(0;0)

(0;1)

(1;0)

Если a£b, то стрелку ставим от a к b.