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

 

Приложение изложенных в предыдущих параграфах методов построения сокращенного базиса и решения логических задач существенно ограничивается объемом памяти ЭВМ и их быстродействием. Так, например, если общее число элементов А₁, ..., А_n; Ω₁ ..., Ω_m равно 20, то полный базис b[А₁ ..., А_n; Ω₁ ..., Ω_m] содержит 2²⁰=1 048 576 столбцов. Операции с изображающими числами 1 • 10⁶ разрядов и матрицами такой же размерности невыполнимы на современных ЭВМ. Для построения сокращенного базиса не. обязательно перебирать все колонки полного базиса и проверять истинность булевых функций (6.31), представляющих собой наложенные на элементы А₁, ..., А_n; Ω₁ ..., Ω_m связи при всех возможных комбинациях значений истинности этих элементов. Вместо этого можно выписать только те колонки базиса b[А₁, ..., А_n, Ω₁ ..., Ω_m], которые удовлетворяют (6.31). Чтобы построить таким способом сокращенный базис b_С[А₁, ..., А_n; Ω₁ ..., Ω_m], необходимо представить исходные связи (6.31) в виде

 

(7.1)

 

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

 

(7.2)

 

где обозначает конъюнкцию функций f₁ ...,f_N.

Если представить функцию Е(А₁ ..., А_n; Ω₁ ..., Ω_m) в СДНФ

 

(7.3)

 

то каждое слагаемое (7.3), являясь элементарным произведением, явным образом указывает те значения истинности элементов А₁, ..., A_n, Ω₁ ..., Ω_m, при которых функция Е истинна, и следовательно, может быть интерпретировано как колонка сокращенного базиса. Например, функции (7.3) соответствуют следующие колонки базиса b_с[А₁ ..., А_n; Ω₁ ..., Ω_m]:

 

(7.4)

 

Так как при представлении булевой функции в СДНФ суммируются те и только те элементарные произведения, при которых данная функция истинна, то (7.4) действительно содержит все колонки базиса b_с[А₁ ...,А_n, Ω₁ ..., Ω_m], сокращенного в соответствии со связями (7.1) или (7.2).

Рассмотрим соотношениеВ, связывающее элементы А, В, С, X, Y. По определению эквивалентности, данное соотношение можно записать в виде или в виде

 

(7.5)

 

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

 

(7.6)

 

Трансформируя каждое слагаемое в (7.6) в колонку сокращенного базиса b_С[А, В, С, X, Y], получим

 

(7.7)

 

Базис (7.7) устанавливает следующее соответствие между номерами i и j столбцов базисов b [А, В, С] и b[X, Y]:

 

 

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

В некоторых случаях при формировании функции Е(А₁ ..., А_n; Ω₁ ..., Ω_m)=1, представляющей наложенные на элементы А₁ ..., А_n; Ω₁ ..., Ω_m связи, необходимо производить как умножение, так и сложение отдельных соотношений вида (7.1). Например, если в задаче, рассмотренной в § 6.6, в качестве исходных зависимостей, связывающих элементы А, В, С и А¢, В¢, С¢, взять соотношения (6.27) и (6.29)

 

(7.8)

 

или

 

(7.9)

 

то для построения сокращенного базиса b_С[А, В, С; А¢, В¢, С¢] необходимо вначале сложить левые части соотношении С×(A¢×B¢+`A×`B¢)+`C×(A¢×`B¢+`A¢×B¢)=I; C×(`A¢×`B¢+`A¢×C¢+A¢×`B¢´`C¢)+`C¢×(A¢×`B¢+A¢×C¢+`A¢×B¢×C¢) эквивалентных зависимостям С7.9), и полученный результат умножить на функции

эквивалентные связям (7.8). Тогда

 

(7.10)

 

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

 

(7.11)

 

Соответствие между номерами /и; столбцов базисов b [А, В, С] и b[А¢,B¢, С] в виде

 

 

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

Вернемся еще раз к задаче о нахождении неизвестной функции F(Ω₁,Ω₂,...,), удовлетворяющей уравнению

 

(7.12)

 

где G(A₁, А₂, ...) — заданная функция, А₁ А₂, ..., Ω₁, Ω₂,... — элементы, связанные зависимостями (6.31).

С формальной точки зрения сведения G (А_1, А₂,...) о признаках А₁ А₂ ... распознаваемых объектов, явлений или процессов Ω₁, Ω₂, можно рассматривать как дополнительную связь

 

(7.13)

 

накладываемую на элементы А_1, А₂, ..., наряду с зависимостями (6.31). Соотношение (7.13) выражает утверждение, что некоторая совокупность признаков, характеризующая распознаваемые явления (процессы) Ω₁, Ω₂, ... и представленная функцией G(A₁ A₂, ...), действительно имеет место.

Для нахождения функции F(Ω₁, Ω₂) необходимо определить, какие комбинации классов Ω₁, Ω₂... будут истинны при различных предположениях об истинности признаков А_1, А₂, ... . Наиболее просто эта задача решается для случая, когда функция G(A_1, A₂, ...) имеет вид элементарного произведения, составленного из А_1, А₂, ..., так как при этом значения истинности А_1, А₂, ... определены однозначно. Пусть, например, применительно к связям (7.5) дополнительно утверждается, что

 

(7.14)

 

Соотношение (7.14) справедливо тогда и только тогда, когда одновременно А = 0, В=1, С= 1. Подставляя эти значения истинности элементов А, В, С в (7.5), получим или после упрощения

 

(7.15)

 

Следовательно, из истинности функции (7.14) следует истинность (7.15), т. е

В общем случае функция G(A_1, A₂, ...) представляется в виде суммы нескольких элементарных произведений и предыдущие рассуждения применяются отдельно к каждому слагаемому. Логическая сумма полученных следствий будет представлять собой искомую функцию F(Ω₁, Ω₂...).

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

 

(7.16)

 

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

 

(7.17)

 

Например, допустим, что при наличии связи (7.10) дополнительно утверждается, что или в СДНФ Последовательно подставляя в (7.10) значения А=1, В=0, С=1; А=1, В=0, С=0, А = 0, В=0, С=1 и складывая полученные результаты, найдем т. е.

 

(7.18)

 

Между отдельными слагаемыми функции Е[А₁, А₂, ..., Ω₁, Ω₂) и колонками базиса b_с[А₁ А₂, ...; Ω₁, Ω₂] имеется взаимно однозначное соответствие. Если каждый суммируемый член в функции G(A_1, A₂, ...) представить также в виде колонки, аналогичной колонкам базиса b[А_1, А₂, ...], то умножение функции Е на функцию G можно выполнить как операцию над колонками сокращенного базиса b_с[А₁ А₂, ...; Ω₁, Ω₂...] и колонками, отвечающими функции G. Такое представление функций E и G весьма удобно в случае, когда для решения логической задачи по определению следствий, вытекающих из заданных посылок, привлекается ЭВМ.

Для нахождения следствий, вытекающих из некоторых заданных посылок, можно обойтись и без представления функций Е(А₁ А₂, ...; Ω₁, Ω₂...) и G(A_l, А₂, ...) в СДНФ. Достаточно записать функцию Е(А_и А₂, ...; Cl_u Q₂, ...) в виде суммы произведений, установить, какие из слагаемых в Е(А_1, А₂, ..., Ω₁, Ω₂,) не дают нуля при умножении их на G(A_1, А₂ ...), а затем суммировать входящие в эти члены произведения, составленные только из элементов Ω₁, Ω₂,... или их отрицаний. Например, если наряду с (7.10) положить то при умножении (7.10) на В • С отличными от нуля будут членыа при умножении на .— члены

Складывая произведенияполучи

т. е. при наличии связи (7.10) верноЭтот прием, аналогичный предыдущему, особенно полезен тогда, когда число элементов А_1, А₂, ...; Ω₁, Ω₂, ... столь велико, что операции с сокращенным базисом b_c[A₁, A₂, ...; Ω₁, Ω₂, ...] невозможны из-за ограничений по объему памяти и быстродействию ЭВМ.

При большом числе элементов А_1, А₂, ...; Ω₁, Ω₂, ... можно добиться значительной экономии памяти ЭВМ, если ввести в рассмотрение сокращенный базис b_´ [А_1, А₂, ...; Ω₁, Ω_2, ...], колонки которого соответствуют отдельным слагаемым в функции Е(А_1, А₂, ...; Ω₁, Ω₂, ...), представленной не в СДНФ, а в форме простейшей суммы произведений, т. е. в тупиковой ДНФ. Если приведение функции Е к тупиковой форме почему-либо затруднительно, то можно ограничиться произвольной ДНФ функции Е.

При построении базиса b_´ [А₁, А₂,...; Ω₁, Ω₂...] трансформируем каждое слагаемое функции Е(А_1, А₂, ...; Ω₁, Ω₂, ...) в колонку базиса, заменив элменты Ω_i, и A_j единицей, элементы, `Ω<sub>r</sub>, и `A_s — нулями, а на место отсутствующих элементов, поставив знак ´, подразумевая, что ´ может иметь значение как нуля, так и единицы. Например, базис b[А, В, С; X, Y], отвечающий функции (7.5), запишется так:

 

(7.19)

 

Если во всех столбцах базиса (7.19) заменить каждый знак ´ один раз на 0, а другой раз на 1 и записать столбец 2 раз, где k — количество ´ в данном столбце, то после отбрасывания всех повторяющихся столбцов получим базис b_c[А, В, С; X, Y], эквивалентный (7.7).

Представим функцию G(A_1, A₂, ...) в форме простейшей суммы произведений и каждое слагаемое трансформируем в колонку, заменив, как и раньше, элементы A_i единицами, элементы `A_j — нулями, а на место отсутствующих элементов, записав знак ´, который имеет прежний смысл.

Чтобы выбрать из базиса b_´ [А_1, А_2, ...; Ω₁, Ω_2,...] колонки, совместимые со значениями истинности элементов, входящих в виде сомножителей в слагаемые функции G(A_1, А₂ ...), достаточно поразрядно сравнить каждую колонку, отвечающую отдельному слагаемому в функции G, со всеми колонками базиса b_´ [А₁, А₂, ...; Ω₁, Ω₂, ...] по следующим правилам:

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

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

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

При сравнении колонок, отвечающих отдельным слагаемым в функции G, с колонками базиса b_´ [А_, А₂, ...Ω₁, Ω_2,...] в рассмотрении участвуют только те разряды колонок базиса, которые представляют собой значения истинности элементов А₁, А₂, ... После того как будут отобраны колонки базиса b_´ [А_1, А₂, ...Ω₁, Ω_2,...], сравнимые с колонками, отвечающими функции G(A_1, A₂, ...), разряды Ω₁, Ω₂, ... отобранных колонок объединяются в таблицу, которая и будет представлять собой искомую функцию F(Ω₁, Ω₂, ...). Выполнив над колонками этой таблицы операции, аналогичные операциям, используемым при приведении булевой функции к тупиковой ДНФ, можем трансформировать каждую колонку таблицы в произведение, составленное из элементов Ω_r и `Ω_s и сложить все такие произведения. Результат сложения будет представлять в явном виде функцию F(Ω₁, Ω₂, ...) в тупиковой ДНФ.

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

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

представляется таблицей откуда

Если бы в рассматриваемом случае функция G имела вид G= то колонки базиса (7.19) сравнивались бы с колонкамиС первой колонкой сравнимы только первая и третья колонки базиса, а со второй — первая, вторая и пятая колонки. Следовательно, функция F(X, Y) представляется таблицей Трансформируя колонки в отдельные слагаемые функции F(X, Y), получим Таким образом, т. е. в данном случае существует только тавтологическое решение уравнения

Изложенный алгоритм определения неизвестной функции F(Ω₁, Ω₂, ...) легко программируется для ЭВМ с троичной системой счисления. На ЭВМ с двоичной системой счисления для представления каждого столбца базиса b_´ [А_1, А₂, ...Ω₁, Ω_2,...] и слагаемых в функции G(A_1, A₂, ...) можно использовать две ячейки. Значение истинности, например элемента A_i=0, записывается двумя нулями в i-м разряде обеих ячеек, элемента j=l — двумя единицами в j-м разряде обеих ячеек и элемента А_k= ´ — как 0 в k-м разряде первой ячейки и I в k-м разряде второй ячейки. В ряде задач данный способ более выгоден, чем операции с сокращенным базисом.