Файл: Учебника по курсу Основы дискретной математики и логики.pdf

представлять кортежем, а список всех таких записей и есть описание данного отношения. Каждый кортеж, в свою очередь, – это элемент декартова произведения тех множеств, откуда берутся элементы кортежа. Тем самым мы приходим к следующему определению.
Таким образом, отношения бывают двуместные, или бинарные, трехместные, четырехместные и т. д. Отношение «меньше» на множестве чисел бинарное. Отношение «точка лежит внутри треугольника» тоже бинарное на совокупности из двух множеств – множества точек и множества треугольников. Отношение «лежать между» на множестве точек трехместное, отношение «четыре точки лежат на одной окружности» на множестве точек плоскости четырехместное.
Слайд 25
Остановимся более подробно на отношении, заданном на двух множествах, т. е. бинарном отношении. Бинарные отношения занимают особое место среди всех отношений, поскольку многие из наиболее важных отношений бинарные.
Бинарным отношением между множествами A[а] и B[бэ] называется любое подмножество φ[фи] декартова произведения этих множеств. Если упорядоченная пара (x, y)[икс, игрек] принадлежит бинарному отношению
φ[фи], то говорят, что x[икс] находится в отношении φ[фи] с y[игрек].
Обозначения, используемые в этом случае, приведены в формуле (1.58). Если множества A[а] и B[бэ] совпадают, то говорят, что отношение φ[фи] задано на множестве A[а]. Формула (1.59) задает конкретные множества A[а] и B[бэ], а формула (1.60) – пример бинарного отношения между ними.
Понятие отношения как подмножества декартова произведения формализовано в теории множеств и получило широкое распространение в языке математики во всех ее ветвях. Теоретико-множественный взгляд на отношение характеризует его с точки зрения объема – какими комбинациями элементов оно наполнено. Содержательный подход рассматривается в

математической логике, где отношение – пропозициональная функция, то есть выражение с неопределенными переменными, подстановка конкретных значений для которых делает его истинным или ложным. Важную роль отношения играют в универсальной алгебре, где базовый объект изучения раздела – множество с произвольным набором операций и отношений. Одно из самых ярких применений техники математических отношений в приложениях – реляционные системы управления базами данных, методологически основанные на формальной алгебре отношений.
Поскольку отношение – это по определению некоторое множество, то его можно задавать так же, как задают множества – списком или указанием характеристического свойства. Ясно, что первый способ целесообразен, когда множества, на которых рассматривается отношение, конечны. Если же среди множеств имеются бесконечные, то отношение задается с помощью характеристического свойства.
Если f[эф] отображение из X[икс] в Y[игрек], то бинарным отношением между множествами X[икс] и Y[игрек] является график этого отображения, определяемый формулой (1.61).
Слайд 26
Примером бинарного отношения на множестве действительных чисел
R[эр] является отношение порядка
[меньше или равно]. Оно состоит из всех упорядоченных пар действительных чисел (x, y) [икс, игрек], для которых х[икс] не превосходит y[игрек]. Это отношение можно рассматривать и на других числовых множествах, например, на множестве целых чисел Z[зет], на множестве натуральных чисел N[эн]. Другим примером бинарного отношения на множестве натуральных чисел N[эн] является отношение делимости, состоящее из всех упорядоченных пар натуральных чисел (x, y)[икс, игрек], для которых х[икс] без остатка делится на y[игрек].

Примером бинарного отношения на множестве A[а] букв русского алфавита является отношение, задаваемое формулой (1.62). Исходя из данной формулы, мы видим, что в данном отношении φ[фи] состоят пары гласных или согласных букв.
Теперь рассмотрим, какими свойствами обладают отношения.
Бинарное отношение φ[фи] на множестве A[а] называется рефлексивным, если каждый элемент х[икс] множества A[а] находится в отношении φ[фи] с самим собой.
Примером рефлексивного отношения является отношение порядка
[меньше или равно] на множестве действительных чисел.
Бинарное отношение φ[фи] на множестве A[а] называется антирефлексивным, если каждый элемент х[икс] множества A[а] не находится в отношении φ[фи] с самим собой.
Стоит отметить, что свойство антирефлексивности не является противоположным свойству рефлексивности. Отношение может не обладать ни свойством рефлексивности, ни свойством антирефлексивности.
Примером антирефлексивного отношения может служить отношение строгого порядка <[меньше] на множестве действительных чисел. Это отношение состоит из всех упорядоченных пар действительных чисел (х,
y)[икс, игрек], для которых х[икс] строго меньше y[игрек].
Определения рефлексивного и антирефлексивного отношений с помощью математических символов представлены формулами (1.63), (1.64).
Слайд 27
Бинарное отношение φ[фи] на множестве A[а] называется симметричным, если для любых элементов х, y[икс, игрек] множества A[а] из того что х[икс] находится в отношении φ[фи] с y[игрек] следует, что y[игрек] находится в отношении φ[фи] с х[икс].

Примером симметричного отношения является отношение равенства на множестве целых чисел, состоящее из всех пар целых чисел вида (x, x)[икс, икс].
Бинарное отношение φ[фи] на множестве A[а] называется антисимметричным, если для любых различных элементов х, y[икс, игрек] множества A[а] из того что х[икс] находится в отношении φ[фи] с y[игрек] следует, что y[игрек] не находится в отношении φ[фи] с х[икс].
Примером антисимметричного отношения может служить отношение <
[меньше] на множестве действительных чисел.
Определения симметричного и антисимметричного отношений с помощью математических символов представлены формулами (1.65), (1.66).
Аналогично свойству рефлексивности свойства симметричности и антисимметричности не являются противоположными друг другу. Если отношение не является симметричным, то это не означает, что оно обладает свойством антисимметричности.
Слайд 28
Бинарное отношение φ[фи] называется транзитивным, если для любых
x, y, z[икс, игрек и зет] из того, что x[икс] находится в отношении с y[игрек ], а y[игрек] находится в отношении с z[зет] следует, что x[икс] находится в отношении с z[зет]. Определение данного свойства с помощью математических символов представлено формулой (1.67).
Примером транзитивного отношения является отношение < [меньше] на множестве действительных чисел.
Бинарное отношение φ[фи] на множестве A[а] называется связным, если для любых элементов x, y[икс, игрек] множества A[а] либо х[икс] находится в отношении φ[фи] с y[игрек], либо y[игрек] находится в отношении φ[фи] с х[икс]. Формула (1.68) определяет свойство связности с помощью математических символов.

Примером связного отношения может служить отношение [меньше или равно] на множестве действительных чисел. Помимо уже отмеченных свойств рефлексивности и связности, данное отношение обладает свойствами антисимметричности и транзитивности.
Рассмотренное ранее отношение делимости на множестве натуральных чисел обладает свойствами рефлексивности, антисимметричности и транзитивности.
Слайд 29
Говорят, что бинарное отношение φ[фи] на множестве A[а] является отношением эквивалентности, если оно одновременно рефлексивно, симметрично и транзитивно. Для отношения эквивалентности φ[фи] используют запись, приведенную в формуле (1.69).
Примером отношения эквивалентности является отношение равенства на множестве целых чисел. Это же отношение можно рассматривать на множествах действительных, натуральных, рациональных чисел. Другим примером отношения эквивалентности служит отношение подобия на множестве всех треугольников плоскости. Данное отношение определяет формула (1.70).
Если на множестве A[а] задано отношение эквивалентности, то множество A[а] разбивается на непересекающиеся подмножества эквивалентных друг другу элементов. Эти подмножества называются классами эквивалентности. Примером такого разбиения является разбиение множества всех четырехугольников плоскости на подмножества равновеликих четырехугольников.
Слайд 30
Отношение на множестве M[эм] называется отношением порядка, если оно рефлексивно, транзитивно и антисимметрично.

Вот несколько примеров отношений порядка: на множестве прямоугольников: содержаться; на множестве действительных чисел: меньше или равно; на множестве сотрудников одного учреждения: быть начальником.
Исторически сложилось так, что отношение порядка в литературе обычно называют отношением частичного порядка. Мы для краткости слово
«частичного» будем опускать.
Множество целых чисел упорядочено отношением «меньше или равно», множество подмножеств произвольного множества упорядочено отношением
«быть подмножеством». Даже знаки для этих отношений похожи. Удобно и для произвольного отношения порядка иметь какой-то похожий значок.
Обозначение отношения порядка приведено на слайде.
В упорядоченном множестве нередко интересуются, так сказать, крайними элементами, т. е. такими, для которых уже нет меньших элементов или, наоборот, больших.
Рассмотрим примеры.

Эти примеры показывают, что упорядоченное множество может не иметь минимальных элементов, может иметь один минимальный элемент, а может иметь несколько, и даже бесконечно много, минимальных элементов.
Слайд 31
Рассмотрим примеры отношения и определим, какими свойствами они обладают. Первый пример – это отношение, заданное на множестве прямых в пространстве. Две прямые находятся в отношении φ[фи], если они имеют хотя бы одну общую точку.
Любая прямая имеет с собой множество общих точек, следовательно, отношение рефлексивно.
Если прямая x[икс] имеет общую точку с прямой y[игрек], то, конечно же, прямая y[игрек] имеет общую точку с прямой x[икс], т. е. отношение симметрично.
Проверим, обладает ли данное отношение свойством транзитивности.
На рисунке представлена ситуация, когда x[икс] находится в отношении
φ[фи] с y[игрек], y[игрек] находится в отношении φ[фи] с z[зет], но x[икс] не находится в отношении φ[фи] с z[зет]. Следовательно, свойство транзитивности не выполняется.
Так как существуют прямые, которые не пересекаются, т. е. есть элементы, не находящиеся в данном отношении друг с другом, то отношение не является связным.
Слайд 32
Рассмотрим еще один пример отношения, заданного на множестве действительных чисел. Два числа находятся в отношении φ[фи] друг с другом, если они удовлетворяют уравнению в правой части формулы (1.71), т. е. сумма их квадратов равна единице. Поскольку указанное уравнение имеет в точности два решения, данное отношение не является ни рефлексивным, ни антирефлексивным.

Уравнение является симметричным относительно переменных х[икс] и
у [игрек], а следовательно, отношение φ[фи] будет симметричным.
Рассматриваемое отношение не обладает свойством транзитивности. Это подтверждает пример таких значений x[икс], y[игрек], z
, что x[икс] находится в отношении φ[фи] с y[игрек], y[игрек] находится в отношении
φ[фи] с z[зет], но при этом x[икс] не находится в отношении φ[фи] с z[зет].
Такими значения являются х[икс], равное нулю, y[игрек], равное единице, и
z[зет],. равное нулю.
Отношение φ[фи] не является связным, так как существуют такие пары значений х[икс] и y[игрек], которые не удовлетворяют требуемому уравнению. Например, пара (1;1)[один один].
Слайд 33
Поскольку отношения – это подмножества декартова произведения, для них определены теоретико-множественные операции объединения и пересечения. Они называются соответственно операциями объединения и пересечения отношений. Можно также рассматривать операцию дополнения заданного отношения до универсального отношения. Обозначения этих операций такие же, как для операций над множествами.
Отношение, совпадающее с декартовым произведением двух множеств, на которых задано данное отношение, называется универсальным.
Рассмотрим пример, приведенный на слайде. Так как объединение двух множеств состоит из всех элементов, принадлежащих хотя бы одному из множеств, то в объединение данных отношений входят все пары прямых, которые параллельны или пересекаются. Параллельные или пересекающиеся прямые в пространстве определяют плоскость, поэтому свойством, задающим объединение данных отношений, является принадлежность прямых одной плоскости.
Теперь определим свойство, описывающее отношение, равное пересечению дополнений данных отношений. В дополнение первого

отношения входят пары прямых, которые не являются параллельными, т. е. пары пересекающихся или скрещивающихся прямых. В дополнение второго отношения входят пары прямых, которые не являются пересекающимися, т. е. пары параллельных или скрещивающихся прямых. Тогда в пересечение дополнений входят пары скрещивающихся прямых.
Слайд 34
Отношение, обратное данному, определяется аналогично обратному соответствию. Математическая запись определения обратного отношения приведена в формуле (1.72). В обратное отношение входят те пары переменных y[игрек], х[икс], для которых пара х[икс], y[игрек] принадлежит отношению φ[фи].
Операция обращения отношения сохраняет свойства отношения, т. е. обратное отношение обладает теми же свойствами, что и отношение φ[фи].
Например, если отношение рефлексивно, то оно содержит все пары вида (х,
х)[икс икс], и обратное отношение также будет содержать все пары такого вида.
Аналогично операция пересечения нескольких отношений, имеющих общее свойство, сохраняет это свойство.
Для объединения отношений ситуация иная. При объединении отношений, обладающих общим свойством, может получиться отношение, не имеющее этого свойства. Рассмотрим, например, антисимметричные отношения. Они не содержат одновременно пары вида х[икс], y[игрек] и
y[игрек], x[икс]. При объединении двух отношений может оказаться, что первое отношение содержит пару х[икс], y[игрек], а второе – пару y[игрек],
x[икс], тогда объединение данных отношений не будет обладать свойством антисимметричности.