Задача1. Преобразовать заданную булеву функцию к многочлену Жегалкина.
а) f=(х «
)(zÅ 
);
б) f= 
.
Булевы функции и их свойства
Напомним два фактора:
1. Всякая булева функция может быть представлена в виде композиции дизъюнкции, конъюнкции и отрицания.
2. Всякая булева функция может быть представлена в виде композиции сложения, умножения и константы.
Определение. Система булевых функций {j1,…, jn} называется полной, если любая булева функция может быть представлена в виде их композиций.
Булева функция имеет следующие свойства:
1. Свойство сохранения нуля Р0. Булева функция сохраняет ноль, если на нулевом наборе значений она принимает значение 0.
2. Свойство сохранения единицы Р1. Булева функция сохраняет единицу, если на единичном наборе значений она принимает значение 1.
3. Линейность L. Булева функция является линейной, если ее можно представить в виде f(x 1… x n)= a 0+ a 1 x 1+…+ a n x n, то есть в виде многочлена Жегалкина степени не выше первой.
4. Монотонность М. Булева функция является монотонной, если для любых произвольных наборов a и b следует, что f( a)£ f (b).
Введем соотношение предшествования двух наборов:
a(a1…an);
b(b1… bn).
a£b (a предшествует b), если все элементы набора a находятся в соотношении a1£b1… an£bn
Сравнение наборов и значение функций удобно проверить на гиперкубе.
Для функции двух переменных сравнимые наборы можно рассмотреть на квадрате
| (1;1) |
| (0;0) |
| (0;1) |
| (1;0) |
Если a£b, то стрелку ставим от a к b.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1. a(0,1,1,0,1); b(0,1,1,1,1); a£b (a предшествует b).
a(1,0,1,0,1);
b(0,1,1,0,1);
Решение. Наборы несравнимы, так как 1>0, 0<1.
Задача 2. Проверить функцию f(x,y)=x(x®y)«
| x | y | x®y | 
| f |
Решение.
(0;0)£(1;1) f(0;0)³f(1;1);
(0;0)£(1;0) f(0;0)³f(1;0);
(0;0)£(0;1) f(0;0)³f(0;1);
(0;1)£(1;1) f(0;1)³f(1;1);
(1;0)£(1;1) f(1;0)³f(1;1).
Так как на меньшем наборе функция принимает большее значение, то в данном случае функция не является монотонной.
Теорема (критерий монотонности)
Всякая дизъюнктивная нормальная форма (ДНФ), не содержащая отрицаний переменных, является монотонной функцией, отличной от констант 0 и 1. И наоборот: для любой монотонной функции, отличной от 0 и 1, существует равная ей ДНФ, не содержащая отрицаний переменных.
1. Двойственность. Двойственной функцией к булевой функции f(x 1, …, x n) называется функция f*=f (
).
2. Самодвойственность S. БФ называется самодвойственной, если ее двойственная функция совпадает с самой функцией f, то есть f*=f.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задача 1. 
.
Решение. 
.
Задача 2. f(x)= .
Решение. f*= . Следовательно, данная функция самодвойственна.
