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

явления

как элементарные высказывания.

Пусть А и

Az, ■■■,

Ап — множество признаков, а Кі, Кг,

. . ., Кт—

между

высказываниями

Кі,

■■■,

Кт и Ai, ..

Ап и,

с другой — зависимости

только

между

элементами

А и . ..,

А п или только между

элементами

Кі,

..., Кт,

К г ~ fi (А, , ..., Ап),

Кj —■hj(Al

t , Лп),

Lt (Al,..., Ап) —*Ки

Кі (Aj,..., An;

Kl t ... , Km) = Hi(Ait ... , An\

Кj,...,Km),

. (5.39)

®h(Alt ..., An;

Kt, ... ,K m) — l,

47r(Alt ...,An) = l,

/s (K„ ..., Km) ■--=I,

Предположим

также,

что

наряду

с (5.39)

дополни­

тельно

известны

некоторые

данные

части

признаков

А 1, ...,

Ап, присущих явлениям Кі, ...,

Кт, и что эти дан­

вания, сводится к

нахождению

неизвестной

функции

F (Ки . ■., Кт), удовлетворяющей уравнению

G(Ai, ...,

Ап) + F (Кі,

Кт)= I

(5.40)

при

ограничениях

(5.39), наложенных на

элементы

А і,

..., Ап; Кі, ■• -, Кт-

Задача, сопряженная с данной, состоит в том, чтобы

установить, какие

совокупности признаков

Аі, .... А п

Fi{Ku

• •

•> Кт) А-Gi (А1,

. . . , Ап) = I

(5.41)

при заданной функции Fi(Ki, ■

. Кт) и связях

(5.39).

Положим в соотношениях (5.40) и (5.41)

F(Ki,

.... Km) =Fi(Kl........ Km)-

Тогда,

если

Gi(Aiß

..., Ап) = G(Ai,

. .., A n),

то,

пере­

множив левые части (5.40) и (5.41),

получим

или

G-F + G-F = I,

G(Ai,

. .

An)=F(Ki,

- -

Km),

(5.42)

иначе говоря, в этом случае посылки G(Ait ...,

Ап) (или

Fi(Ki,

..

.,

Кт))

И следствия F(Ki, ..., Кт)

(или

Gi(Ai,

. .

Ап)) эквивалентны.

G{AI, ..., Ап), из

которых следуют некоторые выводы

F(Кі, ..., Km), при

условии, что

элементы Аи ...,

Д„;

Кі, ..., Km связаны зависимостями

(5.39). Покажем,

что

пусть F(Ki, ..

Km)

есть заданная функция, импликаиты

которой требуется найти в виде функции G(AU ..., Ап).

Перейдем

от

функции F(Ki, . •., Km)

к ее отрицанию

Fi = F(Kи •..,

Km)

и с помощью соотношения

(5.41) оп­

ределим

функцию

Gi(Ai, . .., Ап),

которая

связана

с F(Ki, ..., Km) зависимостью

F(Ki, .. ., Km)— >Gi(Ai, ...,

An).

(5.43)

Gi(Ai, ..., An)—+F(Ki, ..., Km),

(5.44)

то, следовательно, G{AU ..., Ап) =ДДЛі, ..., Ап) и яв­

ляется искомой функцией, Если окажется, что

наряду

с (5.44)

справедливо

соотношение

F (Кі, : .

Кт )—^

— »G (Ль ..

Л„),

то F(Ki,

..., Km)=G(Al, . .

Ап), т. е.

G(Aь ..

Л „ ) — полный

набор

импликант

функция

F (Кі, ...,

Кт), через сумму которых

данная

функция

может быть выражена.

Методы решения всех перечисленных выше задач

основываются на

построении

сокращенного

базиса

0с(Лі, .. ., Ап;

Кі,

. ..,

Кт],

который определяется следу­

дачи решаются либо в рамках уравнений

(5.40)

или

(5.44), либо (5.42).

Рассмотрим на конкретных примерах различные частные случаи

соответствия базисов 6С[ЛЬ ..

., А п 1 и Ь С[ К \ , . .., К т \ .

Пример 1. Предположим, что при некоторых условиях, характе­

ризуемых

признаками А і, А г ,

А 3,

в системе

могут

протекать

три

процесса

К і , К г , К з , причем

связи

между К і ,

К ч , К з

и А и

А 2,

А 3

представлены следующими двумя соотношениями:

К і • К г • А і • Лз+ ІСі • К ч ' А і • Лз+

+ Кі-Кч-Аі-Аз-\-Кі-Кг-Аі-Аз = \,

(5.45)

цам базиса Ь[Аи А2, А3, К\, Кг,

К3]. Сохраняя перечисленные столбцы

и отбрасывая остальные,

получаем следующий

сокращенный

базис:

/ =

3 5 0 4

1 7 2 6

4 М , =

1 100

1 1 00

#

Аг =

10 0 0

0 111

= М 3 = о і 0 1 0 10 1

# ^ = 0 1 0 1

0 10 1

#

Кг =

0 0 1 1

ООП

#

Л'з =

0 0 0 0

1111

і = 0 1 2 3

4 5 6 7

Разобьем базис (5.46) на

два

базиса

ЬС[А\, Аг,

А 3] и ЬС[Кь

Кг, ДзІ.

цов стандартных базисов Ь[Кі, Кг,

Кгі

и Ь[Аи Аг, А 3] соответственно.

Согласно (5.46) между значениями і

и /

устанавливается сле­

дующее взаимно однозначное соответствие:

I =•

0,

1,

2,

3,

4,

5,

6,

7;

/ =

3,

5,

0,

4,

1,

7,

2,

(5.47)

6

/ =

0, 1, 2, 3, 4, 5, 6,

7;

(5.48)

і =

2, 4, 6, 0, 3, 1, 7,

5.

Из (5.47) следует, что изображающие числа

ф Л 2 и # Л 3

отно­

сительно базиса Ь [ К і , К г ,

/(з] запишутся как

і =

0 1 2 3

4 5 6 7

4Мі =

1 100

110 0

= # j ? a,

# Д = І 0 0 0

0 111 = # { Е г К2-Е, + К3-{Кі+Кг)}-

(5-49)

# Л 3=

0101

0 101

= # * ,.

/ 3 5 0 4 1 7 2 6

0000

0010

(%) =

1000

0000

(5.50)

0001

0000

0100

0000

0000

0001

0000

0100

Аналогично (5.48) показывает, что в

базисе

Ь[Аи А2,

А31

#/<і = 0000

1111 = # А 3,

#/<2=1010

1010= # Л ь

(5.51)

#/(з=0110

0011 = #

{ A 1 - Ä 2 - Ä 3 + A 2 - ( ä , + A

3) } ,

а матрица ( R i j ) перехода от элементов К ъ

К ъ К з к

А и А2, А 3 по­

цессы К і ,

К ъ К з

проявляют

себя через какие-либо совокупности

признаков

Аь Л2,

А 3,

причем

сведения о признаках можно

предста­

вить в виде, булевой

функции

G(Ab А2, Аз), например,

G(Ai, Аг, Л3)= Л з+ Л ,-Л 2.

(5.52)

сов К и /<2 , К з

на основании

информации (5.52)

и связей (5.45). По

формуле (5.34)

находим

0010 0000

0000

1000

0000 0010

# ( А ,+ Л 1.А2) =

1000

0000

(0100 1111)

0000

0001

0100

0000

0000

0001

0000

0100

= (0101

1101) = # F ( К г , К г ,

К з)

и, следовательно,

F ( K i , К і , K 3) = G ( A i ( K \ , К 2, К з ) , А г ( К і , К г , К з ) ,

А 3 ( К \ ,

К г , К з ) ) = К г + К 2 - К з ,

(5.53)