Введение

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

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

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

Глава 1 Элементы теории множеств

1. Множества и их спецификация

   1. Элементы и множества

Понятие множества относится к числу фундаментальных понятий математики.

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

1. Можно рассматривать множества объектов любой природы: множество городов России, множество студенческих групп на факультете ИВТ, множество букв русского языка, множество натуральных чисел…

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

• Множества обычно обозначают прописными буквами (А, В, С и т.д.), а их элементы – строчными (например: x, y, z).

Если элемент x принадлежит множеству А, то пишут x  A. Запись x  A означает, что элемент x не принадлежит множеству А.

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

• Обычно семейства множеств обозначают рукописными буквами латинского алфавита для отличия их от обычных множеств.

Множество, не содержащее элементов, называется пустым множеством и обозначается символом .

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

Мощность множества M обозначается как |M| и для конечного множества равняется числу элементов в нем.

• Заметим, что || = 0, но |{}| = 1.

Для числовых множеств здесь и далее будем использовать следующие обозначения: N – множество натуральных чисел, Z – множество целых чисел, R – множество действительных чисел, P – множество простых чисел, Q – множество рациональных чисел.

1. Задание множеств. Парадокс Рассела

2. Рассмотрим несколько множеств:

1. А = {2, 4, 6}; 2) B = {1, 3, 5}; 3) C = {A, B}; 4) D = {x R | x>0}; 5) E = {2·y | y=1, 2, …, n}; {мн-во четных чисел} 6) F = {x | x=1 или x=2·y, yF } {степени двойки: 1, 2, 2², 2³, 2⁴, …}

В первом и втором пунктах примера множества заданы путем перечисления их элементов. В третьем пункте – тоже, но здесь элементами множества C являются множества. Заметим, что множество C имеет только два элемента и, в частности, 1 C, хотя 1 A  и A C . Действительно: 1A и 1B,  1 C, т.к. только A и B являются элементами C.

В 4-м примере множество D задано путем его описания, т.е. задания неких свойств его элементов.

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

Задание множества путем указания его свойств может приводить к противоречиям. Например, один из наиболее типичных теоретико-множественных парадоксов носит название парадокса Рассела и состоит в следующем. Рассмотрим множество всех множеств, которые не содержат себя в качестве элемента: F = {X | XX}. Спрашивается, является ли само множество F элементом F? Возможны только два случая:

1) FF. Тогда для него выполняется условие содержания элемента в множестве, т.е. FF.

2) FF. Тогда для F не выполняется условие содержания элемента в множестве, т.е. F содержит само себя: FF.

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

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

1. Перечислением элементов множества (множества A, B, C) {1,2,3}.

Этот способ применим только для конечных множеств.

2. Указанием свойств элементов множества, или заданием т.н. характеристического предиката: D = {x | P(x)} (Другими словами – задание разрешающей процедуры).

Здесь P(x) обозначает некоторое условие, выраженное в форме логического утверждения; это условие может быть проверено для любого элемента.

3. Порождающей процедурой: E = {y | y:=f(x)}.

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

1. Контрольные вопросы

1. Что такое множество? Могут ли в составе множества быть одинаковые элементы?

2. Являются ли множествами следующие наборы: {a, b, c, d}? {Обь, Иртыш, Енисей, Лена}? {1, 2, 5, 1, 3, 2, 3}?

3. Что такое семейство (или класс) множеств? Что является элементом класса множеств?

4. Что такое пустое множество – ?

5. Что будет являться универсумом для следующих трех множеств: {1, 3, 5, 7}, {2, 4, 6}, {8, 9, 10}?

6. Что такое мощность множества? Чему равна ||? А |{}| ?

7. Какое множество обозначают через R? А через N?

8. Какие способы задания множеств Вы знаете?

9. Какой способ использован при задании множества A = {y  Z | y < 10}? Что здесь является характеристическим предикатом?

10. Что такое порождающая процедура?

11. Какие способы использованы при задании множеств A, B, C, D, если A = {1, 2, 3, 4}, B = {x  Z | x = 3 или x = 3·x}, C = {A, B}, D={x | x = 2·y | y = 1, 2, 3, 4, 5}?

2. Операции над множествами

   1. Сравнение множеств

Если каждый элемент множества А является элементом множества В, то пишут А  В (А является подмножеством множества В). Считается, что   А для любого множества А.

Подмножество C множества B называется его собственным подмножеством, если C  В, но C  В. Обычно для обозначения этого факта используется символ : C  В.

Два множества равны, если они состоят из одних и тех же элементов. Равенство множеств обозначается как А = В. Если множества не равны, то пишут А  В.

Множество А равно множеству В, если А  В и В  А.

Для числовых множеств выполняется N  Z  R.

3. Рассмотрим множества из примера 1.2: А = {2, 4, 6}; B = {1, 3, 5}; C = {A, B}. Очевидно, что А  C, но тем не менее А  C, поскольку ни один из элементов А не является элементом C (т.е. множество А является элементом множества C, но А не является подмножеством множества C.

Если |А| = |В|, то такие множества называются равномощными.

2. Операции над множествами. Диаграммы Венна

Обычно рассматриваются следующие операции над множествами:

Объединением (или суммой) множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В: A  B = {x | x  A или x  B}.

Пересечением (или произведением) множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат каждому из множеств А и В: A  B = {x | x  A и x  B}.

Если A  B = , то множества А и В называются непересекающимися.

Разностью множеств А и В называется множество A \ B , состоящее из тех и только тех элементов, которые принадлежат А, но не принадлежат В: A \ B = {x | x  A и x  B}.

Симметрической разностью множеств А и В называется множество A Δ B = (A  B) \ (A  B) = {x | (x  A и x  B) или (x  B и x  A)}.

Дополнением множества А называется множество всех элементов универсального множества, не входящих в A: A = U \ A = {x |  x  A}.

Операции объединения и пересечения допускают обобщение для большего количества множеств (в том числе и бесконечного). В общем случае для объединения k множеств используется обозначение , или для бесконечного числа множеств: = {x |  i  I | x  A_i}. Аналогично, для пересечения k множеств используется обозначение , или , если количество множеств бесконечно: = {x |  i  I |x  A_i }.

На рисунке 1.1 (справа) приведены т.н. диаграммы Эйлера-Венна, графически иллюстрирующие вышеописанные операции над множествами. Введенные операции показаны на диаграммах Венна темным цветом. Такие геометрические представления множеств часто используются при решении задач или доказательстве каких-либо утверждений.

4. Рассмотрим два множества чисел: А = {1, 2, 3, 4}; B = {1, 3, 5, 7}. Тогда операции над этими множествами будут иметь вид: объединение A  B = {1, 2, 3, 4, 5, 7}; пересечение A  B = {1, 3}; разность A \ B = {2, 4} и B \ A = {5, 7}; симметрическая разность A Δ B = {2, 4, 5, 7}. Для рассмотрения дополнения A необходимо знать универсальное множество, все элементы которого за исключением элементов A и будут являться дополнением.

3. Представление множеств в ЭВМ

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

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

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

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

Если универсум велик, а подмножества имеют сравнительно небольшую мощность, то использование характеристических функций невыгодно, т.к. в них будет много нулей. Для представления таких множеств обычно используют списки элементов. Элемент множества тогда может быть представлен записью с двумя полями: информационным и указателем на следующий элемент. Трудоемкость операций включения, пересечения и объединения определяется как O(mn), где m и n – мощности множеств; операции  – как O(n).

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

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

1. Проверка включения AB

Вход: Два упорядоченных множества A и B (массивы).

Выход: да или нет (1 или 0, true или false).

i:=1; j:=1; // указатели на начало множеств

пока i|A|+1 и j|B|+1 цикл

если A[i] < B[j] то вернуть 0 и выход // элемент A отсутствует в B

иначе если A[i] > B[j] то j:=j+1 // переход к след. элементу B

иначе // элементы совпали – перейти к следующим

i:=i+1; j:=j+1;

конец если

конец цикла

если i=|A|+1 то вернуть 1 иначе вернуть 0.

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

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

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

4. Разбиения и покрытия

Пусть Ě ={E_i} для i I – некоторое семейство непустых подмножеств множества M, E_i  M. Тогда семейство Ě называется покрытием множества M, если каждый элемент множества M принадлежит хотя бы одному из E_i: M    x M  i I |  x E_i.

Семейство Ě называется дизъюнктным, если элементы этого семейства попарно не пересекаются, т.е. каждый элемент множества M принадлежит не более чем одному из множеств E_i: i,j I, ij  E_i   E_j=. (илл. на д. Венна)

Дизъюнктное покрытие Ě называется разбиением множества M.

5. Пусть имеется множество M={1,2,3}. Тогда семейство {{1,2}, {2,3}, {3,1}} является покрытием, но не разбиением; семейство {{1},{2},{3}} – покрытием и разбиением, а семейство {{1},{2}} является дизъюнктным, но в то же время не является ни покрытием, ни разбиением.

Совокупность всех подмножеств множества M называется булеаном и обозначается P (M), или 2^M: 2^M = {A | A  M}.

6. Пусть имеется множество M = {1,2,3}. Тогда булеаном для него будет являться семейство {,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

5. Свойства операций над множествами

Пусть задан универсум U. Тогда A, B, C  U выполняются свойства:

1. Идемпотентность

   A  A = A

   A  A = A

2. Коммутативность

   A  B = B  A

   A  B = B  A

3. Ассоциативность

   A  (B  C) = (A  B)  C

   A  (B  C) = (A  B)  C

4. Дистрибутивность

   A  (B  C) = (A  B)  (A  C)

   A  (B  C) = (A  B)  (A  C)

5. Операции с пустым множеством (свойства нуля)

   A   = A

   A   = 

6. Операции с универсальным множеством (свойства единицы)

   A  U = U

   A  U = A

7. Свойства дополнения

   Инволютивность:

   A A = U A A=

8. Поглощение

   (A  B)  A = A

   (A  B)  A = A

9. Двойственность (законы де Моргана)

10. Выражение для разности

A \ B = A B

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

На основании свойств 1–10 можно получить новые свойства и равенства.

7. Разные способы определения симметрической разности. Доказать, что верно равенство (AB)\(AB)(A\B)(B\A). (A  B) \ (A  B)  ⁽¹⁰⁾ (A  B)  (AB)  ⁽⁹⁾ (A  B)  (A B)  ⁽⁴⁾  ((A  B) A)  ((A  B) B)  ⁽⁴⁾  ((A A)  (B A))  ((A B)  (B B))  ⁽⁷⁾  (  (BA))  ((AB)  ) = ⁽⁵⁾ (BA)  (A B) = ⁽¹⁰⁾ (B \ A)  (A \ B).

1. Контрольные вопросы

1. Что означает запись А  В? В чем отличие от записи А  В?

2. Пусть B = {1, 2, 3, 4}, A = {2, 4}. Какое из утверждений справедливо: А  В? B  A? А  В? B  A?

3. Справедливо ли равенство |A| = |B|, если A = {a, b, c}, B = {2, 3, 5}?

4. Чем отличается объединение множеств от их пересечения? Какое из них содержит больше элементов и почему?

5. Как определяется симметрическая разность множеств?

6. Пусть A = {1, 2, 3}, B = {2, 3, 4}. Определите результат следующих операций: 1) A  B; 2) A  B; 3) A \ B; 4) B \ A; 5) A Δ B ; 6) A  A; 7) A  A .

7. Какую трудоемкость имеет алгоритм типа слияния множеств? Опишите этот алгоритм для определения операции разности множеств.

8. Что такое разбиение множества и в чем его отличие от покрытия?

9. Что из приведенных множеств будет являться разбиением множества A = {1, 2, 3, 4}: {{1}, {3,4}, {1,2}}, {{2}, {1,3}, {4}}, {{1,2,3},{4}}?

10. Какое из приведенных множеств является булеаном множества A={a, b, c}: B = {{a}, {b,c}, {c}}, C = {, {a,b,c}, {b,c}, {a}, {b}, {c}, {a,b}, {a,c}}, D = {{a},{b},{c}}? Является ли что-то из перечисленного разбиением A?

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

Рассмотрение «жизненного», точнее, «программистского», примера. Пусть есть три множества: D – данных, P – программ и R – результатов. Для каждой программы возможны отношения: данные для этой программы, результаты работы этой программы, и т.п. Набору данных можно сопоставить множество программ, которые могут с этими данными работать, и множество результатов, которые могут быть получены после обработки этих данных, и т.п.

Перейдем к формализации понятия «отношения».

1. Прямое произведение множеств

Упорядоченная последовательность, содержащая n элементов некоторого множества, называется n-кой, или набором из n элементов. Обычно n-ка, образованная последовательностью a₁, a₂,…, a_n обозначается (a₁, a₂,…, a_n). При малых n говорят о двойках элементов, тройках и т.д.

• Согласно этому определению, один и тот же элемент может встречаться в n-ке несколько раз. Кроме того, поскольку n-ка является упорядоченной последовательностью, две n-ки, составленные из одних и тех же элементов, но в разном порядке, является различными.

8. Для множества чисел А = {1, 2, 3, 4} можно рассмотреть тройки: (1, 2, 2), (3, 4, 1), (2, 1, 2), причем первая и последняя тройки различны, несмотря на их одинаковый состав.

Прямым (или декартовым) произведением множеств А₁, А₂, …, А_n называется множество всех упорядоченных наборов (x₁ ,x₂, … x_n) таких, что x_i  A_i при  i = 1, 2, …, n. Декартово произведение обозначается А₁  А₂ … А_n. Если одним из сомножителей является пустое множество, то и произведение является пустым множеством.

Степенью множества A называется его прямое произведение само на себя n раз; обозначается Aⁿ.

9. Рассмотрим два множества: чисел Q = {1, 2, 3, 4, 5, 6, 7, 8} и букв: P = {a, b, c, d, e, f, g, h}. Тогда если рассмотреть произведение PQ, то оно будет иметь вид упорядоченных пар: (a,1), …, (a,8), (b,1), …, (b,8), …, (h,1), …, (h,8). Мощность такого произведения равна 88=64, а сами элементы – клетки шахматной доски.

10. Пусть имеются множества A={1,2}, B={2,3,4}. Тогда А  B = {(1,2), (1,3), (1,4), (2,2), (2,3), (2,4)}. Если рассмотреть A³ = {(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)}.

• Точка на плоскости может быть задана упорядоченной парой координат, т.е. двумя точками на координатных осях. Т.о., R² = RR. Метод координат был введен в употребление Рене Декартом, отсюда и название «декартово произведение».

2. Отношения

N-местным отношением R или N-местным предикатом R на множествах А₁, …, А_n называется любое подмножество прямого произведения А₁ … А_n: R  А₁ … А_n. Элементы a₁, a₂, …, a_n | a_i  A_i при  i = 1, 2, …, n связаны отношением R тогда и только тогда, когда упорядоченный набор (a₁ ,a₂, … a_n)  R.

При N = 1 отношение R является подмножеством множества А₁ и называется унарным отношением или свойством.

Наиболее часто встречается двухместное отношение (N = 2), которое называется бинарным отношением R из множества А в множество В, или соответствием: это подмножество произведения множеств А и В: R  А B.

Если элементы a и b множеств А и В (a,b)R, то говорят, что они находятся в отношении R, для чего часто используется т.н. инфиксная форма записи: aRb. Если R  А A (т.е. А=В), то R называется бинарным отношением на множестве А. Соответственно, отношение R  А ⁿ называется N-местным предикатом на множестве А.

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

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

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

3. Множества A и B показаны точками на параллельных линиях, а отношения между ними – стрелками, направленными от a к b.

11. Рассмотрим множества A={1,2,3,4,5,6}, B={1,2,3}. Определим на этих множествах отношение RAB: R = {(x,y) | x делится на y}. R можно представить графически так, как это показано на рисунке справа. Кроме того, можно задать это же отношение множеством упорядоченных пар: {(1,1), (2,1), (2,2), (3,1), (3,3),(4,1), (4,2), (5,1), (6,1), (6,2), (6,3)}, которые соответствуют тем же точкам на плоскости.

Определим несколько отношений, необходимых при рассмотрении множеств.

Пусть R есть отношение на множестве A: R  А A, a,b  A. Тогда:

Обратное отношение: R^–1 = {(b,a) | (a,b)  R}.

Дополнение отношения: R = {(a,b) | (a,b)R}.

Тождественное отношение, или диагональ: I_А = {(a,a) | a  A}.

Универсальное (или полное) отношение: U_A = {(a,b) | a  A и b  A}.

Свяжем с каждым бинарным отношением R между множествами A и B два множества – область определения _R и множество (или область) значений _R. Они определяются следующим образом:

_R = {xA| yB | (x,y)R },

_R = {yB| (x,y)R для некоторого xA}.

12. Пусть на множестве A = {1,2,3,4,5} задано отношение R: R = {(x,y) | остаток от деления y на x равен 1}. Тогда R = {(5,1),(4,1),(3,1),(2,1),(2,3),(3,4),(2,5),(4,5)}, _R = {2,3,4,5}, _R = {1,3,4,5}.

Образом множества X относительно предиката R называется множество R(X) = {y | (x,y)R для некоторого xX}

Пусть имеются множества A, B, C и отношения R₁  AB, R₂  BC. Определим отношение R  AC следующим образом: оно действует из A в B посредством R₁, а затем из B в C посредством R₂. Такое отношение называется составным (композицией), или произведением отношений и обозначается R = R₂◦R₁: R = {(x,y) |  z  B, для которого выполнено (x,z)  R₁, (z,y)  R₂}. Обратите внимание на последовательность записи множеств в их композиции!

13. Пусть A={1,2,3,4}, на множестве A определим два отношения: R₁ = {(x,y) | 2x  y} и R₂ = {(x,y) | x+3y кратно 2}. Найдем графические представления отношений R₁, R₂, R = R₂ ◦R₁ Найдем области определения и области значений для всех отношений. (R₁)={1,2}, (R₁)={2,3,4}, (R₂)={1,2,3,4}, (R₂)={1,2,3,4}, (R)={1,2}, (R)={1,2,3,4}.

Если записать эти же отношения в виде пар, то получим: R₁ = {(1,2), (1,3), (1,4), (2,4)} и R₂ = {(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)}. Тогда композиция отношений R: (1,2), (2,2)(1,2); (1,2), (2,4)(1,4) и т.п. R = R₁◦R₂ = {(1,2), (1,4), (1,1), (1,3), (1,2), (1,4), (2,2), (2,4)}. Устранив повторяющиеся элементы, получим: R = {(1,2), (1,4), (1,1), (1,3), (2,2), (2,4)}.

Пусть R – бинарное отношение на множестве A. Степенью отношения R на множестве A называется его композиция с самим собой. Rⁿ=R◦R◦…◦R.

3. Свойства отношений

Теорема 1.1: Для любых бинарных отношений P, Q, R выполняются следующие свойства:

1. (P^–1)^–1=P; 2. (P◦Q)^–1= Q^–1◦P^–1; 3. (P◦Q)◦R=P◦(Q◦R) (ассоциативность композиции).

Доказательство:

1. По определению обратного отношения условие (x,y)P равносильно условию (y,x)P^–1, что выполняется  когда (x,y)(P^–1) ^–1.

2. Пусть (x,y)(P◦Q)^–1, тогда (y,x)(P◦Q)   z | (y,z)Q и (z,x)P. Тогда (x,z)P^–1, (z,y)Q^–1  (x,y)Q^–1◦P^–1. Обратное включение аналогично.

3. Пусть (x,y)(P◦Q)◦R, тогда, по определению,  u, v | (x,u)R, (u,v)Q, (v,y) P. Это равносильно тому, что (x,u)R, (u,y)P◦Q.

В силу свойства ассоциативности обычно композицию отношений обозначают (P◦Q)◦R  PQR.

Бинарное отношение R на множестве А называется рефлексивным, если для любого его элемента a выполняется aRa: a   aRa.

Бинарное отношение R на множестве А называется антирефлексивным, если для любых его элементов a,b aRb  a  b.

Бинарное отношение R на множестве А называется симметричным, если из его выполнения для a, b следует выполнение для b, a:  a, b   aRb  bRa.

Бинарное отношение R на множестве А называется антисимметричным, если из его выполнения для a, b и b, a следует, что a и b совпадают.  a, b   aRb и bRa  a = b.

Бинарное отношение R на множестве А называется транзитивным, если из его выполнения для a,b и для b,c следует его выполнение для a,c:  a, b, c   aRb и bRc  aRc.

Бинарное отношение R на множестве А называется полным, или линейным, если для любых двух различных элементов множества A оно выполняется или для a, b, или для b, a:  a, b   | ab  aRb или bRa.

14. Рассмотрим отношение R на множестве натуральных чисел следующим образом: R = {(x,y) | x – делитель y}. Это отношение является рефлексивным, т.к. x/x =1 x  N Отношение R антисимметрично, т.к. если x/y  N и y/x  N , то x = y. Проверим транзитивность R. y/x  N и z/y  N  z/x = z/y  y/x  N  отношение транзитивно.

15. Определим отношение R на множестве натуральных чисел: (a+2b делится на 3). Это отношение является рефлексивным, т.к.  Отношение R симметрично. . Для того, чтобы проверить выполнение bRa, необходимо показать, что ,  bRa выполнено. Проверим, что R – транзитивно. ,  a+2b = 3n  a=3n–2b. .  b+2c = 3m  2c=3m–b. Для того, чтобы проверить выполнение aRc, необходимо показать, что . aRc выполнено. 

Теорема 1.2 (о проверке свойств отношения):

Отношение R на множестве A²: