Дискретная математика

71 - в каждое слагаемое входят все переменные xi,x2,:.,x „ один и только один раз (и только они) с отрицанием либо без отрицания. С.д.н.ф. для функции / можно построить по таблице истинности этой функции. Для этого выбираем строки, где функция/равна 1; пусть это будут строки кик2,...,кт- Для каждой выбранной строки ki, 1< i < т, строим конституенту единицы К, следующим образом. Если в выбранной строке к,- переменная Xj принимает значение 1, то в Ki она входит без отрицания, если же Xj=0, то в К, она входит с отрицанием. Дизъюнкция построенных конституент единицы и будет с.д.н.ф. Конституенты единицы, построенные для строк, где функция/равна 1, называются сабственньши конституентсти единицы функцииf. Рассмотрим пример на построение с.д.н.ф. Пример. Пусть функция/(Зс.з'.г^ равна нулю тогда и только тогда, когда принимает значение нуль один и только один из аргументов функции. Найти с.д.н.ф. для f(x,y,z). Решение. Составим таблицу истинности, исходя из задания функции. Выберем строки, где/принимает значение 1, т.е. строки с номерами: 1,2,3,5 и 8. Для первой строки конституента единицы представляется в виде конъюнкции 1 Х&1 У&1 Z, для второй - 1 Х&1 у& Z. Построив таким образом собственные конституенты единицы данной функции, получим с.д.н.ф.: lx&ly&lzvlx&ly&zvlx&y&lzvx&ly&Izvx&y&z. Второй метод нахождения с.д.н.ф. - метод равносильных преобразований. Он применяется, когда булева функция задана в виде формулы и состоит в следующем. Для заданной формулы А находим д.н.ф. (которая всегда существует) и пусть д.н.ф. равна: D/vDjV... v £)„, ( т>\), где Di (1< i<m) ~ элементарное произведение. Построенная д.н.ф. может удовлетворять указанным условиям, тогда это с.д.н.ф. Если в некоторое Д входит хотя бы одна племенная вместе с ее отрицанием, то Д - противоречие и из д.н.ф. Д можно исключить. Если при такой процедуре нужно отбросить все слагаемые из д.н.ф., то Л - противоречие и с.д.н.ф. не существует. Если в некоторое £ ), не входит одна из переменных Xj формулы Л, то заменяем Д на равносильную: (Д,<Ё х^ v{Dj&Ixj). Таким образом, добиваемся, чтобы каждое слагаемое содержало все аргументы формулы А. Если в полученной форме окажутся одинаковые слагаемые, то оставляем только одно из них. В результате получим с.д.н.ф. Правая часть разложения (3.20): X у Z f(x.y.z) О О О \ 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 I 1 0 I 0 1 1 0 0 1 1 1 1