Дизъюнктивная совершенная нормальная форма.

 

Введем в рассмотрение характеристическую функцию единицы F _a (X _n-1,…X _i,…X ₁,X ₀), которая равна 1 на наборе значений переменных (X _n-1,…X _i,…X ₁,X ₀), обозначенном a, и равна 0 на всех остальных наборах.

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

 

Пример.

 

F ₂ (X,Y,Z,W) – характеристическая функция единицы для набора значений переменных (X,Y,Z,W) с номером 2. (0010 = 2).

В таблице представлены функции F ₃ и F ₅ , которые принимают значение 1 на наборах №3 и 5, соответственно (отсчет начинается с набора №0).

 

X	Y	Z	F3	F5

 

Теорема 1.

Любая бф не равная константе 0 может быть представлена в виде

(X _n-1,…X _i,…X ₁,X ₀) = F _a1 F _a2 … F _ai = F _{a i}, при условии, что a _iÎ M ₁^*, где M ₁^* - множество всех номеров, на которых F(X _n-1,… X _i,… X ₁, X ₀) равна 1.

Доказательство:

 

Возьмем произвольный набор с номером a.

Пусть на этом наборе F(X _n-1,…X ₁, X ₀) = 1.

Тогда в правой части равенства найдется F _a (X _n-1, …X _i,…X ₁,X ₀) и правая часть будет иметь вид 1 F, тоесть значения левой и правой части совпадают.

Если на наборе с номером a мы имеем F(X _n-1, …X _i,…X ₁,X ₀) = 0, то справа не будет F _a , и правая часть будет иметь вид 0 0 … 0, то есть будет равна 0.

Таким образом, значения левой и правой части всегда совпадают.

 

Следствие.

 

Любая бф не равная константе 0 может быть представлена в виде

F(X _n-1,…X _i,…X ₁,X ₀) = F _{a i}, где - знак операции «сумма по модулю два».

 

X	Y			Результаты операций «дизъюнкции» и «суммы по модулю два» совпадают, если X и Y одновременно не равны 1.

 

F _a1 F _a2 ... F _ai = F _a1 F _a2 ... F _ai , так как среди характеристических функций единицы F _ai только одна принимает значение 1, а остальные равны нулю.

Замечание: Операция «сумма по модулю два» не является операцией алгебры Буля, но часто используется в булевых алгебрах с расширенным набором операций.

Рассмотрим процедуру получения характеристических функций единицы.

Если рассматривать b как степень булевой переменной X, то

 

Т. е. X ^b = 1 только в том случае, если значение Х равно значению b.

Докажем это с помощью таблицы истинности.

 

Х	b	Xb

 

Отсюда следует, что конъюнкция степеней булевых переменных X _n-1,…X _i,…X ₁, X ₀ равна 1, если для всех Х значения степеней равны значениям переменных. Поэтому конъюнкция переменных X _n-1, … X ₁, X ₀ со степенями, соответственно, a _n-1,...a ₁,a ₀ является характеристической функцией единицы для набора значений переменных a _n-1,...a ₁, a ₀.

 

Рассмотрим примеры характеристических функций.

 

Характеристическая функция единицы для набора №3 функции от трех переменных

F ₃ (X,Y,Z) = F ₀₁₁ (X,Y,Z) = X ⁰ &Y ¹ &Z ¹ =

 

Характеристическая функция единицы для набора №10 функции от четырех переменных

F ₁₀ (X,Y,Z,W) = F ₁₀₁₀ (X,Y,Z,W) = X ¹ Y ⁰ Z ¹ W ⁰=

 

Зная как построить характеристические функции единицы, можно на основании теоремы 1 сформулировать правило получения аналитической записи любой бф не равной константе 0: