Математическая логика и теория алгоритмов

С.к.н.ф. для пропозициональной формы А можно построить по таблице истинности этой формы. Для этого выбираем строки, где А=Л. Для каждой строки, гд,еЛ~Л, строим элементарную сумму (кон- ституенту нуля) следующим образом. Если в выбранной строке буква принимает значение И,гов R? она входит с отрицанием, если Aj=JI, то А/ входит в К° без отрицания. Конъюнкция построенных конституент нуля и будет с.к.н.ф. Рассмотрим пример на построение с.к.н.ф. для рассмотренной пропозициональной формы. Решение. Таблица истинности уже построена. Выберем строки, где Л принимает значение Л, т. е. строки с номерами: 4, 6 и 7. Для чет­ вертой строки элементарная сумма (конституента нуля) представляет­ ся в виде B V L C ; для шестой в виде; 1 А У В \ Л С , а для седьмой ~ IAVIBVC . В результате получим с.к.н.ф.: v ] S v ] С)&(1^ v S v l С)&(1 Av^ BvQ. Второй метод построения с.к.н.ф. - метод равносильных пре­ образований - заключается в следующем. Для заданной формы А находим к.н.ф., которая имеет вид Ki&K2&...&K „„ затем добиваемся выполнения указанных условий. Если в Ki входит некоторая буква вместе с ее отрицанием, то Kj -тавтология и из к.н.ф. множитель/Г/ можно исключить. Если при такой процедуре нужно отбросить все множители из к.н.ф., то А - тавтология и с.к.н.ф. не существует. Если некоторый множитель к.н.ф., например К,, не содержит букву А, то вводим ее согласно равносильности К, ~( K,VA)&.{K,'J\A). Таким образом, добиваемся, чтобы каиодый множитель к.н.ф, содержал все аргументы исходной формы/1. Если в некотором множнггеле окажутся одинаковые слагаемые, то оставляем только один из них. Если в полученной форме окажутся одинаковые множители, то оставляем только один из них. В результа­ те получим с.к.н.ф. 36