КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Тема 3.2 Совершенная ДНФ. Совершенная КНФ
Совершенной дизъюнктивной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой: 1. различны все члены дизъюнкции; 2. различны все члены каждой конъюнкции; 3. ни одна конъюнкция не содержит одновременно переменную и отрицание этой переменной; 4. каждая конъюнкция содержит все переменные, входящие в формулу, т.е. имеет вид , где дизъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=1. Теорема (о СДНФ). Для всякой не равной тождественному нулю формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СДНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки дизъюнктивных членов. Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой: 1. различны все члены конъюнкции; 2. различны все члены каждой дизъюнкции; 3. ни одна дизъюнкция не содержит переменную вместе с отрицанием этой переменной; 4. каждая дизъюнкция содержит все переменные, входящие в исходную формулу, т. е. имеет вид , где конъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=0. Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки конъюнктивных членов. Опишем два способа приведения к совершенным нормальным формам. 1-й способ – аналитический. Приведение к СДНФ. Алгоритм приведения. 1. привести формулу с помощью равносильных преобразований к ДНФ.
2. удалить члены дизъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся); 3. из одинаковых членов дизъюнкции (если такие окажутся) удалить все, кроме одного; 4. из одинаковых членов каждой конъюнкции (если такие окажутся) удалить все, кроме одного; 5. если в какой-нибудь конъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой конъюнкции член и применить закон дистрибутивности конъюнкции относительно дизъюнкции; 6. если в полученной дизъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3. Полученная формула и является СДНФ данной формулы.
Привести следующие формулы к СДНФ с помощью равносильных преобразований: 1. ; 2. ; 3. . Решение. 1. . 2. 3.
Приведение к СКНФ. Алгоритм приведения. 1. привести формулу с помощью равносильных преобразований к КНФ. 2. удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся); 3. из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного; 4. из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного; 5. если в какой-нибудь дизъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член и применить закон дистрибутивности дизъюнкции относительно конъюнкции; 6. если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3. Полученная формула и является СКНФ данной формулы.
Привести следующие формулы к СКНФ с помощью равносильных преобразований: 1. ; 2. . Решение. 1. 2. 2-й способ – табличный. Составляем таблицу истинности для данной функции. Приведение к СДНФ. Алгоритм приведения. Строим таблицу значений формулы. Рассматриваем только те строки, в которых значение формулы равно единице. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем, аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций.
Построить СДНФ для данных формул логики высказываний. 1. . 2. Решение. 1. . Строим таблицу истинности для формулы F:
Рассматриваем только 4, 5 и 7 наборы, так как только на этих наборах формула принимает значение равное единице. СДНФ имеет вид: 2. 2. Строим таблицу истинности для формулы F:
СДНФ (1): № 3: F = x y.
Приведение к СКНФ. Алгоритм приведения. Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием. Наконец, образуют конъюнкцию полученных дизъюнкций.
Построить СКНФ для данных формул логики высказываний. 1. . 2. Решение. 3. Строим таблицу значений, используя предыдущий пример.
Рассматриваем только наборы, на которых формула принимает значение ноль. СКНФ (0): № 0, 1, 2, 3, 6: 4. Строим таблицу значений, используя предыдущий пример.
СКНФ (0): № 0, 1, 2:
Дата добавления: 2014-01-04; Просмотров: 548; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |