Конституенты нуля. Совершенные конъюнктивные и шефферовы нормальные формы

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

Определение. Пусть на наборе`a ⁿ =(a₁, ... ,a_n ) булева функция f (х ⁿ)принимает значение 0. Дизъюнктивной конституентой нуля функции f назовем дизъюнкцию вида

D = х₁^Øa1Ú ... Ú х_n ^Øan ,

где х_i ^{Øa i} = `х_i при a _i =1 и х_i ^Øai = х_i при a _i =0(1£ i £ n).

Аналогично шефферовой конституентой нуля функции f назовем подстановку вида S =| (х₁ ^a1 , ... , х_n^an).

Как дизъюнктивная, так и шефферова конституенты нуля, соответствующие набору`a ⁿ , принимают значение 0 только на нем. На всех остальных наборах они равны 1.

Пример 3. Построить все дизъюнктивные и шефферовы конституенты нуля функции, заданной таблицей истинности.

Решение. Функция принимает значение 0 на наборах (0, 1, 0), (0, 1, 1), (1, 0, 1). На наборе (0, 1, 0) дизъюнктивная конституента нуляД₁= хÚуÚz, на наборе(0, 1, 1)Д₂=хÚуÚz , на наборе(1, 0, 1)Д₃ =`хÚуÚz . В таблице дополнительно указаны векторы истинности конституент Д₁ — Д₃. Каждая из них выделяет ровно один из нулей в векторе истинности исходной функции.

Шефферовы конституенты получаем из Д₁ — Д₃, инвертируя внутренние переменные в них и заменяя дизъюнкцию функцией Шеффера. В итоге получим: S₁ =| (х, у,`z); S<sub>2</sub> =|(х, у, z); S<sub>3</sub> =| (х,`у, z). Поскольку преобразование эквивалентное, векторы истинности S₁— S₃совпадают с векторами для Д₁ — Д₃.

Определение. Совершенной конъюнктивной нормальной формой (СКНФ) булевой функции f (х ⁿ) называют выражение вида:

f = D₁& ... & D_р,

где D₁, ... , D_р — дизъюнктивные конституенты нуля функции.

Совершенной шефферовой нормальной формой (СШНФ) булевой функции f ( х ⁿ)называют выражение вида:

f = Ø|( S₁, ... , S_р ) ,

где S₁, ... , S_р — шефферовы конституенты нуля функции f (`х ⁿ).

СКНФ, как и все КНФ, являются функциями в базисном наборе {Ø, &, Ú}. СШНФ можно наряду с основным представлением задать в однофункциональном базисном наборе {|}.

Пример 4. Построить СКНФ и СШНФ (для каждого из базисных наборов {Ø, |} и {| }) функции f = (11001011)из Примера 3.

Решение.

1. Дизъюнктивные конституенты нуляД₁ — Д₃найдены в Примере 3. СКНФ получаем, логически умножая их:

f = (х Ú`у Ú z) & (х Ú `у Ú`z) & (х Ú у Ú`z).

2. Шефферовы конституенты S₁— S₃также были найдены в Примере 3. СШНФ в базисном наборе {Ø, |}получаем, подставляя S₁— S₃в функцию Шеффера с последующим её инвертированием:

f =Ø| (| (x, y, z),| (x, y, z),|(x,`y, z)) .

СШНФ в базисном наборе {|}имеет вид:

f =|[|(|((x,х), y, (z,z)), | ((x,x), y, z), | ( x,( y,y), z )), |(| ((x,х), y, (z,z)), | ((x,x), y, z), | (x,( y,y), z))] .

Искомые формы построены.

СКНФ и СШНФ существуют только для функций, не равных тождественной единице. В случае, когда вектор истинности функции имеет только один нуль, ее СКНФ и СШНФ являются вырожденными.

Рассмотренные выше ДНФ, КНФ, ВНФ и ШНФ допускают неединственное представление функций. Совершенные формы являются их частными случаями.

Полиномы Жегалкина

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

Определение. Произведением над множеством переменных Х=(х₁, ... , х_n ) называют выражение вида:

P = х_i1& . . . & х_is,

где (х_{i1, ... ,} х_is )Í Х .

Определение. Полиномом Жегалкина булевой функции f(хⁿ)называют выражение вида :

f =a₀ Åa₁P₁Å ... Åa _k P_k,

где (P₁, ..., P_k) – все возможные произведения над множеством переменных Х=(х₁, ... , х_n), a ₀ , a₁, ... ,a _k - булевы константы (0 или 1), знак Åозначает сумму по модулю 2.

Произведения, входящие в полином с нулевыми коэффициентами, обычно просто опускают.

Полиномы Жегалкина задают разложение функций в базисном наборе {0, 1, &, Å}. Функция &—пороговая, функции (0, 1, Å) - симметричные. В виде полинома Жегалкина может быть представлена любая булева функция. Рассмотрим первый метод определения полинома по таблице истинности функции.