Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

рой — А&—В&С. Построив таким образом элементарные А В с лтс) произведения для этих строк, получим с.д.н.ф.: Л Л л и -А&-пВ&-^С v^&-^B&C v^&B&-nCvA&-^B&-nCv Л Л и и А&В&С. Л И л и Второй метод нахождения с.д.н.ф. - метод Л И и л равносильных преобразований, который состоит в И л л и следующем. Для заданной формы А находим д.н.ф. И л и л (которая всегда существует) и пусть д.н.ф. равна: И и л л D1VD2V vDm (т>1), И и и и где Di(l< i<m) - элементарное произведение. Построенная д.н.ф. может удовлетворять требуемым условиям, тогда это с.д.н.ф. Если в некоторое Д входит некоторая буква вместе с ее отрицанием, то Z)/ - противоречие и из д.н.ф. Д можно исключить. Если при такой процедуре нужно отбросить все слагаемые из д.н.ф., то А - противоречие и с.д.н.ф. не существует. Если в некоторое Д не входит одна из букв Aj формы А, то заменяем Д на равносильную: (Di&Aj)v(Di&-^j). Таким образом, добиваемся, чтобы каждое слагаемое содержало все аргументы формы Л. Если в полученной форме окажутся одинаковые слагаемые, то оставляем только одно из них. В результате получим с.д.н.ф. Совершенной конъюнктивной нормальной формой (с.к.н.ф.) пропозициональной формы A(Ai,A2,...,An) называется к.н.ф. этой формы, удовлетворяющая следующим условиям: -нет одинаковых множителей; -в каждый множитель входят все буквы из пропозициональной формы А один и только один раз (и только они) с отрицанием либо без отрицания. С.к.н.ф. для формулы А можно построить по таблице истинности этой формы. Для этого выбираем строки, где А=Л. Для каждой строки, где А=Л, строим элементарную сумму (конституенту нуля или полную дизъюнкцию) следующим образом. Если в выбранной строке буква Aj принимает значение И, то в ^ она входит с отрицанием, если Aj=JI, то Aj входит в без отрицания. Конъюнкция построенных конституент нуля и будет с.к.н.ф. Рассмотрим пример на построение с.к.н.ф. для указанной формы. Решение. Таблица истинности уже построена. Выберем строки, где Л принимает значение Л, т.е. строки с номерами: 4, б и —i. Для четвертой строки элементарная сумма (конституента нуля) представляется в виде А v —l8 v —С; для шестой в виде: —AvBv—iC, а для седьмой — \ Av —^Bv С. В результате получим с.к.н.ф.: 19