Свойства отношений. Доказательство. Представление отношений в ЭВМ.

Пусть 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

£ ³ Í - нестрогий порядок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Симметричное отношение. Композиция отношений.

Исходя из того, что отношение – это множество, над ними можно выполнять все теоретико-множественные операции.

Кромке того вводятся некоторые спец. операции.

Специальные операции:

1) Обращение

Отношение, симметричное отношению АÌХ´Х обозначается А^-1 и является подмножеством множества А^-1 ÌХ´У, для которых (х,у)ÎА

2) Композиция отношений

Пусть заданы 3 множества X,Y,Z и AÌX´Y BÌY´Z

Композицией отношений А и В является отношение С, являющееся подмножеством Х´ Z. (x,z)ï$y (x,y)ÎA (y,z)ÎB)

xAy, yBz xCz=xABz

Функциональное отношение.

Отношения АÌХ´У будем называется функциональным, если все его элементы (упорядоченные пары) имеют различные первые координаты.

Х={х₁ х₂ х₃ х₄ х₅}

У={у₁ у₂ у₃}

АÌХ*У={(x1 у1), (х1 у2) (х1 у3) (х2 у1)…}

Функциональное отношение из множества Х в У называется функцией и обозначается:

f:X®Y

Обычно для задания функции используют префиксную запись:

y=f(x), х-аргумент, у – значение.

Пусть задана f(x) f:X®Y

Область определения функции:

f_x={x| $y f(x)=y}

f_y={y| $x y=f(x)}

Если обл. определения f(x) является вся мн. Х, то функция называется тотальной.

f_xÌХ – частичная.

Пусть f:X®Y, а f₁:Q®Y

QÌX

Причем для "хÎQ f и f₁ значения сходятся, тогда функцию f₁ называют схождением функции f на множестве Q, а функцию f – продолжением функции f₁ на мн. Х.