Электронный практикум по дискретной математике

Электронный практикум по дискретной математике

для бакалавров факультета «Прикладная информатика»

 

 

 

Краснодар-2020

Практические занятия № 1. Множества.

Элементы теории

Операции над множествами.

Цель занятия:	1.	изучить способы задания множеств;
	2.	получить навыки в применении операций над множествами.

Множества можно задавать двумя способами:

1.перечислением элементов множества.

Например, множество M={x, y, z} состоит из трёх элементов, порядок перечисления которых не имеет значения, т.е. {x, y, z}={y, x, z}=... 

2.описанием элементов множеств:

- описанием характеристических свойств, объединяющих элементы в виде уравнений, диаграмм Эйлера-Венна и геометрически. Например, множество M = {x2 Î N; x – простое число} задано квадратами простых чисел.

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

       Например, подмножество М всех нечетных натуральных чисел с помощью порождающей процедуры имеет вид: M={xÎN: x=1+2n, nÎN}

Операции над множествами

Рассмотрим операции над множествами. Пересечением (произведением) двух множеств называется множество С, состоящее из тех и только тех элементов, которые принадлежат множествам А и В одновременно.  Обозначение: С = А ì üВ	U
Объединением (суммой) двух множеств А и В называется множество С, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В (или тому и другому вместе). Обозначение: С = А î þВ	U U
Разностью множеств А и В называется такое множество С, которое состоит из тех и только тех элементов, которые принадлежат множеству А, но не принадлежат множеству В. Обозначение: С = А ½ В или С = А \ В	U
Дополнением множества А до универсального множества U называется множество С, равное разности U½A. Обозначение: С = U ½А или С =     Симметрической разностью двух множеств А и В называется множество	U
С = А î þ В | А ì ü В. Обозначение: С = А D В     Формула включений и исключений для двух множеств А и В: n(А î þВ)= n(А)+ n(В) - n(А ∩В). для трех множеств А, В и С:	U

n(А î þ В î þ С)= n(А)+ n(В)+ n(С)- n(А ∩ В)-n(А ∩ С)-n(В ∩ С)-n(А ∩ В ∩ С)

где n(Z) – количество элементов множества Z, т.е. его мощность.

 

Примеры выполнения заданий

1. Заданы множества: А = {1, 3, 5, 7, 9}, B = {1, 2, 3, 4, 5}.

Найдите элементы множеств: Д = Аîþ В и Е = АìüВ.

Д= {1, 2, 3, 4, 5, 6, 7,8, 9}, Е = {1, 3, 5}.

2. Представьте заштрихованные области формулами теории множеств Решение: D = (A D B) | (D D C) 3. Пусть (x, y) - координаты точек плоскости. Укажите штриховкой множество: А = {(x, y) | | x + y | < 1}.

Решение: |x+y|<1Û   Û

Y        -1                           1    X                                                    Y=1- x                                                                       Y= - x                                Y= -1 - x

Задания для самостоятельного выполнения

1. Задайте множество А перечислением его элементов:

0)A={xÎR| (x^2–6x+5)×(x^2–x–12)=0}	1) A={xÎR |(x^2–5x+6)×(x^2+x–20)=0}
2)A={xÎR| (x^2 –5x +4)×(x^2–x–6)=0}	3) A={xÎR|(x^2+4x–5)×(x^2–7x+12)=0}
4)A={xÎR| (x^2+3x–4)×(x^2+x–12)=0}	5) A={xÎR |(x^2–5x–6)×(x^2–x–6)=0}
6)A={xÎR |(x^2 +x–2)×(x^2–7x+6)=0}	7) A={xÎR|(x^2–3x–4)×(x^2–9x+20)=0}
8)A={xÎR |(x^2–3x+2)×(x^2–4x–5)=0}	9) A={xÎR |(x^2–x–2)×(x^2–x–20)=0}

2. Заданы множества: А = {1, 3, 9, 10, 8}, B = {5, 3, 11, 4, 8} и
 C = {1, 4, 8, 9, 10}. Найдите элементы множеств Д и Е:

0) Д = АîþВìüС; Е = (А D В) | С;	1) Д = (АîþС) | (ВìüС); Е = А| ВìüС;
2) Д = АîþВîþС; Е = АìüС D В;	3) Д = (АîþС)ìüВ;   Е = А DВîþС;
4) Д = (АîþС) | В; Е = (В D С) | А;	5) Д = АìüВìüС;            Е = С D В | А;
6) Д = Аîþ(В D С); Е = А | В | С;	7) Д = (ВîþС) | (АìüС); Е = АîþВ | С;
8) Д = (АîþВ)ìüС; Е = А D В | С;	9) Д = (АîþВ) D С;         Е = АìüВ | С;

3. Пусть (x, y) - координаты точек плоскости. Укажите штриховкой множеств a A ì ü B и A î þ B:

0) А={(x, y) | x^2 + y^2 | £ 1}; B={(x, y) | | x + 2y | < 3}	1) А={(x, y) |x^2 + y^2 ³ 4}; B={(x, y)| | 4x - y | £ 2};
2) А={(x, y) | x^2 + y^2 = 9}; B={(x, y) | | 4y + x| > 1};	3) А={(x, y) | x^2 + y^2 < 25}; B={(x, y) | | 2x + 2y| >5};
4) А={(x, y) | x^2 + y^2 ³ 4}; B={(x, y) | | 3x + y| < 6};	5) А={(x, y) | x^2 + y^2 £ 16}; B={(x, y) | | x + 3 | ³1};
6) А={(x, y) | x^2 + y^2 < 36}; B={(x, y) | | x + y | ³ 2};	7) А={(x, y) | x^2 + y^2 > 9}; B={(x, y) | | 2x - y | £ 1};
8) А={(x, y) | x^2 + y^2 > 16}; B={(x, y) | | x - 3y| > 5};	9) А ={(x, y) | x^2 + y^2 £ 36}; B={(x, y) | | x + 4y| <8};

Практические занятия № 3,4.

Элементы теории

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

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

       Пусть элемент , рассмотрим множество объединение множествА,В .

 

 Заполним следующую таблицу:

 

№	А	В
1
2
3
4

Возможны четыре случая:

1.  Для этого случая заполним первую строку таблицы

 

№	А	В
1	0	0	0
2
3
4

 

Здесь 0 означает, что элемент а не принадлежит множеству, соответствующему данному столбцу.

2.

3.

4.

Соответствующим образом заполним 2,3 и 4 строки рассматриваемой таблицы.

 

№	А	В
1	0	0	0
2	0	1	1
3	1	0	1
4	1	1	1

 

В результате построена таблица вхождения элементов в множества для множества . Данной таблице соответствует диаграмма Эйлера-Венна

 

 

Построим таблицы вхождения элементов в множества и соответствующие им диаграммы Эйлера для пересечения множеств

 

 

 

для разности множеств  

 

 

 

 

для симметрической разности множеств

 

 

 

для дополнения множества

 

 

 

Примеры решения задач.

Пример 1. Построить таблицы вхождения элементов множества  и изобразить его на диаграммах Эйлера-Венна.

Решение.

Так как в данной задаче рассматривается операция над тремя множествами, поэтому в формируемой таблице будет 8 строк.

 

№	A	B	C
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

 

В данной таблице необходимо учитывать, принадлежит ли произвольный элемент каждому из трех исходных множеств, а далее согласно построенным выше таблицам вхождения для конкретной операции делать вывод, принадлежит ли он формируемым множествам. Отметим, что множества A, B, C мы называем исходными, а , формируемыми.

Заполним столбец таблицы для первого действия   формулы .

 

№	A	B	C
0	0	0	0	0
1	0	0	1	0
2	0	1	0	1
3	0	1	1	1
4	1	0	0	1
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

Например, в строке 3 имеем элементы 0 1 1, т.е.  и согласно таблице для  (), ставим значение 1 в столбец   в строке 3.

Далее заполним столбец , получим результирующую таблицу.

 

№	A	B	C
0	0	0	0	0	0
1	0	0	1	0	0
2	0	1	0	1	0
3	0	1	1	1	1
4	1	0	0	1	0
5	1	0	1	1	1
6	1	1	0	1	0
7	1	1	1	1	1

           

По таблице строим диаграмму Эйлера Венна для формулы .

       Укажем область на диаграмме Эйлера, соответствующую строке 3 для которой .

 

           

Подобным образом нанесем на диаграмму Эйлера номера строк для остальных областей.

 

 

Далее закрасим желтым цветом области на диаграмме, которым соответствует значение 1 в последнем столбце  таблицы.

 

№	A	B	C
0	0	0	0	0	0
1	0	0	1	0	0
2	0	1	0	1	0
3	0	1	1	1	1
4	1	0	0	1	0
5	1	0	1	1	1
6	1	1	0	1	0
7	1	1	1	1	1

 

получим диаграмму (области для строк 3,5,7)

 

 

Пример 2. Построить таблицы вхождения элементов в множества для заданного множества и изобразить его на диаграммах Эйлера-Венна: .

Решение.

С учетом порядка действий в формуле M=  составим таблицу вхождения элементов во множество.

 

№	A	B	C
0	0	0	0	1	0	1	1	0	1
1	0	0	1	0	0	1	1	0	1
2	0	1	0	1	0	1	1	0	1
3	0	1	1	0	1	1	1	0	1
4	1	0	0	1	0	0	0	0	0
5	1	0	1	0	0	0	0	1	1
6	1	1	0	1	0	0	0	0	0
7	1	1	1	0	1	0	1	1	0

 

Составим диаграмму Эйлера с отмеченными областями.

 

 

Закрасим на данной диаграмме необходимые области желтым цветом согласно единичным значениям в таблице вхождения элементов в множества.

 

№	A	B	C
0	0	0	0	1
1	0	0	1	1
2	0	1	0	1
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	0
7	1	1	1	0

 

получим диаграмму (строки 0,1,2,3,5)

 

 

Пример 2.3. Даны множества

;

.

Изобразить на числовой прямой следующее множество: .

Решение.

Изобразим на числовой прямой множества U, A, B, ,С,  :

 

Ответ: [2,5].

 

Пример 2.4. Даны множества

;

.

Изобразить на числовой прямой следующее множество: .

Решение.

Ответ: (-3,4] È(5,6).

Пример 2.5. Даны множества

;

.

Найти и изобразить на числовой прямой следующее множество: .

Решение.

Ответ:

 

Пример 2.6. Даны множества

;

.

Найти и изобразить на числовой прямой следующее множество: .

Решение

Ответ:

Задания для самостоятельного выполнения

 

Задание.1. Построить таблицы вхождения элементов в множества для заданных множеств и изобразить их на диаграммах Эйлера-Венна.

 

0
1
2
3
4
5
6
7
8
9

Задание 2. Даны множества

.

Изобразить на числовой прямой следующие множества:

 

0
1
2
3
4
5
6
7
8
9

 

Задание 3. Даны множества

Найти и изобразить на числовой прямой множества:

 

0
1
2
3
4
5
6
7
8
9

Практическое занятие № 5. Операции
над множествами.

Цель занятия:	1.	изучить способы задания множеств;
	2.	получить навыки в применении операций над множествами.

 

Элементы теории

 

Примеры выполнения заданий

 

1. Докажите тождество:  º Z

Решение.

 º  º U ìü Z º Z

 

Задания для самостоятельного выполнения

1. Изобразите с помощью диаграмм Эйлера-Венна в двух вариантах расположения следующие множества:

0) а) U½ ; б) ìü B½C;	1) а) CîþА½ ; б) (А½В)îþC;	2) а) (A D В)½C; б) ìüС;
3) а) АìüВ½С; б) AìüВîþС½А;	4) а) ½С; б) (В½А)ìüC;	5) а) ìü ½С; б) ½С;
6) а) С½АîþВ; б) ìü (В D С);	7) а) U½ ; б) CìüА½ ;	8) а) A½ (B D C); б) С½АìüВ;

 

9) а) (АîþВ)ìü(В D С); б)  AîþВ½C; а)

U             A       B                           C

U       А       В        С

 

б)

U             A       B                           C

U       А       В        С

 

Задания для самостоятельного выполнения

 

1. Проверить, верны ли тождества:

0) X ∪  º Z ∪ X  º ∩  X ∩ ∪ Z | º Z |  Y | (  ∪ Z) º Æ;	1) X ∩Y∩(X∩Z∪X∩Y∩Z ∪Z∩ t) º X ∩Y∩Z  º Y ∪ ∪ (X | (X | )) ∪ ( | ( | )) º  ∩ (  | X ∪ ) º Æ;
2) ∩Y∩ Z∪X∩Z º (X ∪Y) ∩Z X∪ ∪ ºX∪Z∪ Y | (Y | X ∪ ) º Y ∩ X ( ∩  | X) |  º Æ;	3) X ∩Y∪X∩Y∩Z ∪X∩Y∩Z∪X∩Y∩Z º X∩Y º X ∩  ∩ Y (X | ) |  º X (X ∩ ) | ( ∪ ) º Æ;
4)  ∪ Y ∩ Z ∪ ∪ ∪ º U  ∩ º ∩  |  º Z | Y  º Æ;	5) ((X ∪ Y) ∪ (  ∩ )) ∩  º X ∩ º ( ∪ Z) ∩ X | Y ∪ X ∩ Z º X | Y ∩ º Æ;
6)  º U º X ∩ Y  |  º X ∩  ∩ Y  ∩ (Y ∪ Z) ∩ X ∩Y º Æ;	7) (X ∪ Y ∪ Z) ∩ (X ∪ Y) ∪ Z º X ∪ Z ∪ Y º ∪ Y | (X ∩Y | ) º Y | X  | ∪Y º Æ;
8) X ∪ ∪ X ∩ Z º U  ∪ º ∪ X ∪  ∩ (Y| ) º X  | ∪  º Æ;	9) (X ∪ Z) ∩ (X ∪ Y) ∩ (Y ∩ Z) º Y ∩ Z        ∩ º (Y ∪ ) ∩ ( | ) |  º X | Z  ∩  º Æ;

Элементы теории

 

Пусть X и Y - два множества. Если каждому элементу x множества X поставлен в соответствие некоторый элемент f(x) множества Y, то говорят, что задано отображение f из множества X в множество Y.   Обозначение: f: X ® Y.

При этом, если   f(x) = y, то элемент y называется образом элемента x при отображении f, а элемент x называется прообразом элемента y при обратном отображении f ^-1.

 

Отображение f: X ® Y является сюръективным, если каждый элемент yÎY имеет хотя бы один прообраз.

 

Отображение f: X ® Y называется инъективным, если для любого элемента yÎY существует не более одного прообраза. Если отображение f сюръективно и инъективно одновременно, то оно называется биективным (взаимно однозначным соответствием).

 

Пусть f: X ® Y и g: Y ® Z - два отображения. Зададим правило h, применение которого к элементу x из X состоит в том, что мы применяем к x правило f, затем к результату f(x) применяем второе правило g, получая в итоге g(f(x)). То есть h(x) = g(f(x)). Полученное отображение h: X ® Z называют композицией отображений g и f и обозначают h = g ° f. Тогда g ° f(x) = g(f(x)).

Декартово произведение двух множеств А и В - множество упорядоченных пар <a, b> таких, что aÎA и bÎB. Мощность декартова произведения равна произведению мощностей исходных множеств.

Бинарное отношение множеств А и В - подмножество декартового произведения А на В. Область определения отношения (левая область отношения) - множество всех первых элементов пар отношения. Область значений отношения (правая область отношения) - множество всех вторых элементов пар отношения.

Рефлексивное отношение на множестве А - отношение, которое справедливо для каждого элемента множества А как отношение этого элемента к самому себе. Например =, ³ - рефлексивные, ¹, > - нерефлексивные.

Симметричное отношение - отношение, результат которого не меняется при перестановке операндов.

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

Отношение эквивалентности - отношение, являющееся одновременно рефлексивным, симметричным и транзитивным.    

Класс эквивалентности R - набор элементов множества, для которых эквивалентное отношение R будет давать одинаковый результат.

 

Примеры выполнения заданий

1. Для отображения f: {0,1,3,4} ® {2,5,7,8}, заданного рисунком, найдите f({0,3}), f({1,3,4}), f ^– 1 (2), f ^– 1 ({2,5}), f ^–1 ({5,8}).   Решение: f ({0,3}) = {5, 8};              f ({1,3,4}) = {5, 7};              f ^- 1 (2) = {Æ};              f ^- 1 ({2,5}) = {3, 4};                f ^- 1 ({5,8}) = {0, 3, 4}

0           2   1           5   3           7   4           8

2. Выясните, к какому типу относится заданное отображение f:

A = {a, b, c}; B = {2, 4, 6, 8}; f: a ® 2; b ® 4; b ® 6; c ® 8;  

Решение: находим образы: y = f (x):   f (a) = 2; f (b) = {4, 6}; f (c) =8

Находим прообразы: x = f ^--1 (y): f ^-1 (2) = a; f ^-1 (4) = b; f ^-1 (6) = b; f ^-1 (8) = c;

Все элементы В имеют прообразы, значит f – сюрьективно.

Т.к элементы 4 и 6 имеют равные прообразы, то f – неинъективно,

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

3. Пусть f: {1,2,3,5} ® {0,1,2}, g: {0,1,2} ® {3,7,9,13}, h: {3,7,9,13} ® {1,2,3,5} – отображения, показанные на рисунке:

 

f: 1             0   2             1   3             2    5

g: 0              3   1              7   2              9                 13

h: 3              1   7              2   9              3   13             5

 

Нарисуйте композиции отображений:

 

а) g(f); б) h(g); в) h(f (g));

 

Решение: