ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ. Задача1. Преобразовать заданную булеву функцию к многочлену Жегалкина

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

а) f=(х« )(zÅ );

б) f= .

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

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

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

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

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

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

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

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

3. Линейность L. Булева функция является линейной, если ее можно представить в виде f(x₁… x_n)=a₀+a₁x₁+…+ a_nx_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.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

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

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

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задача 1. .

Решение. .

Задача 2. f(x)= .

Решение. f*= . Следовательно, данная функция самодвойственна.