Основные понятия теории множеств. Способы задания множеств. Отношения бинарные и n-арные, страница 6

6      0 1 0 0 0 1 0 0 0                                      d                      d, e, 4, 7, 5

7      0 1 0 0 1 0 1 0 1

8      1 0 1 1 0 0 0 1 0              d,4,8,10,c,e,i,2                 10

(3)

(2)

(2)

9      0 0 0 0 0 1 0 1 0                                      5                           i     

10    0 0 0 1 0 0 0 0 1                          g                      h

дальнейшие поиски

по этим ветвям

       b c  f h  i                   b  f g h            6                               нецелесообразны

2     1 1 0 0 0          5       0 1 1 1               7

6     1 0 1 0 0          6       1 1 0 0

8     0 1 0 1 0          7       1 0 1 0

9      0 0 1 1 0         9       0 1 0 1

10  0 0 0 0  1

Рассмотрим задачу о вырожденности троичной матрицы

Рассмотрим булеву матрицу с большим числом строк

1 0 1 1 0    необходимо найти вектор ортогональный каждой

1 1 1 1 0    строке матрицы или убедиться в том, что такого

1 0 1 1 1    вектора нет. Если это так --> матрица

1 1 1 1 1    вырождена (?).

1 – 1 1 –

a b c d e f

1 -  - -  - 0         Существует ли такой вектор, который был

1 – 1 – 1 –          ортогонален каждой строке

1 0  -  - 1 1

1 -  -  -  0 1

1 1 0 -  - 1

0 1 -  -  -  1        U – исходная матрица

0 -  -  -  0 1        v – искомый вектор

0 0 -  -  1 0 -  -  0 1 0        T – минор матрицы            текущее

0 1 -  1 1 0        w – частичное решение     время

0 1 -  -  0 0                     (вектор)

0 0 0 -  0 0                троичный 1,0,-

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

Правило определения допустимого значения:

Если во всем столбце отсутствуют 1 или 0, то в этот вектор можно подставить отсутствующее значение.

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

Т  = U          w  = - - - - - -

e

f

a

 a         1        4        …   c b   … осталась                b c    

a

                                                        стр 5               2 – 1 

2 0 –

                                                                                5 1 0 

– – – – – 0                              110–11

 

Следовательно на этом пути решения нет.

Задача:

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

Приближенный метод

-  выбираем столбцы до тех пор пока все строки различны

-  составляем матрицу из столбцов

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

Задача о диагностическом тесте

Мн-во А состоит из объектов-явлений.

Мн-во В состоит из признаков

Они связаны причинно-следственным отношением

Пример:

Неисправности в ЭВМ

Зная признаки нужно выявить какие явления имеют место.

Рассмотрим простейшую модель.

Бинарное отношение А и В представим в виде булевой матрицы