3. Совершенная дизъюнктивная нормальная форма

 

Как уже указывалось, логическая функция n-переменных f(x₁, x₂, ..., x_n) может быть задана таблицей истинности, в которой значение функции f_i принимает значение 0 или 1.

СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице истинности f ; каждому единичному набору (x₁, x₂, ..., x_n) соответствует конъюнкция всех переменных, в которой x_i взято с отрицанием, если x_i = 0, и без отрицания, если x_i = l. Таким образом, существует взаимнооднозначное соответствие между таблицей функции f(x₁, x₂, ..., x_n) и ее СДНФ, и, следовательно, СДНФ для всякой логической функции единственна (точнее, единственна с точностью до порядка букв и конъюнкций: это означает, что ввиду коммутативности дизъюнкции и конъюнкции, формулы, получаемые перестановкой конъюнкций и букв в конъюнкции, не различаются и считаются одной и той же СДНФ).

В совершенной дизъюнктивной нормальной форме логическая функция выражается через три функции: конъюнкцию (логическое умножение), дизъюнкцию (логическое сложение) и инверсию (отрицание). Формулы, содержащие кроме переменных (и, разумеется, скобок) только знаки функций дизъюнкции, конъюнкции и отрицания, называют булевыми

Таким образом, для того чтобы записать совершенную дизъюнктивную нормальную форму логической функции, необходимо выбрать те наборы аргументов, на которых логическая функция принимает значение 1. Представить каждый такой набор в виде произведения всех переменных, заменив в наборах значения 1 на значение соответствующей переменной, а значение 0 – на инверсное (отрицание), и соединить эти логические произведения переменных знаками дизъюнкции. Это правило еще называют правилом записи логической функции по единицам.

 

Совершенная конъюнктивная нормальная форма

Если рассматриваемая логическая функция n-переменных принимает значение 1 на большинстве из 2ⁿ наборов аргументов, то ее представление в совершенной дизъюнктивной нормальной форме будет достаточно громоздким. В этих случаях удобнее использовать другую форму представления логической функции – совершенную конъюнктивную нормальную форму (СКНФ).

Для того чтобы записать совершенную конъюнктивную нормальную форму логической функции, необходимо выбрать те наборы аргументов, на которых логическая функция принимает значение 0. Представить каждый такой набор в виде логической суммы всех n переменных, заменив в наборах значение 1 на инверсное значение соответствующей переменной, а значение 0 – на прямое значение соответствующей переменной, и соединить эти логические суммы переменных знаком конъюнкции. Это правило называют правилом записи логической функции по нулям.