 |
Задачи для самостоятельного решения
|
|
|
|
Задача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 | 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 1, …, x n) называется функция f *= f (
).
2. Самодвойственность S. БФ называется самодвойственной, если ее двойственная функция совпадает с самой функцией f, то есть f*=f.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задача 1. 
.
Решение. 
.
Задача 2. f(x)= .
Решение. f*= . Следовательно, данная функция самодвойственна.
Функциональная полнота. Теорема Поста
Функциональный набор логических функций это такой набор функций, который позволяет любую функцию математической логики описать с помощью функции данного набора.
Теорема Поста. Для того чтобы набор функций f (x 1, …, x n) был функционально полным, необходимо и достаточно, чтобы для всего набора функций в целом не выполнялось свойство сохранения нуля, сохранения единицы, линейность, монотонность и самодвойственность. Полноту набора функций удобно определять по таблице Поста, в котором знаком + или – обозначаются функции, принадлежащие (+) или не принадлежащие (-) к одному из этих классов.
В силу теоремы Поста, для полноты системы необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один минус.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1.
|
|
|
F={f1,f2}
| P0 | P1 | L | M | S | |
| f1 | + | + | - | + | + |
| f2 | - | + | - | - | - |
Решение. Так как f1 и f2 ÎР1, следовательно, {f1,f2} не является полной.
Задача 2. Выяснить, является ли система функций f1=x®1 и f2=(x«)®x полной.
Решение. f1=x®1º1
| x | f |
| 0 | 1 |
| 1 | 1 |
f2=(x«)®x
| x | y | x«
| f |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Составим таблицу Поста
| P0 | P1 | L | M | S | |
| f1 | - | + | + | + | + |
| f2 | - | + | - | - | - |
f2=(x«)®x
= 
Многочлен Жегалкина второй степени линейностью не обладает, так как таблица содержит столбец со всеми плюсами, то исходная система булевых функций по теореме Поста не является полной.
|
|
|
