2.2.1 Теоретические сведения и методические рекомендации по решению задач

Упорядоченной парой иликортежем длины дваназывается совокупность, состоящая из элементов х и у, стоящих в определенном порядке.

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

Бинарным отношениемиз множества А во множество В называется подмножество, т.е..

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

Областью значений бинарного отношенияназывается множествотакое х, что.

Тождественнымназывается отношение.

Универсальнымназывается отношение.

Обратным отношениемдляназывается отношение.

Композицией отношенийиназывается отношениесуществует такоеz, чтои.

Пусть и. Перенумеруем элементы множества А.

Матрицей отношения называется квадратная матрица порядкаn, элементы которой

Бинарные отношения обладают следующими свойствами.

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

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

Симметричным называется отношениетакое, что.

Антисимметричным называется отношениетакое, что.

Транзитивным называется отношениетакое, что.

Связнымназывается отношениетакое, чтоили. Другими словами,или, или.

Свойства бинарных отношений можно установить с помощью следующих признаков:

1. рефлексивно тогда и только тогда, когда;

2. антирефлексивно тогда и только тогда, когда;

3. симметрично тогда и только тогда, когда;

4. антисимметрично тогда и только тогда, когда;

5. транзитивно тогда и только тогда, когда;

6. транзитивно тогда и только тогда, когда.

Пусть и- отношения на множествеА. Отношениеназываетсязамыканиемотносительно свойстваС, если

а) обладает свойствомС, т.е.;

б)является надмножеством:;

в) является наименьшим:(любое, обладающее свойством С и содержащее в себе, содержит в себе также и).

Для вычислении замыканий бинарных отношений необходимо опираться на следующие факты:

1) транзитивным замыканием бинарного отношения является объединение положительных степеней;

2) рефлексивным и транзитивным замыканием бинарного отношения является объединение неотрицательных степеней.

Рефлексивное, симметричное и транзитивное отношение, заданное на множестве А, называется эквивалентностью на множестве А.

Классом эквивалентности , порожденным элементом, называется подмножество множестваА, состоящее из тех и только тех элементов у, которые состоят в отношении эквивалентности с х.

Совокупность множеств ,, …,называетсяразбиением множества А, если выполняются два условия:

1) ;

2) = Ø,,.

Всякое отношение эквивалентности на множестве А определяет разбиение множества А, причем среди элементов разбиения нет пустых. Верно и обратное утверждение: всякое разбиение на множестве А, не содержащее пустых элементов, определяет отношение эквивалентности на этом множестве

Антисимметричное и транзитивное отношение, заданное на множестве А, называется отношением порядка на множестве А.

Порядок, обладающий свойством рефлексивности, называется нестрогим, а свойством антирефлексивности – строгим.

Порядок, являющийся связным, называется полным(линейным), в противном случае порядок называетсячастичным.