5.1.3 Представление множеств в компьютере
Существуют разные методы представления множеств в компьютере. Самый простой из них – сохранять элементы множества в неупорядоченном виде как список. Но если хранить множества в таком виде, то операции объединения, пересечения, разности, симметрической разности над этими множествами требуют значительного количества времени из-за поиска соответствующих элементов. Поэтому, как правило, используется метод, основанный на каком-либо упорядочении элементов универсального множества. Такой метод представления множеств даёт возможность легко и быстро проводить операции над множествами.
Предположим, что
универсальное множество
конечно.
Во-первых, в множестве
произвольным образом упорядочим все
элементы, например
.Представим
подмножество
множества
в виде битовой строки длины
,
где
-ый
бит в строке равен 1, если
,
и 0 в противном случае. Следующий пример
поясняет этот метод.
Пример. Пусть
и
пусть упорядочение элементов
произведено в возрастающем порядке,
т.е.
.
Запишем строки битовые строки,
представляющие подмножество всех чётных
чисел из
,
подмножество всех нечётных чисел из
и подмножество всех простых чисел из
.
Так, битовая строка,
представляющая подмножество чётных
чисел, а именно
,
имеет единичный бит на второй, четвёртой,
шестой, восьмой и десятой позиции
соответственно и нули на остальных
позициях:
(пробелы добавлены
для удобства чтения, поскольку длинные
строки неудобно читать). Аналогично,
подмножество нечётных чисел
представляется
строкой
.
Множество простых
чисел из
,
,
представляется строкой
.
Используя для
представления множеств битовые строки,
легко вычислить дополнение множества,
объединение, пересечение и разности
множеств. Чтобы найти битовую строку
для дополнения множества, используя
битовую строку для множества, надо
просто заменить каждую единицу нулём,
а каждый ноль – единицей, так как
тогда
и только тогда, когда
.
Чтобы получить
битовую строку для объединения и
пересечения двух множеств, введём
попарные булевы операции над битовыми
строками, представляющими эти множества.
Бит на
-ой
позиции битовой строки, представляющей
объединение, равен единице, если хотя
бы в одной из соответствующих строк бит
на
-ой
позиции равен 1, и равен нулю, если в
каждой строке бит на
-ой
позиции равен 0. Бит на
-ой
позиции битовой строки, представляющей
пересечение, равен единице, если в каждой
битовой строке соответствующие биты
равны 1, и нулю в противном случае.
Например, битовые строки для множеств и имеют вид, как показано ранее, и соответственно.
Битовая строка для объединения этих множеств будет
,
что соответствует
множеству
,
а битовая строка для пересечения этих
множеств имеет вид
,
что соответствует
множеству
.
Заметим, что число
различных битовых строк длины
равно
,
причём каждая из строк соответствует
какому-либо подмножеству универсального
множества, содержащего
элементов. Тем самым доказана теорема
из параграфа 5.1.1.
5.1.4 ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Пусть и – множества. Докажите, что
а)
;
б)
.
Пусть и – множества. Докажите, что
.Пусть и – множества. Докажите, что
.Пусть и – множества. Докажите, что
.Пусть , ,
–
множества. Докажите, что
а)
;
б)
;
в)
.
Пусть , , – множества. Докажите, что а)
;
б)
.Пусть , , – множества. Докажите или опровергните, что
.Пусть , , – множества. Докажите или опровергните, что
.Пусть , , – множества. Докажите или опровергните, что
Пусть , , – множества. Известно, что
.
Докажите или опровергните, что
.Пусть
для
. Найдите
а)
;
б)
.Пусть
для
. Найдите
а)
;
б)
.Пусть и – подмножества универсального множества . Расположите список множеств по возрастанию мощности:
,
,
,
,
.
Пусть и – подмножества универсального множества . Расположите список мощностей множеств по возрастанию:
,
,
,
,
.Пусть , , – множества. Докажите, что
.Пусть и – подмножества универсального множества . Докажите, что
5.2. ОТНОШЕНИЯ
5.2.1 БИНАРНЫЕ ОТНОШЕНИЯ
Отношением
множеств
и
называется
произвольное подмножество их декартова
произведения
.
Если
,
то это обозначается
;
при этом говорят, что
и
находятся
в отношении
.
Если
,
то отношение
есть подмножество декартова произведения
;
такое отношение называются бинарным
отношением на
.
В дальнейшем, как правило, будут рассматриваться бинарные отношения, поэтому термин «отношения» подразумевает бинарные отношения на множестве .
Примеры.
Пусть
.
Тогда
– множества пар чисел таких, что
без остатка делится на
– есть бинарное отношение на множестве
.Пусть – множество целых чисел. Определим отношение
.Пусть – множество действительных чисел. Тогда на этом множестве можно определить отношение
.Пусть – множество точек на плоскости. Определим отношение как множество точек и
,
таких что расстояние между ними равно
единице.
Пусть – множество людей. Два человека и находятся в отношении , если имеет ту же фамилию, что и .
Отношения могут быть заданы одним из следующих способов:
словами (используя подходящие высказывания);
как множество упорядоченных пар;
как ориентированный граф;
как матрица.
Рассмотрим подробнее два последних способа задания графа.
Пусть – конечное множество и – бинарное отношение на нём. Изобразим элементы этого множества точками на плоскости (эти точки принято называть вершинами). Для каждой упорядоченной пары отношения нарисуем дугу (линию со стрелкой), соединяющую вершины, представляющие компоненты пары. Такой объект называется ориентированным графом.
Пример. Изобразим отношение, заданное в примере 1, в виде ориентированного графа. Запишем сначала отношение как множество упорядоченных пар
.
Затем построим соответствующий ориентированный граф (рис. 5.2).
Рис. 5.2.
Ещё один способ
задания бинарного отношения на конечном
множестве основан на использовании
матриц. Пронумеруем элементы множества
и выпишем их в установленном порядке:
.
Для определения
отношения
зададим
матрицу
размера
.
Элементы матрицы
определим
следующим образом:
В таких обозначениях матрица отношения из примера 1 имеет вид
Надо заметить, что задание отношения на как множество упорядоченных пар, как ориентированный граф и как матрица допустимо лишь для конечного множества .