Файл: Горелик, А. Л. Некоторые вопросы построения систем распознавания.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 112
Скачиваний: 1
Сопоставляя эти |
результаты |
с результатами |
решения |
уравнений |
а—в, замечаем, что |
в первые |
разряды t'= 1 # А |
и # У |
нельзя впи |
сать ни одну из возможных пар Х>, Y>, так чтобы все три уравнения были удовлетворены. Следовательно, нельзя сделать предположения, согласованного с данными наблюдений, относительно отождествле ния самолетов типа А' и Y с самолетами типов А и В.
5.7.ЗАМЕНА ПЕРЕМЕННЫХ
Понятие замены переменных в булевой алгебре ана логично понятию замены переменных в обычной алгебре. Если А, В, С,... — элементарные высказывания и мы
совершаем замену переменных, полагая
А = Л ( А ' , В', С',...), |
В = В(А', В', С',...), |
||
|
С = С(А', В', С',...),..., |
(5.19) |
|
где Л', В', |
С',... — новые |
переменные, |
то необходимо |
убедиться, |
что не вводится |
зависимости |
между А, В, |
С, ..., обусловленной специальным выбором булевых функций (5.19). При этом новые элементы А', В', С',...
также будут независимы друг от друга.
Рассмотрим, например, следующее преобразование
элементов Л и В в А' и В'\ |
|
A^A'-B'+Ä'-B', ß = A '. |
(5.20) |
Вычислим по отношению к Ь[А', В г] |
|
# Л = 1 00 1, |
|
# 5 = 1 0 1 0 |
(5.21) |
3 0 12 |
|
Так как в наборе (5.21) имеются все 22 чисел |
(0, 1, 2,3), |
то, следовательно, функции (5.20) независимы и преоб разование допустимо.
Первая задача, которая возникает в связи с заменой переменных, состоит в следующем. Предположим, что задана некоторая функция Л (Л, В, С, ... ) и совершает
ся преобразование переменных вида (5.19). Требуется найти функцию
Gi(A', В', С',...) =Fi[A (А', В', С',...), |
|
В (A', B', С', |
(5.22) |
136
В теории электрических цепей задача интерпретируется следующим образом. Пусть имеется некоторый набор проводников А', В', С', .... На каждый вход может по
даваться либо высокий, либо низкий потенциал. Мы будем считать, что высокому потенциалу соответствуют значения А' = 1, В'= 1,
С—1, ..., а низкому—
Л'=0, В’= О, С' = 0, ...
Предположим, что име ются электрические це пи, соответствующие независимым булевым функциям, ко входам которых подключены
проводники |
А', |
В', |
|
|
|
С', ..., а к выходам — |
|
|
|||
проводники А, В, С,... |
|
|
|||
и, кроме того, еще од |
Рис. |
5.1. |
|||
на электрическая |
цепь, |
||||
|
|
||||
отвечающая |
булевой |
|
С,... и выхо |
||
функции .Fi (Л, |
В, |
С ,...) со входами А, В, |
|||
дом Gi (рис. 5.1). Спрашивается, какой сигнал будет на
Gi, если сигналы на исходных проводниках А', В', С',...
заданы? |
|
|
вычислим изоб |
|
Для нахождения фбДЛ ', В', С', ...) |
||||
ражающие |
числа |
ФФ ф й , ф С , ... |
по |
отношению |
к Ь[А', В', |
С',...] |
и произведем над фЛ, |
фД, |
ф С , ... те |
действия; посредством которых из элементов А, В, С, .. .
формируется функция Fi(A, В, С ,...). Полученный ре
зультат и |
будет |
ф Gi(Ar, B’, С , . . . ) |
по |
отношению |
к Ь[А’, В', |
С , ...]. |
Например, если |
|
|
|
|
F\=A -B+Ä -B |
|
(5.23) |
и совершается преобразование (5.20), |
то фДДЛ', В') = |
|||
= (1001) • (0101) + (ОНО) • (1010) =0011 |
и, |
следова |
||
тельно, |
|
Gi(A', В')=В'. |
|
(5.24) |
|
|
|
||
В более общем случае требуется одновременно преобра зовать несколько функций Fi(A, В, С,...), F2{A, В, С, . . . ) , . . . от переменных А, В, С, ... к функциям от пе ременных А', В', С',. .. . Например, наряду с (5.23) мо
жет быть задана также функция
F<i—A-\- В, |
(5.25) |
137
Которая |
в |
результате преобразования (5.20) |
переходит |
||||||
в функцию |
|
|
G2=A' + B', |
|
|
(5.26) |
|||
|
|
|
|
|
|
||||
причем # G 2(4', В') = 1001+0101 = ! 101. |
|
/^(Л, В, |
|||||||
Замена |
переменных (5.19) |
в |
функциях |
||||||
С ,...), |
F2(A, |
В, С, . . . ) , . . . |
эквивалентна |
переходу от |
|||||
Fi(A, |
В, С ,...), |
^ F 2(A, |
В, |
С, . . . ) , . . . , |
вычисленных |
||||
относительно |
Ь(А, |
В, С,...], |
к |
^G \(A', В', С',...), |
|||||
ф 0 2(Л', |
В', |
С', . . . ) , . . . , |
вычисленным |
относительно |
|||||
Ь[А\ В', С',.. . ]. Этот переход в случае независимых
функций (5.19) сводится просто к перестановке |
столб |
||
цов в наборе |
|
|
|
#/Л (Л , В, С,... ), |
|
||
фР2(А, В, С ,...), |
(5.27) |
||
так что в результате получается набор |
|
||
^G iiA ', |
В', |
С',...), |
|
# 0 2(Л', |
В', |
С',...), |
(5.28) |
Перестановка столбцов выполняется при помощи пере становочной булевой матрицы (Rij), которая должна
строиться таким образом, чтобы
( F M ) ® ( R a ) = ( G k j ), |
(5.29) |
где (Fm) — матрица, составленная из набора |
(5.27), |
а (Ghj) — матрица, составленная из набора (5.28), при чем индекс «k» относится к номеру преобразуемой стро ки (номер функций F h , G k ) , а индексы і и j—номера раз
рядов в |
и |
соответственно. |
|
F 3= C , ..., со |
|
В частном случае, когда F \ = A , F 2 = B , |
|||||
гласно (5.19) выполняются равенства: |
|
|
|||
С і = Л ( Л ' , |
В ' , С , . . . ) , |
G 2 = B ( A ' , |
В ' , |
С ' , . . . ) , |
|
|
|
G 3 = C ( A ' , В ' , С ' , . . . ) , . . . , |
|
||
где функции |
Л(Л', В ' , С ' , . . . ) , В { А ' , |
В ' , |
С ' , . . . ) , С ( А ' , |
||
В ' , С ' , . . . ) , . . . |
|
считаются |
известными. |
Исходя из этого |
|
условия определяется перестановочная матрица (Rij),
когда замена переменных (5.19) задана. Например, при
138
преобразовании (5.20) матрица (Rij) должна переводить
набор
#Л=О101,
# 0 = 0011,
представляющий собой просто базис b[A, ß], в набор изображающих чисел #Л (Л ', В') и # £ (Л ', В'), вычис ленных относительно Ь[А', В'], т. е. в набор (5.21). Таким образом, матрица Rij должна удовлетворять уравнению
і = 0 1 2 |
3 |
/=0123 |
|
|
/ 0 1 0 1 |
/1 0 0 г |
(5.30) |
||
Ѵо 0 |
1 1 |
1 0 |
1 0 , |
|
Столбцы с номерами і и / переставляются следующим образом: і = 0— >-/=1, і =1 — y j = 3, і = 2— yj = 2, і —
= 3— yj— 0. Если в матрице (Rij) элементы с указанны
ми значениями индексов і |
и / положить |
равными еди |
нице, а остальные — нулю, |
т. е. взять |
|
|
( 0100\ |
|
|
0001 \ |
(5.31) |
|
оою Ь |
|
|
1000 / |
|
то уравнение (5.30) удовлетворится. При этом преобра зование функций Fi и Fi, заданных выражениями (5.23)
и (5.25), получится из соотношения (5.29):
|
/0100' |
0011\ = # G „ |
|
f 0001 |
|
#/% = |
0010 |
1101/ = #G 2, |
( 1000 |
и, таким образом, Gi = ß', |
Gz=A' + В'. |
|
||
В общем случае перестановочная матрица (Rij), со |
||||
ответствующая |
заданному |
преобразованию |
переменных |
|
(5.19), |
строится |
аналогично: если столбец |
i=k базиса |
|
Ь[А, В, |
С,...] переводится |
в столбец j = h |
набора изо |
|
бражающих чисел |
|
|
||
|
|
#Л (Л ', |
В', С',...), |
|
|
|
# В ( А ', |
В', С , ... ) , |
|
|
|
#С (Л ', |
В', С',...), |
|
вычисленных относительно базиса Ь[А', В', С', ... ], то матричный элемент RhH= \ l все другие элементы Rij=0.
139