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

Скачать файл (7,05Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 23.10.2024

Просмотров: 110

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Для квадратной перестановочной булевой матрицы (Rij), содержащей только одну единицу в каждом столб

це и в каждой строке, существует обратная матрица (Ru)-', равная транспонированной матрице (Rij)T:

№ . 0 - 1= № і ) т = № 0 ,

и, таким образом,

(5.32)

где 6jj — единичная

матрица.

Например,

для

матрицы

(5.31)

обратной является

матрица

(

00014

і о ші

(5-33)

0100 /

Умножая

соотношение

(5.29) справа

на

транспониро

ванную матрицу (Ra), получаем

( Gb } ) ®

( R } i ) = (FM).

(5.34)

В частном случае, когда

= #

А ' ,

(G„-) =

ß ' ,

(G„.) =

' , ...

т. е. когда матрица

( G k j )

совпадает с базисом Ь [ А ' , В ' ,

С/,. ..],

выражение(5.34)

определяет

преобразование

переменных, обратное по отношению к преобразованию

(5.19),

(Дг-) =

#Д'(Л,

В, С,...),

{Fti) =

# B '{A ,

В. С,..),

(Узг) = #С'(Л, В, С,...),....

Здесь

изображающие числа

функций

А ' ( А ,

В , С,... ),

В ' ( А ,

В ,

С,... ),

С ' ( А , В ,

С ,

. . . ) , . . . записаны в

базисе

Ь [ А ,

В ,

С , . . . ] .

Например,

используя

матрицу

(5.33),

можно получить обратное к (5

ременных:

11004

# А ’ ( А ,

В ) ,

ОНОУ =

# В ' ( Л ,

В ) ,

или А' = В , В ' =

- B + Ä - В , причем если функции Gi(A',

В ' )

G 2 { A ' , В ' )

заданы

выражениями

(5.24) и

(5.26),

140

то в переменных А, В согласно (5.34) получим:

Рассмотрим теперь обратную задачу. Предположим,

что функции Fi(A,	В, С ,..	.),	FZ(A,	В,	С , ... ) , ... и
Gi{A', В', С ',...,),	GZ(A',	B',	С	' ,	заданы. Тре

буется найти такое преобразование переменных вида

(5.19),		которое переводило			бы функции	Fh в функции
Gk,	т.	е. при всех k=\,		2,. . .	Fh[A(A', В',	С',. .	В(А',
В',	С ',...), С(А',		В',	С , . . . ) , . . ] = Gk{A', В',			С',...).
	В	отличие от	предыдущей решение			данной	задачи

существует не всегда и, кроме того, может быть неодно значным. Например, для

F(A,	В) =А + В,	G(A', В ')= А '-В ',
когда изображающие числа функций
#Е (Л ,	В) =1101,	# G (Л', В')=Ш 00

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

А=А(А', В'), В = В(А', В')

при независимых функциях Л(Л', В'), В(А', В'), кото рая переводила бы функцию F в G.

Если наборы изображающих чисел (5.27) и (5.28) отличаются только порядком расположения столбцов, то задача решается при помощи соотношения (5.29). При этом перестановочная матрица (Rij) строится так же,

как и в прямой задаче. Укажем для каждой колонки на

бора	(5.27), на какое			место		ее следует перевести					с та
ким	расчетом,	чтобы		в результате					получился		набор
(5.28). Тогда,		если колонка				i = k	переводится на				место
j = h, то элемент Rhh=h					все другие			элементы R0 = 0.
Например, пусть
F(A,	В, C )= Ä - C + A - B + B-C,						G(A',		В',	С')=А' + С'.
Тогда, поскольку изображающие числа
					і =	0 1 2 3		4 5 6 7
	# F (А,		В,	С )=		0 111		1	1 1 0	и
					I/ = 0 1 2 3				4 5 6 7
	#G(A',		В', С')		=	0 101			1111

И!

отличаются только порядком расположения нулей и еди ниц, то, следовательно, существует преобразование пере менных вида (5.19), переводящее F в G. Положим в ма трице (Ra) элементы Roo, Rie, Rn, Дзг, Rn, Ru, Reu и R13

равными 1, а все остальные Дц = 0. Это означает, что

разряд t' = 0 переводится в разряд / = 0, разряд і = 1 — в разряд / = 6; і= 2 — в / = 7 и т. д. Таким образом мы

выбираем

1000 0000

0000 0010

0000 0001

0010 0000

т0100 0000

0000 1000

0000 0100

0001 0000

Соответствующее данной перестановочной матрице (Ra)

преобразование переменных можно определить с по мощью соотношения (5.29), если положить

( Л г ) = # Л (/v ) = # ß , (/ѵ) = # С .

Относительно базиса Ь[А, В, С] получим

1000 0000

0000 0010

	/0101	0101	0000 0001
			0010 0000
	ООП ООП
# с			0100 0000
	ѵОООО	1111,
			0000	1000

			0000 0100
			0001	0000

/ООН 1010\ = # А ( Л ' , В’, С),

ООП 0101 ] = # Я( Л' В', С'),

\0101 1100/ = # С (А ', В', С).

Откуда следует, что

A ^ Ä ' - C + B'-C', В = А ' -C' + B'-C', С =А'-С '+В'-С ,

142

Обратное преобразование по отношению к данному по лучается как.

			1000 0000
			0000	1000
# А ' =	/0101 0101		0001	0000
# В ' =	ООП ООН		0000 0001
			0000 0100
# С ' =	\0000 1111
			0000 0010
			0100 0000
			0010 0000
/0010		1011\ =	#Л'(Л, В, С),
0111		0001 ] =	# В '(А ,	В,	С),
ОНО 0110/ =			# С'(Л,	В,	С),

т. е. А '= А (В + С)+В-С, В’ = А- (В + С) +В-С, С'=А-В + + А - В.

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

F(A, В, C)=G(A', B', С').

В самом деле, если положить

0010 0000

0100 0000


	,	0001		0000
	,	0000		1000
	(Axj) —■			t
		0000 0100
		0000 0010
		0000 0001
		1000 0000
то другое	возможное	преобразование будет иметь			вид
	A = Ä '- C ' + B'-C',		B = A '-B'+ Ä '-B ',
	C = (A ' + B')-C'+Ä'-B'-C/.
Всего же	в данном случае		существует 2-61 = 1440		раз

личных перестановочных матриц (Rij). В отдельных слу

чаях к замене переменных сводится задача нахождения решения специальных булевых уравнений.

Рассмотрим пример [13]. Предположим, что разведчик, прово дивший в течение какого-то времени наблюдения за действиями войск противника с целью получить сведения о тактике вооружен-

143

ных сил, представил своему командованию доклад следующего содержания.

1. На холмистой местности в ясные дни локализованные атаки пехоты сопровождались действиями дальнобойной артиллерии, а не

танков.

2. На равнине в ночное время или при плохой погоде применя лась легкая артиллерия и никогда не предпринималось общее наступление пехоты на широком фронте, поддерживаемое тяжелыми

танками.

3. На холмистой местности ночью или при плохой погоде в дневное время использовались тяжелые танки и осуществлялись

локализованные атаки пехоты или же применялась дальнобойная
артиллерия	и проводилось наступление пехоты на широком	фронте.
4. При	плохой погоде ночью или при плохой погоде на	равнин

ной местности, или же при хорошей погоде на холмистой местности применялись либо локализованные атаки пехоты, либо дальнобойная артиллерия и тяжелые танки совместно с наступлением пехоты на

широком фронте.		донесения требуется ответить на три вопроса:
На	основе этого
1)	как влияет	на тактику пехоты: а) равнинная местность,
б) ночное время, в)		плохая погода?

2)при каких условиях будет предпринято: г) наступление на широком фронте, д) использована дальнобойная артиллерия, е) ис пользованы тяжелые танки?

3)если предположить, что битва происходит на равнине в яс

ный день, то какова будет тактика противника?

Для того чтобы решить эту задачу, выделим, прежде всего,

основные понятия, использованные в донесении			разведчика:
— характер рельефа — местность — или		плоская, или холмистая,
но не одновременно плоская и холмистая;		день,	или ночь;
— время проведения	операции — или
-- погода — хорошая	или плохая;

—атака пехоты — или локализованная, или наступление на ши роком фронте. Заметим здесь же, что все битвы происходили с ата ками пехоты;

—артиллерия — дальнобойная или легкая;

—танки — тяжелые или легкие (легкие танки вообще не участ

вовали в сражениях).

В соответствии с перечисленными понятиями введем в рассмот

рение следующие элементарные высказывания:			В — ночь,
А — местность плоская, А — местность	холмистая,
В — день, С — плохая погода, С — хорошая	погода,	А' — наступле
ние пехоты на широком фронте, _А' — локализованная		атака пехоты,
В' — дальнобойная артиллерия, В' — легкая	артиллерия,		С' — тяже