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

Рассмотрим пример на построение с.д.н.ф. Пусть форма А{А,В,С) ложна тогда и только тогда, когда ложен один и только один из аргументов. Найти с.д.н.ф. ТЯА{А,В,С). Р е ш е н и е . Составим таблицу истинности. Выберем строки, где А принимает значение И, т.е. строки с номерами: 1, 2, 3, 5 и 8. Для первой строки элементарное произведе­ ние представляется в виде конъюнкции "U&1 В<й1с, для второй - В&С. Построив таким образом элементарные произведения для этих строк, получим с.д.н.ф.: 1/г&1 B&1Cv"U&l 5&Cy'U&5&lCv^&l B&^CvA&B&C. Второй метод наховдения с.д.н.ф. - метод равносильных пре­ образований, который состоит в следующем. Для заданной формы А находим д.н.ф. (которая всегда существует) и п>'сть д.н.ф. равна: Di v D 2V... vD, „ { т> 1 ), где Di{]< i<m) - элементарное произведение. Построенная д.н.ф. может удовлетворять требуемым условиям, тогда это с.д.н.ф. Если в Di входит некоторая буква вместе с ее отрицанием, то DI - противоречие и из д.н.ф. D, можно исключить. Если при такой процедуре нужно отбросить все слагаемые из д.н.ф., то А - противо­ речие и с.д.и.ф. не существует. Если в некоторое Д- не входит одна из букв AJ формы А, то 'лшеияем Di на равносильную: (i)/&A jM DiSclij). Таким образом, добиваемся, чтобы каждое слагаемое содержало все аргументы формы Если в полученной форме окажутся одинаковые слагаемые, то оставляем только одно из них. В результате гюлучим с.д.н.ф. Совершенной конъюнктивной нормальной формой (с.к.н.ф.) пропозициональной формы называется к.н.ф. этой фор­ мы, удовлетворяющая следующим условиям: - нет одинаковых множителей; - в калсдый множитель входят все буквы из пропозициональ­ ной формы А один и только один раз (и только они) с отрица­ нием, либо без отрицания. 35