Лабораторная работа Лабораторная работа Основы теории множеств

Пример. Найти произведение и произведение перестановок , и .

Решение. Найдем . Процесс вычисления реализуем в виде диаграммы:

.

Таким образом, получили перестановку .

Аналогичным образом находим :

Получили: .

Решение задачи закончено. Замечание. Из данного примера видно, что, вообще говоря, , т.е. операция умножения перестановок не является коммутативной.

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

Пример. Дана перестановка . Найти обратную перестановку .

Решение. Для нахождения обратной перестановки достаточно поменять местами строки ее таблицы:

.

Данный ответ является верным. Но его целесообразно привести к каноническому виду (т.е. однозначно определенному) путем перестановки столбцов полученного ответа таким образом, чтобы в верхней строке получилась стандартная последовательность . Окончательный ответ имеет вид: .

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

и выполняется соотношение .

Такая перестановка записывается в виде .

Пример. Дан цикл . Записать эту перестановку в стандартном виде.

Решение. Элементы множества остаются неподвижными при действии данной перестановки, а элементы множества переставляются по схеме: . Получаем перестановку .

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

Пример. Перестановку представить в виде произведения циклов.

Решение. Представим перестановку в виде ориентированного графа на множестве вершин . Расположение вершин графа произвольно, выбираем расположение по кругу. Образы элементов изображаем ориентированными ребрами. Получаем граф:

Из визуального анализа данного графа получаем, что в графе имеется ориентированный цикл длины 3, орцикл длины 2 и 3 элементарных цикла- петли длины 1. Получаем искомое разложение в виде циклов. Порядок циклов в разложении и выбор первого элемента каждого цикла не существенен. Если порядок перестановки предполагается известным, то полученное разложение на циклы можно записать более кратко . Порядком перестановки называется наименьшее положительное целое число такое, что . Пусть перестановка разложена в произведение непересекающихся циклов с длинами , . Тогда порядок перестановки находится по формуле . Например, для данной перестановки имеем . Отсюда .

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

Решение. Используем результат предыдущего примера, в котором было получено разложение данной перестановки в произведение циклов: . В данном разложении первый цикл уже является транспозицией, а второй цикл можно представить в виде произведения двух перестановок , т.е. циклический сдвиг можно реализовать серией двух последовательных парных обменов при которых первый элемент “проталкивается” вдоль цикла. Таким же образом любой цикл длины можно представить в виде произведения транспозиции в виде . В данном примере получаем разложение перестановки на транспозиции: =. В том разложении имеется три перестановки, т.е. нечетное число. Такая перестановка называется нечетной и это записывается в виде . Если число транспозиций в разложении перестановки четное, то перестановка называется четной и для нее выполняется свойство .

Изучение множеств с помощью логических функций.

Одномерный булевский куб это - множество, состоящее из 0 и 1. Многомерный булевский куб - множество n - координатных двоичных наборов, n-мерный булевский куб. При этом - мощность множества , например, . Для каждого двоичного вектора определяется число - десятичный эквивалент двоичного набора или номер набора, при этом , где правая часть соотношения принадлежности это множество всех возможных номеров двоичных наборов.

Пример.

Соответствие взаимно-однозначно, т.е. является нумерующей биекцией .

Пример: Найти 5- мерный двоичный набор , для которого .

Решение:

Используем таблицу весов двоичных разрядов:

	5	4	3	2	1	0
	32	16	8	4	2	1

Имеем начальное число Находим наибольший вес . Таким весом является Выделяем найденный максимальный вес разряда, получаем . К остатку применяем тот же алгоритм. Получаем , где - новый остаток. К полученному новому остатку применяем тот же алгоритм последовательного выделения весов. Получаем . Получили последний остаток . Работа алгоритма закончена. В результате получено разложение исходного числа по степеням 2: . Получаем ответ задачи:

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

Пример. Дан универсум . Найти десятичный эквивалент подмножества универсума .

Решение. Строим характеристический булев вектор: . Находим десятичный эквивалент данного подмножества:

. Итак, данное подмножество характеризуется своим десятичным эквивалентом

Пример 2. Дан универсум . Найти состав подмножества универсума, которое имеет десятичный эквивалент

Решение. Находим 4-разрядное двоичное число, соответствующее десятичному числу 14:

Выписываем состав искомого подмножества:

.

Задание 1. Для двух перестановок найти

a) их произведение ;

b) произведение ;

c) обратную перестановку ;

d) Обратную перестановку ;

e) Разложение перестановки в произведение циклов;

f) Разложение перестановки в произведение циклов:

g) Порядок перестановки ;

k) Порядок перестановки ;

l) Разложение перестановки в произведение транспозиций;

m) Разложение перестановки в произведение транспозиций;

n) Четность перестановки ;

o) Четность перестановки ;

Для выполнения пунктов задания 1 следовать примерам, изложенных в теоретической части.

Индивидуальное задание 1.

Nv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Задание 2. Дан универсум и подмножество этого универсума. Найти десятичный эквивалент данного подмножества. Считать, что элементы универсума пронумерованы в естественном порядке слева направо.

Индивидуальное задание 2.

Nv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Задание 3. Дан универсум и целое число . Найти подмножество универсума, для которого десятичный эквивалент (каноническая нумерация) равен заданному числу . Считать, что элементы универсума пронумерованы в естественном порядке слева направо.

Индивидуальное задание 3.

Nv
1		17
2		19
3		11
4		7
5		23
6		30
7		28
8		14
9		16
10		5
11		12
12		16
13		11
14		13
15		26
16		15
17		4
18		31
19		0
20		11
21		12
22		18
23		21
24		22
25		24

Лабораторная работа 5. Формула включений и исключений.

Цель. Изучить типичные применения формулы включений и исключений.

Задание. Решить три задачи комбинаторики, в которых используется формула включений и исключений. Ответить на контрольные вопросы.

Краткие теоретические положения.

Пусть в универсуме заданы конечные подмножества . Тогда справедливы формулы

- (1)

- формула включений и исключений для двух подмножеств.

(При подсчете мы включаем и подсчитываем элементы как подмножества в количестве , так и элементы подмножества в количестве . При этом элементы их пересечения учитывались дважды и их нужно исключить путем вычитания числа ), далее для

(2)

- формула включений и исключений для трех множеств.

(Здесь мы удаляем лишние парные пересечения, но тройное пересечение удалено трижды, а в сумме оно имеет две избыточные копии, следовательно, для компенсации число необходимо добавить)

и в общем случае:

(3)
Пример 1.

В классе человек. Из них занимаются боксом, - футболом, и боксом и футболом. Сколько человек не занимается этими видами спорта.

Решение. Пусть - множество школьников, занимающихся боксом, - множество школьников занимающихся футболом. Тогда - множество школьников, которые занимаются обоими этими видами спорта. По условию имеем

. По формуле включения-исключения получаем . Нас интересует мощность дополнения . По формуле дополнения имеем: . Итак, 9 учащихся класса не занимается ни боксом ни футболом.

Пример 2. Сколько целых чисел в интервале не делятся ни на 3, ни на 4, ни на 6.

Решение. Пусть подмножества чисел интервала , делящихся соответственно на 3,4,6. Найдем мощности этих множеств, их пересечений и их тройного пересечения. Имеем: . Ограничения, фигурирующие в описании множества можно записать в виде или . Так как - целое число, можно записать . Видим, что имеется биективное соответствие . Отсюда получаем . Аналогично получаем . Далее получаем: . Отсюда . Таким же методом находим , . Отсюда . Найдем мощности попарных пересечений множеств . Имеем . Дале, . Можно записать или , откуда =56. Таким же образом . Отсюда . Для третьего пересечения получаем . Поэтому . Остановимся на методике вычисления наименьшего общего кратного Используем метод разложения на простые множители: , . Отсюда . Продолжим решение задачи. Найдем мощность тройного пересечения . Это вычисление уже выполнялось, поэтому получаем . По формуле включения-исключения далее имеем

.

Окончательно, по формуле дополнения получаем =

Формула включения-исключения допускает значительное уточнение. При этом используется важное понятие констинуенты относительно данной системы базовых множеств. Пояснение этого понятия приведем для случая трех базовых множеств. Пусть даны универсум и три подмножества , которые называются базовыми или исходными. Констинуентой в алгебре подмножеств универсума порожденной системой базовых множеств называется подмножество , где использовано соотношение . Например, . Таким образом, констинуента- это пересечение базовых множеств или их дополнений в зависимости от компонент булевского вектора , индексирующего констинуенту. Для трех базовых множеств имеется констинуент, начиная от констинуенты и заканчивая констинуентой . Констинуенты взаимно не пересекаются, т.е. и их объединение равно всему универсуму, т.е. . Важность констинуент объясняется их свойством атомности: любой подмножество, полученное из базовых множеств применением теоретико- множественных операций, т.е.применением формулы алгебры множеств после всех упрощений представляется в виде объединения(непересекающихся) констинуент, входящих в данное множество. Таким образом, с помощью констинуент мы описываем алгебру подмножеств, порожденную данными тремя множествами , т.е. порожденную подалгебру булеана вида . Мы имеем . Пусть нам даны мощности универсума, базовых множеств , их парных пересечений и тройного пересечения. Таким образом, имеем 8 независимых данных. Из этих данных мы можем найти также 8 независимых величин мощностей всех констинуент. Эти подсчеты удобнее всего пояснить следующей таблицей:

Расположение констинуент можно проиллюстрировать следующей диаграммой:

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