Представление булевой функции СДНФ и СКНФ

(проблема разрешимости).

Пусть булева функция f(x₁,…,x_n)задана своей таблицей, и пусто f не является тождественным нулём. Каждому набору значений переменных, для которого f равна 1 составим элементарную конъюнкцию по следующему правилу: если в наборе x_i=1, то в конъюнкцию войдёт x_i, а если x_i=0, то _i. Дизъюнкция всех таких конъюнкций и будет ДНФ, равносильной данной функции. Она называется совершенной ДНФ (СДНФ). Число слагаемых в такой сумме равно числу наборов, для которых f равно 1, а сами слагаемые определяются единственным образом по этим наборам.

Аналогично строится совершенная КНФ. Если f не является тождественной 1, то каждому набору, для которого f равна 0, сопоставляется элементарная дизъюнкция: если x_i=0, то входит x_i, а если x_i=1, то входит _i. Конъюнкция всех таких дизъюнкций равносильна f.

Пример 1. Построить СДНФ и СКНФ, равносильные функции

fº

Пример 2. Построить СДНФ и СКНФ для функции, заданной столбцом своих значений (11001110).

Мы уже говорили, что для удобства наборы располагаются в порядке, соответствующем двоичной записи порядкового номера. Так, данная функция f принимает значение 1 для наборов с номерами 0,1,4,5,6, т.е. для наборов: 000, 001,100,101,110, а потому

fº

Поскольку f равна 0 для наборов 010,011 и 111, то fº

Замечание 1. Если функция f задаётся 2^k своими значениями, то совершенные нормальные формулы для f содержит k переменных. Если число существенных переменных меньше k, то для f можно построить совершенные нормальные формы с меньшим числом переменных.

Замечание 2. Если СДНФ функции f содержит r слагаемых, то СКНФ содержит 2^k - r сомножителей, где k - число переменных функции f.

Дадим теперь аналитическое определение СДНФ и СКНФ.

Определение. Совершенной дизъюнктивной нормальной формулой (СДНФ) от переменных x₁, x₂,…, x_k называется ДНФ, обладающая следующими свойствами:

1. Нет одинаковых конъюнкций.

2. Каждая конъюнкция для каждого переменного x_i содержит либо x_i, либо _i, но не может содержать их одновременно.

3. Все сомножители в каждой конъюнкции различны.

Аналогично определяется совершенная конъюктивная нормальная формула (СКНФ) заменой слова "конъюнкция" на слово "дизъюнкция".