1.4. Кортежи и декартово произведение множеств
Для описания свойств множеств удобны
векторные представления. Пусть
представляют интерес свойства элементов
множества
по
характеристикам
,
причем каждая
характеристика может быть представлена
множеством из
допустимых значений элементов
.
Тогда каждый элемент
множества
может быть задан упорядоченным набором
значений
.
Упорядоченный набор элементов
называется вектором
или кортежем. Упорядоченный набор
элементов – вектор заключается в круглые
скобки, где
- компоненты или координаты вектора
.
Число
компонент вектора называется его
размерностью или длиной.
Два вектора одинаковой длины
и
называются равными, если попарно равны
их координаты
и т.д.
Кортежи с двумя элементами (длины два) называют упорядоченными парами, кортежи длины три — упорядоченными тройками, и т.д. Для краткости речи слово «упорядоченные» часто опускают. Кортеж, не содержащий ни одной координаты, т. е. кортеж длины 0, называется пустым.
Основные отличия понятий кортежа и множества следующие:
а) в множестве порядок элементов не играет роли, а кортежи, отличающиеся порядком элементов, различны, даже в случае, когда они имеют одинаковый состав;
б) в множестве все элементы различны, а в кортеже координаты могут повторяться.
По этим причинам, чтобы различать множества и кортежи, элементы множества заключаются в фигурные скобки, а координаты кортежа — в круглые (иногда угловые).
Пример 1.5. При отборе претендентов на работу интересуются следующими характеристиками претендентов:
пол,
,
возраст,
,
образование,
,
общий
стаж работы (лет),
,
владение
компьютером,
,
семейное
положение,
.
Известно, что претенденту Высечкину 30 лет, что он окончил ВГТУ, проработал 10 лет, владеет компьютером , не женат.
При указанной последовательности характеристик векторное описание таково:
.
Пусть
—
некоторые множества. Их декартовым
или прямым произведением
называют множество различающихся
векторов
длины п,
где
,
,
…,
.
Декартово произведение
обозначается так:
.
Произведение
сокращенно обозначается
как А
и называется декартовой
ой
степенью множества
А.
Пример 1.6. Для двух множеств
и
найти произведение
и
.
Декартовы произведения
двух множеств равны:
,
.
Обратим внимание на некоммутативность операции произведения множеств.
1.5. Бинарные отношения. Свойства отношений
Отношения представляют собой один из способов задания взаимосвязей между элементами множеств. Самыми часто используемыми оказались унарные (одноместные) и бинарные (двухместные) отношения.
Унарное
отношение или свойство
отражают наличие некоторого признака
у элементов множества
,
например, «быть тузом» на множестве
игральных карт, или «быть белым» на
множестве шаров в урне. Тогда все элементы
с данным признаком образуют подмножество
,
называемое унарным
отношением
.
Бинарные отношения используются для определения взаимосвязей, которыми характеризуются пары элементов, принадлежащие либо одному, либо двум множествам. Примерами бинарных отношений являются отношение «быть меньше» на множестве действительных чисел, или отношение «быть родственником» на множестве работников фирмы.
Пусть А
и B
два конечных множества. Декартовым
произведением множеств А
и В
называют множество
,
состоящее из всех
упорядоченных пар
,
где
Бинарным
отношением R
из множества А
в множество В называется
любое подмножество R
множества
,
т.е.
.
Если R
есть
бинарное отношение, то говорят, что
элементы
и
связаны бинарным
отношением R,
если пара
является элементом R,
т. е.
.
Наличие бинарного
отношения
для элементов
и
часто записывается как
.
Если
,
то говорят, что бинарное отношение
определено на множестве А.
Областью определения
бинарного отношения
называется множество,
состоящее из таких
,
для которых
хотя
бы для одного
.
Областью значений
бинарного отношения
называется множество
всех
,
для которых
хотя бы для одного
.
Рассмотрим свойства бинарных
отношений. Пусть имеется отношение
.
Отношение
рефлексивно,
если имеет место
для любого
.
Например, отношение «быть делителем»
рефлексивно на множестве натуральных
чисел
.
Отношение антирефлексивно, (иррефлексивно) если ни для какого не выполняется . Например, отношение «быть сыном» антирефлексивно на множестве людей.
Бинарное отношение R
на множестве А
называется симметричным,
если
влечет за собой
.
Например, отношение «работать на одной
фирме» симметрично.
Бинарное отношение R на множестве А называется антисимметричным, если ни для каких различающихся элементов и отношения и не выполняются одновременно. Например, отношение «быть начальником» антисимметрично.
Бинарное отношение R
на множестве А
называется транзитивным,
если
и
влекут за собой
.
Например, отношения «быть моложе», или
«быть братом» транзитивны.
Бинарное отношение R называют отношением эквивалентности или эквивалентностью, если оно рефлексивно, транзитивно и симметрично.
Бинарные отношения задаются
обычно списком пар (перечислением), для
которых это отношение выполняется, или
матрицей отношения, где каждый элемент
принимает значение 1, если между элементами
и
существует бинарное отношение, или
значение 0 в противном случае.
Пример 1.7. Для множества
отношение
«быть больше или равным» описывается
парами
,
или матрицей
.
Графы как удобный и наглядный способ описания бинарных отношений будут рассмотрены позже.