Текст книги "Дискретная математика. Краткий курс. Учебное пособие"

1.30. Найти формулу для множества заштрихованного на диаграмме Венна (рис. 1.29).

Рис. 1.29

Как видно из диаграммы Венна, искомое множество образовано тремя областями, задающими три фундаментальных произведения. Левая область на диаграмме представляет собой ту часть множества А, которая не имеет пересечений ни с В, ни с С, т. е. представляет пересечение А с дополнениями В и С, А ∩ ВС ∩ СС. Правая часть состоит из двух непересекающихся областей: верхняя состоит из той части пересечения В ∩ С, которая не содержит А, т. е. АС ∩ В ∩ С, а нижняя состоит из той части множества С, которая не имеет пересечения ни с А, ни с В, т. е. АС ∩ ВС ∩ С. Таким образом, заштрихованное множество выражается формулой, представляющей объединение этих трех частей:

(А ∩ ВС ∩ СС) ∪ (АС ∩ В ∩ С) ∪ (АС ∩ ВС ∩ С).

Формулу можно упростить, если вынести из двух правых скобок АС ∩ С, что дает окончательное выражение для искомого множества:

(А ∩ ВС ∩ СС) ∪ (АС ∩ С)

1.31. В медицинском центре производится диагностика пациента для обнаружения у него одного из трех возможных заболеваний X, Y или Z. Каждое заболевание характеризуется следующими симптомами (которые обозначим номерами):

X = {1, 2, 3, 4), Y = {3, 4, 5}, Z = {4, 5, 6, 7}.

Обследование проведено на двух устройствах, от каждого из которых поступили следующие данные. Первое устройство определяет симптомы, которых нет в пересечении X ∩ Y, и тех, которые есть в пересечении Y ∩ Z, что дает выражение (X ∩ Y)C ∪ (Y ∩ Z).

Второе устройство выявляет симптомы, определяемые следующим выражением:

((X ∩ YC) ∪ (XС ∩ ZC))C ∪ (YC ∩ Z).

Необходимо определить заболевание, диагностируемое у данного пациента.

Решить задачу можно двумя способами: либо подставив все значения в формулу диагноза, либо выполнив алгебраические преобразования этой формулы. Для решения первым способом найдем все пересечения, используемые в формуле:

X ∩ Y = {3, 4}, (X ∩ Y)C = {1, 2, 5, 6, 7}, Y ∩ Z = {4, 5},

XC = {5, 6, 7}, YC = {1, 2, 6, 7}, ZC = {1, 2, 3},

X ∩ YC= {1, 2}, XС ∩ ZC = Ø, YC ∩ Z = {6, 7}.

Подставим значения в формулу диагноза

((X ∩ Y)C ∪ (Y ∩ Z)) ∩ (((X ∩ YC) ∪ (XС ∩ ZC))C ∪ (YC ∩Z)),

({1, 2, 5, 6, 7} ∪ {4, 5}) ∩ ({1, 2} ∪ Ø}C ∪ {6, 7}),

{1, 2, 4, 5, 6, 7} ∩ {3, 4, 5, 6, 7} = {4, 5, 6, 7} = Z.

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

Для решения вторым способом выполним эквивалентные преобразования формулы диагноза

1.32. Доказать что

А = А ∩ (ВС ∪ СС)

тогда и только тогда, когда А ∩ В ∩ С = Ø.

Докажем необходимость. Пусть х ∈ А. Тогда по определению пересечения х ∈ (ВС ∪ СС). Предположим противное, что х ∈ А, но х ∉ (ВС ∪ СС). Тогда х должен принадлежать дополнению (ВС ∪ СС), т. е. х ∈ (ВС ∪ СС)С = В ∩ С. При этом предположении х ∈ А и х ∈ В ∩ С, отсюда следует, что х ∈ А ∩ В ∩ С, но это невозможно, потому что по условию задачи А ∩ В ∩ С = Ø. Полученное противоречие и доказывает исходное равенство.

Докажем достаточность. Пусть теперь А ∩ В ∩ С = Ø. Множество А является объединение четырех фундаментальных произведений

А = (А ∩ ВС ∩ СС) ∪ (А ∩ ВС ∩ С) ∪ (А ∩ В ∩ СС) ∪ (А ∩ В ∩ С).

Последнее произведение пусто, поэтому

А = (А ∩ ВС ∩ СС) ∪ (А ∩ ВС ∩ С) ∪ (А ∩ В ∩ СС) =

Добавим произведение (А ∩ ВС ∩ СС), что не меняет выражения, вследствие закона идемпотентности

= (А ∩ ВС ∩ СС) ∪ (А ∩ ВС ∩ С) ∪ (А ∩ В ∩ СС) ∪ (А ∩ ВС ∩ СС) =

Из первых двух скобок вынесем А ∩ ВС, а из оставшихся А ∩ СС получим

= (А ∩ ВС) ∩ (С ∪ СС) ∪ (А ∩ СС) ∩ (ВС ∪ ВС) = (А ∩ ВС) ∪ ∪ (А ∩ СС) = А ∩ (ВС ∪ СС).

Определение минимальных форм

1.33. Дана формула

((А ∩ В)С ∪ (В ∩ С)) ∩ (((А ∩ ВС) ∪ (АС ∩ СС))С ∪ (ВС ∩ С)).

Найти ее минимальную форму.

Применим закон де Моргана

(АС ∪ ВС(В ∩ С)) ∩ (((АС ∪ В) ∩ (А ∪ С)) ∪)) =

Раскроем скобки

(АС ∪ (ВС ∪ В) ∩ (ВС ∪ С)) ∩ ((АС ∩ С) ∪ (А ∩ В) ∪

∪ (ВС ∩ С)) =

Здесь ВС ∪ В = U, а В ∩ С уберем по правилу соседства

(АС ∪ ВС ∪ С) ∩ ((АС ∩ С) ∪ (А ∩ В) ∪ (ВС ∩ С)) =

Раскроем скобки и, применив законы поглощения и идемпотентности, получим

= (АС ∩ С) ∩ (ВС ∩ С) ∪ (А ∩ В ∩ С) =

Из всех трех скобок вынесем С

С ∩ (АС ∪ ВС ∪ (А ∩ В)) = С ∩ (АС ∪ ВС ∪ А) = С ∩ U = С.

1.34. Дана формула

((А ∩ С) С ∪ (А ∩ ВС) ∪ ((А ∩ ВС ∩ СС)) С ∩ ((А ∪ С) С ∪ (В ∩ СС) С).

Найти ее минимальную форму.

Применим закон де Моргана:

Здесь, поскольку скобка с большим числом литералов (АС ∪ В ∪ С), включает в себя скобку с меньшим числом литералов (АС ∪ В), то поэтому, по закону поглощения, большая скобка вычеркивается из выражения

= (А ∩ С) ∩ (АС ∪ В) ∩ ((АС ∩ СС) ∪ ВС ∪ С) =

Раскроем скобки в левой части, используя закон дистрибутивности

= (А ∩ С ∩ АС) ∪ (А ∩ С ∩ В) ∩ ((АС ∩ СС) ∪ ВС ∪ С) =

= Ø ∪ (А ∩ С ∩ В) ∩ (((АС ∩ СС) ∪ С) ∪ ВС) =

Далее раскроем скобки в правой части выражения

= (А ∩ С ∩ В) ∩ ((АС ∪ C) ∩ (СС ∪ С) ∪ ВС) =

= (А ∩ С ∩ В) ∩ ((АС ∪ C) ∩ U ∪ ВС) =

= (А ∩ С ∩ В) ∩ ((АС ∪ C ∪ ВС) =

Снова раскроем скобки

= ((А ∩ С ∩ В) ∩ АС) ∪ ((А ∩ С ∩ В) ∩ С ∪) ((А ∩ С ∩ В) ∩ ∩ ВС) = = Ø ∪ (А ∩ С ∩ В) ∪ Ø = А ∩ В ∩ С.

1.35. Дана формула

((АС ∩ В ∩ СС) ∪ (А ∩ С))С ∩ ((А ∩ ВС) ∪ (В ∩ С)) С ∩ ∩ ((В ∩ С) С ∪ А).

Найти ее минимальную форму.

Применим закон де Моргана к трем скобкам исходного выражения

=

 ∩ (АС ∪ СС)) ∩ (АС ∪ В) ∩ (ВС ∪ СС) ∩ ∩ (ВС ∪ СС ∪ А) =

Здесь скобка (АС ∪ СС) вычеркнута по правилу соседства (имеются две скобки (АС ∪ В) и (ВС ∪ СС), которые содержат переменную В и ее дополнение ВС, а две другие переменные этих скобок АС и ВС как раз и образуют скобку, которую нужно вычеркнуть по правилу соседства). Скобка (ВС ∪ СС ∪ А) вычеркнута потому, что она поглощается скобкой (ВС ∪ СС). Всего остается три скобки

= (А ∪ ВС ∪ С) ∩ (АС ∪ В) ∩ (ВС ∪ СС) =

Раскроем первые две скобки (выражения, равные Ø, не пишем)

= ((А ∩ В) ∪ (АС ∩ ВС) ∪ (АС ∩ С) ∪

 ∩ (ВС ∪ СС) = ((А ∩ В) ∪(АС ∩ ВС) ∪ (АС ∩ С)) ∩ (ВС ∪ СС) =

Раскроем скобки еще раз (произведения, дающие Ø, также опускаем)

= (А ∩ В ∩ СС) ∪ (АС ∩ ВС) ∪ (АС ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ С) =

Две последние скобки поглощаются скобкой (АС ∩ ВС), поэтому окончательно получается следующая минимальная форма:

= (А ∩ В ∩ СС) ∪ (АС ∩ ВС).

Замечание

Поскольку в алгебре множеств используются две бинарные операции ∩, ∪ и одна унарная операция С, то можно не писать операцию ∩, подразумевая, что она всегда имеется неявно между каждой парой литералов, или между каждой закрывающейся и открывающейся скобками. Такая запись не приводит ни к каким противоречиям, однако она в определенной мере упрощает запись выражения. Например, запись А ∩ ВС будет выглядеть как АВС. Выражение А ∪ (В ∩ С) запишется как А ∪ ВС, при этом можно опустить и круглые скобки, поскольку приоритет операции ∩ сильнее приоритета ∪, и поэтому запись А ∪ ВС должна пониматься как А ∪ (ВС), а не как (А ∪ В)С.

1.36. Дана формула

(АВС ∪ ВССС) ((АСВ ∪ АС)С ∪ ВС)С ∪ АСВССС.

Найти ее минимальную форму.

Применим закон де Моргана

= (АВС ∪ ВССС) ((А ∪ ВС) (АС ∪ СС) ВССС ∪ АСВССС =

Раскроем скобки

= (АВС ∪ ВССС) (АСС ∪ АСВС ∪ ВССС ∪ ВС) ВССС ∪ АСВССС =

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

= ВССС ∪ АСВССС =

Здесь также можно применить закон поглощения и минимальная форма получена

= ВССС.

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

1.37. Пусть имеется формула, представленная в полной нормальной форме пересечения объединений (пример 1.8):

(А ∪ В ∪ С) (А ∪ ВС ∪ С) (А ∪ ВС ∪ СС).

Найти ее выражение в виде минимальной нормальной формы объединения пересечений и в виде минимальной нормальной формы пересечения объединений.

Вынесем из первых двух скобок выражение А ∪ С, получим

(А ∪ С) (В ∪ ВС) (А ∪ ВС ∪ СС) = (А ∪ С) U (А ∪ ВС ∪ СС) = = (А ∪ С)(А ∪ ВС ∪ СС) =

Раскроем скобки

= А ∪ АВС ∪ АСС ∪ АС ∪ ВСС =

Вычеркнув, в соответствии с законом поглощения все три произведения, которые включают в себя переменную А, получим минимальную нормальную форму объединения пересечений

А ∪ ВСС

Раскроем скобки в этом выражении и получим минимальную нормальную форму пересечения объединений

(А ∪ ВС) (А ∪ С).

1.38. Формула представлена в виде нормальной формы объединения пересечений:

АВС ∪ АВСС ∪ АСВСС

Найти ее выражение в виде минимальной нормальной формы пересечения объединений.

По закону поглощения второе произведение поглощается первым:

АВС ∪ АСВСС.

Далее вынесем за скобки общий литерал ВС

= ВС (А ∪ АСС) =

Для выражения в скобках применим закон дистрибутивности объединения относительно пересечения и удалив U (по закону тождества), получим минимальную нормальную форму пересечения объединений

= ВС (А ∪ АС) (А ∪ С) = ВСU (А ∪ С) = ВС (А ∪ С).

1.39. Дана формула

(АВ ∪ ВССС) (АВ ∪ (АСС)СВС).

Найти ее минимальную нормальную форму пересечения объединений.

Применим закон де Моргана

= (АВ ∪ ВССС) (АВ ∪ А ∪ СС ∪ ВС) =

Произведение АВ поглощается А

= (АВ ∪ ВССС) (А ∪ СС ∪ ВС) =

Раскроем скобки

Применяя законы поглощения и идемпотентности, получим

= АВ ∪ ВССС =

Раскроем скобки, применив закон объединения относительно пересечения

Скобка (А ∪ СС) удаляется по правилу соседства (в других скобках есть В и ВС), и получаем минимальную нормальную форму пересечения объединений

= (А ∪ ВС) (В ∪ СС).

Нахождение минимальных форм на графе

1.40. Пусть имеется полная нормальная форма объединения пересечений

АВС ∪ АВСС ∪ АСВСС ∪ АВССС.

Найти ее минимальную форму, используя граф.

Разобьем фундаментальные произведения на три группы: в первой будет одно произведение АВС (оно не имеет дополнений), во второй тоже одно АВСС (оно содержит одну переменную с дополнением) и в третьей два: АСВСС и АВССС (две переменные с дополнениями). Поставим в соответствие каждому фундаментальному произведению вершину графа и соединим ребрами те вершины, которые различаются в одной позиции. Например, можно соединить АВСС и АСВСС, потому что первая позиция фундаментального произведения АВСС – это литерал А, первая позиция второго произведения – это литерал АС. Эти литералы не совпадают. Однако литералы во второй позиции – (ВС) и в третьей (С) – совпадают, что и позволяет ввести ребро в графе. Полученный граф представлен на рис. 1.30.

Рис. 1.30

Минимальное покрытие вершин этого графа содержит три куба размерности 1 (три ребра), которые показаны на рис. 1.31.

Рис. 1.31

Покрытие определяет минимальную форму АС ∪ ВСС ∪ АВС.

1.41. Дана формула

АС (ВСС ∪ ВСС)С ∪ (СС ∪ АВС ∪ АСВ)С.

Найти ее минимальную форму, используя граф.

Применим закон де Моргана и, раскрыв скобки, преобразуем формулу к полной нормальной форме объединения пересечений:

АС (ВС ∪ С) (В ∪ СС) ∪ С (АС ∪ В) (А ∪ ВС) = АС (ВССС ∪ ВС) ∪ С (АСВС ∪ АВ) = АСВССС ∪ АСВС ∪ АСВСС ∪ АВС.

Все четыре фундаментальных произведения образуют четыре группы, и в каждой группе по одной вершине; соединив их, получим граф (рис. 1.32).

Рис. 1.32

Вершины этого графа покрываются двумя ребрами, что дает минимальную форму

ВС ∪ АСВС.

1.42. Дана формула

((АВС)С ∪ ВСС) (ВС ∪ АСС)С ∪ АВ.

Найти ее минимальную форму, используя граф.

Найдем все фундаментальные произведения:

((АВС)С ∪ ВСС) (ВС ∪ АСС)С ∪ АВ = (АС ∪ В ∪ ВСС) (ВС ∪ СС) (АС ∪ С) ∪ АВ = (АС ∪ В ∪ С) (АСВС ∪ ВСС ∪ АССС) ∪ АВ = АСВС ∪ АСВСС ∪ АССС ∪ АСВСС ∪ АСВСС ∪ ВСС ∪ АВ = АВС ∪ АВСС ∪ АВСС ∪ АСВСС ∪ АСВСС ∪ АСВССС.

По этим шести фундаментальным произведениям построим граф (рис. 1.33).

Рис. 1.33

Три ребра покрытия дают следующую минимальную форму:

АВ ∪ АССС ∪ ВСС.

Однако нетрудно видеть, что данный граф имеет и другое, отличное от данного, покрытие. Это покрытие дает вторую минимальную форму (рис. 1.34).

Рис. 1.34

Минимальная форма представляет собой объединение трех импликант покрытия

АС ∪ ВСС ∪ АСВС.

Обе эти формы задают одно и то же множество и являются эквивалентными

АВ ∪ АССС ∪ ВСС = АС ∪ ВСС ∪ АСВС.

1.43. Дана формула ВС ∪ АССС ∪ АСВС ∪ ВССС.

Найти:

(a) минимальную форму объединения пересечений,

(b) минимальную форму пересечения объединений.

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

(a) Применяя алгоритм 1.2, приведем выражение к полной нормальной форме и найдем все фундаментальные произведения

ВС ∪ АССС ∪ АСВС ∪ ВССС = ВС (А ∪ АС) ∪ АССС (В ∪ ВС) ∪ АСВС (С ∪ СС) ∪ ВССС (А ∪ ∪ АС) = АВС ∪ АСВС ∪ АСВСС ∪ АСВССС ∪ АСВСС ∪ АСВССС ∪ ∪ АВССС ∪ АСВССС = АВС ∪ АСВС ∪ ∪ АСВСС ∪ АСВСС ∪ АВССС ∪ АСВССС.

Разобьем произведения на четыре группы и построим граф. В первой группе одно произведение АВС, во второй тоже одно АСВС, в третьей три: АСВСС, АСВСС, АВССС (три, потому что три фундаментальных произведения имеют одну переменную без дополнения), и в четвертой все переменные с дополнениями АСВССС. Соединив вершины, соответствующие фундаментальным произведениям с различием в одном литерале, получим граф на рис. 1.35.

Рис. 1.35

Чтобы покрытие стало более наглядным, изобразим граф иначе (не нарушая при этом изоморфизм) (рис. 1.36).

Рис. 1.36

Для минимального покрытия вершин этого графа требуется два ребра (два куба размерности 1) и цикл длины 4 (куб размерности 2). Покрытие определяет три импликанта, которые и дают минимальную форму объединения пересечений:

АС ∪ ВС ∪ ВССС.

(b) Для определения минимальной формы пересечения объединений выпишем оставшиеся фундаментальные произведения, которые не вошли в полную нормальную форму объединения пересечений. Таких произведений два: АВСС и АВСС, и они определяют граф (рис. 1.37).

Рис. 1.37

Этот граф не имеет ребер, и поэтому его покрытие определяет формулу АВСС ∪ АВСС. Дополнение к этой формуле и определяет минимальную форму пересечения объединений

(АВСС ∪ АВСС)С = (АС ∪ ВС ∪ С) (АС ∪ В ∪ СС).

Глава 2
ОТНОШЕНИЯ

2.1. Введение

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

Имеется три вида отношений, которые играют важную роль в дискретной математике:

1) отношения эквивалентности;

2) отношения порядка;

3) функции.

Обычно отношения определяются в терминах упорядоченных пар (a, b). Именно пары являются элементами отношений, но и каждая такая пара (a, b), в свою очередь, сама состоит из элементов, где a является первым элементом пары, а b – вторым элементом. В частности,

(a, b) = (c, d)

тогда и только тогда, когда a = c и b = d. Поэтому (a, b) ≠ (b, a) при a ≠ b. Для множеств, которые рассматривались в главе 1, это было не так, поскольку список {a, b} и список {b, a} определяли одно и то же множество, т. е. {a, b} = {b, a} при любых a и b.

2.2. Декартово произведение множеств

Пусть имеется два произвольных множества А и В. Множество всех упорядоченных пар (a, b), где a ∈ A и b ∈ B называется произведением или декартовым произведением множеств А и В и обозначается А × В. По определению

А × B = {(a, b): a ∈ A и b ∈ B}.

Вместо А × А можно записать А2.

Пример 2.1. Поскольку R – это множество вещественных чисел, то R2= R × R является множеством упорядоченных пар вещественных чисел. Геометрическим представлением декартова произведения R2 являются точки плоскости, как на рис. 2.1.

Рис. 2.1

Каждая точка плоскости является упорядоченной парой (a, b) и наоборот. Иногда R2 называют декартовой плоскостью.

Рассмотрим пример с конечными множествами.

Пример 2.2. Пусть А = {1, 2} и B = {a, b, c, d}. Тогда

А × В = {(1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c), (2,d) },

В × А = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2), (d, 1), (d, 2) }.

Также можно найти произведение А на себя.

А × A = {(1, 1), (1, 2), (2, 1), (2, 2) }.

Декартово произведение не коммутативно, т. е. А × В ≠ В × А, и это следует из того что декартово произведение образуется из упорядоченных пар.

Если обозначить через n(A × B) количество элементов, то для любых конечных множеств А и В количество элементов n(A × B) = n(A) · n(B). Такое произведение получается потому, что с каждым из n(A) элементов множества А можно образовать n(B) пар (a, b) для A × B.

Можно распространить произведение множеств на любое число конечных множеств. Так, для множеств А1, А2, …, Аn множество всех упорядоченных наборов элементов (a1, a2, …, an), где a1 ∈ А1, a2 ∈ А2, …, an ∈ Аn,

называется декартовым произведением этих множеств (или прямым произведением) и обозначается

Вместо записи А1 × А2 × … × Аn можно записать An. Так, например, запись R × R × R = R3 используется для описания трехмерного пространства.

2.3. Отношения

Определение. Пусть имеются множества А и В. Бинарным отношениемR или просто отношениемR между двумя множествами А и В называется любое подмножество декартова произведения A × B, т. е. R ⊆ A × B.

Отношение R представляет собой множество упорядоченных пар, где каждый первый элемент пары входит в множество А, а второй в множество В. Для каждой пары a ∈ A и b ∈ B истинно точно одно из следующих утверждений:

1)(a, b) ∈ R, т. е. a находится в отношении R к b (иногда это пишут как aRb);

2)(a, b) ∉ R, т. е. не находится в отношении R к b (или можно записать a

b).

Если R является отношением на множестве А с самим собой, т. е. R является подмножеством А2= А × А, то говорят, что R является отношением на А. Областью определения отношения R называется множество всех первых элементов упорядоченных пар R, и областью значенийR называется множество вторых элементов пар R. Если отношение образовано более чем из двух множеств, то при n множествах его называют n-арным отношением. Сечением по элементу a ∈ A отношения R называется множество элементов b ∈ B, для которых (a, b) ∈ R. Множество всех сечений отношения R называется фактормножеством множества В по отношению R, и оно однозначно задает отношение R.

Пример 2.3. Пусть А = {1, 2, 3} и В = {1, 2, 3, 4, 5, 6}.

Пусть (a, b) ∈ R означает, что элемент b ∈ В является делителем элемента a ∈ А. Для того чтобы найти отношение R, выпишем сначала все пары декартова произведения A × B:

Выберем из них те пары, в которых второе число является делителем первого

R = {(1, 1), (2, 1), (2, 2), (3, 1), (3, 3)}.

Найдем для всех элементов множества А их сечения

1 2 3

{{1} {1, 2} {1, 3}} фактормножество множества В по отношению R.

Пример 2.4

(a) Пусть имеется отношение R, означающее «быть соседними» для любых двух стран, которые имеют общую границу. Поэтому

(Италия, Швейцария) ∈ R.

(Италия, Германия) ∉ R.

(Италия, Россия) ∉ R.

(Франция, Германия) ∈ R.

(b) Пусть имеются множества А = {лыжи, коньки, ласты}, В = {снег, лед, вода}. Определим отношение R между А и В как (a, b) ∈ R, если a используется на b, т. е.

R = {(лыжи, снег), (коньки, лед), (ласты, вода)}.

Можно прочитать «лыжи используются на снегу», или лыжи R снег, «коньки используются на льду», или коньки R лед и т. д.

(с) Множество, порождаемое включением ⊆, является отношением на любом семействе множеств.

(d) Для множества прямых на плоскости свойства параллельности и перпендикулярности являются отношениями. Для любой пары прямых на плоскости a и b всегда можно определить, параллельны они или нет либо перпендикулярны или нет.

(е) Пусть А произвольное множество. Тогда A × А и Ø будут подмножествами произведения A × А и, следовательно, отношениями на А. Они называются соответственно универсальное отношение и пустое отношение.

Обратное отношение

Пусть R любое отношении между множествами А и В. Тогда обратное отношение для R обозначается как R-1 и является отношением между В и А и состоит из пар отношения R, элементы которых меняются местами.

R-1 = {(b, a): (a, b) ∈ R}.

Пусть, например, A = {1, 2, 3}, B = {x, y, z}.

Тогда, если R = {(1, x), (2, x), (2, y), (3, y), (3, z)}, то обратное для него

R-1 = {(x, 1), (x, 2), (y, 2), (y, 3), (z, 3)}.

Для любого отношения R выполняется (R-1)-1 = R. Область определения R-1 равна области значений R, а область значений равна области определения R. Если R некоторое отношение на А, то его обратное также всегда будет отношением на А.