Лекція 5 Булева похідна та її застосування для обчислення спостерігальності Визначення бпx
та її застосування для обчислення спостерігальності
О п о р д і л е н н ня БПx.
dF(X) / dxi = F(x1, .xi, .xn) · F(x1.xi, .xn),
де · - Сума "за модулем два";
xi – інверсне значення xi.
Цей вираз еквівалентний наступному
dF(X) / dxi = F (x1, .1. xn) · F (x1.0,. xn).
Наприклад, БП функції F(X) = x1x2 + x2x3 по змінній x1 матиме такий вигляд:
dF(X) / dx1 = (x1x2 + x2x3) · (x1x2 + x2x3).
Для спрощення побудованого вислову замінимо логічне АБО сумою "за модулем два":
dF(X) / dxi = x1x2 · x2x3 · x1x2x3 · x1x2 · x2x3 · x1x2x3.
Після елементарних перетворень отримаємо dF(X)/dxi = x2x3.
Для логічної функції F(X), представленої суперпозицією інших функцій f1(X), . fm(X):
за аналогією з визначенням БПx вводиться
Про п е д е л е н ня БПf.Бульової похідної функції
за функцією fi(Х) називається логічний вираз виду:
dF(X) / dfi(X) = F [X, f1(X), . fi(X), . fm(X) ] ·
- F [Х, f1(Х), . fi(Х), . fm (Х)].
Наприклад, БП функції F(X) = F [X, f(X)] = x1x2 + f(X), за функцією f(X) = x2x3 визначається наступним чином:
dF(X) / df(X) = [x1x2 + f(X)] · [x1x2 + f(X)].
В отриманому виразі логічне "АБО" замінюємо на "що виключає АБО":
dF(X) / df(X) = [ x1x2 · f(X) · x1x2f(X) ] ·
- [x1x2 · f (X) · x1x2f (X)].
Після змін остаточно отримаємо: dF(X)/df(X) = x1+ x2. В цілому, обчислення мінімальних виразів БП є досить складною процедурою, що підтверджують наведені вище приклади. Для спрощення доцільно застосовуватинаступні
Своїстя БП
A1) dF'(X) / dxi = dF(X) / dxi;
A2) dF(X) / dx'i = dF(X) / dxi;
A3) d [dF (X) / dxj] / dxi = d [dF (X) / dxi] / dxj;
A6) d[F(X) · G(X)] / dxi = dF(X)/dxi · dG(X)/dxi;
A7) dF(X) / dxi = 0, якщо F(X) не залежить від xi;
A8) dF(X) / dxi = 1, якщо F(X) = xi;
A10) d[F(X) + G(X)] / dxi = F'(X) & dG(X)/dxi, якщо F(X) не залежить від xi.
П р і м е р.Визначити БП функції F(X) = x1x2 + x2x3 по х1. Відповідно до властивості A10 маємо:
d (x1x2 + x2x3) / dxi = (x2x3)& d(x1x2)/dx1 .
Застосовуючи властивість A9, остаточно отримуємо:
dF(X) / dx1 = (x2x3) & х2 = х2 х3,
що збігається з отриманим раніше результатом без використання наведених властивостей.
Властивості БП застосовні і для похідної функції.
П р і м е р.Отримати БП функції F(X,f(Х)) = x1x2 + f(X) за функцією f(X) = x2x3.
Застосовуючи послідовно властивості A10 та A8 отримуємо:
dF(X,f(Х)) / df(Х) = (x1x2)& df(Х)/df(Х) = x1 + x2.
З прикладів видно, що застосування властивостей А1. А10 спрощує отримання виразів БП. Однак одержання мінімальних виразів БП навіть із застосуванням властивостей А1. А10 все ж таки представляє досить трудомісткий процес. У деяких випадках його можна спростити, якщо вихідну функцію представляти не в ДНФ, а в поліноміальній формі або поліном Жегалкіна.
Як відомо, диз'юнктивною нормальною формою (ДНФ) функції F(X) називається вираз виду:
,
де Ki = x1 l1 & x2 l2 &. & xni lni - елементарні кон'юнкції над змінами над змінними функції F(X). ДНФ, у якій кожна кон'юнкція має ранг n, де n - число змінних функцій F(X), називається диз'юнктивною досконалоюнормальною формою (ДСНФ). Кон'юнкції в ДСНФ таким чином можна подати так:
Ki = x1 l1 & xi l2 &. & xn ln ,
тобто. вони включають усі змінні функції F(X).
Поліноміальною нормальною формою (ПНФ) функції F(X) називається логічний вираз, представлений у базисі (&, ·, НЕ) :
ПНФ можна отримати з ДНФ, застосовуючи наступне співвідношення:
а1 + а2 = а1 · а2 · а1а2.
Поліномом Жегалкіна функції F(X) називається вираз виду:
де K`i = xi1 & xi2 &. & xini - кон'юнкція змінних функцій F(X).
Відмінність полінома Жегалкіна від ПНФ у тому, що кон'юнкції першого складаються над прямими значеннями аргументів функції, тоді як кон'юнкції ПНФ можуть утворювати і прямі та інверсні аргументи. До полінома Жегалкіна легко перейти від ПНФ, якщо замість змінних хj з інверсіями підставити xj · 1 .
Нехай деяка функція представлена ДСНФ:
F(X) = х1х2х3 + х1х2х3 + х1х2х3.
Отримання похідних F(X) по ДСНФ пов'язані з великою трудомісткістю, т.к. в цьому випадку необхідно двічі застосувати властивість А5, що призведе до великої громіздкості обчислень. Мінімізація цієї функції також не зменшить трудомісткість, оскільки мінімальна ДНФ збігається з ДСНФ. З метою спрощення обчислень похідних перейдемо від ДСНФ до ПСНФ:
F(X) = х1х2х3 · х1 х2 х3 · х1х2х3.
Тоді на основі властивості А6
dF/dx1 = (x1x2x3)/dx1 · (x1 x2 x3)/dx1 · (x1x2x3)/dx1 =
= x2x3 · x2x3 · x2x3 = x2 v x3.
Перейдемо далі від ПСНФ до полінома Жегалкіна:
F(X) = x1x2x3 · (x1·1)(x2·1)x3 · (x1·1)x2(x3·1) =
= x1x3 · x3 · x2 · x1x2 · x1x2x3.
Отримаємо похідну F(X) , представленої поліномом Жегалкіна:
dF(X)/dx1 = d(x1x3)/dx1· dx3/dx1 · dx2/dx1 · d(x1x2)/dx1 ·
- d(x1x2x3)/dx1 = x3 · x2 · x2x3 = x2 v x3.
З наведених прикладів видно, що у деяких випадках представлення функції поліноміальної формі спрощує обчислення похідних.
Інтерпретація та діагностичні властивості
Нехай функція F(X) описує реалізуючу її комбінаційну схему (КЛС) з виходом F і безліччю входів X = < xi >, i = 1. n. КЛС складається з множини V = < Vk >логічних елементів (вентилів), k = 1. m , таких, що вентиль Vk реалізує функцію
fk(Х). Тоді БП функції F(X) із зовнішньої xi чи внутрішньої fк(X) змінної схеми є функцією спостереження значення змінної на виході F схеми. Умовимося позначати функцію спостереження КТ Кк схеми, як
де fk(X) - функція, що реалізується схемою КТ Кк.
Позначимо безліч коренів рівняння H(X) = 1 як R = < rj >, де rj - вхідний вектор розмірністю n: H(rj) = 1 . Нехай також r1 і r2 належать множині R і забезпечують протилежні значення функції fk(Х): fk(r1) = a; fk(r2) = a. Тоді за визначенням спостереження КТ схеми, якщо F(r1) = b, то F(r1) = b, тобто. послідовна подача на входи КЛС векторів r1 і r2 забезпечує перемикання значень сигналів у точці Кk і на виході схеми. Тому кажуть, що якщо виконано умову спостереження КТ схеми, її вихід стає " чутливим " (залежний) від цієї точки. Найчастіше несправні стани цифрових пристроїв описуються з урахуванням моделі одиночних константних несправностей (КН). КН моделює обрив ( = 1 ), або коротке замикання з шиною " земля " ( = 0 ) на вході, виході елемента, або зовнішньому виведенні схеми. Константну несправність h КТ Кк умовимося позначати як Кк = h. При тестуванні КН виникає завданнявизначення спостережуваності точки, де моделюється несправність. Як було показано вище, спостереження несправності може бути обчислена через БП вихідний функції F(X) схеми, що тестується. При цьому необхідно вибрати змінну, щодо якої обчислюватиметься похідна.
Для ілюстрації правила, яким вибирається змінна БП для різних КТ, розглянемо фрагмент КЛС
\ Vl │ xi │ fk o────── . / fm o──── F
Рис.5.1 Фрагмент КЛС для ілюстрації вибору змінної БП
Якщо моделюється несправність на виході вентиля Vk, то спостерігання цієї КТ обчислюється як БП функції F(X) функції fк(X). Як шуканої змінної v при обчисленні спостережуваності безпосередніх входів вентиля виступає джерело вироблення сигналів (зовнішній вхід схеми чи вихід вентиля, який живить цей вхід). При цьому, якщо ланцюг, якому належить розглянута КТ, має відгалуження, то обрана змінна позначається (як позначка, наприклад, може виступати додатковий індекс або апостроф). Так 2-му і 3-му входам вентиля Vk необхідно присвоїти змінні без міток, змінні ж для 1-го і 4-го входів позначаються апострофом.
Після вибору змінної спостереження КТ обчислюється як БП функції F(X) цієї змінної. Наприклад, спостережливість виводів вентиля Vк повинна обчислюватися таким чином
Vк.вих : dF(X) / dfк(X) ,
Vк.вх1 : dF(X) / dxj" ,
Vк.вх2 : dF(X) / dfl(X) ,
Vк.вх3 : dF(X) / dxi ,
Vк.вх4: dF(X) / dfp"(X).
Спостережуваність зовнішнього входу xi схеми обчислюються як БП вихідний функції схеми змінної xi. Спостережуваність зовнішнього виходу схеми дорівнює 1. Якщо при обчисленні спостереження КТ вибирається змінна з міткою, виникає необхідність зміни опису вихіднийфункції вентиля, з якою з'єднана КТ. Наприклад, для вентиля Vk, 1-му та 4-му входам якого присвоєні змінні з міткою,
вихідну функцію fк(Х) необхідно описати через позначену змінну:
Vк.вх1: fк(xj, fl, xi, fp)? fк(xj", fl, xi, fp);
Vк.вх4: fк(xj, fl, xi, fp)? fк(xj, fl, xi, fp").
Для 2-го та 3-го входів та виходу вентиля Vк перетворення функції fк(Х) не потрібні.
При обчисленні БП по позначеної змінної v", дана змінна та відповідна їй змінна v розглядаються як різні змінні схеми.
П о п о р о з д л я с а м о к о н т р о л я
1. Дайте визначення булевої похідної по змінній функції.
2. Перерахуйте властивості БП.
3. На основі визначення БП доведіть її властивості.
4. Перерахуйте способи опису булевої функції та як вибір способу впливає на складність обчислення БП?
5. Дайте фізичну інтерпретацію БП.
6. Наведіть характерні приклади КТ схеми та покажіть як їм обчислюється БП.