Бинарные отношения и их свойства

Основы дискретной математики.

Понятие множества. Отношение между множествами.

Множество – совокупность объектов, обладающих определенным свойством, объединенных в единое целое.

Объекты, составляющие множество называются элементами множества. Для того чтобы некоторую совокупность объектов можно было называть множеством должны выполняться следующие условия:

· Должно существовать правило, по которому моно определить принадлежит ли элемент к данной совокупности.

· Должно существовать правило, по которому элементы можно отличить друг от друга.

Множества обозначаются заглавными буквами, а его элементы маленькими. Способы задания множеств:

· Перечисление элементов множества. - для конечных множеств.

· Указание характеристического свойства .

Пустым множеством – называется множество, не содержащее ни одного элемента (Ø).

Два множества называются равными, если они состоят из одних и тех же элементов. , A=B

Множество B называется подмножеством множества А ( , тогда и только тогда когда все элементы множества B принадлежат множеству A.

Например: , B =>

Свойство:

Примечание: обычно рассматривают подмножество одного и того е множества, которое называется универсальным (u). Универсальное множество содержит все элементы.

Операции над множествами.

A

B

1. Объединением 2-х множеств А и В называется такое множество, которому принадлежат элементы множества А или множества В (элементы хотя бы одного из множеств).

Н-р: , ,

 

2.Пересечением 2-х множеств называется новое множество, состоящее из элементов, одновременно принадлежат и первому и второму множеству.

Н-р: , ,

 

Свойство: операции объединения и пересечения.

· Коммутативность.

;

· Ассоциативность. ;

;

· Дистрибутивный. ;

;

A

B

3.Разностью двух множеств называется множество элементы которого принадлежат мн-у А, но не принадлежат мн-у B.

Н-р: , ,

 

А

U

4.Дополнение. Если А – подмножество универсального множества U, то дополнением множества А до множества U (обозначается ) называется множество состоящее из тех элементов множества U, которые не принадлежат множеству А.

 

 

Бинарные отношения и их свойства.

Пусть А и В это множества производной природы, рассмотрим упорядоченную пару элементов (а, в) а ϵ А, в ϵ В можно рассматривать упорядоченные «энки».

(а₁, а₂, а₃,…а_n), где а₁ ϵ А₁; а₂ ϵ А₂; …; а_n ϵ А_n ;

Декартовым (прямым) произведением множеств А₁, А₂, …, А_n , называется мн-во, которое состоит из упорядоченных n^k вида .

Н-р: М = {1,2,3}

М× М= М² = {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Подмножества декартова произведения называется отношением степени n или энарным отношением. Если n=2, то рассматривают бинарные отношения. При чем говорят, что а₁, а₂ находятся в бинарном отношении R, когда а₁ R а_2.

Бинарным отношением на множестве M называется подмножество прямого произведения множества n самого на себя.

М× М= М² = {(a, b)| a, b ϵ M} в предыдущем примере отношение меньше на множестве М порождает следующее множество: {(1,2);(1,3); (2,3)}

Бинарные отношения обладают различными свойствами в том числе:

· Рефлексивность: .

· Антирефлексивность (иррефлексивность): .

· Симметричность: .

· Антисимметричность: .

· Транзитивность: .

· Асимметричность: .

Виды отношений.

· Отношение эквивалентности;

· Отношение порядка.

v Рефлексивное транзитивное отношение называется отношением квазипорядка.

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

v Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.

v Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.