Парадигма развития науки. Методологическое обеспечение (стр. 99 )

I5 I8= {a, d, f, e}, J5 J8= ,

I5 I8= ,

I5 I9 ={f, e}, J5 J9 = {e} дает [M5],

15 I9={f}, J5 J9 = {a, d, f, b, е} дает [M9],

I6 I7 = {a. d, f b, c, e}, J7 J7 = ,

I6 I7 = {a, d, f, b}, J6 J7 = {a, d, f} содержится в [M1],

I6 I8 = {a, d, f, b, c}, J6 J8 = {a, d} дает [М6],

I6 I8 = {a, d}, J6 J8 = {a, d, f, b, с} дает [М8],

I6 I9 = {a. d, f, b, c}, J6 J9 = {a. d} дает [M6],

I6 I9 = {f}, J6 J9 = {a, d, f, b, e} дает [M9],

17 I8 = {a, d, f, b, e}, J7 J8 = {f} дает [M7],

I7 I8 = { a, d}, J7 J8 = {a, d, f, b, c} дает [M8],

I7 I9 = {a, d, f, b, e}, J7 J9 = {f} дает [M7],

I8 I9 = {f}, J7 J9 = {a, d, f, b, e} дает [M9],

I8 I9 = {a, d, f}, J8 J9 = {a, d, f, b} содержится в [М1],

I8 I9 = .

Этап 5 (вторая итерация). Выпишем новое покрытие

С'′= {[M1], [M6], [M7], [M8], [M9], [М10], [М11]}. (*)

Мы исключили подматрицы [М2], [M3], [M4], [М5] как такие, что содержатся в других подматрицах покрытия (*).

Этап 6 (первая итерация). Не тяжело удостовериться в том, что новых матриц получить больше нельзя. Итак, покрытие С" (*) состоит из следующих основных матриц:

(**)

В этом покрытии содержатся три квадратные подматрицы [М1], [М10] и [М11]; они дают три непересекающихся подотношений. На рис. 3 представлены эти три подотношения, ни одно из которых не содержится в другом.

Рис. 3.

Заметим, что выявление матриц [М6]=[М8]' и [М7]=[М9]' небесполезно, ими обеспечивается «стыковка» между подотношениями.

Второй алгоритм - алгоритм Пишá.

Этот алгоритм пригоден исключительно для симметрических квадратных матриц, которые представляют значительный интерес.

Рассмотрим верхнюю треугольную матрицу, такую, например, как на рис. 4.

Рис. 4.

Поочередно в каждом строке матрицы выделим нули. Рассматривая элементы матрицы как булевы переменные, свяжем булевым знаком суммирования индекс строки и индексы столбцов, в которых находятся нулевые элементы этой строки, и полученные суммы объединим знаком булева произведения ∙, причем, если в строке нет нулей, будем считать, что сумма равна 1.

Упростим полученное в результате произведение, (используя для этого следующие правила упрощения булевых выражений: х+х=х, х∙х=х, х+ху=х) приведя его к максимальной форме. Для каждого слагаемого в этой форме возьмем его дополнение. Таким образом получим максимальные подотношения, которые устанавливают покрытие.

Рассмотрим пример на рис. 2, для которого верхнетреугольная матрица представлена на рис. 4.

Для строки

а получим а + е,

b «b +се,

с «c + ef,

d « d+ e,

е « 1,

f « 1.

Теперь имеем

S=(ae)∙(bce)∙ (cef)∙ (d e)∙1∙1=(a e)∙ (bce)∙ (c ef)∙(de) =

= (ab ace be ce) (c ef)(d e) =

= (abcabefcecef bcebef) (d e) = (abc bef ce) (d e) =

= abcd abce bdef bef ced ce = abcd bef ce.

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

S' = ef аcd abdf.

Это дает нам три подмножества

{е, f}, {а, c, d}, {а, b, d, f},

которые определяют основные подматрицы, составляющие покрытие (см. [М11], [М10] и [М11] в (**)).

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

{е, f} {a, c, d} = ,

{а, c, d} {а, b, d, f} = {a, d},

{a, b, d, f} {e, f} = {f}.

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

(х, у) = (у, х)=1, если (х, у) = (у, х) > 0,

если (х, у) ≠ (у, х)