§ 5.7. Методы решения логических задач распознавания

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

- Пусть множество объектов подразделено на классы а для описания объектов используются признаки

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

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

Одна из задач, которые могут возникнуть при распознавании объектов, состоит в том, чтобы определить, какие выводы можно сделать относительно на основе общих сведений априорного характера (5.39) и апостериорной информации

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

при ограничениях (5.39), наложенных на элементы

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

при заданной функции и связях (5.39).

Положим в соотношениях (5.40) и Тогда, если перемножив левые части (5.40) и (5.41), получим

или

иначе говоря, посылки и следствия эквивалентны.

Другая задача, которую назовем обратной задачей распознавания, заключается в том, чтобы определить множество априори неизвестных посылок из которых следуют некоторые данные выводы при условии, что признаки связаны зависимостями (5.39).

Покажем, что решение этой задачи приводится к решению предыдущей задачи. Пусть есть заданная функция, импликанты которой требуется найти в виде функции Перейдем от функции к ее отрицанию и припомощи (5.41) определим функцию связанную с зависимостью

Поскольку (5.43) эквивалентно соотношению

то и является искомой функцией.

Если наряду с (5.44) справедливо соотношение то т. е. представляет собой полный набор импликант функции через сумму которых эта функция может быть выражена.

Методы решения прямой и обратной задач распознавания основываются на построении сокращенного базиса определяемого следующим образом. Соотношения (5.39)

накладывают определенные ограничения на возможные комбинации значений истинности элементов так, что не все столбцы полного базиса совместны с этими соотношениями. Если отбросить столбцы базиса противоречащие хотя бы одному из соотношений (5.39), то оставшиеся столбцы, по определению, образуют сокращенный в соответствии с данными связями базис. Сокращенный базис устанавливает соответствие между колонками базиса и базиса и определяет тем самым возможные преобразования соотношений (5.39) к такому виду, для которого рассматриваемые задачи решаются либо в рамках уравнений (5.40) или (5.44), либо (5.42).

Рассмотрим на конкретных примерах различные частные случаи соответствия базисов

1. Предположим, что при некоторых условиях, характеризуемых признаками в системе могут протекать процессы причем связи между представлены соотношениями

Изображающие числа булевых функций, представленных соотношениями (5.45), относительно базиса соответственно равны

Перемножив эти два изображающих числа, получим . Следовательно, соотношения (5.45) удовлетворяются только при таких комбинациях значений истинности элементов которые соответствуют 3, 13, 16, 28, 33, 47, 50 и 62-му столбцам базиса Сохраняя перечисленные столбцы и отбрасывая остальные, получим следующий сокращенный базис:

Разобьем базис (5.46) на два базиса: Тогда сокращенный базис будет совпадать с полным стандартным базисом а базис будет представлять собой полный нестандартный базис для элементов Пусть обозначают порядковые номера столбцов стандартных базисов соответственно.

Базис (5.46) устанавливает следующее взаимно однозначное соответствие между значениями

или при другом порядке расположения чисел:

Из (5.47) следует, что изображающие числа относительно базиса запишутся как

а перестановочная матрица будет иметь вид

Аналогично (5.48) показывает, что в базисе

а матрица перехода от переменных к переменным получается как транспонированная по отношению к матрице (5.50). Полученный результат означает, что исходные связи (5.45) полностью эквивалентны либо соотношениям (5.49), либо соотношениям (5.51).

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

Какие выводы можно сделать относительно процессов на основании информации (5.52) и соотношений

и, следовательно,

т. е. либо протекает только один процесс либо можно утверждать, что процесс протекает, а относительно процессов ничего сказать нельзя, либо, наконец, имеет место При таком не очень определенном выводе может потребоваться узнать, какие признаки из числа должны быть обнаружены дополнительно, для того чтобы убедиться, что в системе протекает только процесс

В соответствии с (5.29)

откуда

т. е. в группе наблюдений, где было установлено требуется дополнительно обнаружить наличие признака Утверждения (5.53) и (5.54) имеют смысл необходимых и достаточных условий, когда посылки и следствия полностью эквивалентны.

2. Предположим, что в результате продолжительных наблюдений за воздушным противником установлено, что на выполнение боевого задания всегда одновременно направляются следующие самолеты: либо появляются истребители-перехватчики и штурмовики и при этом нет ни тяжелых бомбардировщиков, ни истребителей сопровождения; либо появляются тяжелые бомбардировщики и истребители сопровождения и нет истребителей-перехватчиков, причем легкие бомбардировщики и штурмовики появляются одновременно, или нет ни штурмовиков, ни легких бомбардировщиков [21].

На основании этих данных требуется определить: а) какие выводы можно сделать относительно появления бомбардировщиков, если известно, что ожидается налет, в котором будут участвовать истребители сопровождения и не будет штурмовиков; б) что можно сказать о возможности появления истребителей и штурмовиков, если известно, что в налете либо вообще не будут участвовать бомбардировщики, либо будут только легкие бомбардировщики и не будет тяжелых.

Введем следующие обозначения: тяжелый бомбардировщик; легкий бомбардировщик; истребитель сопровождения; истребитель-перехватчик; штурмовик. После этого условия задачи запишутся в виде одного соотношения эквивалентности:

Сокращенный в соответствии с (5.55) базис имеет вид

Как следует из (5.56), между столбцами имеет место следующее соответствие:

Здесь номера столбцов стандартных базисов Это означает, что в (5.56) представляют собой изображающие числа элементов вычисленные относительно базиса

Следовательно, соотношения

полностью эквивалентные связи (5.55), можно рассматривать как решение уравнения (5.55) относительно Как показывает (5.57), функции зависимы, поэтому комбинации значений истинности отвечающие столбцам базиса с номерами — особые в том смысле, что при наличии связи (5.55) или (5 58) соответствующие элементарные произведения из всегда ложны. Кроме того, как следует из (5.57), уравнение (5.55) или соотношения (5.58) невозможно разрешить относительно Используя (5.58), можно любую заданную функцию преобразовать к переменным так, чтобы Преобразование выполняется при помощи унитарной перестановочной матрицы которая строится так же, как и перестановочная матрица при замене переменных: если столбец переводится в столбец то элемент остальные элементы Булева матрица -унитарная, если в каждом ее столбце содержится только одна единица. Соответствующая (5.58) унитарная перестановочная матрица

Тогда

Если в соответствии с первым вопросом задачи положим

то изображающее число функции относительно находится как

Таким образом, ответ на первый вопрос будет следующий: в налете примут участие тяжелые бомбардировщики и не примут участия легкие бомбардировщики. Единица, стоящая в шестом

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

Рассмотрим преобразование

выполняемое над функцией матрицей Покажем, что определяемая (5.61) функция в общем случае при произвольной функции удовлетворяет условию

Так как произведение матрицы на унитарную матрицу равно

где единичная матрица; в общем случае отличная от нулевой симметричная девиаторная матрица, то, умножая (5.61) справа на матрицу получим

Согласно (5.60), в правой части этого соотношения стоит вычисленное относительно изображающее число Поскольку в общем случае

то соотношение (5.62) доказано.

Если в соответствии со вторым вопросом задачи положим то согласно (5.61)

Аналогично, если то

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

Так как в переменных

то

Этот пример показывает общее свойство преобразования, осуществляемого перестановочной матрицей транспонированной к унитарной матрице При таком преобразовании функции связанные зависимостью (5.61), будут в общем случае удовлетворять соотношению импликации

3. Предположим, что у противника имеется три типа мин: осколочного действия, — осколочно-фугасного действия; фугасного действия. В инструкции по применению этих мин сказано, что: 1) осколочные мины применяются на равнинной местности с каменистым грунтом или на песчаных холмах; 2) осколочно-фугасные мины применяются либо на равнине, либо на местности с каменистым грунтом; 3) фугасные мины не применяются, если грунт каменистый, а местность холмистая.

Требуется определить: 1) какие мины будут применены противником в зависимости от вида ландшафта и типа грунта; 2) что можно сказать о свойствах местности, если известно, что противник применяет только осколочно-фугасные мины.

Вводя обозначения: каменистый грунт; песчаная почва; равнинная местность; холмистая местность, — можно представить перечисленные выше условия в виде соотношений

Сокращенный в соответствии с (5.65) базис имеет вид

Соответствие между столбцами устанавливаемое базисом (5.66), следующее:

Здесь номер столбца номер столбца стандартного базиса

Соответствие (5.67) показывает, что существует различных решений уравнения (5.65) относительно Изображающие числа в базисе для каждого решения получаются при различных комбинациях столбцов базиса под номерами ; со столбцами базиса соответственно.

Унитарные перестановочные матрицы для каждого из решений

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

Каждое решение (5.68) позволяет преобразовать заданную функцию к переменным различным образом, т. е.

причем

При логическом сложении результатов всех преобразований одной и той же функции к переменным совместных с соотношениями (5.65), получаем функцию

изображающее число которой есть сумма изображающих чисел

Перестановочная матрица преобразования (5.70)

в отличие от матриц не является унитарной, и поэтому

Так как для каждого преобразования (5.68) при фиксированном К выполняется соотношение (5.69), то в общем случае

Рассмотрим преобразование

осуществляемое над изображающим числом произвольной функции матрицей

транспонированной по отношению к

Согласно (5.61), (5.62), преобразование

при каждом фиксированном определяет функцию связанную с соотношением импликации

откуда следует, что в (5.73) функции также связаны соотношением импликации

Формулы дают возможность найти ответы на поставленные в задаче вопросы. Применяя преобразование (5.73) к

набору функций получим:

Таким образом,

где, например, последнее соотношение расшифровывается так: если местность холмистая, то либо применяются мины осколочные и не применяются осколочно-фугасные, либо применяются только мины осколочно-фугасные.

Чтобы ответить на второй вопрос задачи, применим преобразование (5.70) к функции

откуда заключаем, что и, следовательно,

Таким образом, если в каком-либо районе противник применяет только осколочно-фугасные мины, то это означает, что данная местность покрыта каменистыми холмами.

При доказательстве соотношений (5.72) и (5.75), связанных с преобразованиями (5.70) и (5.73), не учитывался конкретный вид перестановочной матрицы так же как и то, что функция зависит от двух переменных, а функция от трех переменных. Поэтому можно утверждать, что и в общем случае функции Ли) и связанные преобразованием вида (5.70) или (5.73), удовлетворяют соотношению импликации (5.72) или (5.75) соответственно.

4. Предположим, что у противника имеются роты стрелковая, пулеметная, автоматчиков и следующее вооружение: легкие пулеметы, бронированные автомобили, автоматы.

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

Пусть дополнительно известно, что в данном районе нет других рот противника и что по крайней мере одна из названных рот находится в поле:

Кроме того, известно, что рота автоматчиков никогда не сопровождает роту пулеметчиков:

Допустим, что разведчик, наблюдая за противником, заметил, что солдаты несли или пулеметы, или автоматы (он не мог точно определить) и не было бронированного автомобиля, т. е. донесение разведчика представляется как

На основании (5.79) и априорных сведений о противнике требуется установить, какие роты противника находятся в поле. Иначе говоря, при наличии зависимостей требуется определить неизвестную функцию связанную с функцией (5.79) соотношением импликации

Сокращенный в соответствии с базис имеет вид

Поскольку в базисе отсутствуют столбцы с номерами , а в базисе столбцы с номерами

построенная по общему правилу перестановочная матрица

будет иметь строки и столбцы , составленные из одних нулей. В соответствии с этим полученное в результате преобразования вида (5.70) из всегда будет содержать нули в разрядах при любой функции Аналогично, возникающее при преобразовании вида (5.73) из всегда будет содержать нули в разрядах при любой функции Это ограничение на обусловлено наличием связей (5.77), (5.78) и не затрагивает основных свойств преобразований вида (5.70), (5.73).

Применяя преобразование вида (5.73) к (5.79), получим

Следовательно,

т. е. в поле находится одна стрелковая рота.