17. Свойства отношений. Доказательство. Представление отношений в эвм.

Пусть a и b – любые элементы множества А. Отношение R оюладает следующими свойствами:

1. Рефлексивность aA aRa - истина

2. Антирефлексивность aA ¬aRa - истина

3. Симметричность a,bA aRbbRa

4. Антисимметричность a,bA aRb и bRaa=b

5. Транзитивность a,b,cA aRb и bRcaRc

6. Полнота a,bA ab aRb и bRa

18. Отношение эквивалентности. Класс эквивалентности.

Отношения различны по своей природе и могут обладать теми или иными свойствами

Рефлексивное, симметричное, транзитивное отношение называется отношением эквивалентности. Обозначается .

Примером явл. подобие фигур, одинаковый остаток в результате деления.

Для того, чтобы сформулировать термин «отношение эквивалентности», рассмотрим 3 условия. Только выполнение этих 3 условий свидетельствует о наличии этого отношения.

Условия выполнения эквивалентности:

1) каждый элемент эквивалентен сам себе; а=а

2) утверждение, что 2 элемента эквиваленты, не требует уточнения какой из элементов рассматривается первым, а какой вторым (свойство симметричности) a=b, b=a

3) два элемента эквивалентны третьему, эквивалентны между собой (свойство транзитивности) a=b, b=ca=c

Отношение эквивалентности связано с понятием разбиение множества.

Пусть Х – множество, для которого определено отношение эквивалентности

Подмножеством элементов эквивалентных любому х Х будем называть классом эквивалентности.

Очевидно, что все элементы одного класса эквивалентности, эквиваленты между собой.

Всякий элемент х Х может находится только в одном классе эквивалентности.

19. Отношение порядка. Минимальный элемент.

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

Во всех этих случаях на множестве Х можно ввести отношение порядка и расположить элементы множества в соотв. порядке.

Антисимметричное, транзитивное отношение называется отношением порядка . Отношение может быть и рефлексивным, тогда оно называется отношением нестрогого порядка.

   - нестрогий порядок

Отношение может быть антирефлексивным(тогда оно отношение строго порядка)

 - отношение порядка

Отношение нестрого порядка обладает след. свойствами:

1) рефлексивность хх – истина

2) антисимметричность ху and ух, если х=у

3) транзитивность ху, yz, xz

Отношение строгого порядка обладает след. свойствами:

1) антирефлексивность хх – ложь

2) антисимметричность хy and yx

3) транзитивность ху, yz, x z

Множество Х называется упорядоченным, если для  двух его элементов устанавливается отношение порядка ху, х=у, ух

20. Отношение преобладания (доминирования).

На множестве Х определено отношение доминирования, если элементы множества обладают следующими свойствами: 1) каждый индивидуум не может доминировать над самим собой (антирефлексивность) ху - ложь

2) для любой пары элементов только один доминирует над другим (антисимметричность) ху and ух – ложь

3) отношение доминирования не обладает свойством транзитивности