2015-06-28
289
Раніше для знаходження булевой різниці використалися наслідки, що випливають із визначення поняття булевой різниці. Якщо функція F(Х) складна, потрібні додаткові перетворення. У тому числі можна дати більше зручне для обчислення d(Х)/dхi визначення булевой різниці.
Визначення. Булевой різницею функції F(х1,x2,...,хi,...,xn) щодо змінної хi називається вираження виду
d(x)/dхi = F(x1, х2,..., 1,...,xn) Å F(x1, x2,..., 0,...,хn),
справедливе для будь-яких хi, 1 £ i £ n.
Тобто d(Х)/dхi є результатом додавання по модулі 2 двох членів, першим з яких є F(Х) при хi = 1, другим F(Х) при хi = 0.
Еквівалентність двох визначень підтверджується вираженням
d(Х)/dхi = (хi(x1, х2,..., 1,...,xn) Å `хi(x1, х2,..., 0,...,xn)) Å
Å (`хi(x1, х2,..., 1,...,xn) Å хi(x1, х2,..., 0,...,xn)) =
= (хi Å`хi)(F(x1, х2,..., 1,...,xn)) Å (`хi Å хi)(F(x1, х2,..., 0,...,xn)) =
= (F(x1, х2,..., 1,...,xn)) Å (F(x1, х2,..., 0,...,xn)).
Приклад. Нехай дана функція F(х1, x2, x3) = `x1`x2+x3, потрібно визначити d(х1, x2, x3)/dх2.
d(х1, x2, x3)/dх2 = (`x10 + x3) Å (`x11 + x3) = x3 Å (`x1 + x3) =
= `x1 Å `х1 x3 = `х1`x3.
35.2.1. Метод карт Карно
По першому визначенню булевой різниці
|
|
|
d(x)/dхi = F(x1, х2,..., хi,...,xn) Å F(x1, x2,..., `хi,...,хn)
Можна побудувати дві карти Карно: одну для F(x1, х2,..., хi,...,xn), іншу для F(x1, x2,..., `хi,...,хn). Відповідні елементи карт складаються по модулю 2. Результатом додавання є звичайна карта Карно для d(x)/dхi.
Карта Карно є спеціальною таблицею істинності, що включає всі двійкові вектори змінних функції, тому будь-яка логічна операція між двома функціями F й G може бути перетворена в логічну операцію між відповідними елементами карт для F й G.
Приклад. Нехай дана функція F(х1, x2, x3) = `x1`x2+x3, потрібно визначити d(х1, x2, x3)/dх2 методом карт Карно.
Дві карти (табл.. 35.1 і 35.2) складаються по модулі 2 у спосіб за табл. 35.3.
Таблиця 35.1
| F x1,x2 x3 | ||||
`x1`x2+x3
Таблиця 35.2
| F x1,x2 x3 | ||||
`x1x2+x3
Таблиця 35.3
| F x1,x2 x3 | ||||
 1
| ||||
`x1`x3
Отже, d(х1, x2, x3)/dх2 = `x1`x3.
35.2.2. Метод карт Хсиао Скотта
Метод припускає подання будь-який булевой функції F(x) поруч простих імплікант, що складаються по модулю 2. Результуюча рівність називається нормальною формою, що виключає (ИНФ).
Для одержання ИНФ по карті Карно групуються аргументи, при цьому кожен аргумент використається тільки непарне число раз. Послідовність визначення d(Х)/dхi зводиться до наступних дій:
1. F(Х) представляється в ИНФ за допомогою угруповання кожного аргументу карти F(Х) непарне число раз.
2. ДО ИНФ застосовуються тотожності булевой різниці, представлені на початку лекції, внаслідок чого легко виходить результат для d(Х)/dхi.
Приклад. Дано функцію Cn = an bn + (an+ bn)Cn-1, потрібно визначити dСn/dCn-1.
|
|
|
На першому кроці Cn перетворюється в ИНФ (табл. 35.4).
Таблиця 35.4
| Cn a1,b2 Cn-1 | ||||
 1
| ||||
 1
|  1
|
Отже, Cn = an bn Å anCn-1 Å bnCn-1,
dCn/dCn-1 = d(an bn Å d(anCn-1)/dCn-1 Å d(bnCn-1)/dCn-1)/dCn-1 =
= 0 Å an Å bn = an Å bn.
Як, наслідок, можна визначити ще одну властивість булевой різниці
13. Якщо F(x) = A(X) +xi(X) + `xi(X), де A(X), B(X) і C(X) не залежать від xi, то справедливо
d(Х)/dхi = `A(X)(B(X) Å C(X))
