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

функций fi, ..., fn, при которых соответствующие элемен­

b[fu--;fn], которые имеют номера отсутствующих в на­

боре (5.5) столбцов, поставить нули, а в остальных раз­ рядах — единицы.

Например, рассмотрим функции

fi = Ä - C + B-C, fz=Ä -C+ B-C, f3=B .

Вычислим по отношению к Ь[А, В, С] изображающие чи­

Выпишем последовательно все столбцы в этом наборе изображающих чисел как строки или соответствующие двоичные числа и укажем справа их десятичные значе­ ния:

к b[fi, /2, /з] изображающее число функции F[fv /2, /з]=1 имеет вид ф Л /і, /г, /з]= 1110 0111.

Так как

1110 0111 = ф [(/ і+ / 2) •/з+(/і+/г) */з],

то, следовательно, функции /і, fz, /з связаны соотноше­

нием

(/і + /г) -/з+ (/і + /г) •/з=І.

121

В справедливости последнего равенства можно убедить­ ся непосредственно, если подставить в него выражения для fь fb fa, заданные через А, В, С. Мы выполним эту подстановку с помощью изображающих чисел fi, f2, !з по

Р. С. Ледли [13] рассматривает следующий пример. Предполо­ жим, что на основе данных, полученных из разных источников, были составлены следующие высказывания о самолетах противника:

1.Самолет с реактивным двигателем и малым радиусом дей­ ствия является бомбардировщиком.

2.Поршневые двигатели бомбардировщиков покрыты тяжелой броней.

3.Поршневые двигатели истребителей рассчитаны на малый ра­ диус действия.

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

5.Реактивные самолеты имеют тяжелую броню.

6.Самолеты, покрытые тяжелой броней, с малым радиусом дей­ ствия — истребители.

7.Легкую броню имеют или самолеты с большим радиусом дей­ ствия, или истребители.

8.Тяжелую броню имеют или самолеты с поршневыми двигате­ лями, или самолеты с малым радиусом действия.

На основе анализа этих восьми высказываний необходимо дать ответы на следующие вопросы:

— Все ли эти утверждения совместны, т. е. нет ли среди них противоречивых высказываний?

— Если высказывания несовместны, то будем предполагать, что только одно из них неправильно. Спрашивается, может ли единствен­

ное утверждение быть отброшено с тем, чтобы оставшиеся выска­ зывания были совместны и если да, то какое это высказывание?

—Зависимы ли какие-либо высказывания?

—Не являются ли некоторые высказывания избыточными?

—Какие заключения можно сделать при различных предполо­ жениях об ошибочности отдельных высказываний?

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

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

двигатель) имеет малый радиус действия, D — имеется легкая броня, D — имеется тяжелая броня.

122

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

fi = (В • С— >-Л) = (JS + C+-4 = I),

и=‘(Л-В—+Б) = (А +В+Б= I),

fa=(A • В -—*■€) = (Ä+B + C—1),

h = (В ■С— >D) = (ß + C+£> = I),

h = ( B —+Ü) = (B + D = l),

h = ( D - C — *A) = (D+ C+A = I),

/7= (A + C—>-£>) = (Ä ■C+D = l),

fs= (B + C— +B) = (B-C + D = I).

По отношению к стандартному базису Ь\А, В, С, D\:

#.4=0101 0101 0101 0101

#ß=0011 ООП ООП ООП

#С =0000 1111 0000 1111

# 0 = 0000 0000 1111 1111

вычислим изображающие числа функций /ь /2, . . ., f8:

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

Для ответа на второй вопрос также необходимо составить произ­ ведения изображающих чисел # f,, не включая в него те числа # f 3-, противоречивость которых проверяется. Заметим, что если любое из высказываний 1—4 (или же все эти высказывания) отбросить, то

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

123

единицы. Следовательно, ответ на второй вопрос будет: «Одно из высказываний 5, 6, 7 или 8 — ложно».

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

из которых для дальнейшего будет существенна только зависимость fi+fa = h и, кроме того,

(/7 + /і = і ) = (fi—

(/а+?2=І) — (fs— *-fü)-

имеются только колонки, соответствующие числам 2, 3, 4, 5, 7. По­ этому # f ( f i, /7, fs) =0011 1101. Найдем все первые импликанты функции F(fь f7, fs):

Таким образом, функции f1, f7, fa связаны зависимостью

fi • fa+fi - fi+ fi • fa+fi • f8=1

или

}т (fi+fs+fi) +fs • (/1+ / 8 + / 7) =

—(fi+fa) ’ (/7+ /s+ fi) =1.

Последнее соотношение показывает, что одновременно должны вы-

полняться условия: fi+fa = l, как было ранее установлено, и fi-fs+ +fi = I или f i - fa— >-/і. Совершенно аналогично можно получить связь

fi, ..., fi являются избыточными.

Выше мы установили, что среди fs,..., fs содержится ложное высказывание, а высказывания f i, .... f4 истинные. Если предполо­

124

так и ложными. Если рассматривать и истинный, и ложный выводы как возможные исходы случайного события, то, вообще говоря, веро­ ятность получить верный вывод из ложных посылок, как правило, должна быть меньше, чем вероятность получить ложный вывод. Но даже если принять, что эти вероятности равны 0,5, то вероятность получить из ложных посылок f7, fs четыре истинных вывода fi,

!з, fi будет (0,5)4~0,06. Поэтому было бы в значительной степени обоснованным одно из двух несвязанных утверждений f5 или / 6 рас­ сматривать как ложное.

Предположим, что дополнительно было установлено, что выска­ зывание f6 ложно. Тогда среди высказываний fb .. ., f5, f7 и fs утверждения fu .. ., (4 являются избыточными; таким образом, сле­ дует оставить только высказывания f5, / 7 и fs. Ввиду того что эти

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

Если предположить, что утверждение / 5 ошибочно, то остаются высказывания fs, f7 и fs, изображающее число произведения которых равно

# f 6.;f7.f8= 0000 0000 0000 ООП = # ß . C - D .

При этом противник располагает самолетом с легкой броней, реак­ тивным двигателем и большим радиусом действия.

5.6.БУЛЕВЫ УРАВНЕНИЯ. ОБЩИЙ МЕТОД РЕШЕНИЯ СИСТЕМЫ БУЛЕВЫХ УРАВНЕНИИ В ФОРМЕ ЭКВИВАЛЕНТНОСТИ

Решение многих задач, связанных с распознаванием или классификацией объектов, можно свести к решению булевых алгебраических уравнений с одним или более неизвестными.Примером булева уравнения с одним неиз­ вестным может служить следующее соотношение:

X • ( А + В ) = А - В - С ,

где X — некоторая булева функция, зависящая от А, В, С, которую требуется найти так, чтобы в результате под­ становки Х(А, В, С) в данное уравнение оно обраща­ лось в тавтологию. Перейдем от элементов X, А, В, С к их изображающим числам. Относительно базиса Ь[А, В, С]найдем

# ( Л - ß- C)=0000 0001, # (Л + 0)=0111 0111

125