Лекция 5 Булево производно и неговото приложение за изчисляване на наблюдаемостта Определяне на bnx

и приложението му за изчисляване на наблюдаемостта

ОПРЕДЕЛЕНИЕ НА PSUx. Булевата производна (BP) на функцията F (X), X =, по отношение на променливата xi е логическа функция на формата

dF (X)/dxi = F (x1,. xi,. xn) F (x1. xi,. xn),

където · - сумата "по модул две";

xi - обратна стойност на xi.

Този израз е еквивалентен на следното

dF (X)/dxi = F (x1,. 1.xn) F (x1. 0,. xn).

Например BP на функцията 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):

по аналогия с дефиницията на BPx въвеждаме

ОПРЕДЕЛЕНИЕ НА PSU f. Булева производна на функция

чрез функция fi (X) се нарича логически израз на формата:

dF (X)/dfi (X) = F [X, f1 (X),. fi (X),. fm (X)] ·

  • F [X, f1 (X),. fi (X),. fm (X)] .

Например BP на функцията 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. Като цяло изчисляването на минималните изрази на BP е доста сложна процедура, което се потвърждава от горните примери. За простота е препоръчително да приложите следното

Захранващ блок

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.

PRI ме r. Определете BP на функцията F (X) = x1x2 + x2x3 по x1. Според свойство A10 имаме:

d (x1x2 + x2x3)/dxi = (x2x3) & d (x1x2)/dx1 .

Прилагайки свойство A9, най-накрая получаваме:

dF (X)/dx1 = (x2x3) & x2 = x2 x3,

което съвпада с получения по-рано резултат, без да се използват горните свойства.

BP свойствата са приложими и към производната по отношение на функцията.

PRI ме r. Вземете BP на функцията F (X, f (X)) = x1x2 + f (X) от функцията f (X) = x2x3.

Прилагайки последователно свойства A10 и A8, получаваме:

dF (X, f (X))/df (X) = (x1x2) & df (X)/df (X) = x1 + x2.

Примерите показват, че използването на свойства А1. A10, улеснява получаването на изрази на BP. Получаване на минимални изрази на BP дори с използването на свойства А1. A10 все още е доста трудоемък процес. В някои случаи тя може да бъде опростена, ако оригиналната функция е представена не в DNF, а в полиномна форма или като полином на Жегалкин.

Както знаете, дизюнктивната нормална форма (DNF) на функцията F (X) е израз на формата:

,

където Ki = x1 l1 & x2 l2 &. & xni lni - елементарни съвпад върху промени над променливи на функция F (X). DNF, в който всяка връзка има ранг n, където n е броят на променливите на функцията F (X), се нарича дизюнктивна перфектна нормална форма (DSNF). Следователно съединенията в DSNF могат да бъдат представени по следния начин:

Ki = x1 l1 & xi l2 &. & xn ln,

тези. те включват всички променливи на функцията F (X).

Полиномиалната нормална форма (PNF) на функцията F (X) е логически израз, представен в основата (&, ·, NOT):

PNF може да се получи от DNF чрез прилагане на следното съотношение:

a1 + a2 = a1 a2 a1a2.

Полиномът на Жегалкин на функцията F (X) е израз на формата:

където K`i = xi1 & xi2 &. & xini - съвпадение на променливи от функция F (X).

Разликата между полинома Жегалкин и PNF е, че конюнктите на първия се съставят върху преките стойности на аргументите на функцията, докато конюнктите на PNF могат да образуват както преки, така и обратни аргументи. Лесно е да преминем към полинома Жегалкин от PNF, ако вместо променливи хj с инверсии заместим xj .

Нека някаква функция бъде представена от DSNF:


F (X) = х1х2х3 + х1х2х3 + х1х2х3 .

Производството на производни F (X) от SDSF е свързано с голяма трудоемкост, тъй като в този случай е необходимо да се приложи свойство A5 два пъти, което ще доведе до големи тромави изчисления. Минимизирането на тази функция също няма да намали сложността, тъй като минималният DNF съвпада с DNF. За да опростим изчисленията на дериватите, ще преминем от DSNF към PSNF:


F (X) = х1х2х3 х1 х2 х3 х1х2х3 .

След това, въз основа на свойство A6

dF/dx1 = (x1x2x3)/dx1 (x1 x2 x3)/dx1 (x1x2x3)/dx1 =

= x2x3 x2x3 x2x3 = x2 v x3 .

Нека да преминем от PSNF към полинома Жегалкин:

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) описва комбинационната схема (CLS), която я реализира с изхода F и набора от входове X = < xi >, i = 1.n. CLS се състои от множеството V = < Vk >логически елементи (портали), k = 1.m, така че портата Vk реализира функцията

fk (X). Тогава BP на функцията F (X) по отношение на външната xi или вътрешна fk (X) променлива на веригата е функцията на наблюдаемостта на стойността на променливата на изхода на F веригата. Нека се съгласим да обозначим функцията за наблюдение на QD Kk схемата като

където fk (X) е функцията, реализирана от веригата в CT Kk.

Обозначаваме множеството корени на уравнението H (X) = 1 като R = < rj >, където rj е входен вектор с размерност n: H (rj) = 1. Нека също r1 и r2 принадлежат към множеството R и предоставят противоположни стойности на функцията fk (X): fk (r1) = a; fk (r2) = a. Тогава, чрез дефиницията за наблюдаемост на QD схема, ако F (r1) = b, тогава F (r1) = b, т.е. последователното подаване на вектори r1 и r2 към входовете на CLS осигурява превключване на стойностите на сигнала в точката Kk и на изхода на веригата. Следователно се казва, че ако условието за наблюдаемост на QD веригата е изпълнено, тогава нейният изход става "чувствителен" (зависим) от дадена точка. Най-често дефектните състояния на цифровите устройства се описват въз основа на модела с единични постоянни повреди (CS). KN симулира отворено (= 1) или късо съединение със заземяващата шина (= 0) на входа, изхода на елемента или на външния изход на веригата. Постоянна грешка h в CP Kk ще се съгласим да обозначим като Kk = h. При тестване на CF възниква проблемът с определянето на наблюдаемостта на точката, в която се симулира повредата. Както е показано по-горе, забележимостта на повреда може да бъде изчислена чрез BP на изходната функция F (X) на тестваната верига. В този случай е необходимо да изберете променлива, по отношение на която ще бъде изчислена производната.

За да илюстрирате правилото, чрез което променливата BP се избира за различни CT, разгледайте фрагмент от CLS

\ Vl │ xi │ fk o──────./fm o──── F

Фигура 5.1 Фрагмент от CLS за илюстриране на избора на променливата BP

Ако се симулира неизправност на изхода на портата Vk, тогава наблюдаемостта на този CT се изчислява като BP функция F (X) от функцията fк (X). При изчисляване на наблюдаемостта на директните входове на порта, източникът на генериране на сигнал (външният вход на веригата или изходът на портата, който захранва този вход) се използва като желаната променлива v. В този случай, ако веригата, към която принадлежи разглежданият CT, има клонове, тогава избраната променлива се маркира (например допълнителен индекс или апостроф може да действа като етикет). Така че на 2-ри и 3-ти входове на портата Vk трябва да бъдат присвоени променливи без етикети, докато променливите за 1-ви и 4-ти входове са маркирани с апостроф.

След избора на променливата, наблюдаемостта на CT се изчислява като BP на функцията F (X) за тази променлива. Например, наблюдаемостта на изходите на порта Vk трябва да се изчисли, както следва

Vc.out: dF (X)/dfk (X),

Vc.in1: dF (X)/dxj ",

Vc.in2: dF (X)/dfl (X),

Vc.in3: dF (X)/dxi,

Vc.inx4: dF (X)/dfp "(X).

Наблюдаемостта на външния вход xi на веригата се изчислява като BP на изходната функция на веригата по отношение на променливата xi. Наблюдаемостта на външния изход на веригата е 1. Ако при изчисляване на наблюдаваемостта на CT е избрана променлива с етикет, тогава става необходимо да се промени описанието на изходната функция на портата, към която е CT свързани. Например за портата Vk, чийто първи и четвърти вход са присвоени на променливи с етикета,

изходната функция fк (X) трябва да бъде описана чрез обозначената променлива:

Vc.in1: fк (xj, fl, xi, fp)? fк (xj ", fl, xi, fp);

Vc.in x4: fк (xj, fl, xi, fp)? fк (xj, fl, xi, fp ") .

За втория и третия вход и изхода на портата Vk не се изисква преобразуване на функцията fk (X).

Когато се изчислява BP за маркираната променлива v ", тази променлива и съответната променлива v се считат за различни променливи на веригата.

Въпроси за l Аз съм в течение на l

1. Дайте дефиниции на булева производна по отношение на променлива, функция.

2. Избройте свойствата на захранването.

3. Въз основа на определението за BP докажете неговите свойства.

4. Избройте начините за описване на булева функция и как изборът на метод влияе върху сложността на изчисляването на BP?

5. Дайте физическа интерпретация на BP.

6. Дайте типични примери за CT схеми и покажете как се изчислява BP за тях.