Таблицы Брадиса

Как мы уже знаем, число

Как мы уже знаем, число

Элементы математики в задачах - Г. А. Мерзон

3) транзитивным, если для любых а, Ь, с е М из а ~ Ь и Ь ~ с следует а ~ с.

ш Решать задачи 1-4 надо «одновременно», разбирая конкретные примеры из задач 3 и 4, возвращаясь к утверждениям задач 1 и 2.

Задача 1. Сколько существует отношений на множестве из п элемен­тов? Сколько существует симметричных отношений на множестве из п элементов?

Решение. Отметим, что отношение — это множество упорядоченных пар элементов, а симметричное отношение — это множество неупо­рядоченных пар. Число отношений на множестве из п элементов — это число подмножеств в множестве упорядоченных пар, т. е. в мно­жестве из п2 элементов. Как мы уже знаем, число таких подмножеств равно 2п .

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

но, а это 11(~'1 + 1') клеток. Поэтому симметричных отношений будет

п(п+1)/2

Задача 2. Приведите примеры отношений, которые удовлетворяют ровно одному, ровно двум свойствам из определения 2.

Ш Как мы уже заметили, симметричным отношениям отвечают сим­метричные относительно диагонали таблицы. У рефлексивных отно­шений в таблице на главной диагонали стоят единицы. Транзитив­ность легко увидеть из таблицы нельзя.

Если задавать отношение в виде графа, то симметричным отноше­ниям отвечают графы, в которых, если есть стрелка из а в Ь, то есть и обратная стрелка из Ь в а. Для графа рефлексивного отношения у всех вершин должны быть петли. Если отношение транзитивно, то «для любого длинного пути есть прямой путь», а именно, если есть ориентированный путь из а в Ь, то из а в Ь ведет стрелка.