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

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

Логическую функцию n аргументов, которая принимает значение, равное единице, только на одном наборе аргументов называют конституентой единицы. Конституенту единицы выражают через логическое произведение (конъюнкцию) всех аргументов x_i, каждый из которых входит в это произведение со знаком инверсии (отрицания), если x_i = 0, или без него, если x_i =1.

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

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

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

Из сказанного выше следует, что всякая логическая функция может быть представлена булевой формулой, т.е. как суперпозиции конъюнкции, дизъюнкции и отрицания.

Действительно, для всякой функции, кроме константы 0, таким представлением может служить ее СДНФ. Константу 0 можно представить булевой формулой`хх.

Пример 4.2.

Представим в совершенной дизъюнктивной нормальной форме функцию штрих Шеффера из табл. 4.3: f₁₄(x,y) = x | y.

Таблица 4.4

Подставив конституенты единицы через конъюнкцию аргументов, получим

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

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

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

Конституентой нуля называют логическую функцию n переменных, которая принимает значение, равное нулю, только на одном наборе.

Конституенту нуля можно представить в виде дизъюнкции всех ее переменных, часть из которых может быть без отрицания, а часть с отрицанием.

То есть чтобы записать конституенту нуля, равную нулю на i-том наборе переменных, следует в дизьюнкции всех аргументов расставить отрицания над теми переменными, которые в этом наборе принимают значения, равные единице. Таким образом, в конституенте нуля отрицания ставятся над теми переменными, над которыми в конституенте единицы с тем же индексом отрицания нет.

В связи с тем, что число различных наборов от n переменных равно 2ⁿ, число различных конституент нуля равно 2ⁿ.

Обозначим конституенты нуля буквой Z с индексом, равным номеру набора, на котором конституента обращается в нуль.

Совершенной конъюнктивной нормальной формой называется произведение конституент нуля, которые равны нулю на тех же наборах, что и заданная функция.

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

При этом любая логическая функция имеет единственную совершенную конъюнктивную нормальную форму.

Термин «совершенная» опускают, т.е. говорят просто о нормальной дизъюнктивной (ДНФ) или нормальной конъюнктивной форме (КНФ) в тех случаях, когда не требуется, чтобы каждый член этой формы обязательно содержал конъюнкцию или соответственно дизъюнкцию всех переменных.

Пример 4.3.

Представим в совершенной конъюнктивной нормальной форме функцию стрелка Пирса из табл. 4.3: f₈(x,y) = x ¯ y.

Таблица 4.5

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

Пример 4.4.

Представим функцию штрих Шеффера в СДНФ и СКНФ.

Таблица 4.6

СДНФ ® f₁₄(x,y) = f₀ × K₀ Ú f₁ × K₁ Ú f₂ × K₂ Ú f₃ × K₃ = 1× K₀ Ú 1× K₁ Ú 1× K₂ Ú 0× ×K₃ = K₀ Ú K₁ Ú K₂ =`x`y Ú`x y Ú x`y.

СКНФ ® f₁₄(x,y) = (f₀ Ú Z₀) × (f₁ Ú Z₁) × (f₂ Ú Z₂) × (f₃ Ú Z₃) = (1Ú Z₀) × (1 Ú Z₁) × ×(1 Ú Z₂) × (0 Ú Z₃) =1×1×1×Z₃ = Z₃ = `x Ú`y.

Получаем эквивалентные выражения для функции f₁₄ штрих Шеффера:

f₁₄(x,y) = `x`y Ú`x y Ú x`y = `x Ú`y.