Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

Пример 1.5. При отборе претендентов на работу интересуются следующими характеристиками претендентов:

пол, ,

возраст, ,

образование, ,

общий стаж работы (лет), ,

владение компьютером, ,

семейное положение, .

Известно, что претенденту Высечкину 30 лет, что он окончил ВГТУ, проработал 10 лет, владеет компьютером , не женат.

При указанной последовательности характеристик векторное описание таково:

.

Пусть — некоторые множества. Их декартовым или прямым произведением называют множество различающихся векторов длины п, где , , …, . Декартово произведение обозначается так:

.

Произведение

сокращенно обозначается как А и называется декартовой ой степенью множества А.

Пример 1.6. Для двух множеств и найти произведение и .

Декартовы произведения двух множеств равны: ,

.

Обратим внимание на некоммутативность операции произведения множеств.

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

Отношения представляют собой один из способов задания взаимосвязей между элементами множеств. Самыми часто используемыми оказались унарные (одноместные) и бинарные (двухместные) отношения.

Унарное отношение или свойство отражают наличие некоторого признака у элементов множества , например, «быть тузом» на множестве игральных карт, или «быть белым» на множестве шаров в урне. Тогда все элементы с данным признаком образуют подмножество , называемое унарным отношением .

Бинарные отношения используются для определения взаимосвязей, которыми характеризуются пары элементов, принадлежащие либо одному, либо двум множествам. Примерами бинарных отношений являются отношение «быть меньше» на множестве действительных чисел, или отношение «быть родственником» на множестве работников фирмы.

Пусть А и B два конечных множества. Декартовым произведением множеств А и В называют множество , состоящее из всех упорядоченных пар , где

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

Если R есть бинарное отношение, то говорят, что элементы и связаны бинарным отношением R, если пара является элементом R, т. е. . Наличие бинарного отношения для элементов и часто записывается как .

Если , то говорят, что бинарное отношение определено на множестве А.

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

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

Рассмотрим свойства бинарных отношений. Пусть имеется отношение . Отношение рефлексивно, если имеет место для любого . Например, отношение «быть делителем» рефлексивно на множестве натуральных чисел .

Отношение антирефлексивно, (иррефлексивно) если ни для какого не выполняется . Например, отношение «быть сыном» антирефлексивно на множестве людей.

Бинарное отношение R на множестве А называется симметричным, если влечет за собой . Например, отношение «работать на одной фирме» симметрично.

Бинарное отношение R на множестве А называется антисимметричным, если ни для каких различающихся элементов и отношения и не выполняются одновременно. Например, отношение «быть начальником» антисимметрично.

Бинарное отношение R на множестве А называется транзитивным, если и влекут за собой . Например, отношения «быть моложе», или «быть братом» транзитивны.

Бинарное отношение R называют отношением эквивалентности или эквивалентностью, если оно рефлексивно, транзитивно и симметрично.

Бинарные отношения задаются обычно списком пар (перечислением), для которых это отношение выполняется, или матрицей отношения, где каждый элемент принимает значение 1, если между элементами и существует бинарное отношение, или значение 0 в противном случае.

Пример 1.7. Для множества отношение «быть больше или равным» описывается парами

,

или матрицей

.

Графы как удобный и наглядный способ описания бинарных отношений будут рассмотрены позже.

1.6. Соответствия. Отображения. Функции

Если для каждого элемента указан элемент , то говорят, что между множествами X и Y установлено соответствие Г, состоящее из множества упорядоченных пар (x,y), таких, что и y Y : Г .

Образом элемента x при соответствии Г называется множество Im(x) элементов , соответствующих элементу x.

Прообразом элемента y при соответствии Г называется множество Coim(y) элементов x, переводящихся соответствием в элемент y.

Множество прообразов создают область определения X (область отправления соответствия), а множество образов образуют область значений Y (область прибытия соответствия).

Для каждого соответствия существует обратное соответствие , которое любому y Y сопоставляет x X, причем ={(y,x) (x,y) }.

Частным случаем соответствия является однозначное отображение , которое каждому элементу х Х сопоставляет единственный элемент у Y . При отображении соответствие между х и у записывается в виде у = (x), a само отображение определяет запись : X Y, при этом Х называется областью определения отображения, Y – областью значений. Говорят, что отображает Х на Y.

Многозначное отображение возникает, если некоторым значениям х Х соответствует более чем один элемент.

Если Х – область определения, а Y – область значений отображения , то Если отображает Х на Y и Y Z , то говорят о композиции отображений.

Рассмотрим свойства отображений.

Отображение : X Y называется сюрьективным, или сюръекцией, если любой y Y есть образ по крайней мере одного х Х.