Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

21 ). ,..., ( ) ,..., ( ,..., n 1 n 1 n 1 x x f f x x n 1 n 1          Но 0 f n 1  ) ,..., (   либо . ( , , ) 1 f n 1     Следовательно, при f x x 0 n 1  ) ,..., ( оно может быть преобразовано к виду , ) ,..., ( ) ,..., ( ,..., ,..., n 1 n 1 n 1 n 1 n 1 n 1 1 f n 1 n 1 x x x x f                   т.е. n 1 n 1 n 1 n 1 1 f n 1 x x f x x           ) ,..., ( ,..., ) ,..., ( – СДНФ. Отсюда вытекает порядок построения СДНФ по функции, заданной таблицей. 5. Построение СДНФ для функции, заданной таблицей СКНФ. Основные эквивалентные преобразования Построение СДНФ для функции, заданной таблицей На предыдущей лекции была доказана теорема о разложении функций по переменным. В качестве следствия из нее получено разложение функций по всем переменным, являющееся СДНФ. Данное следствие носит конструктивный характер, т.к. оно по таблице функции позволяет построить формулу, являющуюся СДНФ (если 0 f  ). СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице f ; каждому «единичному» набору (  1 ,…,  n ), т.е. набору, на котором значение функции равно 1, соответствует конъюнкция всех переменных, в которой x i взято с отрицанием, если  i =0, и без отрицания, если  i =1. Пример 5.1. Записать СДНФ для функции x 1  x 2 . Запишем в табличном виде данную функцию, и все соответствующие основные элементарные конъюнкции