Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Преобразование КНФ в СКНФ



Шаг 3.

Если в КНФ есть несколько одинаковых элементарных дизъюнкций, то оставляем только одну - это преобразование приводит к равносильной формуле,т.к. x&x=x.

Шаг 4.

Делаем все элементарные дизъюнкции правильными с помощью следующих двух преобразований:

- если в элементарной дизъюнкции переменная входит со своим отрицанием, то удаляем эту дизъюнкцию из КНФ.

- если некоторая переменная входит в элементарную дизъюнкцию несколько раз, причём либо во всех случаях без отрицаний, либо во всех случаях с отрицаниями, то оставляем только одну эту переменную.

Шаг 5.

Преобразуем правильные дизъюнкции в полные. Пусть в некоторую элементарную дизъюнкцию не входит переменная x, тогда рассмотрим выражение (x ) и повторим шаги 2 и 3. Если недостающих переменных несколько, то проделать аналогичные преобразования со всеми недостающими переменными.





Дата публикования: 2014-11-03; Прочитано: 672 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...