Читайте также:
|
|
Шаг 3.
Если в КНФ есть несколько одинаковых элементарных дизъюнкций, то оставляем только одну - это преобразование приводит к равносильной формуле,т.к. x&x=x.
Шаг 4.
Делаем все элементарные дизъюнкции правильными с помощью следующих двух преобразований:
- если в элементарной дизъюнкции переменная входит со своим отрицанием, то удаляем эту дизъюнкцию из КНФ.
- если некоторая переменная входит в элементарную дизъюнкцию несколько раз, причём либо во всех случаях без отрицаний, либо во всех случаях с отрицаниями, то оставляем только одну эту переменную.
Шаг 5.
Преобразуем правильные дизъюнкции в полные. Пусть в некоторую элементарную дизъюнкцию не входит переменная x, тогда рассмотрим выражение
(x
) и повторим шаги 2 и 3. Если недостающих переменных несколько, то проделать аналогичные преобразования со всеми недостающими переменными.
Дата добавления: 2015-04-20; просмотров: 105 | Поможем написать вашу работу | Нарушение авторских прав |