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

 

Рассмотренные операции над множествами позволяют из одних множеств получать другие множества. Эти операции обладают рядом свойств, знание которых зачастую существенно упрощает анализ новых полученных множеств.

Приведем основные свойства операций. Пусть заданы множества A, B и C некоторого универсального множества U. Тогда для этих множеств верны тождества:

 

1. = , = – коммутативность;

2. – ассоциативность;

3. – дистрибутивность;

4. ,

5.

6.

7. – идемпотентность;

8. – законы де Моргана;

9. – законы поглощения;

10.

11.

12.

13.

Доказательство каждого из приведенных тождеств основано на использовании свойства симметричности отношения включения. Напомним это свойство: А = В, если и .

Доказывая тождество, сначала выбирают любой элемент х, принадлежащий левой части этого тождества. Выполняя преобразования над множествами в соответствии с приведенными операциями, пытаются доказать, что этот элемент принадлежит множеству из правой части этого тождества. Если это удается доказать, то, поскольку выбран произвольный элемент, это будет верно для любого другого элемента. Поэтому делается вывод, что множество из левой части тождества содержится во множестве из правой части.

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

Докажем тождество 3. Пусть Тогда на основании операции дизъюнкции или а на основании операции конъюнкции и Отсюда ясно, что если то и Отсюда следует Таким образом,

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

Приведем доказательство тождества, содержащего операцию отрицания. Для этого выберем тождество 8 и докажем его.

Пусть Тогда (U – универсальное множество) и Следовательно и поэтому очевидно, что и откуда следует, что Таким образом,

Пусть теперь Отсюда следует и следовательно и а поэтому но тогда Таким образом, и тождество доказано.

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

 

 

Отношения на множествах

Многие объекты (предметы) окружающей нас действительности находятся в определенной взаимосвязи. В математике эту взаимосвязь выражают термином «отношение». В предложениях естественного языка отношения выражаются самыми различными словосочетаниями, но чаще всего они выступают в форме сказуемого (предиката). Так, например, отношение родства между людьми выражаются в форме: «Алексей – брат Татьяны», «Татьяна – сестра Алексея», «Наталья – мать Алексея и Татьяны».

Отношение «быть братом» (аналогично, как и «быть сестрой») будет полностью определено, если мы составим список всех пар людей таких, что один из них брат второго. Предположим, что Татьяна, Александр и Михаил – дети одних и тех же родителей. Тогда на этом множестве из трех людей отношение «быть братом» выполнено для следующих пар:

«Александр – брат Татьяны»;

«Александр – брат Михаила»;

«Михаил – брат Татьяны»;

«Михаил – брат Александра».

В первом и третьем предложениях объекты (точнее – субъекты) нельзя поменять местами. Это означает, что отношение «быть братом», в общем случае не симметрично. Оно всегда и нерефлексивно, т.е. отношение «Александр – брат Александра» не выполняется (не имеет смысла).

В этом примере отношения рассматривались между объектами одного и того же множества – детьми одних и тех же родителей.

Отношения можно устанавливать и между объектами разных множеств. Так, если М₁ – множество студентов некоторого вуза, а М₂ – множество преподавателей того же вуза, то можно установить отношение «х –студент y», где х – один из студентов (элемент множества М₁), а y – один из преподавателей (элемент множества М₂). Ясно, что для одного и того же студента х это отношение может выполняться при разных y. И, наоборот, один и тот же преподаватель y имеет разных студентов x.

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

В математике отношения выражаются сказуемыми: …меньше, чем…, …больше, чем…, …равно…, …конгруэнтно…, …делится на… и многими другими. Хороший пример трехместных (тернарных) отношений представляют алгебраические операции. Например, отношение «образовывать сумму» применимо для троек чисел и выполняется в том случае, когда Пропорциональность чисел

есть отношение, выполненное для четверок чисел .

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

Важным понятием при формальном рассмотрении отношений является понятие упорядоченной пары. Упорядоченные множества часто называют кортежами, а упорядоченная пара – это кортеж, состоящий из двух элементов. В обычных множествах порядок расположения элементов значения не имеет, а в кортежах – имеет. Элементы кортежа заключают в уголковые скобки. Так кортеж, состоящий из элементов х и y, будет записан так – Причем

Пусть даны множества A и B. Рассмотрим множество всех упорядоченных пар элементов (кортежей) вида , где , Множество таких пар принято обозначать и называют декартовым произведением. Это множество образовано всеми упорядоченными парами, первые элементы которых принадлежат множеству А, а вторые – множеству B. Если то Если же то

Например, для множеств А = {1, 2} и B = {3, 4, 5} декартово произведение

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

Отношением Ф на множестве М называют подмножество множества Содержательный смысл такого определения состоит в том, что выбор подмножества Ф во множестве определяет, какие упорядоченные пары находятся в отношении Ф. При этом используют следующие обозначения. Если упорядоченная пара входит в Ф, т.е. то пишут что читается: «х находится в отношении Ф с у».

Следует отметить, что отношение – это не любое множество соответствующих пар, а подмножество множества пар при фиксированном М. Говоря формально, отношением называется упорядоченная пара где Таким образом, отношение – это пара где М – множество, на котором определено отношение (область определения отношения), а Ф – множество пар, для которых это отношение выполняется (область значений отношения). Множество М называют также областью задания отношения Ф, а множество пар Ф называется графиком отношения Как видим, определение графика в теории множеств есть именно то, к чему мы давно привыкли.

Приведенные выше записи отношений и требуют комментария. Привычные нам обозначения знаков математических отношений, такие как <, ≤, >, ≥ и др., исходят не от обозначения , а от в котором Ф заменено на соответствующий знак =, <, ≤ или ≥, ≠. В связи с этим могут возникнуть определенные недоразумения: с одной стороны Ф – это множество, но в записи отношения в конкретном случае символ Ф мы заменяем на соответствующий математический знак отношения =, <, ≤ и т.д., которые не представляют множество. Поэтому нужно иметь ввиду, что отношение , в котором Ф заменено на соответствующий математический знак, должно выполняться на всем множестве Ф.

Рассмотрим примеры. Пусть А = В = {0, 1, 2, 3, 4}. Декартово произведение этих множеств можно представить в виде квадратной матрицы, каждый элемент которой будет состоять из двух цифр. Первая цифра берется из множества А, вторая – из множества В.

. (1)

Исходя из (1), отношение равенства для элементов (цифр) множеств А и В будет определяться диагональной матрицей, являющейся частью . Каждый элемент диагональной матрицы будет содержать две одинаковые цифры. Обозначим ее символом е (от e quality – равенство)

е = . (2)

Отношение порядка а ≤ в будет представлять треугольную матрицу (обозначим ее о, order – порядок), также являющуюся частью

о = (3)

Отношение строгого порядка а < в представляет треугольную матрицу (обозначим ее символом s), являющуюся частью , имеет вид

s = (4)

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

Рассматривая в начале данного подраздела вербально выраженные отношения родства, например «Александр – брат Татьяны», мы отметили, что оно не симметрично, т.е. нельзя поменять местами Александра и Татьяну. В то же время отношение «Михаил – брат Александра» – симметрично. Это наталкивает на мысль, что для каждого отношения может существовать или не существовать обратное отношение.

Формально обратным отношением для Ф называется отношение Ф ^-1, записываемое в виде

ǀ .

Иначе говоря, обратное отношение Ф ^-1 образовано всеми теми упорядоченными парами (кортежами) , для которых существует кортеж выполнимый на множестве Ф. Так, например, обратным отношением е^{- 1} для отношения равенства е, определяемого матрицей (2) с областью определения (1), является оно само, т.е. е^{- 1} = е.

Обратным отношением порядка о^-1 для отношения о (т.е. а ≤ в), заданного матрицей (3), является отношение вида в ≤ а

 

о^-1 = .

Обратным отношением строгого порядка s^-1 для отношения s (т.е.вида а < в), заданного матрицей (4), является отношение вида в < а

 

s^-1 = .

 

Операции над отношениями

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

Объединением отношений и на множестве А называется отношение

Например, для отношений и , где A = {1, 2, 3} их объединением будет отношение

= .

Пересечением отношений и на множестве А называется отношение

Пересечением отношений из предыдущего примера будет отношение

Разностью отношений и на множестве А является отношение

Разность отношений и из предыдущего примера будет иметь вид

Инверсией отношения называется новое отношение , в котором элементы множества значений (графика) Ф^{- 1} являются инверсиями элементов графика Ф.

Например, для отношения инверсией будет отношение

Операция композиции может рассматриваться в тех случаях, когда заданы три множества А, В, и С. Тогда композицией отношений и называется новое отношение в котором каждый элемент (кортеж) графика получается по правилу

(5)

Здесь для обозначения операции композиции используется символ «» (кружок), а для всех кортежей, входящих в правило (5), должны выполняться условия: и .

В частных случаях возможно , тогда должно выполняться условие

Рассмотрим пример выполнения операции композиции для отношения строгого порядка, определяемого треугольно матрицей (4). Для удобства выполнения операции композиции все элементы отношения строгого порядка, задаваемые матрицей (4), запишем в одну строку

Тогда, пользуясь правилом (5), получим

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

Рассмотрим другой пример построения композиции отношения, но не с самим собой. Пусть Тогда

Рассматриваемые до сих пор операции над отношениями выполнялись на одной и той же области определения. Но возможны случаи отношений с разными областями определения. Для таких случаев вводится операция, меняющая область определения. Она называется операцией сужения отношения и формулируется следующим образом. Пусть задано отношение на множестве А, и имеется другое множество Тогда операция сужения отношения на множество В определяет новое отношение

Например, пусть = и Тогда

 

Основные свойства отношений

Таких свойства три: рефлексивность, симметричность и транзитивность.

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

Отношение называется симметричным, если для любых выполняются отношения и .

Отношение называется транзитивным, если для любых из и следует

Хорошими пояснениями приведенных свойств отношений являются следующие вербальные типы отношений. Так содержательный смысл рефлексивности поясняет отношение знакомства: каждый знаком с самим собой. Содержание симметричности поясняет отношение родства: если а родственник в, то и в родственник а. Содержательный смысл транзитивности поясняет отношение связи: если город а связан железной дорогой с городом в, который связан железной дорогой с городом с, то город а связан железной дорогой с городом с.

Кроме основных свойств отношений имеют место и некоторые другие, например, с добавкой частицы «анти». Среди них следует выделить свойство антисимметричности.

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

В качестве иллюстрации этого свойства рассмотрим такой пример. Пусть отношение Ф задано на множестве R действительных чисел, и Ф есть отношение «≤». Тогда отношение Ф рефлексивно, так как для любых Это отношение не симметрично, так как, например 2 ≤ 3, но 3 ≤ 2 не верно. Отношение транзитивно, так как очевидно, что если х ≤ у, у ≤ z, то x ≤ z. Отношение антисимметрично, так как х ≤ у и у ≤ х только при х = у.