Дифференциал и интеграл булевой функции, страница 14

¶F₂(x_1,x₂,..., x_n+1)  

                    ______________        = f(x_1,x₂,..., x_n) = f₂(x_1,x₂,..., x_n);

¶х_n+1                  Ú

Отсюда следует, что f₁(x_1,x₂,..., x_n) = f₂(x_1,x₂,..., x_n), что противоречит  предположению, что f₁(x_1,x₂,..., x_n) ¹ f₂(x_1,x₂,..., x_n). Теорема доказана.

Теорема 5. 

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

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

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

Теорема доказана.

Для примера найдем интеграл по операции дизъюнкция для всех функций от двух переменных.

В таблице 1 приведены все логические функции от двух переменных, а также количество переменных, от которых фактически  зависит функция, и ее сложность (количество термов при минимизации):

                                                                                                                Таблица 1

x1	x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
Пер.		0	2	2	1	2	1	2	2	2	2	1	2	1	2	2	1
Слож.		0	2	2	1	2	1	4	2	2	4	1	2	1	2	2	0

Ниже приведены данные логические функции:

_                      _                            _                  _

f₀  = 0; f₁ = x₁&x₂; f₂ = x₁&x₂; f₃ = x₁; f₄ = x₁&x₂; f₅ = x₂; f₆ = x₁&x₂ Ú x₁&x₂;              

_     _          _    _                       _                 _           _

f₇ = x₁Úx₂; f₈ = x₁&x₂; f₉ = x₁&x₂Úx₁&x₂; f₁₀ = x₂; f₁₁ = x₁Úx₂; f₁₂ = x₁;

_                 _    _

f₁₃ = x₁Úx₂; f₁₄ = x₁Úx₂; f₁₅ = 1;

Интегралы логических функций  от двух переменных для операции дизъюнкция:

_          

ò f₀ dx₃ = ò 0 dx₃ = {0; 0& x₃; 0&x₃} = {0};

Ú            Ú