Дифференциал и интеграл булевой функции
В данной главе обобщается понятие дифференциала булевой функции, доказываются свойства дифференциала для основных логических операций и вводится определение интеграла булевой функции.
Ранее введенное понятие дифференциала булевой функции определялось только для операции «сложение по модулю 2" (операция Жегалкина) [1]:
Дифференциалом первого порядка ∂f/∂xi — от булевой функции f по переменной xi называется следующее логическое выражение:
∂f/∂xi = f (xl,x2,...,xi-1,1,...,xn) Ө f (xl,x2,...,xi-1,0,...,xn), где f (xl,x2,...,xi-1,1,...,xn) — единичная остаточная функция;
f (xl,x2,...,xi-1,0,...,xn) — нулевая остаточная функция.
Единичная остаточная функция получается в результате приравнивания переменной xi единице, нулевая — приравнивания xi нулю.
В следующем определении вводится расширенное понятие дифференциала булевой функции для произвольной двуместной логической операции.
Пусть задана логическая функция F(xl,x2,...,xn) и некоторая двуместная логическая операция р(a, b).
Определение 1.1. Дифференциалом логической функции F(xl,x2,...,xn) по переменной xi для операции р(a, b) называется
следующее логическое выражение:
∂F(xl,x2,...,xn)
____________ = p (F(xl,x2,...,xi=0,...,xn), F(xl,x2,...,xi=1,...,xn)).
∂xi p
Рассмотрим теперь определение дифференциала логической функции для операции дизъюнкции и конъюнкции.
Определение 1.2. Дифференциалом логической функции F(xl,x2,...,xn) по переменной xi для операции дизъюнкция является следующая логическая функция:
∂F(xl,x2,...,xn)
____________ = F(xl,x2,...,xi=0,...,xn) v F(xl,x2,...,xi=1,...,xn).
∂xi v
В качестве примера рассмотрим следующую логическую функцию:
_ _
F(xl,x2,x3) = xl x2 v xl,x3.
Найдем дифференциал данной функции по переменным xl,x2,x3 для операции дизъюнкция.
Дифференциал по переменной xl для операции дизъюнкция
∂F(xl,x2,x3)
_________ = F(xl=0,x2,x3) v F(xl=1,x2,x3);
∂x1 v
_
F(xl=0,x2,x3) = x2; F(xl=1,x2,x3) = x3;
∂F(xl,x2,x3) _
_________ = x2 v x3
∂x1 v
Дифференциал по переменной x2 для операции
дизъюнкция
∂F(xl,x2,x3)
_________ = F(xl,x2=0,x3) v F(xl,x2=1,x3);
∂x2 v
_
F(xl,x2=0,x3) = x1 v x1 & x3; F(xl,x2=1,x3) = x1 & x3;
∂F(xl,x2,x3)
_
_
_________ = x1 v x1 & x3 v x1 & x3 = x1 v x1 & x3.
∂x2 v
Дифференциал по переменной x3 для операции дизъюнкция
∂F(xl,x2,x3)
_________ = F(xl,x2,x3=0) v F(xl,x2,x3=1);
∂x3 v
_ _ _ _
F(xl,x2,x3=0) = x1 & x2; F(xl,x2,x3=1) = x1 & x2 v x1;
∂F(xl,x2,x3) _ _ _ _ _ _
_________ = x1 & x2 v x1 & x2 v x1 = x1 & x2 v x1.
∂x3 v
Определение 1.3. Дифференциалом логической функции F(xl,x2,...,xn) по переменной xi для операции конъюнкция
является следующая логическая функция:
∂F(xl,x2,...,xn)
___________ = F(xl,x2,...,xi=0,...,xn) & F(xl,x2,...,xi=1,...,xn).
∂xi &
Далее введем понятие интеграла булевой функции, как обратной операции дифференциала булевой функции.
Определение 2. Интеграл от булевой функции F(xl,x2,...,xn) по переменной xn+1 для операции р(a, b)
∫ F(xl,x2,...,xn)d xn+1
есть множество булевых функций {fl,f2,...,fm}, зависящих от xn+1 переменных, таких, что
∂fi (xl,x2,...,xn,xn+1)
_______________ = F(xl,x2,...,xn), (i=1÷m).
∂xn+1 p
В качестве примера найдем интеграл от функции F(xl) = xl для операции конъюнкция.
Для этого рассмотрим все функции от двух переменных и найдем дифференциалы этой функции по переменной x2 для операции конъюнкция.
Таблица 1
|
xl |
x2 |
f0 |
fl |
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 |
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
