Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм приведения к СКНФ c помощью равносильных преобразований
1. привести формулу с помощью равносильных преобразований к КНФ. 2. удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся); 3. из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного; 4. из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного; 5. если в какой-нибудь дизъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член и применить закон дистрибутивности дизъюнкции относительно конъюнкции; 6. если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3. Полученная формула и является СКНФ данной формулы. Пример. Привести следующие формулы к СКНФ с помощью равносильных преобразований: 1. ; 2. . Решение. 1. 2. 2-й способ – табличный.
|