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

храияется в таблице (fі); далее перейдем к сравнению колонки а+1 с первой колонкой таблицы (f2).

Если (а) -/* ф), ф) +►(а), то перейдем к сравнению ко­

лонки а таблицы (/,) с колонкой ß - f 1 таблицы (f).

Эти операции производятся до тех пор, пока не будут перебраны все возможные пары значений а=1, 2, ... и ß—1, 2, ..., т. е. пока каждая колонка таблицы (/1) не

будет сравнена со всеми колонками таблицы (,/2). В результате часть колонок (может быть пи одна) из таблиц (fi) и (/г) будет перенесена в таблицу (fyjz), а сами таблицы (fi) и (/2) упростятся; обозначим их (f'i) и

(Г 2).

2. Перемножим таблицы (f'i) и (Гг)- Рассмотрим умножение колонки а' таблицы (f'i) на колонку ß' (f'z)- Если колонки а' и ß' несравнимы, т. е. хотя бы в одном

из одинаковых разрядов этих колонок встречаются числа

(/'г). Если колонки и' и ß' сравнимы, то их перемножают

поразрядно по правилам:

0-0=0, 0- Х = X -0= 0, 1■ X = X •1= 1, Ы = 1,

Х - Х = Х.

Результат умножения представляется в виде колонки, аналогичной колонкам-сомножителям, которая записыва­ ется в таблицу (fi•[?.)- Затем перейдем к умножению ко­ лонки а' из (f'i) на колонку ß '+ l из (/'2). Операции по­

вторяются до тех пор, пока каждая колонка таблицы

форме.

Алгоритм приведения булевой функции к тупиковой дизъюнктивной нормальной форме. Для упрощения таблицы (fi-fz), представляющей произведение двух бу­ левых функций, каждую колонку а таблицы сравнивают

с каждой последующей колонкой а + Я этой же таблицы по следующим правилам:

— если сопоставляемые колонки полностью совпада­ ют: (а) = (а + Я), то одна из них, например а, сохраняет-

»74

и а + А;

— если (а + А)— *(а), то колонка а + А отбрасывает­ ся, а колонка а сохраняется; далее сравниваются колон­ ки а и а + Я + 1;

—если все разряды двух сопоставляемых колонок совпадают, кроме одного, и в этом разряде одна колон­ ка содержит 0, а другая 1, то обе колонки заменяются одной, которая совпадает в общей части разрядов со сравниваемыми колонками, а в том разряде, где содер­ жались числа 0 и 1, ставится знак X;

—если две сопоставляемые колонки а и а + А несрав­ нимы только в одном г-м разряде, а содержимое осталь­ ных разрядов таково, что для колонок (а)' и (а + Я)', получающихся из (а) и (а + Я) вычеркиванием г-го раз­ ряда, выполняется условие (а + Я)'— *(а)', то обе колон­ ки а и а + Я сохраняются, но в г-м разряде последней записывается знак X. Далее переходят к сравнению ко­ лонок а и а+А+'І.

Процедура сокращения производится над всеми колонками таблицы результатов (fi-f2) последовательно несколько раз до тех пор, пока дальнейшие упрощения по указанным правилам станут невозможны. Каждая колонка полученной таблицы соответствует одному сла­ гаемому, которое входит в булеву функцию fі • fz, запи­

санную в тупиковой дизъюнктивной нормальной форме. Алгоритм получения отрицания булевой функции

будем предполагать, что функция /(Ль Л2, ...; Ки Кг, ■■•)

представлена в виде таблицы (/), колонки которой обра­ зованы из чисел 0, І и Х . Проделаем следующие операции.

1. Заменим числа, содержащиеся в разрядах колонок

175

в соответствии с алгоритмом приведения булевой функ­ ции к тупиковой дизъюнктивной нормальной форме. По­ лученная таблица будет представлять отрицание функ­ ции /(Л 4, Лг, • • ■; Кі , Кг, .. .) в форме простейшей суммы

произведений.

6.4.КАКАЯ ЗАВТРА ПОГОДА? ПРОБЛЕМА НАКОПЛЕНИЯ АПРИОРНЫХ ДАННЫХ

Рассмотрим задачу прогноза погоды на завтра, основанного на использовании различных народных примет. Для нас эта задача интересна с двух точек зрения. Во-первых, при таком прогнозе используются многочисленные разнородные признаки, характеризую­ щие различные атмосферные явления или поведение животных, при­ чем внешне эти признаки представляются совершенно не связанными между собой высказываниями. Рациональное построение системы распознавания при большом числе независимых признаков имеет свои специфические особенности. Во-вторых, установление основных зако­ номерностей в задаче прогноза погоды, так же как и во многих естественных науках, основывается «а наблюдениях и имеет характер эмпирической индукции. Обобщение данных наблюдений с целью выявления причинно-следственных связей между отдельными призна­ ками явлений составляет одну из кардинальных задач каждой кон­ кретной науки. Решение этой задачи, как будет показано в разби­ раемом ниже примере, может быть получено с помощью алгебры ло­ гики.

Рассмотрим в качестве исходного следующий текст [19], относя­ щийся к зимним месяцам: январю и февралю:

«Какая завтра погода?» Это ты можешь узнать сам, если вни­ мательно приглядишься к солнцу, луне, звездам. Сегодня был мороз, и солнце как бы спряталось за льдистый серебряный дымок. За та­ ким же дымком спрятаны дома и деревья. Дома и деревья казались неясными и расплывчатыми, как солнце морозного дня. Запомни: льдистый серебряный дымок всегда обещает продолжение мороза. О завтрашнем сильном морозе предупредит тебя заходящее солнце. Когда оно уходит на ночь красным, обмороженным, то назавтра не жди снега — будет ясно и холодно.

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

176