Булеві похідні й диференціали

Визначення. Частковою булевою похідною df(x)/dx_i функції f(x) від змінних х₀, х₁,..., х_i,..., х_п по змінній х_i є сума додавання по модулю 2 для f(x):

ðf(x)/ ðх_i = f(x₀, х₁,..., х_i,...,x_n) Å f(x₀, x₁,..., `х_i,...,х_n)

Тотожним даному визначенню є таке визначення часткової БП:

ðf(x)/ ðх_i = f(x₀, х₁,..., х_{i-1, l,}х_i+1,…, x_n) Åf(x₀, х₁,..., х_i-1, 0, х_i+1,…, x_n)

Визначення. Частковим булевим диференціалом (БД) функції d_Xif(x) називається приріст функції f(x) при приросту змінної x_i, на dx_i:

d_Xif(x) = f(x) Å f(x_i Å dx_i)

Існує така залежність між частковим БД і частковою булевою похідною:

d_Xif(x) = (ðf(x)/ ðх_i)dх_i.

Властивості часткової булевой похідній (БП) й операції додавання по модулю 2 відомі. Частковий БД є параметричною формою часткової булевой похідній з параметром dx_i і має ті ж властивості.

Найбільш важлива властивість часткової БП полягає в тому, що коли часткова БП дорівнює одиниці, значення функції f(x) відрізняються для прямого й оберненого значення змінної x_i. Коли часткова БП дорівнює нулю, функція f(x) має те саме значення для прямого й оберненого значення змінної x_i.

Також застосування знайшли повні булеві диференціали.

Визначення. Повним булевим диференціалом функції f(x) називається приріст цієї функції при приросту вхідного вектора X на d:

ðf(x)/ðX = df(x) = f(x) Å f(X Å d)

Існує такий вираз для повного БД:

ðf(x) = Å S_l (ðf(x)/ðX^l)dX^l

Якщо (X₀, X₁) є розбивкою вхідного вектора X, то вираз ðf(d₀ = 1, d₁ = 0) = f(X₀, X₁) Å f(X₀, X₁) одержало назву функції чутливості Rf(x)/RX₀ від функції f(x) по змінних у точці. За допомогою функції Rf(x)/RX₀ повний булев диференціал визначається як диз'юнкція всіх функцій чутливості:

df(x) = Ú_l (Rf(x)/RX^l) d¹ (0<l<=2ⁿ-1)

Існують залежності між функціями чутливості й частковими похідними:

Rf(x)/RX₀ = Å S_l ðf(x)/ðX^l (0<l<=2^p-1)

ðf(x)/ðX₀ = Ú_l Rf(x)/RX^l₀ (0<l<=2^p-1),

де p — число змінних у крапці Х₀.

Булеві диференціали, визначенні раніше, є неорієнтованими й не дають напрямок зміни функції з 1 в 0, або з 0 в 1.

Визначення. Булев диференціал, орієнтований на збільшення df(x), є булевою функцією, що дорівнює 1, тоді й тільки тоді, коли f(x) змінюється при зміні Х з 0 в 1. Булев диференціал, орієнтований на зменшення df(x), є булевою функцією, що дорівнює 1, тоді й тільки тоді, коли f(x) змінюється при зміні X з 1 в 0.

З визначень випливає зв'язок між орієнтованими неорієнтованими БД:

^®df(x) = `f(x)df(x);

df(x) = f(x)df(x).

Можна увести поняття часткового орієнтованими БД (ОБД) і часткових орієнтованих булевых похідних (ОБП) і досліджувати їхнї властивості. З урахуванням виразів зв’язку між орієнтованими і неорієнтованими БД можна записати співвідношення між частковими ОБД і БД:

^®d_xif(x) = `f(x)d_xif(x);

d_xif(x) = f(x)d_xif(x).

Використовуючи залежності між частковими БП і БД, рівності відношень між частковими ОБД і БД можна представити у вигляді

^®d_xif(x) = `f(x) (ðf(x)/ðх_i) d_xi;

d_xif(x) = f(x) (ðf(x)/ðх_i) d_xi.

Визначення. Частковою булевою похідною, орієнтованою на збільшення ^®ðf(x)/ðх_i, називається вираження вигляду `f(x) (ðf(x)/ðх_i). Частковою булевою похідною, орієнтованою на зменшення ðf(x)/ðх_i, називається вираження вигляду f(x) (ðf(x)/ðх_i).

З урахуванням визначень для співвідношень між частковими ОБД і БД часткові ОБД можна представити у вигляді

^®d_xif(x) = (^®ðf(x)/ðх_i) d_xi;

d_xif(x) = (ðf(x)/ðх_i) d_xi.

Підставивши в ОБД початкове вираження часткової БП, можна одержати такі вирази:

^®ðf(x)/ðх_i =` f(x_i)f(`x_j);

ðf(x)/ðх_i = f(x_i) `f(`x_j).

Розв’язання ціх рівнянь, що дорівнює 1, визначає набори вхідних змінних, у яких зміна значення x_j на протилежне приводить до зміни значення функції відповідно з 0 в 1 або з 1 в 0. При цьому змінна x_i може мінятися як з 0 в 1, так і з 1 в 0, тобто є неорієнтованою. Орієнтація диференціала змінної х_i приводить до таких співвідношень для часток ОВД:

^®dx_i f(x) = f(x_i=1)`f(x_i=0)^®dx_i Ú `f(x_i=1) f(x_i=0)dx_i;

dx_i f(x) = f(x_i=1)`f(x_i=0)dx_i Ú `f(x_i=1) f(x_i=0)^®dx_i.

Визначення. Прямою орієнтованою булевою похідною [ðf(x)/ðх_i]_п називається вираження вигляду f(x_i=1)`f(x_i=0), що визначає умови, при яких диференціали dx_i й d_xif(x) мають однакову орієнтацію. Оберненою орієнтованою булевою похідною [ðf(x)/ðх_i]₀ назвемо вираження вигляду `f(x_i=1)f(x_i=0), що визначає умови, при яких диференціали dx_i й d_xif(x) мають різну орієнтацію.

З визначень ОБД слідує, що розв’язання першого рівняння нижче, отримане з умови, що пряма ОБП дорівнює одиниці, активізує у логічній схемі, що реалізує дану булеву функцію, шляхи з парним числом інверторів, а розв’язання, отримане з другого рівняння за умови, що зворотна ОБП дорівнює 1, активізує шляхи з непарним числом інверторів:

[ðf(x)/ðх_i]_п = f(x_i = 1)`f(x_i=0) = 1;

[ðf(x)/ðх_i]₀ = `f(x_i = 1) f(x_i=0) = 1.

Якщо представити функцію f(x) у вигляді f(x) = x_i f(x_i = 1) `x_i f(x_i= 0), то можна одержати наступні залежності ОБП від прямої й оберненої ОБП:

ðf(x)/ðх_i = х_i [ðf(x)/ðх_i]_пÚ `х_i[ðf(x)/ðх_i]_про;

^®ðf(x)/ðх_i = `х_i [ðf(x)/ðх_i]_проÚ х_i[ðf(x)/ðх_i]_про.

Орієнтовані булеві похідні мають нову якість і порівняно зі звичайними БП мають відмінні від них властивості. У зв'язку з цим нижче наводяться основні властивості ОБП.

1. `ðf(x)/ðх_i = ^®ðf(x)/ðх_i; ^®`ðf(x)/ðх_i = ðf(x)/ðх_i.

2. ðf(`x)/ðх_i = ^®ðf(x)/ðх_i; ^®ðf(`x)/ðх_i = ðf(x)/ðх_i.

3. ð(f(x)g(x))/ðх_i = g(x)ðf(x)/ðх_i Ú f(x)ðg(x)/ðх_i.

4. ^®ð(f(x)g(x))/ðх_i = g(`x)^®ðf(x)/ðх_i Ú f(`x)^®ðg(x)/ðх_i.

5. ð(f(x) Ú g(x))/ðх_i = `g(`x)ðf(x)/ðх_i Ú `f(`x)ðg(x)/ðх_i.

6. ^®ð(f(x) Ú g(x))/ðх_i = `g(x)ðf(x)/ðх_i Ú `f(x)^®ðg(x)/ðх_i.

7. ð(f(x) Å g(x))/ðх_i = `g(x)`g(`x)ðf(x)/ðх_i Ú
Ú g(x) g(`x)^®ðf(x)/ðх_iÚ `f(x)`f(`x)ðg(x)/ðх_i Ú
Ú f(x) f(`x)^®ðg(x)/ðх_i.

8. ^®ð(f(x) Å g(x))/ðх_i = `g(x)`g(`x)^®ðf(x)/ðх_i Ú
Ú g(x) g(`x)ðf(x)/ðх_i Ú `f(x)`f(`x)^®ðg(x)/ðх_i Ú
Ú f(x) f(`x)ðg(x)/ðх_i.

Властивості прямої й оберненої ОБП можна вивести з цих відношень.

9. [ð`f(x)/ðх_i]_п = [ðf(x)/ðх_i]_про [ð`f(x)/ðх_i]_про = [ðf(x)/ðх_i]_п

10. [ðf(`x)/ðх_i]_п = [ðf(x)/ðх_i]_про[ðf(`x)/ðх_i]_про = [ðf(x)/ðх_i]_п

11. [ð(f(x)g(x))/ðх_i]_п = g(x=1)(ðf(x)/ðх_i]_n Ú f(x=1)(ðg(x)/ðх_i]_n

12. [ð(f(x) g(x))/ðх_i]_про =g(x=0)(ðf(x)/ðх_i]_про Ú
Ú f(x=0)(ðg(x)/ðх_i]_про

13. [ð(f(x) Ú g(x))/ðх_i]_п = `g(x=0)(ðf(x)/ðх_i]_n Ú
Ú `f(x=0)(ðg(x)/ðх_i]_n.

14. [ð(f(x) Ú g(x))/ðх_i]_про = `g(x=1)(ðf(x)/ðх_i]_про Ú
Ú `f(x=1)(ðg(x)/ðх_i]_про

15. [ð(f(x) Å g(x))/ðх_i]_п = `g(x=1)`g(x=0)(ðf(x)/ðх_i]_n Ú
Ú g(x=1)g(x=0)(ðf(x)/ðх_i]_проÚ `f(x=1)`f(x=0)(ðg(x)/ðх_i]_n Ú
f(x=1)f(x=0)(ðg(x)/ðх_i]_про

16. [ð(f(x) Å g(x))/ðх_i]_o = `g(x=1)`g(x=0)(ðf(x)/ðх_i]_o Ú
Ú g(x=1)g(x=0)(ðf(x)/ðх_i]_nÚ `f(x=1)`f(x=0)(ðg(x)/ðх_i]_o Ú
Ú f(x=1)f(x=0)(ðg(x)/ðх_i]_n

Приклад. Можна обчислити частки ОБД й ОБП за змінною х₂ функції
f(x) = х₁х₂ Ú `х₂х₃.

Булева похідна, орієнтована на зменшення, за змінною х₂ дорівнює ðf(х) /ðх₂ = (x_tx₂ Ú `х₂x₃) ù(x₁`x₂ Ú х₂х₃) = х₁х₂`х₃, Ú `х₁`х₂х₃. Звідси набори х₁ = 1, х₂ = 1, х_э = 0 і х₁ = 0, х₂ = 0, х₃ = 1 визначають умови чутливості функції до змінного х₂. При цьому зміна значення х₂ на протилежне (з 1 в 0 у наборі 110 або з 0 в 1 у наборі 001) приводить до зміни функції з 1 в 0.

Булева похідна, орієнтована на збільшення, по змінній х₂ дорівнює ^®ðf(х) /ðх₂ = ù (x_tx₂ Ú `х₂x₃) (x₁`x₂ Ú х₂х₃) = `х₁х₂х₃, Ú х₁`х₂`х₃. Звідси зміна змінної х₂ з 1 в 0 у наборі 011 або зміна х₂ з 0 в 1 у наборі 100 приводить до зміни значення функції з 0 в 1.

Пряма й обернена ОБП для змінної х₂ мають вигляд [ðf(х) /ðх₂]_n = х₁`х₂; [ðf(х) /ðх₂]_o = `х₁х₂.

Часткові ОБД визначаються так d_x2f(x) = (ðf(х) /ðх₂)dx₂ = (x₁x₂`x₃ Ú x₁`x₂`x₃)dx₂ = `x₁x₃ d_x2 Ú x₁`x₃^®d_x2;^®d_x2 f(x) =
=(^®ðf(х) /ðх₂)dx₂ = (`x₁x₂x₃ Ú x₁`x₂`x₃)dx₂ = `x₁x₃dx₂ Ú x₁`x₃^®dx₂. З ОБД, орієнтованого на зменшення, треба, що зміна функції з 1 в 0 досягається зміною х₂ з 1 в 0 за умови х₁ = 1, х₃ = 0 або зміною х₂з 0 в 1 за умови х₁ = 0, х₃ = 1. ОБД, орієнтований на збільшення, дорівнює 1 при зміні х₂ з 1 в 0 при x₁ = 0, х₃ = 1 або при зміні х₂ з 0 в 1 при х₁ = 1, х₃ = 0.