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

19 Членами конъюнкции являются либо сами переменные x 1 ,…,x n , либо их отрицания. Пример 4.3. Приведем примеры конъюнкций. . , , 1 2 4 5 3 4 1 2 x x x x x x x x Определение. Элементарная конъюнкция, в которую включены все переменные, называется основной элементарной конъюнкцией (ОЭК). Пример 4.4. Следующие конъюнкции являются элементарными конъюнкциями от 5 переменных. 1 1 2 3 4 5 2 1 2 3 4 5 5; , . n K x x x x x K x x x x x    В элементарные конъюнкции 1 K и 1 K входят все пять переменных. Лемма 4.1.        . , , ,... , ... i одного x хотябыдля 0 если x x 1 если x x x i i n 1 1 n n 1 2 n 1 2       Доказательство. Пусть  1 =x 1 ,…,  n =x n . Тогда . x x x x 1 1 1 n 1 n 1 x n x 1 n 1         Пусть , k k x   для некоторого k : 1 k n   . Тогда . x x x x x x 1 1 0 1 1 0 n k 1 n k 1 x n x k x 1 n k 1               Определение. Формула m 1 2 k k k      ... , где k i – элементарные конъюнкции, называется дизъюнктивной нормальной формой (ДНФ). Если все k i являются основными элементарными конъюнкциями, то ДНФ называется совершенной (СДНФ). Пример 4.5. Для функций трех переменных ниже приведены ДНФ и СДНФ.