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

23 Членами дизъюнкции являются либо 1 ,..., n x x , либо их отрицания. Пример 5.2. Приведем примеры элементарных дизъюнкций: . , , 1 2 4 5 3 4 1 2 x x x x x x x x      Определение. Элементарная дизъюнкция, в которую включены все переменные, называется основной элементарной дизъюнкцией (ОЭД). Пример 5.3. Примеры для функции пяти переменных основных элементарных дизъюнкций приведены ниже. 1 2 3 4 5 1 2 3 4 5 5; , n x x x x x x x x x x          . Определение. Формула 1 2 m D D D     , где D i – элементарные дизъюнкции, называется конъюнктивной нормальной формой (КНФ). Если все D i являются основными элементарными дизъюнкциями, то КНФ называется совершенной (СКНФ). Пример 5.4. Для функции 3 переменных приведем примеры КНФ и СКНФ. n=3; 1 2 1 3 2 3 ( )( )( ) x x x x x x    - КНФ, 1 2 3 1 2 3 ( )( ) x x x x x x     - СКНФ. В отличие от КНФ в СКНФ в скобках участвуют все три переменные. Спрашивается, нельзя ли произвольную функцию алгебры логики представить в виде СКНФ? Покажем, что при f 1  это возможно. Пусть f x x 1 n 1  ) ,..., ( . Разложим функцию f * (x 1 ,…,x n ) (очевидно f x x 0 n 1  ) ,..., ( * ) в СДНФ: 1 1 * 1 * 1 1 ,..., ( ,..., ) 1 ( ,..., ) n n n n n f f x x x x         