Дискретная математика

называется n - местным отношением на множестве М.
Говорят, что элементы

находятся в отношении R, если
.

признаками: элемент а – обладает признаком R, если

и

Свойства одноместных отношений это свойства подмножеств М, поэтому для случая n = 1 термин “отношение” употребляется редко.

команде. Любой из нападающих находится в этом отношении со всеми

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

и b находятся в отношении R,
это записывается aRb.
Таким образом,

бинарное отношение, заданное на множестве М, это любое подмножество

а R содержит небольшое количество пар.

Пример:
- алфавит из трех букв,
Отношение R – предшествования букв в алфавите. Тогда R содержит пары:

это квадратная матрица С порядка n, в которой элемент определяется так:

a и b соединяются стрелками, если aRb.

Пример:

.
Отношение –
быть меньше.

любого

выполняется . Главная диагональ матрицы такого отношения содержит только единицы, граф – петлю в каждой вершине.
Пример: Отношение «быть делителем», заданной на множестве N.
1 делитель 1; 2 делитель 2; 3 делитель 3; и т. д.

любого

выполняется . Главная диагональ матрицы такого отношения содержит только нули, граф – не имеет петель.
Пример: Отношение «быть больше», заданной на множестве N.
1 не больше 1; 2 не больше 2; 3 не больше 3; ит.д.

любой пары
из aRb следует bRa (то есть, для любой

пары отношение R выполняется в обе стороны или не выполняется вообще). Матрица симметричного отношения – симметрична относительно главной диагонали, у графа все стрелки парные, симметричные.

одной комнате с В, то и В живет в одной

комнате с А.
Если С живет в одной комнате с D, то и D живет в одной комнате с C.
И так далее.

любой пары

из того, что
одновременно выполняется: aRb и bRa следует что a=b . Матрица антисимметричного отношения не имеет ни одной симметричной 1, у графа все стрелки непарные, направлены лишь в одну строну.

начальником А.
Если C начальник D, то D не является начальником

C.
И так далее.

из того, что выполняется aRb и одновременно bRc
следует,

что aRc.
Пример: Отношение «быть больше», заданной на множестве N.
если 3 больше 2 и 2 больше 1, то 3 больше 1;
если 5 больше 3 и 3 больше 1, то 5 больше 1; итд

Рефлексивно,
Симметрично,
Транзитивно.

остаток от деления на 3.
R – рефлексивно, так как каждое

число само с собой имеет одинаковый остаток от деления на 3,
например 1 и 1, 2 и 2, 3 и 3, итд.

так как каждое если число а имеет с числом b

одинаковый остаток от деления на 3, то и число b с числом а тоже имеет одинаковый остаток от деления на 3,

например 1 и 4 имеют одинаковый остаток от деления на 3, то и 4 и 1 тоже имеют одинаковый остаток;
2 и 5 имеют одинаковый остаток от деления на 3, то и 5 и 2 тоже имеют одинаковый остаток;
3 и 12 имеют одинаковый остаток от деления на 3, то и 12 и 3 тоже имеют одинаковый остаток, итд.

так для каждых чисел а , b и с если

а с b имеют одинаковый остаток от деления на 3, и b с с имеют одинаковый остаток от деления на 3, то и а с с тоже имеют одинаковый остаток от деления на 3,

например 1 и 4 имеют одинаковый остаток от деления на 3, и 4 и 13 тоже имеют одинаковый остаток от деления на 3, тогда 1 и 13 тоже имеют одинаковый остаток.

R – рефлексивно, симметрично и транзитивно, то есть является отношением

эквивалентности.

оно разбивает множество, на котором задано, на классы эквивалентности.

М произвольный элемент и поместить его в

класс , затем поместить в этот класс все элементы, эквивалентные ему;
2) Затем из оставшихся элементов М выбрать элемент
и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему;
3) Делать, пока останутся нераспределенные по классам элементы.
Число классов разбиения – индекс разбиения I.

классы надо:
1) Выбрать произвольный элемент 1 и поместить его

в класс , затем поместить в этот класс все элементы, эквивалентные ему: 4, 7, 10, 13….;
2) Затем из оставшихся элементов М выбрать элемент
2 и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему: 5, 8, 11, 14, 17,…;
3) Затем из оставшихся элементов М выбрать элемент
3 и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему: 6, 9, 12, 15,… Индекс разбиения равен 3.

транзитивно.

антирефлексивно, антисимметрично и транзитивно.

рефлексивно, антисимметрично и транзитивно.

есть aRb или bRa, то a и b сравнимы по

отношению порядка R.

отношению порядка R, то R отношение полного или линейного порядка,

а М называется полностью упорядоченным.

как каждое число является делителем самого себя:
1 делитель 1;
2 делитель

2;
3 делитель 3, итд.

как если числа разные и a делитель b,то b не

является делителем a:
если 1 делитель 2 и 2 делитель 4, то 1 – делитель 4;
если 4 делитель 8 и 8 делитель 24, то 4 – делитель 24, и т. д.

как если числа разные и a делитель b и b

делитель с, то а тоже является делителем с:
если 1 делитель 2 и 2 не делитель 1;
если 4 делитель 8, то 8 не делитель 4;
если 3 делитель 9, то 9 не делитель 3,
и т. д.

антисимметрично и транзитивно, значит
R – отношение нестрогого порядка.

неполный порядок, так как можно найти хотя бы одну пару

несравнимых элементов, например:
2 и 3; 7 и 11; 4 и 9, итд.

транзитивно.