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

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

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

D = х₁ ^1  ...  х_n ^n ,

где х_i ^{ i} = х_i при  _i =1 и х_i ^i = х_i при  _i =0 (1  i  n).

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

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

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

x	y	z	F	Д 1	Д 2	Д 3
0	0	0	1	1	1	1
0	0	1	1	1	1	1
0	1	0	0	0	1	1
0	1	1	0	1	0	1
1	0	0	1	1	1	1
1	0	1	0	1	1	0
1	1	0	1	1	1	1
1	1	1	1	1	1	1

Решение. Функция принимает значение 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₂ = (х, у, z); S₃ = (х,у, 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))] .

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

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

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