Материал: 5540

Способы задания бинарных отношений – любые способы задания множеств (так как отношения определены как подмножества некоторых множеств – прямых произведений). Отношения, определённые на конечных множествах, обычно задаются:

…, an}, соответствует квадратная матрица порядка n, в которой элемент сij, стоящий на пересечении i-й строки и j-го столбца, равен 1, если между ai и aj имеет место отношение R, или 0, если оно отсутствует:

Пример 1.5. Пусть М = {1, 2, 3, 4, 5, 6}. Задайте в явном виде (списком) и матрицей отношение R M M , если R означает «быть строго меньше».

Решение. Отношение R как множество содержит все пары элементов a, b из М такие, что a < b:

R (a, b) a, b M , a b .

Тогда

R = { (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)}.

Матрица отношения:

16

а) R1 – «Быть делителем»;

б) R2 – «Иметь общий делитель, отличный от единицы»;

в) R3 – «Иметь один и тот же остаток от деления на 3».

Пример 1.6. Для отношения R, заданного в примере 1.3, установите область определения и область значений.

Решение. Область определения D(R) = {1, 2, 3, 4, 5}, область

aRа (например, отношение «Быть сыном» – антирефлексивно);

3)R – симметрично, если aRb влечёт bRa (например, отношение «Работать на одной фирме» – симметрично);

4)R – антисимметрично, если aRb и bRa влекут a = b, т.е. ни для каких различающихся элементов a и b (a ≠ b) не выполняется одновременно aRb и bRa (например, отношения «Быть сыном», «Быть начальником» – антисимметричны);

5)R – транзитивно, если aRb и bRс влекут aRс (например, отношения «Быть моложе», «Быть братом» – транзитивны).

Пример 1.7. Каковы свойства отношений, заданных:

1)на множестве натуральных чисел N для R1 – «Быть не больше ≤»;

2)на множестве людей для R2 – «Быть сыном»;

3)на множестве элементов структуры (рисунок 1.7) для R3 – «Быть непосредственно связанным с».

Решение

1)На множестве N, R1 = {(a, b) | a ≤ b}:

–рефлексивно, неантирефлексивно, так как выполняется a ≤ a для всех a M , например, 2 ≤ 2;

–несимметрично, так как 2 ≤ 3, но неверно, что 3 ≤ 2;

–антисимметрично, поскольку если a ≤ b, а b ≤ a, то a = b;

17

–транзитивно, так как если a ≤ b, а b ≤ с, то а ≤ с, например, 2 ≤ 3, 3 ≤ 4 и 2 ≤ 4;

2) R2 = {(a, b) | a – сын b} на множестве людей:

–нерефлексивно, антирефлексивно, так как ни для каких а не выполняется: а – сын а;

–несимметрично, антисимметрично, поскольку ни для каких a ≠ b не выполняется: а – сын b и b – сын a;

–нетранзитивно, так как если: а – сын b и b – сын с, то а – не сын с; 3) R3 = {(a, b) | a – непосредственно связан с b} на множестве

элементов структуры

a

bc

Рисунок 1.7 – Множество элементов структуры

–нерефлексивно, антирефлексивно, если в конкретной интерпретации aR3а не имеет смысла;

–симметрично, неантисимметрично, поскольку для всех a ≠ b, если выполняется aR3b, то bR3a;

–нетранзитивно, так как при aR3b и bR3с не выполняется aR3с (a и с связаны, но опосредованно).

Задача 1.12. Какими свойствами характеризуются следующие отношения на М = {1, 2, 3, ..., 9}:

а) R1 = {(a, b) | (a – b) – чётное}; б) R2 = {(a, b) | (a + b) – чётное};

в) R3 = {(a, b) | (a + 1) – делитель (a + b)}.

18

1.3 Эквивалентность и порядок. Операции над бинарными отношениями

Отношением эквивалентности (или просто эквивалентностью)

называют бинарное отношение на множестве, если оно рефлексивно, симметрично, транзитивно. Например, отношение «Жить в одном городе» на множестве людей – эквивалентность.

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

Отношением нестрогого порядка (или нестрогим порядком)

называют бинарное отношение на множестве, если оно рефлексивно, антисимметрично, транзитивно, и отношением строгого порядка (строгим порядком), если оно антирефлексивно, антисимметрично, транзитивно. Оба эти отношения называют отношением порядка. Например, отношение «Быть не старше» на множестве людей, «Быть не больше» на множестве натуральных чисел – нестрогий порядок; отношения «Быть моложе», «Быть прямым потомком» на множестве людей – строгий порядок.

Элементы a, b M сравнимы по отношению порядка R на М, если выполняется aRb или bRa.

Множество М, на котором задано отношение порядка, может быть:

а) полностью упорядоченным множеством, если любые два элемента из М сравнимы по отношению порядка. В таком случае говорят, что отношение R задаёт полный порядок на множестве М. Например, отношение «Быть не старше» задаёт полный порядок на множестве людей;

19

б) частично упорядоченным множеством – в противном случае. При этом говорят, что отношение R задаёт на множестве М частичный порядок. Например, отношение «Быть начальником» задаёт на множестве сотрудников организации частичный порядок, так как, например, для пары сотрудников одного отдела данное отношение не выполняется: они несравнимы по данному отношению.

Пример 1.8. К каким типам отношений относятся:

1) отношение равносильности на множестве формул, описывающих элементарные функции (формулы равносильны, если они задают одну и ту же функцию, например, (a + b) ∙ (a – b) = а2 – b2);

2) отношение ≤ и < на множестве векторов длины n с компонентами из N, определяемые следующим образом:

а) (а1, ..., аn) ≤ (b1, …, bn), если a ≤ b1, …, an ≤ bn;

б) (а1, ..., аn) < (b1, …, bn), если (a1, …, an) ≤ (b1, …, bn ) и хотя бы в одной координате i выполняется аi < bi.

Решение. Отношения, заданные в п. 1, являются отношениями эквивалентности на соответствующих множествах; отношения, заданные в п. 2, являются отношениями порядка; при этом отношение ≤, определённое в п. 2, есть отношение нестрогого порядка, а отношение < в п. 2 – отношения строгого порядка.

Пример 1.9. Каков индекс разбиения и мощность классов эквивалентности по отношению Ri, если R:

1)отношение равенства (тождества) на любом множестве;

2)отношение «Иметь один и тот же остаток от деления на 5» на множестве натуральных чисел N?

Решение 1. Все классы эквивалентности по отношению равенства (тождества)

Е = {(a, b) | a = b} на любом множестве М, a, b M , состоят из одного элемента. Индекс разбиения М по отношению Е равен мощности тождества М, т.е. M .

2.Индекс разбиения множества N по заданному отношению R равен

5.Множества натуральных чисел, составляющие каждый класс эквивалентности, счётны.

20