Файл: Горелик, А. Л. Некоторые вопросы построения систем распознавания.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 |