Лабораторная работа 3 ОТКДС (553862), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

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

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

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

Таблица 3.1

х1	0	1	  	0	1
х2	1	0		0	1
  
хn	0	1		1	0
1	1	0		1	0
2	0	0		0	1
  
m	1	1	  	0	1

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

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

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

 (х₁‚ х₂‚ х₃‚ ₁‚ ₂) = х₁· х₂ · х₃ · ₁  х₁·х ₂·₁ (х₃·₂  х ₃·₂)

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

Таблица 3.2

Таблица 3.3

T	3	3	4	5
х1	0	0	1	1
х2	1	1	0	0
х3	1	1	0	1
1	0	0	1	1
2	0	1	0	1
j	0	1	2	3

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

i = 3  j = 0, i = 3  j = 1, i = 4  j = 2, i = 5  j = 3.

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

=

Рис. 3.1

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

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

#F (х₁‚ х₂‚...‚ х_n) = #G (_1‚ _{2‚ ...‚} _k)  E^т (3.7)

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

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

#Q (_1‚ _{2‚ ...‚} _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 (_1‚ _{2‚ ...‚} _m).

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

Рис. 3.2

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

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

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

#Q (_1‚ ₂) = (00001010)  = (0010),

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

б) #G (_1‚ ₂) = # ( ₁) = (1100),

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

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

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

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

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

Q (x_1, х₂‚ … х_n)  R (_1‚ _{2‚ . . .} _k) = 1, R (₁‚ ₂, …, _k) =?,

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

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

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

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

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

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

х ₁ = ₁ , х ₂ = ₁ , х ₃ = ₁  ₂ .

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

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

Q (_1‚ ₂) = R (f₁ (_1‚ ₂)‚ f₂ (_1‚ ₂)‚ f₃ (_1‚ ₂)) = ₁· (₁  ₂) = ₁· ₁· ₂ = ₌ ₁ · ₂ ,

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

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

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

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

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

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

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

Характеристики

Список файлов книги