- •1.Предикаты. Кванторы.
- •Построение разбиения, порождаемого отношением .
- •Определение: Элемент a называется наибольшим (наименьшим) в отношении , если b a(a b) ( a a(b a)).
- •10.Отношения линейного порядка.
- •12.Дизъюнктивные нормальные формы.
- •13.Минимизация днф.
- •14. Монотонные функции
- •1. Списки ребер
- •2. Матрицы смежности
Построение разбиения, порождаемого отношением .
Пусть отношение эквивалентности на множестве A.
Для каждого x A обозначим как [x] множество {yxy}. Поскольку отношение рефлексивно, то x [x], а, значит, каждое множество [x] является непустым и система множеств [x], где x A, содержит все элементы A. Из семейства множеств {[x] x A } удалим кратные вхождения одинаковых множеств. В результате получим семейство непустых несовпадающих множеств R, в которых содержатся все элементы A.
Обоснование того, что R образует разбиение.
Пусть [x] и [y] произвольные классы из семейства R. Покажем, что они либо не пересекаются, либо совпадают, т.е. возможны только два случая:
1) [x] [y] = ;
2) [x] [y] .
Предположим, что это свойство является неверным. То есть для некоторых двух элементов x и y множества [x] и [y] пересекаются, но не совпадают (рис 3.1).
[x] [y]
x z y
a b
Рис.3.1
Здесь z это элемент, общий для классов [x] и [y], а a и b произвольные элементы в [x] и [y] соответственно.
1. Докажем, что [x] [y]. Пусть x a. Покажем, что справедливо отношение y a:
a) поскольку x z, то из симметричности следует, что z x;
b) поскольку z x и x a, то из транзитивности вытекает, что z a;
c) из y z и z a и транзитивности имеем y a. Поэтому a [y], а, значит, [x] [y].
2. Обратное включение [y] [x] может быть доказано, если повторить проведенные рассуждения, поменяв в них местами x и y, а также a и b.
Следовательно, справедливо равенство множеств [x] и [y]. Последнее противоречит предположению о том, что эти множества являются разными.
Это означает, система множеств R образует разбиение множества разбиение A.
3. Обоснование того, что R разбивает A на классы эквивалентных элементов.
3.1. Покажем, что в каждом классе из R любые два элемента находятся между собой в отношении .
Пусть выбраны произвольное множество [x] R и элементы a, b A. Покажем, что a b. Действительно, по определению множества [x] справедливы соотношения: xa и xb. Из соотношения xa и симметричности следует, что ax. Из ax и xb, а также транзитивности следует, что ab.
3.2. Покажем, что элементы из разных классов в R не находятся в отношении . Пусть [x], [y] R и a[x], b[y] произвольные элементы этих множеств. Покажем, что (a, b) . Предположим противное. Пусть ab. Тогда из симметричности отношения следует, что ba. Поскольку yb и ba, то из транзитивности следует, что ya. Поэтому a[y]. Последнее противоречит тому, что множества [x] и [y] не пересекаются.
Следовательно, (a, b) .
Доказательство окончено.
9. ОТНОШЕНИЯ ПОРЯДКА
ОПРЕДЕЛЕНИЕ
Рефлексивное, антисимметричное и транзитивное отношение на некотором множестве называется отношением порядка.
Отношение порядка на некотором множестве А можно интерпретировать как отношение старшинства или подчиненности между элементами A.
Например, если A множество сотрудников некоторого учреждения, то отношение "руководить" является отношением порядка на этом множестве. То есть, если обозначить данное отношение как , то соотношение a b означает, что сотрудник a руководит сотрудником b, или, что то же самое, a является начальником b.