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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вырезать номер из смс http://www.cyberforum.ru/cpp-beginners/thread263151.html
реализовать функцию "ВЫРЕЗАТЬ ТЕЛЕФОННЫЙ НОМЕР Из СМС"
C++ Записать парадигму Записать парадигму (все падежи) для прилагательного мужского рода C++ http://www.cyberforum.ru/cpp-beginners/thread263150.html
Алфавитная соритровка структур из файла C++
Всем доброе утро. struct zapchasti { char firma; char tovar; int kol; int cena; int garantia;
C++ Функции по обработке строк!
Записать числа от 1 до 100 словами.
C++ Вывести числа от 1 до 100 словами используя строки http://www.cyberforum.ru/cpp-beginners/thread263143.html
НАдо вывести числа от 1 до 100 словами используя строки. При чём предусмотреть возможность ввода числа, и вывода его названия. Обязательна кирилица.
C++ Записать время (час: мин) словами. Записать время (час: мин) словами. C++ подробнее

Показать сообщение отдельно
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
24.03.2011, 13:29
Сначала надо вычислить значение формулы на всех возможных наборах переменных (т.е. построить таблицу истинности формулы). Затем:

1. Для КНФ:
Находим строку таблицы истинности, где формула ложна (равна нулю). Берём все переменные в этой строке и делаем их логическую сумму (дизъюнкт), причём, если переменная ложна, то она входит в дизъюнкт как есть, а если истинна - то входит в дизъюнкт с отрицанием. Строим такие дизъюнкты из всех наборах переменных (строках таблицы), где формула ложна. Затем строим конъюнкцию полученных дизъюнктов - вот вам и КНФ.
2. Для ДНФ:
Здесь всё наоборот. Т.е. мы строим ТИ, выбираем все единичные строки, строим конъюнкты всех входящих в эти строки переменных, причём если переменная истинна, она входит в конъюнкт как есть, а если ложна - входит в него с отрицанием, и затем строим дизъюнкцию всех полученных элементарных конъюнктов. ДНФ готова.
Фух, вроде ничего не напутал...
2
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru