Задачи для самостоятельного решения
Задача 1. Преобразовать в СДНФ булеву функцию, заданную формулой
а)
f=(
у)(z
);
б)
f=
;
в)
f=(
z)V(y
).
Задача 2. По таблице истинности получить СДНФ булевой функции
а)
f=(x
)(z
);
б)
f=
.
§ 2. Совершенная конъюнктивная нормальная форма (скнф)
Существует и другая нормальная форма (конъюнктивная).
Выражение
(отрицание на любых местах) называется
элементарной дизъюнкцией (ЭД).
Конъюнкция нескольких ЭД называется конъюнктивной нормальной формой (КНФ).
Если к тому же все ЭД правильны и полны, то КНФ называется совершенной (СКНФ).
Рассмотрим способ получения СКНФ с помощью СДНФ.
Пусть дана булева функция f(x1…xn). Двойственной булевой функцией называется булева функция f*, заданная формулой
f*(x1…xn)=
Заметим, что (f*)*=f.
Например,
для f=xVy
двойственной
является f*=
=xy.
Таким образом, двойственной к дизъюнкции является конъюнкция и наоборот.
Теорема (закон двойственности). Двойственная к композиции булевых функций есть соответствующая композиция двойственных булевых функций (композиция булевых функций – сложная функция, составленная из нескольких булевых функций).
Следствие 1. Если в формуле присутствует только дизъюнкция, конъюнкция и отрицания, то для получения достаточно заменить дизъюнкцию конъюнкцией и наоборот.
Следствие 2. Двойственной к СДНФ является СКНФ.
Из следствия 2 вытекает практический алгоритм преобразования данной формулы в СКНФ, используя двойственность:
найти f*;
преобразовать f* в СДНФ;
еще раз взять двойственную. (f*)*=f=СДНФ*=СКНФ.
Аналогично тому, как с помощью таблицы истинности была получена СДНФ, можно получить СКНФ. Для этого в последнем столбце таблицы выбираем нули, а в исходных наборах 0 заменим переменной, 1 – отрицанием переменной.
Примеры решения задач
Задача
1.
Найти двойственную функцию f*
к функции f=x(y
).
f*=
x(
.
Заметим, что двойственная функция к дизъюнкции является конъюнкцией с сохранением переменных и их отрицаний, и наоборот.
Задача
2.
f=
.Найти
f*.
Решение.
f*=(x
)=
.
Задача 3. Преобразовать СКНФ булеву функцию, заданную формулой (ху)(z+x).
Решение. Действуем по алгоритму:
Находим f*=(ху)(z+x)=(
f*=
Преобразуем ее в СДНФ:
Еще раз возьмем двойственную:
f=(
.
Получили СКНФ, задача решена.
Найдем СКНФ данной функции с помощью таблицы истинности
|
х |
у |
z |
xy |
z |
(xy)(
z |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
0 |
0 |
)В последнем столбце таблицы выберем нули. На исходных наборах 0 соответствует переменной, а 1 ее отрицанию, тогда СКНФ:
Задачи для самостоятельного решения
Задача 1. Преобразовать в СКНФ булеву функцию, заданную формулой
а)
f=(
)(z
);
б)
f=
;
в)
f=(
)
(z
).
Задача 2. По таблице истинности получить СКНФ заданной булевой функции
а)
f=(x
)(zt);
б)
(x
).