Построение сокращенной д.н.ф. для не всюду определенной (частичной) булевой функции

Построение сокращенной д.н.ф. булевой функции, заданной к.н.ф.

Лекция 6

В прошлый раз говорилось, что нас в основном будет интересовать случай, когда функция задана множеством нулей и когда задана конъюнктивной нормальной формой (КНФ). вида , где – элементарная дизъюнкция (э.д.), .

Напомню, что если каждая из дизъюнкций содержит в точности слагаемых, то КНФ называют совершенной. Известным фактом (см. лекцию 4) является

Утверждение 1. Задание множества нулей функции (множества ) равносильно заданию ее совершенной КНФ

Пусть функция задана КНФ вида . Через будем обозначать сокращенную ДНФ функции .

Рассмотрим задачу преобразования КНФ в в случае, когда - совершенная КНФ. Нам понадобятся приводимые ниже утверждения 2 и 3.

Утверждение 2. Э.к. является допустимой для тогда и только тогда, когда каждая дизъюнкция ,, содержит хотя бы один множитель из .

Доказательство. 1. Пусть ‑ допустимая конъюнкция для . Покажем, что каждая дизъюнкция , , содержит хотя бы один множитель из .

Предположим противное. Пусть некоторая дизъюнкция не содержит ни одного множителя из . Не ограничивая общности можно считать, что . Тогда имеет вид

.

Рассмотрим набор . По построению . С другой стороны, набор обращает в 0 и, следовательно, . Противоречие.

2. Пусть каждая дизъюнкция , , содержит некоторый множитель из . Тогда, очевидно, любой набор из обращает КНФ в 1, т.е. принадлежит .

Утверждение доказано.

Утверждение 3. Э.к. ранга является неприводимой для тогда и только тогда, когда в КНФ можно указать дизъюнкций таких, что каждая дизъюнкция содержит в точности один множитель из и, если ,, , то дизъюнкции и содержат разные множители из .

Доказательство. 1. Пусть э.к. является неприводимой для и пусть условие утверждения не выполнено. Это означает, что в можно указать переменную такую, что для каждой дизъюнкции в исходной КНФ выполнено одно из двух следующих условий:

1) не содержит ;

2) содержит и содержит некоторую другую переменную из .

Удалим из . Получим э.к. . Обозначим через множество дизъюнкций в исходной КНФ, не содержащих переменные из , через аналогичное множество для . Очевидно, и . Отсюда следует, что . Противоречие.

2. Пусть для э.к. выполнено условие утверждения. Покажем, что ‑ неприводимая конъюнкция.

Предположим противное. Тогда можно указать э.к. такую, что и . Э.к. получается из удалением хотя бы одного множителя . В исходной КНФ есть дизъюнкция, содержащая и не содержащая ни одного другого множителя из . Таким образом, и, значит, . Противоречие.

Утверждение доказано.

Утверждения 2 и 3 являются соответственно критериями допустимости и неприводимости э. к. для функции, заданной совершенной КНФ.

Приведем описание двух алгоритмов построения ДНФ .

Дата добавления: 2014-01-11