Решение. Какими признаками характеризуется матрица отношения R,

Пример 1.

Какими признаками характеризуется матрица отношения R,

если R соответственно: рефлексивно, антиреф­лексивно, симметрично, антисимметрично, транзитивно.

Пусть R задано на М, R Í M х М.

1) R рефлексивно, если для любого, а Î М имеет место a R a, т.е. оно выполняется для всех пар (а, а), а Î М.

В мат­рице этим парам соответствуют элементы с. Такие элемен­ты составляют главную диагональ матрицы. Следовательно, главная диагональ матрицы рефлексивного отношения со­держит только единицы;

2) R антирефлексивно, если ни для какого а Î М не вы­полняется a R а. Из этого следует, что главная диагональ мат­рицы антирефлексивного отношения должна содержать толь­ко нули; 3) R симметрично, если для пары (а, b) Î М х M из a R b следует b R a, т.е. для любой пары отношение R выполняется в обе стороны либо не выполняется вообще.

Таким обра­зом, если в матрице 1 стоит на Çi- стро­ки и j - столбца, т.е. с_ij = 1, то она должна стоять и на Ç j - строки и i- столбца, т.е. с_ji = 1,

и наоборот, если с_ji = 1, то с_ij = 1. Таким образом, в матрице симметричного отношения с_{ij =} с_ji, т.е. матрица симметрична относительно главной диагонали;

4) R антисимметрично, если a R b и b R a следует а = b. Это означает, что в матрице ни для каких ij Î[1,2… m ], m = | М |, i ¹ j, не выполняется с_ij = с_ji = 1. Таким образом, в матрице антисимметричного отношения отсутствуют единицы, симметричные относительно главной диагонали.

5) R транзитивно, если для любых а, b, с из a R b и b R с следует a R с.

В матрице отношения должно выпол­няться условие: если в i -й строке стоит единица, например в j -й координате (столбце) строки, т.е. с_ij = 1, то всем единицам в j -й строке (пусть этим единицам соответ­ствуют k -е координаты c_jk = 1 1) дол­жны соответствовать единицы в I - строке в тех же k-х координа­тах, т.е. с_ik = 1 (и, мо­жет быть, еще и в других координатах).

	…	ak1	…	aj	…	ak2	…	akr
·
·
·
ai				1
·		­				­		­
·		­				­		­
·		­				­		­
aj	®		®	®	®		®

Это условие иллюстриру­ется на рис. 2.6, где кружком выделена единица с_ij = 1, для ко­торой производится проверка условия, а стрелками показа­на последовательность проверки данного условия.

В матрице транзитивного отношения это условие должно вы­полняться для любых i,j Î m = | M | таких, что с_ij = 1. И наоборот, если в матрице R имеется хотя бы одна единица с_ij = 1, для кото­рой данное условие не выполняется, то R не транзитивно * Правила выявления нетранзитивности смотри в ч. 1.гл 3, §5

Дата добавления: 2014-01-20