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

пам объектов, с целью определить, какие выводы можно сделать о данных объектах на основании полученного сообщения;

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

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

ные типы объектов и их признаки (задача обучения). Вместе с тем, в настоящее время имеется сравнитель­

но немного работ, где предпринимается попытка приме­ нить аппарат алгебры логики к решению задач распоз­ навания объектов [13— 17]. Это объясняется, с одной стороны, тем, что широкий круг инженеров не в доста­ точной степени знаком с вычислительными методами алгебры логики и, с другой — некоторой трудностью стандартного применения этих методов к решению логи­ ческих задач с числом элементов порядка 20 и более.

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

В гл. 5 изложены фундаментальные идеи, лежащие в основе вычислительных методов алгебры логики и свя­ занные с понятиями изображающего числа булевой функции, базиса и сокращенного базиса. Эта глава пред­ ставляет собой переработанный (иногда весьма значи­ тельно) и дополненный новыми примерами материал некоторых разделов книги [13], с чтения которой началось наше знакомство с данным предметом. Эта глава долж­ на ввести читателя в круг основных понятий и идей исчисления высказываний и обрисовать в общих чертах область приложений данного математического аппарата, связанную главным образом с задачами построения ло­ гических систем распознавания объектов.

106

5.2.ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ. ФОРМУЛЫ БУЛЕВОЙ АЛГЕБРЫ

По определению, алгеброй *) называется непустое

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

предложение, которое может иметь два значения истин­ ности: быть либо истинным, либо ложным. Например,

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

Логическое умножение совершается по крайней мере

над двумя высказываниями, что соответствует комбина­ ции этих двух высказываний при помощи связки И и обозначается знаком «•», например, А-В читается «А и Ву>. П о определению, высказывание А-В истинно тогда и только тогда, когда истинны и А, и В одновременно. На­

пример, конъюнкция двух высказываний: «самолет — это летательный аппарат»-«прямое попадание мощного сна­ ряда в цель приводит к поражению цели» является истинным, тогда как. конъюнкция «три — четное чис­ ло»-«применение танков целесообразно» ло^кна.

Логическое сложение совершается по крайней мере

над двумя высказываниями, соответствует объединению этих двух высказываний при помощи связки ИЛИ и обо­ значается знаком « + », например, А + В читается «А или В». По определению, высказывание А + В истинно, когда истинно либо только одно А, либо только одно В, либо А я В вместе. Например, высказывание «танки могут

остановить наступление пехоты» + «собака — насекомое» истинное. Дизъюнкция А + В ложна тогда и только тогда, когда А ложно и В ложно.

*> Точнее, абстрактной алгеброй.

107

Операция отрицания в отличие от умножения и сло­

жения может совершаться над одним высказыванием. Эту операцию мы будем обозначать чертой над буквой, например, Л читается «не Л». По определению, высказы­ вание Л истинно тогда и только тогда, когда А ложно.

Как мы уже отметили, высказывания являются эле­ ментами области алгебры логики и поэтому наряду со словом «высказывание» мы часто будем употреблять термин «элемент». В результате применения операций конъюнкции, дизъюнкции и отрицания к некоторому исходному набору элементов А, В, С, ... возникают но­ вые комбинированные элементы X, У, ..., которые назы­ ваются булевыми функциями*~> от элементов А, В, С, ...

Чтобы подчеркнуть зависимость функций от данных эле­ ментов, часто пишут: Х(А, В, С, ...), Y(A, В, С,

Рассмотрим _две особо важные булевы функции А + + В и A - B+Ä - B, с помощью которых выражаются опре­ деленные связи между элементами А и В.

Предположим, что булева функция Ä + B истинна.

Тогда в соответствии с определённей операций дизъюнк­ ции и отрицания заключаем, что если А истинно, то В тоже истинно, если В ложно, то А также ложно. Однако

определения операций над высказываниями следует, что А и В имеют одинаковые значения истинности, т. е. А и В либо оба истинны, либо оба ложны. Такая зависимость между А и В называется эквивалентностью и записы­ вается в виде А = В, читается «А эквивалентно В». Если

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

108

соотношение (5.1). Такие функции называются тавтоло­ гиями. Поскольку все тавтологии не различаются между

собой с точки зрения значений истинности, их обозна­ чают одинаково через I. Таким образом, мы могли бы

написать A + Ä = I, А - В + А = I и т. д. Отрицание I, т. е.

I, является тавтологически ложным элементом и обозна­ чается через 0. Легко видеть, что для любого X соотно­

шения (0— к А )= 0 + Х = І и (X— ѵ І)= х + І= І являются тавтологиями, так как не зависят от значения истинно­ сти X. Необходимо отличать тавтологически истинные

элементы от функций, которые истинны вследствие сде­ ланных предположений или физических законов. Первые не несут никакой полезной информации, в то время как

В дальнейшем мы познакомимся с другими возможными формами связей.

Приведем, наконец, основные формулы рассматривае­ мой нами булевой алгебры.

Эти формулы должны рассматриваться как тавтоло­ гии. Справедливость этих соотношений может быть про-

109

верена посредством вычисления значений истинности сложных высказываний в левой и правой частях равен­ ства. Некоторые из этих формул могут быть выведены из других, например, 19-я формула устанавливается с по­ мощью 12-й, 15-й, 7-й, 6-й, 4-й, 3-й и 17-й формул сле­ дующим образом:

А-В + А-С + В - С = А -В + А-С-1 + В-С = А- В +

+А-С- (В + В) +В-С = А - В + (А- С) -В+{ А-С) ‘В +

+В-С = А - В +( А - В ) -С+ В-С+(В-С) -А— А - В + В-С.

5.3.ИЗОБРАЖАЮЩИЕ ЧИСЛА И БАЗИС. ОПРЕДЕЛЕНИЕ ИЗОБРАЖАЮЩИХ ЧИСЕЛ БУЛЕВЫХ ФУНКЦИИ

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

Условимся значение истинности элемента «истина» обозначать единицей, а значение «ложь» — нулем. Тогда для одного элемента А базисом будет

О 1

# А = 0 1

для двух элементов А, В базис содержит 22 столбцов:

0 1 2 3

#А = 0 1 0 1

#5 = 0 0 1 1

для трех элементов А, В, С базис состоит из 23 столб­

цов:

# С = 0 0 0 0 1 1 1 1

и вообще для п элементов А\, ..., А„ базис содержит п

строк и 2" столбцов. Если колонки базиса рассматривать как целые двоичные числа, записанные так, что самый младший разряд их соответствует первой строке базиса,

110

а самый старший — последней строке, то колонки базиса для п элементов представляют собой числа от 0 до 2”— 1.

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

т. е. (2П)!. Стандартный базис для элементов А, В, С, ...

обозначается b [А, В, С, . . .], причем порядок элементов

в квадратных скобках совпадает с порядком строк ба­ зиса.

Строки базиса называются изобраэюающими числами

соответствующих элементов. Для их обозначения следует приписывать слева от элемента знак ф . Заметим, что по отношению к стандартному базису Ь[А, В, С, ...] изобра­

жающее число фЛ состоит из чередующихся нулей и единиц, ф б — из пар нулей и пар единиц, фС — из чет­ верок нулей и четверок единиц и т. д., так что, например,

в Ь[А, В, С, £>]

# £ > = 0000 0000 1111 1111.

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

По определению, изображающее число суммы двух элементов равно сумме изображающих чисел слагае­ мых:

причем сложение выполняется поразрядно без переносов в высшие разряды по следующему правилу:

0+ 0= 0, 0+1 = 1+ 0= 1, 1+ 1= 1.

Например, по отношению к Ь[А, В, С]

# (Л+ Д + С ) = # (Л + Д ) + # С = # Л + # Д + # С =

= 0101 0 1 0 1 +0 0 1 1 0 0 1 1 + 0 0 0 0 1111 = 0111 1111.

111