Файл: Горелик, А. Л. Некоторые вопросы построения систем распознавания.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 113
Скачиваний: 1
Продолжая проверку всех оставшихся пар |
значений Х \ |
У-' для нулевых разрядов фХ и # У в Ъ[А, |
В, С], мы от |
бросим пару Х'г, Уг — 0, 1, поскольку |
|
1-О+ О-О+І-ОфО-І + Ы + ЬО,
и запишем в разряд 7= 0 таблицы результатов X3, У3 =
= (1, 1), так как
1-0 + 0- 0+1- 0 = 0-1+0-1 + 1-0.
Аналогично можно выбрать все допустимые пары значе
ний Х>, Уі по отношению к 1, 2-му и т. |
д. разрядам |
фХ и ф У в базисе Ь[А, В, С]. |
|
В общем случае для проверки /-й пары значений X», |
|
У-1 столбцы табл. 5.1, стоящие справа от |
неизвестных, |
последовательно умножаются на г-й столбец коэффици ентов и результаты логически складываются. При совпа дении значений сумм для столбцов, расположенных вы ше и ниже горизонтальной линии, разделяющей наборы чисел для правой и левой частей уравнения, значения Xi, Уі, соответствующие j-му столбцу неизвестных, подставляются в і-й разряд таблицы результатов. Про
должая |
этот процесс, |
мы |
придем |
к указанному в |
||
табл. 5.2 |
решению для фХ и ф К |
Легко видеть, что су |
||||
ществует |
|
|
|
|
|
|
|
2 X 2 X 2 X 4 X 2 X 4 X 3 X 4 = 3072 |
|
||||
различных неэквивалентных |
пар |
решений |
уравнения |
|||
(5.8). Например, если |
взять |
числа, |
стоящие первыми |
|||
в каждом |
разряде (7 = 0, 1,...,7) |
таблицы |
результатов, |
|||
то получим |
|
|
|
|
|
|
фХ = 1000 0010 = # ( Л- Д - С+ Л- Б - С) ,
фГ=0010 Ю00= ф (Ä-B-C + Ä-B-C),
т. е. представление о существовании тела X либо не свя зано ни с одним из названных атмосферных явлений, либо вызвано только появлением облаков и разрядами атмосферного электричества, а представление о сущест вовании группы тел У вызвано либо только облаками,
либо только атмосферными разрядами. В свете полу ченных результатов нет серьезных оснований считать, что небесные тела Х и У действительно существуют.
Описанный метод можно применять и при решении системы булевых уравнений в форме эквивалентности,
130
однако при этом задача усложняется, так как проверяе мая пара значений Х \ Yi должна одновременно удов
летворять всем уравнениям системы. Заметим, что про цедуру отбора пар значений Х \ Yi, удовлетворяющих,
например, уравнению (5.8), можно значительно упро стить, если ввести в рассмотрение операции над буле выми матрицами. Прямоугольная матрица называется булевой, если элементами ее являются числа 0 и 1. Про
изведение булевых матриц
ifiij) = |
(Oft) (g) {bkj), |
(5.14) |
обозначаемое знаком (х), |
определяется |
по правилам ма |
тричного умножения |
|
|
сц = £ aihbk} |
(5.15) |
|
|
k |
|
с той только разницей, что операция суммирования про изведений элементов строк и столбцов (5.15) заменяется логическим сложением.
Например,
Соотношение импликации, обозначаемое (аіз)->-(/;^), справедливо для двух булевых матриц (а,ц) и (Ьц), если нет і и /, таких, что bis= 0 и а^= 1. Например,
Транспонированной матрицей по отношению к (ац), как и обычно, называется матрица (Ьіі) = (ац), получаемая из (aij) при перемене местами строк и столбцов.
Заметим теперь, что последовательное умножение с последующим сложением каждого столбца в наборе изображающих чисел коэффициентов на все столбцы набора изображающих чисел неизвестных эквивалентно умножению булевой матрицы, полученной транспонирова нием матрицы изображающих чисел коэффициентов, на булеву матрицу, составленную из изображающих чисел неизвестных. Выполняя эти вычисления для левой части
9* |
131 |
уравнения |
(5.8), |
получим булеву матрицу |
|
||||||||||
і = о 0 0 0 |
|
|
|
|
/ = |
0 |
1 2 |
3 |
|
||||
= 0 1 2 3 |
= 0 0 0 0 0 |
|
|||||||||||
1 1 0 0 |
|
1 1 1 1 1 |
0 |
|
|||||||||
2 |
0 |
1 0 |
|
/1 |
1 1 1\ |
|
2 |
0 |
1 0 |
(5.16) |
|||
3 |
1 1 0 |
|
|
3 |
1 1 1 1 |
|
|||||||
4 |
0 0 1 |
|
0 |
1 0 |
0 |
|
4 |
0 0 |
11 |
|
|||
|
\0 |
0 1 1, |
|
|
|||||||||
5 |
1 0 1 |
|
|
5 |
1 1 1 1 |
|
|||||||
6 |
0 1 1 |
|
|
|
|
|
6 |
0 |
1 1 1 |
|
|||
7 |
1 1 1 |
|
|
|
|
|
7 |
1 1 1 1 |
|
||||
Аналогично для |
правой |
части |
уравнения (5.8) |
находим |
|||||||||
|
|
|
|
|
|
|
/ |
= |
О |
1 2 3 |
|
||
|
|
1 1 О |
|
|
|
і = 0 |
10 |
10 |
|
||||
|
|
0 1 О |
|
|
|
|
1 |
10 |
10 |
|
|||
|
|
1 ОО |
|
1 ОО0\ |
|
о |
1 0 |
0 0 |
|
||||
|
|
0 0 1 |
|
= |
1 1 1 1 |
=(<*«)■ |
(5.17) |
||||||
|
|
|
10 |
10 |
13 |
||||||||
|
|
1 1 1 |
|
1 1 1 1 / |
|
4 1 1 1 1 |
|
|
|||||
|
|
0 1 1 |
|
|
|
|
5 |
1 1 1 1 |
|
|
|||
|
|
1 0 1 |
|
|
|
|
6 |
1 |
1 |
1 |
I |
|
|
|
|
О0 1 |
|
|
|
|
7 |
1 1 1 1 |
|
|
|||
Сравнение |
матриц |
(Сц) |
и |
(da) |
показывает, что |
||||||||
в строках с номером |
г = 0 совпадают элементы |
с индек |
|||||||||||
сами j —1 |
и j = 3: Coi = doi = 0, Соз= dos= 0 и, следовательно, |
||||||||||||
в разряд г = 0 таблицы результатов должны быть внесе
ны значения А1, У*=1, |
0 и А3, |
У3= 1 , 1. Далее в стро |
|||
ках |
с номером |
і = 1 совпадают |
элементы |
ci0 = dw= 1 и |
|
Ciz=di2 =\ с индексами |
/'= 0 и / = 2; поэтому в разряд |
||||
t= l |
таблицы |
результатов записываются |
значения А0, |
||
У°= 0, 0 и А2, У2 = 0, 1. |
Точно так же получим для всех |
||||
оставшихся г следующие совокупности значений индекса
/: г = 2, |
/ = 2, |
3; і = 3, |
/ = 0, |
1, 2, |
3; і' = 4, |
/ = 2, |
3; |
г = 5, |
|||||
/ = 0, 1, |
2, |
3; |
г = 6, |
/= 1, 2, 3; і = 7, / = 0, |
1, |
2, 3, |
которые |
||||||
полностью |
соответствуют |
результату, |
приведенному |
в |
|||||||||
табл. 5.2. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Для |
системы из г уравнений в форме эквивалентности |
||||||||||||
решения находятся |
из |
условия |
совпадения |
элементов |
|||||||||
одновременно во всех г матрицах (с^) |
и (с?^), 5 |
= |
1 |
г, . |
|||||||||
вычисленных таким же |
образом, |
как и |
матрицы (5.16) |
и |
|||||||||
(5.17). Если при каком-либо і не существует |
таких /, что |
||||||||||||
|
|
|
-ц = |
(s) |
|
, Г, |
|
|
|
|
(5.18) |
||
|
|
|
dи ’ |
|
|
|
|
|
|||||
132
то система уравнений не имеет решения. Заметим также, что для уравнений в форме импликации не нужно тре бовать совпадения элементов матриц (Cij) и (йц)\ для
существования решения достаточно потребовать только, чтобы единице слева обязательно соответствовала еди ница справа.
Рассмотрим пример [131. Предположим, что на острове нахо дятся два пункта опознавания самолетов. В течение нескольких дней в небе летали одни и те же вражеские самолеты. Опознать тип на блюдаемых вражеских самолетов было трудно и это привело к не которой полемике между персоналом двух наблюдательных пунктов.
Предполагается, |
что |
наблюдались |
четыре типа вражеских самоле |
||||
тов. Назовем эти типы А, В, X и У, причем определенно известно, |
|||||||
что типы А и В существуют. На |
протяжении трех |
последующих |
|||||
дней от каждого пункта поступали следующие сообщения: |
|||||||
|
Пункт 1 |
|
|
Пункт |
2 |
||
1-й день: Самолеты были двух |
|
Были самолеты типа Л и не |
|||||
2- |
типов: X и Y |
было самолетов типа В. |
|||||
й день: |
Наблюдались самоле |
Наблюдались самолеты типа |
|||||
|
ты типа А, |
или В , или |
У и не было самолетов типа А |
||||
|
же А и В одновре |
или же это были самолеты ти |
|||||
3- |
менно |
|
|
па X |
|
||
й день: |
Были самолеты типа |
Были самолеты типа А |
|||||
|
X |
и |
одновременно |
|
|
|
|
|
типа |
А |
или В, или и |
|
|
|
|
|
А, и й; или же это |
|
|
|
|||
|
самолеты |
типа А и |
|
|
|
||
|
типа |
У |
|
|
|
|
|
Требуется определить, можно ли на основе только этих сообщений заключить, что самолеты типа X и У в действительности являются
самолетами типов Л и В? |
|
|
|
|
Л и й , |
при |
||
Очевидно, если_пам удастся выразить X и У через |
||||||||
чем Х ф А - В , У ф А - В , |
то ответ |
должен |
быть положительным. Со |
|||||
общения |
наблюдательных пунктов |
|
трансформируются |
в следующие |
||||
булевы |
уравнения |
относительно |
|
неизвестных функций X |
и У: |
|||
а) Х -Y— A -В, б) Д + Й= У -Л + Х, в) Х-(А + Й )+Л -У =Л . |
|
|||||||
Составим рабочую таблицу (табл. 5.3). |
|
|
|
|||||
Для |
уравнения |
а находим |
|
|
|
|
|
|
|
/00014 |
|
|
(1111) = |
|
|
||
I® (0001)= |
Я |
= (4 ‘>), |
|
|
|
|||
|
\ |
0001 / |
|
|
|
|
|
|
для уравнения |
б |
|
/ 0000\ |
|
|
|
||
|
|
|
|
: (Д. |
|
|
||
|
|
|
(1111) = |
/1111 |
|
|
||
|
|
|
|
\ |
1111 |
|
|
|
|
|
|
|
1111 |
|
|
|
|
|
|
'11 |
|
|
/0111 |
|
|
|
|
|
01 |
0011\ _/ 0101 |
|
|
|
||
|
|
11 |
0101/ ” |
0111 |
|
|
|
|
|
|
01 |
|
|
\0101 |
|
|
|
133
Таблица 5.3
Порядковый номер булева уравнения
а
б
в
Коэффициенты и их изобра жающие числа в Ь[А, В]
# і = |
п п |
|
4 М -Л = |
0100 |
|
# (А + |
В) = |
0111 |
# |
Д = |
1010 |
# 1 = |
1111 |
|
# { А + В ) = 0111
#Л = 0101
#Л = 0101
для уравнения в
Изображающие числа комби нации неизвестных в b ( X , Y):
хз = о т
уі = ООП
#А '- У = С001
#1 = 1111
# 1 = 1111
# У = ООП
# X = 0101
44= -АТ = 0101
#У = 0011
#1 = 1111
00' |
'0000' |
|
10 |
ОШ |
= ф . |
0101 |
||
|
0111 |
|
0' |
0000' |
(3) |
IS» (11 И) = |
1111 |
|
0000 |
И/ )• |
|
|
1111 |
|
Сравнивая построчно матрицы (г!?») и (djp), получаем для нуле вой строки
со/’ = ^о)’ при / = 0,1,2;
со/)= 4P пРи / = °;
Cgy»= при / = 0, 1,2, 3,
и, следовательно, только значения А0, У°=0, 0 удовлетворяют всем трем уравнениям в нулевых разрядах и #У . Так как
сС>_ |
rfd) |
при / = |
3; |
сі/ - |
йі/ |
||
с(?)_ |
rf(2) |
при / = |
1,3; |
сі/ — |
diy |
||
с(3)_ |
rf(3) |
при / = |
1,2, 3, |
C l j — |
“ 1; |
134
то только X3, Y3= 1, 1 можно записать в первые разряды |
и фУ, |
||||
Для второй строки |
|
|
|
|
|
4 / )== |
<4)* |
ПРИ / |
= |
0, 1, 2; |
|
с 2/) = |
4 / * |
ПРИ |
/ = 1 . 2 , 3 ; |
|
|
|
4/* |
при / = |
0, 2. |
|
|
Очевидно, что общее значение для |
трех уравнений есть |
/ = 2 и |
|||
потому при t'=2 следует взять |
X2, У2 = 0, 1. Аналогично из того, что |
||||
заключаем, |
что при і = 3 |
X*, У‘= 1, 0. |
Таким образом, |
^y=oilO = #(A. ß + Ä-S). |
|
|
#Х =0101 = #А, |
|
Найденное |
решение Х = А , |
Y = A ■В + А ■В показывает, что наблю |
давшиеся самолеты типа X могли в действительности быть самолета ми типа А, а самолеты типа Y могли быть самолетами либо типа А, либо типа В, но не А • В.
Рассмотрим теперь второй вариант. Предположим, что наблюде ния были такие же, как и раньше, за исключением того, что во вто рой день пост 1 установил, что были самолеты типа В и не было самолетов типа А. Спрашивается, можно ли на основании получен ных наблюдений заключить, что противник имеет только два типа
самолетов: А и 5? |
данных наблюдения _за самолетами |
отвечают |
|
Второму варианту |
|||
следующие уравнения: |
а) |
X-Y=A-B, б) A- B=A-YX, в) |
(А + 5)- |
■X+A-Y=A. Найдем |
возможные решения Х и Y второго |
уравне |
|
ния. По отношению к Ь{Л, |
51 и к Ь[Х, У] соответственно будем иметь |
||
#Л-Д = 0010 |
# |
1 = 1111 |
|
|
=1010 |
# |
У = 0011 |
# 1 |
=1111 |
# |
X =0101 |
и, следовательно,
Откуда получаем
со/> = |
4 |
? |
ПРИ |
і = |
°; |
4 f = |
4 f |
ПРИ І |
= ° ’2 • з; |
|
4 / ' = |
4 |
/ ’ |
ПРИ |
7 = |
1 ,2, |
3; |
4 f = |
4 / ’ |
ПРИ / = |
2. |
135