Индивидуальные задания

№ вар.	U
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

4. Контрольные вопросы

1. Дать определение одномерного и n-мерного булевского куба.

2. Как по двоичному набору строится его десятичный эквивалентный код, как по десятичному ислу находится его двоичное представление.

3. Как строится десятичный исловой код данного подмножества универсума.

4. Как по дестичному коду находитс соответствующее подмножество.

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

1. Цель работы

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

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

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

Тогда справедливы формулы.

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

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

Далее для _.

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

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

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

(3)

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

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

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

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

Решение. Пусть подмножества чисел интервала, делящихся соответственно на 3, 4, 6. Найдем мощности этих множеств, их пересечений и их тройного пересечения.

Имеем:

. Ограничения, фигурирующие в описании множества можно записать в видеили.

Так как  целое число, можно записать . Видим, что имеется биективное соответствие.

Отсюда получаем .

Аналогично получаем . Далее получаем:.

Отсюда .

Таким же методом находим ,.

Отсюда .

Найдем мощности попарных пересечений множеств .

Имеем .

Дале, . Можно записатьили, откуда=56.

Таким же образом .

Отсюда .

Для третьего пересечения получаем . Поэтому.

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

Продолжим решение задачи.

Найдем мощность тройного пересечения . Это вычисление уже выполнялось, поэтому получаем.

По формуле включения-исключения далее имеем

.

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

=

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

Пусть даны универсум и три подмножества, которые называются базовыми или исходными. Констинуентой в алгебре подмножеств универсума _, порожденной системой базовых множеств _, называется подмножество , где использовано соотношение.

Например, .

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

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

Важность констинуент объясняется их свойством атомности: любой подмножество, полученное из базовых множеств применением теоретико-множественных операций, то есть применением формулы алгебры множеств после всех упрощений представляется в виде объединения (непересекающихся) констинуент, входящих в данное множество.

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

Мы имеем .

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

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

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

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

Дано:   число студентов в потоке;

число студентов, изучающих английский язык;

число студентов, изучающих французский язык;

число студентов, изучающих немецкий язык;

число студентов, изучающих английский и французский;

число студентов, изучающих английский и немецкий;

число студентов, изучающих французский и немецкий;

число студентов, изучающих все три языка;

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

Решение. Найдем мощности констинуент в следующей таблице.

Для проверки расчета изобразим диаграмму констинуент вместе с их найденными мощностями.

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

Выпишем констинуентный состав базовых подмножеств (эта часть решения не зависит от данных по мощностям):

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

Имеем:

Суммируем мощности констинуент, составляющих множество :. Итак. 40 студентов потока учат английский или французский языки, но не оба вместе и при этом не изучают немецкий язык.

3. Задание.

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

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

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

№ вар.
1	20	12	5	3
2	30	11	8	3
3	23	6	5	2
4	34	7	4	2
5	27	12	7	4
6	19	10	5	4
7	22	9	5	4
8	23	8	3	1
9	25	6	6	4
10	30	9	6	3
11	19	10	3	1
12	18	11	3	1
13	21	8	2	1
14	20	8	4	3
15	20	7	6	3
16	23	10	6	5
17	34	20	12	6
18	28	12	6	5
19	32	10	4	1
20	23	8	9	3
21	33	12	10	6
22	23	7	4	2
23	24	8	8	1
24	26	10	12	4
25	29	12	11	7
26	31	12	17	8
27	30	2	1	0

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

Найти количество чисел в интервале от 1 до M, которые не делятся ни на , ни на, ни на.

№ вар.	M
1	566	4	5	2
2	234	2	4	5
3	198	3	4	6
4	189	6	8	4
5	156	7	6	2
6	897	8	3	6
7	1000	3	5	4
8	999	8	7	4
9	1200	6	5	4
10	134	12	5	10
11	874	4	5	8
12	345	5	4	8
13	987	8	3	9
14	456	9	4	6
15	733	10	3	3
16	944	3	5	9
17	773	5	4	6
18	567	3	4	7
19	456	3	6	9
20	566	12	6	7
21	788	2	7	11
22	920	8	11	14
23	456	7	14	28
24	189	23	11	12
25	345	12	6	8
26	567	3	5	8

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

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

Найти мощности всех констинуент данного порождающего набора подмножеств, выписать констинуентный состав каждого базового множества и производного множества , а также мощность производного множества.

№ вар.
1	120	30	35	32	10	13	8	3
2	112	45	29	34	12	8	12	4
3	200	34	32	45	12	12	11	2
4	117	35	34	34	13	11	13	2
5	120	29	45	35	8	13	10	1
6	100	32	34	29	12	10	12	2
7	112	34	35	45	11	12	12	2
8	114	45	34	34	13	12	10	3
9	113	34	35	34	10	13	12	3
10	89	35	29	35	12	8	12	3
11	99	29	45	29	12	12	13	3
12	200	45	34	45	13	11	8	2
13	117	34	35	34	8	8	12	2
14	120	35	34	35	12	12	12	3
15	100	29	35	34	11	11	11	3
16	112	32	29	35	13	13	13	4
17	200	34	35	29	8	10	10	2
18	117	34	29	45	12	12	12	2
19	120	35	45	34	11	12	12	1
20	100	29	34	35	13	13	13	2
21	112	45	35	34	10	8	10	2
22	200	34	32	35	12	12	12	3
23	117	35	31	29	12	11	12	3
24	120	34	29	45	13	13	13	3
25	100	35	45	34	12	10	12	3
26	112	29	34	35	11	12	11	2
27	200	45	35	29	13	12	8	2
28	117	34	34	45	10	13	12	1
29	120	35	35	34	12	12	11	2
30	100	32	29	35	12	11	13	2
31	112	31	45	29	8	13	10	3

1. Контрольные вопросы

1. Привести формулу влючения-исключения.

2. Что такое констинуента в алгебре подмножеств универсума.

3. Как находтся мощность констинуенты с использованием формулы вклюения-исключения.

4. Как в терминах констинуент производятся операции над множествами.