Файл: Горелик, А. Л. Некоторые вопросы построения систем распознавания.pdf

в совершенной дизъюнктивной нормальной форме, на­ пример,

Е = А\Аъ■... • Ап ■К і•... • Кт,Л- . • • + Äi •Л2 • . . . ■An •

(6.3)

то каждое слагаемое в (6.3) можно интерпретировать как колонку сокращенного базиса, ибо в элементарном произведении явным образом указываются те значения истинности элементов Ль . .., Л„; К\, . . К т , при кото­ рых функция Е истинна. Так, например, функции (6.3) соответствуют следующие колонки базиса ЬС[Аи .. ., Л„;

Поскольку при представлении булевой функции в совер­ шенной дизъюнктивной нормальной форме суммируются все те и только те элементарные произведения, при ко­ торых данная функция истинна, то базис вида (6.4) действительно содержит все колонки базиса Ьс[Аи .. .,Ап;

Рассмотрим, например, соотношение (5.8):

A + B- X- Y + C - Y = ä - X- Y + B- X + C+ A- B,

связывающее элементы А, В, С, X, Y. По определению

эквивалентности, данное соотношение можно записать в виде

(A + B- X- 7+C- Y) ■{Ж- X - Y + B - X + C + Ä • В ) +

+ (.A + B - X - Y +C - Y ) ■( Ä - X - Y + B- X + C+A- B) = I

или после преобразований

A - B - X + A - C+A - B + B- C- X- Y + C - Y + Ä - B - C - Y +

Г64

Представим функцию (6.5) в совершенной дизъюнктив­ ной нормальной форме

A- ß - C- X- Y + A -В- C - X - Y + A ■B- C- X- Y+ +A - B - C- X - 7 +A - B - C- X - Y+A - B - C - X - Y +

+А - В - С - Х • Y + A - B - C - X - Y + A - В- С- Х- Y+

+A - B - C - X - Y + A - B - C - X - Y + A - B - C - X - Y + +A- B- C- X- Y + A - B - C - X - Y + Ä - B - C - X - T +

+Ä - B - C - X - Y +Ä - B - C - X - Y + Ä - B - C - X - Y + -TÄ-B-C-X • Y+Ä ■В -С-Х ■Y+Ä- B -С-Х- Y+

Трансформируя каждое слагаемое (6.6) в колонку сокращенного базиса ЬС[А, В, С, X, У], получим

і = 5 5 1 17 7.7 7 5 5 3 3 3 3 6 6 6 4 4 2 2 0 0

#А = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0

#В = 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0

# С = 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 (6.7)

# Х = 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1

# У = 10101 0 1 0 1 0 1 0 1 001 1 1 1 1 1 10

і = 2 0 2 0 3 1 2 0 3 1 3 1 2 0 1 3 2 3 2 3 2 3 1

Базис (6.7) устанавливает следующее соответствие меж­

производить как умножение, так и сложение отдельных соотношений вида (6.1). Например, если в задаче, рас­ смотренной в § 5.7, в качестве исходных зависимостей,

165

то для построения сокращенного базиса ЬК[А, В, С; А', В', С'] необходимо вначале сложить левые части соотно­

шений

C -(A'-B'+Ä'-B')+C- (A'-B'+Ä'-B') = l,

С■(Ä'-B' + Ä'-C' + A'-B'-C') + С - (А'-В' + А ' -С' +

+Л'-В'-С') - I ,

эквивалентных зависимостям (6.9), и полученный резуль­ тат

С- {A'-B'+Ä'-B'+Ä'-C') +

+ Ü- (A'-B' + A ' - C ' + Ä ' - B ' ) ^

умножить на функции

A -B'+ Ä'-B' = l,

B-iB'-C' + B'-C') +В-{В'-С' + В'-С') = I,

# С = 1 0 1 1 0 0 1 0 1 0

(6.11)

#А ' = 0 1 1 0 0 1 0 1 1 0

#В ' = 0 0 1 1 1 1 0 0 1 1

# С ' = 0 0 1 1 1 1 1 100

/ = 0 1 7 6 6 7 4 5 3 2

Соответствие между номерами / и / столбцов базисов

Ь[А, В, С] и Ь[А', В', С']

166

полностью согласуется с тем соответствием, которое уста­

Вернемся еще раз к задаче о нахождении неизвест­ ной функции F(Ki, К2, •••)> удовлетворяющей уравнению

стями (5.39). Соотношение (6.13) имеет смысл утверж­ дения: «Некоторая совокупность признаков, характери­ зующая распознаваемые явления (процессы) Кі, К2, ■■■

и представленная функцией G(Ai, Â2, ...), действительно

имеет место».

Для нахождения функции F (Кі, Кг, • • •) необходимо определить, какие комбинации элементов Кі, Кг, ... бу­

дут истинны при различных предположениях об истин­ ности независимых элементов из числа Аи А2........ Наи­

более просто эта задача решается для случая, когда функция G(Ai, А2, ..-) имеет вид элементарного произ­ ведения, составленного из элементов Аи А2, ..., так как при этом значения истинности всех элементов А и Аг, ...

определены однозначно. Пусть, например, применительно к (6.5) дополнительно утверждается, что

Соотношение (6.14) справедливо тогда и только тогда, когда одновременно Л = 0, В = I, С—I. Подставляя эти значения истинности элементов А, В, С в (6.5), полу­ чаем X ■У + У = I, или после упрощения

Следовательно, из истинности функции (6.14) следует истинность (6.15), т. е. А - В ■С— Д(Х+ У).

В общем случае функцию G (Ді, А2, ...) можно пред­

ставить в виде суммы нескольких элементарных произ­

167

ведений и предыдущие рассуждения применить отдель­ но к каждому слагаемому. Логическая сумма получен­ ных следствий будет представлять искомую функцию

F(Ku Кг, ...).

Действительно, пусть для произвольных элементов а, Ь, с, d справедливы зависимости а— *Ь, с— к/

Например, допустим, что при наличии связи (6.10) дополнительно утверждается, что

G(A, В, С) =А- В + В - С = I

или в совершенной дизъюнктивной нормальной форме

G=A - В-С + А -B-C+Ä -В-С=\.

Последовательно подставляя в (6.10) значения

/4 = 1, В = 0, С= I; А = 1, 5 = 0, С= 0;

Л= 0, 5 = 0, С= I

искладывая полученные результаты, находим

F = B'-C'+A'-B'-C'=-A,

Г.сли каждый суммируемый член в функции G(Ai, Аг, ■..)

представить также в виде колонки, аналогичной колон­ кам базиса b[Alt Л2, ...], то логическое умножение Е на G можно выполнить как операцию над колонками со­ кращенного базиса Ьс[Аи Л2, ...; Кі, Кг, ■■■} и набором

168