§3. Многочлены Жегалкина

Мы уже заметили, что конъюнкция совпадает с обычным арифметическим умножением, попробуем ввести сложение: 0+0=0; 0+1-1; 1+0=1; 1+1=? Если принять 1+1=1, то получим дизъюнкцию. Если принять 1+1=0, то получим исключающее или. Принимаем второе соотношение: х+у=ху. Такое сложение совпадает с известным в теории чисел сложением по модулю 2. Заметим, что всегда хх=0.

Всякая композиция сложений, умножений и констант называется арифметическим многочленом.

Многочленом Жегалкина называют многочлен вида , где суммирование ведется по некоторому множеству различных наборов (i₁, i₂,…,i_k), в котором ни один индекс не повторяется.

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

Выразим три основные логические операции через сложение и умножение, превратив их в многочлены Жегалкина.

Конъюнкция ху=ху уже готовый многочлен Жегалкина. Отрицание =х1. Дизъюнкция

=(x1)(y1)+1=xyxy11=xyxy.

Примеры решения задач

Задача 1. Преобразовать многочлен Жегалкина в булеву функцию, заданную формулой (ху)(z+х).

Решение. Последняя скобка уже является многочленом Жегалкина, поэтому преобразуем вначале только первую, затем раскрываем все скобки:

(ху)(z+х)=)(z+x)=((x+1)y)(z+x)=((x+1)y+x+1+y)(z+x)= =(xy+y+x+1+y)(z+x)=(xy+x+1)(z+x)=xyz+xyx+xz+xx+z+x=xyz+xy+xz++x+z+x=xyz+xy+xz+z.

Задачи для самостоятельного решения

Задача1. Преобразовать заданную булеву функцию к многочлену Жегалкина.

а) f=(х)(z);

б) f=.

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

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

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

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

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

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

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

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

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

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

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

(₁…_n);

(₁… _n).

 ( предшествует ), если все элементы набора  находятся в соотношении ₁₁… _n_n

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

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

(0;0)

(0;1)

(1;1)

(1;0)

Если , то стрелку ставим от  к .

Примеры решения задач

Задача 1. (0,1,1,0,1); (0,1,1,1,1);  ( предшествует ).

(1,0,1,0,1);

(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	1
0	1	1	1	1
1	0	0	0	1
1	1	1	0	0

Решение.

(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₁, …, x_n) называется функция f*=f().

2. Самодвойственность S. БФ называется самодвойственной, если ее двойственная функция совпадает с самой функцией f, то есть f*=f.