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

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

решении логической задачи с помощью ЭВМ.

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

нормальной форме. Достаточно записать Е(А ь А2, ...; Кі, Кг, ...) просто в виде суммы произведений, установить, какие из слагаемых в Е(А{, А2, ...; Кі, Кг, ...) при умно­ жении их на G(AU А2, ...) не обращаются в нуль, и за­

тем просуммировать входящие в эти члены произведе­ ния, составленные только из элементов Кі, Кг, ■. ■или их

отрицаний. Например,_если наряду с (6.10) положить G(A, В, С) = В ■С+ А ■С = I, то при умножении (6.10)_на К -С отличными от нуля будут члены А ■В-С_-А^-В'-С' и,

F(A', B', С')=В'-С' + Ж'-В'-С'+А'-В'-С' =

= В ' - (С'+Ж') +А'-В'-С',

т. е. при наличии связи (6.10) выполняется соотношение

С(Ж + В)— >В'- (C'+Ä') + А' ■В' ■С'.

Этот прием, по существу совершенно аналогичный пре­ дыдущему, особенно полезен тогда, когда число элемен­

ваются невозможными из-за ограничений по объему па­ мяти и. быстродействию ЭВМ.

При большом числе элементов Аь А2, ...; Кі, К2, ...

можно добиться значительной экономии объема памя­

Кг, ...), представленной не в совершенной дизъюнктив­

ной нормальной форме, а в форме простейшей суммы произведений, т. е. в так называемой тупиковой дизъ­ юнктивной нормальной форме. Если приведение функции

Е к тупиковой форме оказывается почему-либо затруд­

нительным, можно ограничиться произвольной дизъюнк­ тивной нормальной формой.

169

Если во всех столбцах базиса (6.19) заменить каждый знак X один раз на нуль, а другой—на единицу и запи­ сать столбец 2й раз, где k — количество X в данном

столбце, то после отбрасывания всех повторяющихся столбцов получим базис X [А, В, С, X, У], эквивалент­

ный (6.7;.

Представим функцию G(AU Л2, ...) в форме простей­

шей логической суммы произведений и каждое слагаемое трансформируем в колонку, заменяя, как и раньше, эле­ менты А і единицами, элементы Äj — нулями, а на место

отсутствующих элементов записывая знак X, который имеет прежний смысл. Для того чтобы выбрать все те колонки базиса Ьх [Аи Л2, ...; Кі, АХ • •.], которые со­

вместны со значениями истинности элементов Л,, входя­ щих в виде сомножителей в слагаемые функции G(Ai, А2, ...), достаточно поразрядно сравнить каждую колон­ ку, соответствующую отдельному слагаемому в G, со всеми колонками базиса йх [Аи Л2, ...; Кі, А2, ...] по

следующим правилам:

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

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

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

При сравнении колонок, отвечающих отдельным сла­ гаемым в функции G, с колонками базиса йх [Лі, Л2, ...;

170

Г (К1, Кг, ••.)• Выполнив над колонками этой последней

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

изведения. В результате сложения получим в явном виде

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

следующей таблицей:

нимы только первая и третья колонки базиса, а с пра­ вым— первая, вторая и пятая. Следовательно, функция F(X, У) представляется теперь так:

X i о X X

П Х Х Х 1 /

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

F{X, У ) = Х + І + І+ У=І,

171

Таким образом, А-С + В- С— ѵі, т. е. в данном случае су­

ществует только тавтологическое решение уравнения

A-Ü + S -C —+F(X, У).

Особенно просто составить программу по данному алгоритму определения неизвестной функции F (Кі„ К2, •••) для ЭВМ с троичной системой счисления. На

машинах с двоичной системой счисления для представ­

ряде первой ячейки и 1 в k-ш разряде второй ячейки.

В ряде задач данный способ может оказаться в значи­ тельной степени более выгодным, чем операции с сокра­ щенным базисом bc[A1, Аг, ...; К\, Кг, ■■.].

6.3.ПРИМЕНЕНИЕ ЭВМ ДЛЯ ПОСТРОЕНИЯ СОКРАЩЕННОГО БАЗИСА

В предыдущем параграфе мы показали, как с помо­ щью ЭВМ, используя сокращенный базис Ьх [Аи А2, ..

К\, Кг, • •.], находить решение специальной логической

задачи по определению следствий, вытекающих из неко­ торого заданного набора посылок. Рассмотрим ряд алго­ ритмов, которые позволят применять ЭВМ также и для построения сокращенного базиса, связанного с исходны­ ми логическими зависимостями, наложенными на элемен­ ты А 1, А2, ...; Ки Кг,----

Алгоритм получения произведения двух булевых функций. Пусть требуется найти произведение функции fi (Аі, А 2, ...; Ki, К2, ...) на /г(Лі, А2, ...; Ки Кг, ...)..

Представим каждую из функций либо в дизъюнктивной нормальной форме, либо в форме простейшей суммы про­ изведений и трансформируем каждое слагаемое в колон­ ку таблицы (fi) или (Іг) соответственно, заполнив раз­

ряды колонок числами 0, 1 и X по тем же самым пра­ вилам, которые использовались в § 6.2 при построении

(fi) и (/г) размещены в ячейках памяти ЭВМ так, как показано па рис. 6,1,

172