Лекция 2. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
БИНАРНЫЕ ОТНОШЕНИЯ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
1. Отношения.
2. Бинарные отношения. Основные определения.
3. Свойства бинарных отношений.
4. Эквивалентность и порядок.
Отношения
Отношения — один из способов задания взаимосвязей между элементами множества. Наиболее изученными и чаще всего используемыми являются так называемые унарные и бинарные отношения.
Унарные (одноместные) отношения отражают наличие какого-то определенного признака R (свойства и т.п.) у элементов множества М (например, быть белым на множестве шаров в урне). Тогда все такие элементы а из множества М, которые отличаются данным признаком R, образуют некоторое подмножество в М, называемое унарным отношением R, т.е. а Î R и R Í М.
Бинарные (двухместные) отношения используются для определения каких-то взаимосвязей, которыми характеризуются пары элементов в множестве М (так, на множестве людей могут быть заданы, например, следующие бинарные отношения: жить в одном городе, быть моложе, быть сыном, работать в одной организации и т.п.). Тогда все пары (а, b) элементов из М, между которыми имеет место данное отношение R, образуют подмножество пар из множества всех возможных пар элементов М´М= М2, называемое бинарным отношением R, т.е. (a, b) Î R, при этом R Í М ´ М.
|
|
|
В общем случае могут рассматриваться п -местные отношения, например отношения между тройками элементов — трехместные (тернарные) отношения и т.д.
Под п-местным отношением понимают подмножество R прямого произведения п множеств: R Í М1 ´ М2 ´… ´ Мп. Говорят, что элементы а1, а2, … aп (a1 Î М1, a2 Î М2, … an Î Мn) находятся в отношении R, если (а1, а2…, ап) Î R. Если n -местное отношение R задано на множестве М своих элементов, т.е. М1 = М2 =… = Мn, то R Í Мn.
Бинарные отношения. Основные определения.
Двухместным, или бинарным, отношением R называется подмножество пар (а, b) Î R прямого произведения М1 ´ М2, т.е. R Í М1 ´ М2. При этом множество М1 называют областью определения отношения R, множество М2 — областью значений. Часто рассматривают отношения R между парами элементов одного и того же множества М, тогда R Í М ´ М. Если a, b находятся в отношении R, это часто записывается как а R b.
Пусть R Í А ´ В определено в соответствии с изображением на рис.1. Область определения D(R) и область значении Q(R) определяются соответственно:
D(R) = {а: (а, b) Î R}, Q(R) = {b: (a, b) Î R}.
Рис.1
Способы задания бинарных отношений — любые способы задания множеств (так как отношения определены выше как подмножества некоторых множеств — прямых произведений). Отношения, определенные на конечных множествах, обычно задаются:
|
|
|
1. Списком (перечислением) пар, для которых это отношение выполняется.
