Глава 6. Методы построения логических систем распознавания

Для решения задач распознавания объектов или явлений на практике приходится прибегать к построению систем распознавания (см. гл. 1).

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

В данной главе рассматривается идея использования сокращенного базиса применительно к логическим системам с большим числом элементов; на конкретных примерах показаны особенности построения алгоритмов решения логических задач и реализации этих алгоритмов на ЭВМ.

§ 6.1. Решение задач распознавания при большом числе элементов

Приложение изложенных в предыдущих параграфах методов построения сокращенного базиса и решения логических задач существенно ограничивается объемом памяти и их быстродействием. Так, например, если общее число элементов равно 20, то полный базис содержит столбцов. Операции с изображающими числами в 1 -106 разрядов и матрицами такой же размерности невыполнимы на современных Для построения сокращенного базиса не обязательно перебирать все колонки полного базиса и проверять истинность булевых функций (5.39), представляющих собой наложенные на элементы связи при всех возможных комбинациях значений истинности этих элементов. Вместо этого можно выписать только те колонки базиса которые удовлетворяют (5.39). Чтобы построить таким способом сокращенный базис необходимо представить исходные связи (5.39) в виде

и перемножить функции Так как функции должны быть истинны одновременно, то условия (6.1) можно записать в виде одного соотношения:

где обозначает конъюнкцию функций

Если представить функцию в

то каждое слагаемое в (6.3), являясь элементарным произведением, явным образом указывает те значения истинности элементов при которых функция Е истинна, и, следовательно, может быть интерпретировано как колонка сокращенного базиса. Так, например, функции (6.3) соответствуют следующие колонки базиса

Поскольку при представлении булевой функции в суммируются те и только те элементарные произведения, при которых данная функция истинна, то (6.4) действительно содержит все колонки базиса сокращенного в соответствии со связями (6.1) или (6.2).

Рассмотрим соотношение (5.8)

связывающее элементы По определению эквивалентности, данное соотношение можно записать в виде

или после преобразований — в виде

Представим функцию (6.5) в СДНФ:

Трансформируя каждое слагаемое в (6.6) в колонку сокращенного базиса получим:

Базис (6.7) устанавливает следующее соответствие между номерами столбцов базисов и

Этот результат совпадает с результатом, полученным в § 5.6.

В некоторых случаях при формировании функции представляющей наложенные на элементы связи, необходимо производить как умножение, так и сложение отдельных соотношений вида (6.1). Например, если в задаче, рассмотренной в § 5.7, в качестве исходных зависимостей, связывающих элементы взять соотношения (5.35) и (5.37)

и

или

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

эквивалентных зависимостям (6.9), и полученный результат

умножить на функции эквивалентные связям (6.8). В итоге получим:

Трансформируя отдельные слагаемые выражения (6.10) в колонки сокращенного базиса, будем иметь:

Соответствие между номерами столбцов базисов в виде

полностью согласуется с соответствием, устанавливаемым перестановочными матрицами в (5.35а) и (5.36а).

Вернемся еще раз к задаче о нахождении неизвестной функции удовлетворяющей уравнению

где заданная функция; — элементы, связанные зависимостями (5.39).

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

накладываемую на элементы наряду с зависимостями (5.39). Соотношение (6.13) выражает утверждение, что некоторая совокупность признаков, характеризующая распознаваемые

явления (процессы) и представленная функцией действительно имеет место.

Для нахождения функции необходимо определить, какие комбинации элементов будут истинны при различных предположениях об истинности независимых элементов из числа элементов Наиболее просто эта задача решается для случая, когда функция имеет вид элементарного произведения, составленного из элементов так как при этом значения истинности всех элементов определены однозначно. Пусть, например, применительно к связям (6 5) дополнительно утверждается, что

Соотношение (6.14) справедливо тогда и только тогда, когда одновременно Подставляя эти значения истинности элементов в (6.5), получим

или после упрощения

Следовательно, из истинности функции (6.14) следует истинность (6.15):

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

Действительно, пусть для произвольных элементов справедливы зависимости

или

Перемножая левые части (6.16), добавляя слагаемое и объединяя члены получим откуда на основании (6.16) находим

или

Например, допустим, что при наличии связи (6.10) дополнительно утверждается, что , или в . Последовательно подставляя в (6.10) значения

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

Между отдельными слагаемыми функции и колонками базиса имеется взаимно однозначное соответствие. Если каждый суммируемый член в функции представить также в виде колонки, аналогичной колонкам базиса то умножение функции Е на функцию можно выполнить как операцию над колонками сокращенного базиса и колонками, отвечающими функции Такое представление функций весьма удобно в случае, когда для решения логической задачи по определению следствий, вытекающих из заданных посылок, привлекается ЭВМ.

Для нахождения следствий, вытекающих из некоторых заданных посылок, можно обойтись и без представления функций в Достаточно записать функцию в виде суммы произведений, установить, какие из слагаемых в не дают нуль при умножении их на и затем суммировать входящие в эти члены произведения, составленные только из элементов пли их отрицаний. Например, если наряду с (6.10) положить то при умножение (6.10) на отличными от нуля будут члены , а при умножении на члены . Складывая произведения и получим т. е. при иаличии связи (6.10) верно Этот прием, аналогичный предыдущему, особенно полезен тогда, когда число элементов столь велико, что операции с сокращенным базисом невозможны из-за ограничений по объему памяти и быстродействию ЭВМ.

При большом числе элементов можно добиться значительной экономии памяти ЭВМ, если ввести в рассмотрение сокращенный базис колонки которого соответствуют отдельным слагаемым в функции представленной не в СДНФ, а в форме простейшей суммы произведений, т. е. в тупиковой ДНФ. Если приведение функции Е в тупиковой форме почему-либо затруднительно, то можно ограничиться произвольной ДНФ функции Е.

При построении базиса трансформируем каждое слагаемое функции колонку базиса, заменив элементы единицей, элементы нулями, а на место отсутствующих элементов поставив знак X, подразумевая, что X может иметь значение как нуля, так и единицы. Например, базис отвечающий функции (6.5), запишется так:

Если во всех столбцах базиса (6.19) заменить каждый знак X один раз на 0, а другой раз на 1 и записать столбец раз, где k — количество X в данном столбце, то после отбрасывания всех повторяющихся столбцов получим базис , эквивалентный, (6.7).

Представим функцию в форме простейшей суммы произведений и каждое слагаемое трансформируем в колонку, заменив, как и раньше, элементы единицами, элементы нулями, а на место отсутствующих элементов записав знак X, который имеет прежний смысл.

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

а) если в сравниваемых разрядах хотя бы одной колонки содержится знак X, то эти разряды сравнимы;

б) если в сравниваемых разрядах двух колонок не содержится знака X, то сравнимы только комбинации 0 и 0, 1 и 1, а комбинаци 0 и 1, 1 и 0 несравнимы;

в) если все разряды двух колонок сравнимы, то сравнимы сами колонки; в противном случае колонки несравнимы.

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

Например, предположим, что относительно базиса Трансформируем эту функцию в колонку и сравним последнюю с колонками базиса (6.19). Так с 1

как с данной колонкой сравнимы только четвертая и пятая колонки базиса, то можем утверждать, что функция представляется таблицей откуда Если бы в рассматриваемом случае функция имела вид то колонки базиса (6.19) сравнивались бы с колонками

С колонкой сравнимы только первая и третья колонки базиса, а с колонкой — первая, вторая и пятая колонки. Следовательно, функция представляется таблицей Трансформируя колонки в отдельные слагаемые функции получим Таким образом, т. е. в существует только тавтологическое решение уравнения

Изложенный алгоритм определения неизвестной функции легко программируется для ЭВМ с троичной системой счисления. На ЭВМ с двоичной системой счисления для представления каждого столбца базиса и слагаемых в функции можно использовать две ячейки. Значение истинности, например, элемента записывается двумя нулями в разряде обеих ячеек, элемента двумя единицами в разряде обеих ячеек и элемента — как 0 в разряде первой ячейки и 1 в разряде второй ячейки. В ряде задач данный способ более выгоден, чем операции с сокращенным базисом.