Форум программистов, компьютерный форум CyberForum.ru

Алгоритм приведения к КНФ/ДНФ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.82
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.03.2011, 11:30     Алгоритм приведения к КНФ/ДНФ #1
Что-то я запарился, никак придумать не могу...

Допустим имеется у нас формула

x&y|z
Дерево разбора строится как.

Код
 
               &
           x       |
               y         z
С построением такого дерева проблем нету... Но вот как программно это привести к КНФ или в ДНФ?
Прошу совета по поводу алгоритма. Заранее спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
24.03.2011, 13:29     Алгоритм приведения к КНФ/ДНФ #2
Сначала надо вычислить значение формулы на всех возможных наборах переменных (т.е. построить таблицу истинности формулы). Затем:

1. Для КНФ:
Находим строку таблицы истинности, где формула ложна (равна нулю). Берём все переменные в этой строке и делаем их логическую сумму (дизъюнкт), причём, если переменная ложна, то она входит в дизъюнкт как есть, а если истинна - то входит в дизъюнкт с отрицанием. Строим такие дизъюнкты из всех наборах переменных (строках таблицы), где формула ложна. Затем строим конъюнкцию полученных дизъюнктов - вот вам и КНФ.
2. Для ДНФ:
Здесь всё наоборот. Т.е. мы строим ТИ, выбираем все единичные строки, строим конъюнкты всех входящих в эти строки переменных, причём если переменная истинна, она входит в конъюнкт как есть, а если ложна - входит в него с отрицанием, и затем строим дизъюнкцию всех полученных элементарных конъюнктов. ДНФ готова.
Фух, вроде ничего не напутал...
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.03.2011, 13:40  [ТС]     Алгоритм приведения к КНФ/ДНФ #3
silent_1991, И для программной реализации другого метода, я так понимаю нету?
Т.е. аналогично нужно будет делать через таблицы истины и посылать значение каждой строки в дерево (расписывать по переменным), ну или как-то так, сейчас сформулировать затрудняюсь?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
24.03.2011, 13:47     Алгоритм приведения к КНФ/ДНФ #4
ForEveR, да, полагаю, это наиболее тупой и простой, но в то же время наиболее эффективный (в плане реализации) метод. Есть ещё аналитический метод, который в принципе можно запрограммировать, но я бы с ним возиться не стал, поскольку приведённый алгоритм вполне сносный. Конечно, он может долго работать на большом наборе переменных...
И да, если результат нужно получить в виде дерева, то сразу можно посчитать, сколько строк таблицы нулевые (ненулевые), в корень записывать &, затем в левого ребёнка &, в правого & и т.д., пока счётчик соответствующих (нулевых / ненулевых) строк не обнулится, ну а потом в каждого из полученных детей начинаем впихивать || в количестве переменных, входящих в формулу, а затем в листы сами эти переменные или их отрицания. Надеюсь, понятно)) Ну да вы и без меня, я думаю, поняли, что делать)))
onlwork
1 / 1 / 0
Регистрация: 10.11.2013
Сообщений: 53
22.11.2013, 00:00     Алгоритм приведения к КНФ/ДНФ #5
Цитата Сообщение от silent_1991 Посмотреть сообщение
Сначала надо вычислить значение формулы на всех возможных наборах переменных (т.е. построить таблицу истинности формулы). Затем:

1. Для КНФ:
Находим строку таблицы истинности, где формула ложна (равна нулю). Берём все переменные в этой строке и делаем их логическую сумму (дизъюнкт), причём, если переменная ложна, то она входит в дизъюнкт как есть, а если истинна - то входит в дизъюнкт с отрицанием. Строим такие дизъюнкты из всех наборах переменных (строках таблицы), где формула ложна. Затем строим конъюнкцию полученных дизъюнктов - вот вам и КНФ.
2. Для ДНФ:
Здесь всё наоборот. Т.е. мы строим ТИ, выбираем все единичные строки, строим конъюнкты всех входящих в эти строки переменных, причём если переменная истинна, она входит в конъюнкт как есть, а если ложна - входит в него с отрицанием, и затем строим дизъюнкцию всех полученных элементарных конъюнктов. ДНФ готова.
Фух, вроде ничего не напутал...
Извините, но это СКНФ и СДНФ
Yandex
Объявления
22.11.2013, 00:00     Алгоритм приведения к КНФ/ДНФ
Ответ Создать тему
Опции темы

Текущее время: 08:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru