Лабораторные работы по курсу: ДМ

г==============================================================

¦ Минимизация Функций Алгебры Логики ¦

¦==============================================================¦

¦ Число переменных ФАЛ: = 5 ¦

¦ Изображающее число ФАЛ: ¦

¦ 0 0 1 . . . 0 1 0 1 0 0 0 0 0 0 0 0 0 0 ¦

¦==============================================================¦

¦ Работу выполнил: ¦

¦ Файл с результатами: minfal1.rez ¦

¦ Ключи печати ¦ ¦ Печать СДНФ Да ¦ ¦ Печать Сокращенной ДНФ Да ¦ ¦ Печать имликантной матpицы Да ¦ ¦ Печать всех вариантов покрытия Да ¦

¦ ¦

¦ F4-Вычисления F10-Выход ¦

================================================================

Рис. 2.1.

Данная программа рассчитана на минимизацию ФАЛ от 2 до 5 переменных. Для начала работы необходимо установить число переменных и ввести значение изображающего числа ФАЛ. Для ввода изображающего числа ФАЛ требуется установить курсорное поле в соответствующую позицию и нужным образом скорректировать его нажатием клавиши <Enter> или <Пробел>. По окончанию ввода изображающего числа ФАЛ требуется ввести фамилию выполняющего работу, имя файла результатов и соответствующим образом установить ключи печати. Имя файла с результатами должно быть уникальным. Переключение ключей осуществляется также как и корректировка изображающего числа ФАЛ путем нажатия клавиши <Enter> или <Пpобел>. Для начала выполнения расчетов необходимо нажать клавишу <F4>. По окончанию расчетов будет сформирован файл с результатами.

Результаты ручных и машинных расчетов сравнить между собой, сделать выводы.

Контрольные вопросы

1.Что такое простой импликант, СкДНФ, ТДНФ, МДНФ, КрДНФ?

2. В чем состоят идея, преимущества, недостатки методов неопределенных коэффициентов, Квайна, Мак – Класски, карт Вейча, метода ЛФП?

3. Что такое импликантная матрица?

4. Чему равно число неопределенных коэффициентов для 3-х, 4-х переменных?

5. В чем состоит операция неполного склеивания?

Варианты заданий:

Варианты ФАЛ к п. 1 (ФАЛ 3-х переменных)

NN	Элементы множества Т1
	0, 1, 2, 5, 6, 7 0, 2, 4, 3, 5, 7 1, 4, 0, 7, 3, 6 1, 2, 3, 4, 5, 6 0, 3, 4, 5, 6 0, 6, 1, 3, 5 0, 5, 2, 6, 3 0, 1, 2, 6, 7 0, 2, 3, 4, 5 2, 3, 4, 5, 6

Варианты ФАЛ к п. 4 (ФАЛ 4-х переменных)

NN	Элементы множества Т1
	0, 2, 4, 5, 6, 8, 9, 13, 14 9, 10, 2, 0, 1, 5, 6, 12, 13 1, 2, 4, 5, 8, 9, 10, 12, 13 0, 1, 2, 5, 6, 8, 9, 12, 13 0, 4, 8, 10, 12, 1, 3, 11, 13 0, 8, 1, 5, 9, 2, 6, 7, 11 0, 1, 2, 10, 3, 8, 12, 14, 7 0, 1, 4, 3, 6, 7, 8, 9, 13 0, 2, 4, 6, 7, 8, 12, 14, 15 0, 4, 5, 8, 10, 11, 12, 14, 15

Варианты ФАЛ к п. 2 (ФАЛ 5-ти переменных)

NN

Элементы множества Т1

0, 1, 2, 3, 5, 7, 10, 13, 14, 15, 19, 20, 22, 23, 26, 28, 30, 31 0, 2, 4, 6, 8, 10, 14, 20, 26, 28, 30, 7, 9, 13, 15, 21, 25, 29, 31 0, 8, 16, 24, 9, 25, 18, 11, 19, 27, 28, 5, 21, 29, 22, 7, 23, 31 0, 16, 1, 17, 18, 19, 5, 22, 7, 23, 25, 10, 11, 27, 13, 14, 15, 31 0, 4, 8, 12, 20, 28, 9, 21, 25, 29, 14, 18, 26, 30, 11, 19, 27, 31 0, 16, 8, 24, 20, 28, 10, 22, 14, 30, 25, 5, 13, 29, 11, 7, 15, 31 0, 1, 16, 17, 9, 25, 20, 13, 28, 29, 19, 10, 18, 27, 21, 14, 30, 31 0, 2, 1, 3, 18, 19, 9, 26, 25, 27, 7, 20, 21, 23, 13, 28, 29, 31 0, 2, 4, 6, 5, 7, 18, 21, 19, 23, 14, 9, 11, 15, 26, 25, 27, 31 0, 8, 4, 12, 10, 14, 5, 11, 7, 15, 28, 18, 22, 30, 21, 19, 23, 31

Работа № 3. ИССЛЕДОВАНИЕ ЛОГИЧЕСКИХ АЛГОРИТМОВ РАСПОЗНАВАНИЯ

Цель работы: ознакомление с методами решения логических задач распознавания (образов) на основе использования теории функции алгебры логики (ФАЛ) и реализации этих методов на ЭВМ.

Задание.

Для конкретного варианта исходных данных:

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

2. Используя полученный сокращенный базис выполнить анализ существования и единственности решения исходного уравнения в виде (3.9). Найти все существующие решения.

3. Найти решения поставленных задач распознавания вручную и записать полные качественные ответы на поставленные вопросы.

4. Используя разработанную на кафедре 302 программу‚ получить машинное решение задач распознавания.

5. Проанализировать результаты ручного и машинного счета‚ сравнить их‚ сделать выводы.

6. Сформулировать самостоятельно на материале исходных данных две обратные задачи распознавания‚ осуществить их решение‚ записать качественные ответы.

7. Составить отчет. Ответить на контрольные вопросы.

Общие сведения

Качественное описание задачи распознавания.

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

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

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

Необходимо определить к какому классу может быть отнесен данный объект.

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

Логические задачи распознавания. В проблеме распознавания объектов методы алгебры логики (исчисления высказываний) выступают на первый план в случаях, когда отсутствуют сведения о количественном распределении объектов по пространственным, временным, энергетическим и другим интервалам в соответствующем пространстве признаков, а в распоряжении исследователя имеются лишь детерминированные логические связи между рассматриваемыми объектами и их признаками. Задачи распознавания, удовлетворяющие этим условиям, называются логическими задачами распознавания.

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

- либо появляются истребители-перехватчики и штурмовики и при этом нет ни тяжелых бомбардировщиков, ни истребителей сопровождения;

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

На основании этих данных‚ образующих априорную информацию‚ требуется определить, например:

а) какие выводы можно сделать относительно появления бомбардировщиков‚ если известно‚ что ожидается налет, в котором будут участвовать истребители сопровождения и не будет штурмовиков;

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

На материале этой задачи далее будет рассмотрен общий подход к формализации логических задач распознавания и методы их решения.

Основу для постановки логической задачи распознавания составляют два конечных множества Х и L‚ элементами которых являются двоичные (булевы) логические переменные х_j , l_j :

Х = {х₁‚ х₂‚ ...‚ х_n }, L = {l₁‚ l₂‚ ...‚ l_m}.

Одно из них, например Х, является множеством классов‚ другое – L - множеством признаков. Их значения будут:

Для нашего примера Х = { х₁‚ х₂‚ х₃ }‚ L = {l₁‚ l₂}‚ где булевы переменные означают (равны 1):

х₁ - наличие истребителей сопровождения;

х₂ - наличие истребителей перехватчиков;

х₃ – наличие штурмовиков;

l₁ - наличие тяжелых бомбардировщиков;

l₂ - наличие легких бомбардировщиков.

Как видно‚ в данном случае разница между классами и признаками определяется структурой исходных данных и является весьма условной.

Для конкретной предметной области между логическими переменными х_i (i= 1‚2‚...‚n) и l_j=(j = 1‚ 2‚...‚ m) устанавливаются зависимости‚ выражающиеся в форме логических условий вида:

х_i = F_i (l₁‚ l₂‚ ...‚ l_m);

l_j = Ф_j (х₁‚ х₂‚ ...‚ х_{n) ,}

или

х_i ® F_i (l₁‚ l₂‚ ...‚ l_m) = 1;

Ф_j (х₁‚ х₂‚ ...‚ х_n) ® l_j = 1,

или

F (х₁‚ х₂‚ ...‚ х_n) ® Ф (l₁‚ l₂‚ ...‚ l_m) = 1,

или

F(х₁‚ х₂‚...‚ х_n ‚ l₁‚ l₂‚...‚ l_m) = Ф (х₁‚ х₂‚...‚ х_n , l₁‚ l₂‚...‚ l_m).

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

Y (х₁‚ х₂‚...‚ х_n‚ l₁‚ l₂‚...‚ l_m) = 1 (3.1)

Приведение к форме (3.1) возможно на основе известных преобразований, например:

зависимость F(х₁‚ х₂‚...‚ х_n‚ l₁‚ l₂‚...‚ l_m) = Ф (х₁‚ х₂‚...‚ х_n‚ l₁‚ l₂‚...‚ l_m)

эквивалентна выражению F( ) ~ Ф( ) = 1 = [ F( ) & Ф( ) ]Ú [ F( ) &Ф( )],

а зависимость F( х₁‚ х₂‚...‚ х_n‚ l₁‚ l₂‚...‚ l_m ) ® Ф( х₁‚ х₂‚...‚ х_n‚ l₁‚ l₂‚...‚ l_m ) = 1

эквивалентна F( ) Ú Ф( ) = 1.

В нашем конкретном примере априорная информация может быть представлена в форме

Y (х₁‚ х₂‚ х₃‚ l₁‚ l₂) = х₁· х₂ · х₃ · l₁ Ú х₁·х ₂·l₁ (х₃·l₂ Ú х₃·l₂) = 1, (3.2)

устанавливающей “истинность” перечисленных выше условий‚ регламентирующих состав боевых средств при налете противника.

Задача распознавания возникает‚ когда в дополнение к априорной информации (3.1) появляется полученная на основе дополнительных наблюдений (экспериментов) апостериорная информация‚ устанавливающая “истинность” некоторой заданной булевой функции G(l₁‚ l₂‚ ...‚ l_m) логических переменных l₁‚ l₂‚ ...‚ l_m и требуется определить‚ какие выводы можно сделать относительно логических переменных х₁‚ х₂‚...‚ х_n и выражающей их состояние и взаимосвязь функции F(х₁‚ х₂‚ ...‚ х_n).

Формально это сводится к нахождению булевой функции F(х₁‚ х₂‚ ...‚ х_n)‚ такой, чтобы выполнялось условие

G (l₁‚ l₂‚ ...‚ l_m) ® F (х₁‚ х₂‚ ...‚ х_n) = 1 (3.3)

при ограничениях (3.1). Эта задача называется прямой задачей распознавания.

Если же апостериорная информация задана в виде булевой функции R (х₁‚ х₂‚ ...‚ х_n) переменных х₁‚ х₂‚ ...‚ х_n и нужно определить‚ какие следствия это породит в отношении переменных l₁‚ l₂‚ ...‚ l_m ‚ т.е. найти функцию Q (l₁‚ l₂‚ ...‚ l_m)‚ удовлетворяющую уравнению

R (х₁‚ х₂‚ ...‚ х_n) ® Q (l₁‚ l₂‚ ...‚ l_m) =1 (3.4)

при ограничениях (3.1)‚ то такая задача называется сопряженной задачей распознавания.

Принципиальная разница между прямой и сопряженной задачами распознавания состоит в том‚ что в первом случае апостериорная информация, образующая “посылку”, задается на множестве признаков L‚ а искомое “следствие” определяется на множестве классов Х‚ тогда‚ как во втором случае наоборот. Однако в обоих случаях требуется на основании заданной “посылки” определить “следствие”‚ удовлетворяющее априорной информации (3.1).

Применительно к рассматриваемому примеру апостериорная информация в п. а) формально задается в виде

R(х₁‚ х₂‚ х₃) = x_{1 ·} х₃

и ставится сопряженная задача распознавания:

(x_{1 ·} х ₃) ® Q (l₁‚ l₂) = 1,Q (l₁‚ l₂) = ?.

В п. б) апостериорная информация задается в виде

G (l₁‚ l₂) = (l₁ Ú l₂) Ú l_{1 ·} l₂ = l_{1 ·} l₂ Ú l_{1 ·} l₂ = l₁

и ставится прямая задача распознавания:

l₁ ® F (х₁‚ х₂‚ х₃) = 1,F (х₁‚ х₂‚ х₃) = ?

Наряду с прямой и сопряженной задачами распознавания могут существовать и обратные, когда апостериорная информация задает «следствие», а необходимо определить «посылку», которая это следствие порождает и удовлетворяет априорной информации (3.1).

Так если задана Q (x_1, х₂‚ …, х_n) и требуется найти R (l₁‚ l₂, …, l_m) такую, что

R (l₁‚ l₂, …, l_m) ® Q (x_1, х₂‚ … х_n) = 1, R (l₁‚ l₂, …, l_m) =? , (3.5)

то это обратная прямой задача распознавания.

Если же задана H (l₁‚ l₂, …, l_m) и требуется найти L( х₁‚ х₂‚ …, х_n), такую, что

L ( х₁‚ х₂‚ …, х_n) ® H (l₁‚ l₂, …, l_m) = 1, L ( х₁‚ х₂‚ …, х_n) = ?, (3.6)

то это обратная сопряженной задача распознавания.

Например:

в) Какая ситуация с участием в налете тяжелых и легких бомбардировщиков влечет за собой наличие истребителей сопровождения и отсутствие штурмовиков (обратная прямой задача распознавания) ?

R (l₁‚ l₂) ® x₁ х ₃ = 1, R (l₁‚ l₂) = ?

г) Какая ситуация с участием в налете истребителей и штурмовиков влечет за собой наличие легких бомбардировщиков и отсутствие тяжелых (обратная сопряженной задача распознавания) ?

L ( х₁‚ х₂‚ х₃) ® l_{1 ·} l₂ = 1, L ( х₁‚ х₂‚ х₃) = ?

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

Принципиальная возможность решения поставленных логических задач распознавания связана с существованием логической зависимости между классами и признаками‚ которая содержится в априорной информации (3.1).

Представление этой зависимости в более явной форме в виде соотношения между наборами (х₁‚ х₂‚...‚ х_n) и (l₁‚ l₂‚...‚ l_m)‚ удовлетворяющего (3.1)‚ лежит в основе метода и связана с построением так называемого сокращенного базиса .

Пусть определена функция Y(х₁‚ х₂‚...‚ х_n‚ l₁‚ l₂‚...‚ l_m), выражающая априорную информацию в соотношении (3.1).

Сокращенный базис есть множество (n+m) разрядных наборов ‚ при которых удовлетворяется условие (3.1), то есть множество наборов (х₁‚ х₂‚...‚ х_n‚ l₁‚ l₂‚...‚ l_m) на которых функция y( ) равна единице (множество T₁^y функции y). Сокращенный базис для заданной функции y может быть представлен в виде‚ например‚ специальной таблицы (см. таблицу 3.1).

Таблица 3.1

х1			· · ·
х2
· · ·
хn
l1
l2
· · ·
lm			· · ·

Каждый элемент сокращенного базиса - (n+m) - разрядный двоичный набор (столбец в таблице 3.1)‚ может быть разбит на две части: n - разрядный‚ соответствующий аргументам х₁‚ х₂‚...‚ х_n (верхняя часть таблицы) и m-разрядный‚ соответствующий аргументам l₁‚ l₂‚ ...‚ l_m (нижняя часть таблицы). Таким образом устанавливается соответствие между наборами (х₁‚ х₂‚...‚ х_n) и наборами (l₁‚ l₂‚ ...‚ l_m)‚ при которых априорная информация является “истинной”, (выполняется (3.1)).

Такое соответствие между наборами можно формализовать с помощью булевой матрицы Е размера 2ⁿ×2^m‚ элементы которой e_ij = 1‚ если i-ый набор (х₁‚ х₂‚...‚ х_n) совместно с j-м набором ( l₁‚ l₂‚ ...‚ l_m) образуют элемент множества T₁^y , и e_ij = 0 в противном случае. Назовем такую матрицу перестановочной.

Продемонстрируем построение сокращенного базиса для априорной информации‚ представленной в соответствии с выражением (3.2). Составим для его правой части

Y (х₁‚ х₂‚ х₃‚ l₁‚ l₂) = х₁· х₂ · х₃ · l₁ Ú х₁·х ₂·l₁ (х₃·l₂ Ú х₃·l₂)

таблицу истинности (табл. 3.2) и по ней найдем сокращенный базис (табл. 3.3).

Таблица 3.2

T

x1

x2

x3

λ1

λ2

__ __ x1·x2·x3·λ1

__ x1·x2·x3·λ1·λ2

__ __ __ x1·x2·x3·λ1·λ2

ψ(x1,x2,x3,λ1,λ2)

Таблица 3.3

T
х1
х2
х3
l1
l2
j

Как видно‚ сокращенный базис состоит из четырех 5-ти разрядных наборов (12‚ 13‚ 18 и 23) и регламентирует следующую связь между наборами (х₁‚ х₂‚ х₃) с номерами i и наборами (l_1‚ l₂) с номерами j:

i = 3 ® j = 0, i = 3 ® j = 1, i = 4 ® j = 2, i = 5 ® j = 3.

Соответствующая перестановочная матрица имеет вид (рис. 3.1).

=

Рис. 3.1

После того‚ как определены искомые связи между наборами (х₁‚х₂‚...‚ х_n) и (l_1‚ l_{2‚ ...‚} l_m) прямая и сопряженная задачи распознавания решаются путем удовлетворения соотношениям (3.3) или (3.4) наборами с номерами i и j‚ находящимися в такой связи. Практически это осуществляется путем “вычисления” изображающего числа искомой ФАЛ на основе логического умножения справа изображающего числа ФАЛ‚ задающей апостериорную информацию, на перестановочную матрицу‚ отображающую априорную информацию.

Для прямой задачи распознавания (3.3) это имеет вид:

#F (х₁‚ х₂‚...‚ х_n) = #G (l_1‚ l_{2‚ ...‚} l_k) ÄE^Т (3.7)

(1× 2^m) (1× 2^m) ( 2^m×2ⁿ)

Для сопряженной задачи распознавания (3.4):

#Q (l_1‚ l_{2‚ ...‚} l_m) = #R (х₁‚ х₂‚...‚ х_n) Ä E (3.8)

(1× 2^m) (1× 2ⁿ) ( 2ⁿ×2^m)

Обоснованием данного способа “вычисления” искомых ФАЛ может служить известное свойство‚ проявляющееся при умножении справа изображающего числа ФАЛ‚ отличной от константы «ноль»‚ например‚ R(х₁‚ х₂‚...‚ х_n)‚ на прямоугольную булеву матрицу‚ например Е‚ и заключающееся в том‚ что единица в i-ой строке и j-м столбце матрицы Е (то есть е_ij= 1) обеспечивает перемещение единицы‚ находящейся на i-ом месте в #R (х₁‚ х₂‚...‚ х_n) на j-ое место результата - изображающего числа #Q (l_1‚ l_{2‚ ...‚} l_m).

Это значит‚что при е_ij= 1 единица на i-ом месте #R (х₁‚ х₂‚...‚ х_n) обеспечивает единицу на j-ом месте # Q (l_1‚ l_{2‚ ...‚} l_m) (см. рис 3.2)‚ что соответствует истинности импликации. Если учесть все единицы в #R (х₁‚ х₂‚...‚ х_n)‚ то #R (х₁‚ х₂‚...‚ х_n) ® #Q (l_1‚ l_{2‚ ...‚} l_k) = 1‚ что соответствует решению задачи (3.4).

Аналогично при умножении #G (l₁‚ l₂‚...‚ l_m) на Е^Т получаем #F (х₁‚ х₂‚...‚ х_n)‚ причем #G (l₁‚ l₂‚...‚ l_m) ® #F (х₁‚ х₂‚...‚ х_n) = 1.

Рис. 3.2

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

а) #R (х₁‚ х₂‚ х₃) = # (х₁ · х₃) = (00001010),

#Q (l_1‚ l₂) = (00001010) Ä = (0010),

следовательно Q(l_1‚ l₂) = l₁·l₂, что обозначает: в налете будут участвовать тяжелые бомбардировщики и не будет легких;

б) #G (l_1‚ l₂) = # ( ₁) = (1100),

#F (х₁‚ х₂‚ х₃) = (1101) Ä = (00010000) ,

следовательно F (х₁‚ х₂‚ х₃) = x_{1 ·} х_{2 ·} х₃ , что означает: в налете будут участвовать истребители-перехватчики и штурмовики и не будет истребителей сопровождения.

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

Пусть для заданной функции Q (х₁‚ х₂‚...‚ х_n) требуется найти такую функцию R(l₁‚ l₂‚...‚ l_m) =?‚ что R (l₁‚ l₂, …, l_m ® Q (x_1, х₂‚ … х_n) = 1.

Так как R ® Q = R Ú Q = Q Ú R = Q ® R = 1‚ то рассматриваемая обратная задача может быть заменена прямой

Q (x_1, х₂‚ … х_n) ® R (l_1‚ l_{2‚ . . .} l_k) = 1, R (l₁‚ l₂, …, l_k) =?,

содержащей инверсии заданной и искомой функции.

На этом построение методики решения задач распознавания (3.3)‚ (3.4)‚ (3.5)‚ (3.6) завершено.

В заключение‚ рассмотрим важный частный случай.

Пусть сокращенный базис состоит из 2^m (n + m) - разрядных наборов‚ причем в нем представлены все m - разрядные наборы l₁‚ l₂‚...‚ l_m (такая ситуация имела место в нашем примере и отражена в таблице 3.3). Соответствующая перестановочная матрица Е имеет по одной единице в каждом столбце. Можно заметить‚ что в этом случае логические переменные х₁‚ х₂‚...‚ х_n могут быть представлены‚ как некоторые функции логических переменных l₁‚ l₂‚...‚ l_m‚, образующие решение булевского уравнения (3.1) в виде

х_i = f_i (l₁‚ l₂‚...‚ l_m) ‚ i = 1‚2,..., n. (3.9)

Например‚ таблица 3.3 задает три ФАЛ:

х ₁ = l₁ , х ₂ = l₁ , х₃ = l₁ Ú l₂ .

В данной ситуации решение сопряженной задачи распознавания (3.4) может быть получено аналитически путем подстановки в заданную функцию R(х₁‚ х₂‚...‚ х_n ) функций х_i = f_i (l₁‚ l₂‚...‚ l_m). В результате получится искомая функция Q (l₁‚ l₂‚...‚ l_m).

Для рассматриваемого примера R (х₁‚ х₂‚ х₃) = х₁ · х ₃

Q (l_1‚ l₂) = R (f₁ (l_1‚ l₂)‚ f₂ (l_1‚ l₂)‚ f₃ (l_1‚ l₂)) = l₁· (l₁ Ú l₂) = l₁· l₁· l₂ = ₌ l₁ · l₂ ,

что совпадает с полученными ранее.

При наличии нескольких единиц в каждом столбце сокращенного базиса решение исходного уравнения вида (3.9) будет не единственное. При отсутствии единицы хотя бы в одном столбце решения уравнения (3.1) в виде х_i = f_i (l₁‚ l₂‚...‚ l_m) ‚ i = 1‚2,...,n не существует.

Следует заметить, что рассмотренный выше вариант представления сокращенного базиса в виде перестановочной матрицы соответствует заданию конечного автомата без памяти с двоичными входами l₁‚ l₂‚...‚ l_m и выходами х₁‚ х₂‚...‚ х_n , обеспечивающего решение исходного уравнения (3.1).

Наличие сокращенного базиса позволяет искать решения исходного уравнения (3.1) также в виде

l_j = φ_j (х₁‚ х₂‚...‚ х_n) ‚ j = 1‚2,...,m. (3.10)

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

В данной лабораторной работе необходимо осуществить анализ полученного сокращенного базиса на существование и единственность решения (3.9). При наличие нескольких привести все решения.

В конкретных приложениях логические задачи распознавания приходится решать при наличии больших массивов данных о классах и признаках объектов‚ поэтому весьма актуальными являются алгоритмизация решений и реализация их на ЭВМ.

Методические указания

1) Формализация задачи осуществляется по схеме, описанной в разделе «Общие сведения», и предусматривает следующее:

- определение множества "классов", множества "признаков" и введение соответствующих групп логических переменных;

- запись на языке ФАЛ априорной информации, устанавливающей связь между "классами" и "признаками";

- запись на языке ФАЛ апостериорной информации, характеризующей результат дополнительного наблюдения;

- записи на языке ФАЛ конкретных задач распознавания и определение их вида.

2) Анализ существования и единственности решения полученного уравнения выполнить используя перестановочную матрицу. Найти все существующие решения.

3) Решение задач распознавания производится на основе составления сокращенного базиса, формирования перестановочной матрицы и вычисления изображающих чисел по формулам (3.7) или (3.8).

4) Если решение сопряженной задачи распознавания (3.4) допускает аналитическое решение, то получить его путем подстановки в заданную функцию R(х₁‚ х₂‚...‚ х_n ) функций х_i = f_i (l₁‚ l₂‚...‚ l_m). Если аналитических решений несколько, то найти все решения.

5) Машинное решение задач распознавания предусматривает:

- ознакомление с описанием и работой программы;

- описание на языке программы априорной и апостериорной информации, задание вида задачи распознавания;

- машинный счет с выводом результатов счета на печать.

6) Все этапы решения должны быть подробно отражены в отчете.

7) Анализ результатов включает в себя сопоставление результатов расчетов и затрат на получение ручного и машинного решений с учетом возможного увеличения числа классов, признаков, ограничений и т.п.

Исходные данные (априорная информация).

При функционировании технической системы‚ состоящей из 3–х взаимосвязанных подсистем (блоков) в условиях нормальной (повышенной) температуры и нормальной (повышенной) влажности выявлено наличие совместно 4^-х связей (№№ задаются для каждой бригады) из нижеследующего списка.

1. Пpи ноpмальной температуре и влажности все блоки pаботоспособны.

2. При повышенной температуре и повышенной влажности все блоки неpаботоспособны.

3. Пpи ноpмальной температуре и повышенной влажности теpяет pаботоспособность 2-й блок.

4. Пpи повышенной температуре и ноpмальной влажности теpяет pаботоспособность 1-й блок.

5. Пpи ноpмальной температуре pаботоспособны 1-й и 3-й блоки.

6. Пpи повышенной температуре отказывает 1-й блок, а 2-й и 3-й либо оба pаботоспособны, либо оба неpаботоспособны.

7. Пpи ноpмальной влажности pаботоспособны 2-й и 3-й блоки.

8. Пpи повышенной влажности отказывает 2-й блок, а 1-й и 3-й либо оба pаботоспособны, либо оба не pаботоспособны.

9. Пpи ноpмальной температуре и повышенной влажности теpяет pаботоспособность только 2-й блок.

10. Пpи повышенной температуре и ноpмальной влажности pаботоспособен только 2-й блок.

11. Пpи ноpмальной температуре pаботоспособны блоки 1 и 2-й.

12. Пpи повышенной температуре отказывают 1 и 3-й блоки.

13. Пpи ноpмальной влажности pаботоспособен блок 2, а блоки 1 и 3 или оба pаботоспособны или оба не pаботоспособны.

14. Пpи повышенной влажности отказывает 3-й блок, а блоки 1 и 2-й или оба pаботоспособны или оба не pаботоспособны.

15. Пpи повышенной температуре и влажности pаботоспособен только 2-й блок.

16. Пpи ноpмальной температуре и повышенной влажности не pаботоспособен только 1-й блок.

17. Пpи повышенной температуре и ноpмальной влажности pаботоспособен только 1-й блок.

18. Пpи ноpмальной температуре pаботоспособны 2 и 3-й блоки.

19. Пpи повышенной температуре не pаботоспособны только 3-й блок и какой-либо блок из оставшихся (1-й или 2-й).

20. Пpи ноpмальной влажности pаботоспособен 1-й блок, а остальные либо оба pаботоспособны, либо оба не pаботоспособны.

21. Пpи повышенной влажности 1-й блок не pаботоспособен, а 2-й pаботоспособен.

22. При повышенных температуре и влажности работоспособен только 3-й блок

23. При нормальной температуре и повышенной влажности не работоспособен только 3-ий блок

24. При повышенной температуре и нормальной влажности не работоспособен только 2-ий блок

25. При нормальной температуре работоспособны 1-й и 2-й блоки

26. При повышенной температуре 2-ой блок не работоспособен, а 3-й работоспособен

27. При нормальной влажности работоспособны 1-й и 3-й блоки

28. При повышенной влажности или работоспособен только 3-й блок или не работоспособен только 3-й блок.

Требуется определить (апостериорная информация):

1) Если известно‚ что функционирование системы протекает при нормальной температуре‚ то какие блоки потеряют (не потеряют) работоспособность?

2) Если потерял работоспособность блок 1 или блоки 2 и 3 (совместно)‚ какое сочетаний температуры и