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

20 1 2 1 3 2 3 1 2 3 1 2 3 3; ДНФ, СДНФ. n x x x x x x x x x x x x       Отличие заключается в том, что в СДНФ обязательно должны участвовать все три переменные одновременно, а для ДНФ нет. Разложение булевых функций по переменным Теорема 4.2. (о разложении функций по переменным). Каждую функцию алгебры логики f(x 1 ,…,x n ) при любом m, 1  m  n , можно представить в следующей форме: ) ,..., , ,..., ( ) ,..., , ,..., ( ,.., n 1 m m 1 1 m n 1 m m 1 x x x x f x f x x x m 1 1 m            , (4.1) где дизъюнкция берется по всем возможным наборам значений переменных x 1 ,…,x m . Это представление называется разложением функции по m переменным x 1 ,…,x m . Доказательство. Теорема доказывается подстановкой в обе части равенства (4.1) произвольного набора ( n 1 m m 1     ,..., , ,...,  ) всех n переменных. Левая часть (4.1) дает f(  1 ,…,  n ). Правая – 1 1 1 1 1 1 ,..., 1 1 1 1 ( ,..., , ,... ) ( ,..., , ,..., ) ( ,..., ). m m m m m m n m m m n n f f f                           Получаем, что левая и правая части равны, ч.т.д. В качестве следствия получим два специальных случая разложения. Следствие 4.1. Разложение по k -ой переменной ) ,..., , , ,..., ( ) ,..., , , ,..., ( ) ,..., , , ,..., ( n k 1 k 1 1 k n k 1 k k 1 1 k n k 1 k k 1 1 x x x f x x 0 x x f x x 1 x x f x x x x          Следствие 4.2. Разложение по всем n переменным