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

22 (ОЭК) (Таблица 5.1). Заметим, что ОЭК строятся на значениях функции равных 1, переменные x 1 и x 2 берутся с отрицанием, если на данном наборе принимают значение 0, иначе без отрицания. Таблица 5.1 x 1 x 2 x 1  x 2 Основные элементарные конъюнкции (ОЭК) 0 0 1 1 2 x x 0 1 1 1 x x 2 1 0 0 - 1 1 1 x 1 x 2 Полученные ОЭК записываем в ответ через дизъюнкции, получаем СДНФ. 1 2 1 2 1 2 1 2 1 1 1 2 0 1 0 2 0 1 1 2 f x x x x x x x x x x x x x x       ( , ) . Представление логических функций булевыми формулами Представить логическую функцию булевой формулой – это значит представить f в виде формулы через отрицание, конъюнкцию и дизъюнкцию. Если f x x 0 n 1  ) ,..., ( , то по следствию 4.2 1 1 1 1 1 ,..., ( ,..., ) 1 ( ,..., ) n n n n n f f x x x x          – СДНФ т.е. булевой формулой для f(x 1 ,…,x n ) может служить ее СДНФ. Если же f(x 1 ,…,x n )  0 , то f(x 1 ,…,x n ) = x 1 1 x . Сформулируем изложенные результаты в виде Теоремы 5.1. Всякая логическая функция может быть представлена булевой формулой. (без доказательства) Совершенная конъюнктивная нормальная форма (СКНФ) Определение. Выражение вида 1 2 1 2 ... n n x x x       называется элементарной дизъюнкцией.