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

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 23.10.2024

Просмотров: 117

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

и, следовательно, =)рХ должно быть таким, чтобы выпол­ нялось равенство (0111 0111) • (ф Х )=0000 0001. Откуда следует, что # Х = Х 0 0 0 X 001, где вместо X можно на­ писать как 0, так и 1. Таким образом, рассматриваемое уравнение имеет четыре различных решения, соответст­ вующие изображающим числам 0000 0001. 1000 0001, 0000 1001 и 1000 1001. Эти решения:

АТ=А - В- С, X2= A - B - C+ ä -B-C,

 

Xz— C- (А-В + Ж-В),

Хь— К-В + А-В-С.

 

Совершенно аналогично можно найти решение урав­

нения в виде импликации, например,

 

А- {А+В + С)-+{А - В +В - С) .

(5.7)

Так как 4НЛ + В + С) = 1111

0111, Ф ( А - В + В-С) =

= 0001 1101, то, следовательно, # Х = 000Х X ХОХ, и, таким образом, существует 24=16 различных решений уравнения (5.7), именно:

0, А-В-С,

Ж-В-С, А-В-С,

А- В- С ,

A-B-C+Ä-B-C,

А - (В -С + В • С),

А- В, В - С,

(Ж-В + А-В) -С, А-С, А-В-С + В-С, A - B + Ä - B - C ,

А - (В + С),

(В+А) ■С, А-В + В-С.

Заметим, что уравнение в форме импликации всегда можно записать как соотношение эквивалентности, на­ пример, вместо (5.7) можно было бы написать следую­ щее равенство:

X- (А + В + С)+А-В + Б-С = 1,

пли после упрощения Х + А-В + В-С = I. Необходимо так­

же иметь в виду,

что существуют уравнения, которые

вообще не имеют

решений, например (А + С+ А)-ѵ

->-В + В-С).

 

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

126


недалеко от места предполагаемого появления этих тел. Систематизация результатов опроса показала следую­ щее:

одни жители первого населенного пункта утверж­ дали, что в небе появились сгустки слабо светящейся ионизированной пыли (Л);

другие утверждали, что среди атмосферных обла­ ков (В) они видели одиночное светлое дискообразное

тело радиусом приблизительно 100 м (X) и больше не было никаких других тел (У );

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

Ответы жителей второго населенного пункта можно было объединить в такие группы:

не было ни светящейся ионизированной пыли (Л),

ни большого светлого дискообразного тела

(X), ни си­

гарообразных тел (У);

_

не видели ни атмосферных облаков (В), ни свет­

лого дискообразного тела (X);

наблюдались слабые разряды атмосферного элек­ тричества (С);

среди облаков (В) были видны сгустки слабо све­ тящейся ионизированной пыли (А).

На основании этих данных требуется определить, сле­

дует ли принимать всерьез заявления некоторых лиц

о наблюдавшихся ими странных небесных телах Х и У

или же представления о телах X и У могли быть вызва­

ны комбинированными действиями атмосферных

явле­

ний А, В, С. Используя введенные обозначения,

пред­

ставим результаты опроса в виде следующего

булева

уравнения:

 

 

 

A + B - X - Y + C - Y = Ä - X - Y + B-X + C+A-B.

(5.8)

Решение вопроса о существовании тел Х и

У сводит­

ся к

определению возможности разрешить

уравнение

(5.8)

относительно неизвестных X и У и выразить их как

функции от элементов А, В, С. Если решение Х(А, В, С), У {А, В, С) существует и, кроме того,

Х ф І - В - С , УфА-В-С,

(5.9)

то нет оснований делать вывод о появлении каких-либо тел X, У. Если же не существует решения, отличного от

1 2 7


(5.9), то следует отнестись с большей серьезностью к за­ явлениям «очевидцев».

Вычисление фХ и фУ относительно базиса Ь[А, В, С]

‘ удобно проводить с помощью рабочей таблицы [13]:

Таблица 5.1

Изображающие числа коэффициентов

Комбинации

неизвестных

рри неизвестных по отношению к

(искомых

Ь{А, В, С]

функций)

Левая

4P Л =

0101

0101

I

часть

# 5 = 0 0 1 1

ООП

X-Y

 

# С =

0000

1111

Y

 

4P Л =

1010

1010

X-Y

Правая

4P В =

1100

1100

X

часть

4P( С + # 5 ) =

 

I

 

=

0001

1111

Изображающие числа ком­ бинаций неизвестных по от­ ношению к Ь[X, FJ:

 

Х ’ = 0101

 

KJ= ООП

 

 

/ = 0 1 2 3

 

# 1 = 1 1 1 1

#

X - Y 0100

 

#

 

1

о о

*

 

 

 

#Х -У =

1000

 

# Х =

1010

 

# 1

=

1111

В левой графе таблицы записываются изображающие числа коэффициентов при каждом сочетании неизвест­ ных (отдельно для левой и правой частей уравнения). Средняя графа содержит комбинации искомых функ­ ций, входящих в уравнение как множители при соответ­ ствующих коэффициентах; для членов, не содержащих неизвестных, в среднюю графу записывается тавтологи­ ческий элемент I. В правую графу заносятся изобра­ жающие числа комбинаций неизвестных функций отно­ сительно базиса Ь[Х, У], причем =ф 1 = 1111-

Порядок вычисления фХ и фУ относительно базиса Ь[А, В, С] следующий. Возьмем первую пару значений (Xi, Уз) при /= 0 , т. е. (Х°, У0) = (0, 0), которые соответ­ ствуют нулевому столбцу базиса Ь[Х, У]. Паре значений

(Х°, У0) = (0, 0) отвечает транспонированный столбец 100 в наборе изображающих чисел элементов I, X - Y и У для

левой части уравнения (5.8) и транспонированный стол­ бец 111 в наборе изображающих чисел X T , X и I для правой части этого уравнения. Умножим первый из этих столбцов 100 на нулевой столбец в наборе изображаю-

128



щих чисел коэффициентов А, В и С для левой части

уравнения и просуммируем результаты по правилу ло­ гического сложения

 

0

- 1+0- 0 + 0-0 = 0.

(5.10)

Аналогично поступим со столбцом 111

и нулевым столб­

цом

ПО в наборе фЛ , фІЗ и ф( С+А- . б) для правой

части уравнения

 

 

 

М + 1-1+0-1 = 1.

(5.11)

Так

как результаты

(5.10) и (5.11)

не совпадают, то,

следовательно, пара значений (А0,

У0) = (0,

0) в разря­

дах і = 0 изображающих чисел фА

и фУ,

вычисленных

относительно базиса Ь[А, В, С], не удовлетворяет урав­

нению (5.8) и потому должна быть отброшена.

Проверим теперь пару

(Х\

Н>) = (1, 0) при /= 1

опять-таки в разрядах фА

и

с номером і = 0 по от­

ношению к Ь[А, В, С]. Как и раньше, необходимо вычис­

лить логическую сумму произведения’ столбца

ПО на

столбец 000, т. е.

 

0 Л + 0 Л + 0 - 0 = 0

(5.12)

и сравнить ее с результатом аналогичной операции для столбцов 001 и НО, т. е.

 

0 - 1+0 - 1 + 1-0 = 0.

(5.13)

Поясним, что ПО есть столбец с номером /= 1

в наборе

ф і, ф А -F

и фУ, а 000 — по-прежнему столбец с

но­

мером z = 0

в наборе фА, ф В, фС._Аналогично 001

есть

столбец с номером j= 1 в наборе фХ-У, фХ и_фІ, а ПО есть столбец с номером і = 0 в наборе фЛ, ф В и ф (С + +А-В). Поскольку результаты (5.12) и (5.13) совпада­

ют, мы можем записать в нулевые (/ = 0) разряды фА и

фУ по отношению к Ь[А, В, С] значения

А1 = 1,

У1 = 0,

как показано

в таблице

результатов:

 

 

 

 

 

 

 

 

 

 

Таблица 5.2

Изобра­

 

 

 

Номер столбца

 

 

 

жающие

0

1

2

3

4

5

6

7

числа

# А

1,1

0 ,0

0 ,1

0 , 1 , 0 , 1

0, 1

0 , 1 , 0 , 1

1, 0, 1

0 , 1 , 0 , 1

 

0, 1

0, 1

1,1

0 , 0 , 1 , 1

1,1

0 , 0 , 1 , 1

0 , 1 , 1

0 , 0 , 1 , 1

9 - 4 5 2

129