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

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

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

 

 

 

Краснодар-2015

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

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

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

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

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

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

- описанием характеристических свойств, объединяющих элементы в виде уравнений, диаграмм Эйлера-Венна и геометрически. Например, множество M = {x² Î 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| (x2–6x+5)×(x2–x–12)=0}	1)A={xÎR |(x2–5x+6)×(x2+x–20)=0}
2)A={xÎR| (x2 –5x +4)×(x2–x–6)=0}	3)A={xÎR|(x2+4x–5)×(x2–7x+12)=0}
4)A={xÎR| (x2+3x–4)×(x2+x–12)=0}	5)A={xÎR |(x2–5x–6)×(x2–x–6)=0}
6)A={xÎR |(x2 +x–2)×(x2–7x+6)=0}	7)A={xÎR|(x2–3x–4)×(x2–9x+20)=0}
8)A={xÎR |(x2–3x+2)×(x2–4x–5)=0}	9)A={xÎR |(x2–x–2)×(x2–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) | x2 + y2 | £ 1}; B={(x, y) | | x + 2y | < 3}	1)А={(x, y) |x2 + y2 ³ 4}; B={(x, y)| | 4x - y | £ 2};
2)А={(x, y) | x2 + y2 = 9}; B={(x, y) | | 4y + x| > 1};	3)А={(x, y) | x2 + y2 < 25}; B={(x, y) | | 2x + 2y| >5};
4)А={(x, y) | x2 + y2 ³ 4}; B={(x, y) | | 3x + y| < 6};	5)А={(x, y) | x2 + y2 £ 16}; B={(x, y) | | x + 3 | ³1};
6)А={(x, y) | x2 + y2 < 36}; B={(x, y) | | x + y | ³ 2};	7)А={(x, y) | x2 + y2 > 9}; B={(x, y) | | 2x - y | £ 1};
8)А={(x, y) | x2 + y2 > 16}; B={(x, y) | | x - 3y| > 5};	9)А ={(x, y) | x2 + y2 £ 36}; B={(x, y) | | x + 4y| <8};

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

 

1. Докажите теоретико-числовое равенство: º Z

º º U ìü Z º Z

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

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 ∩ º Æ;

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

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

g: 0 3   1 7   2 9

h: 3 1   7 2   9 3   13 5

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

а) gf; б) hg; в) hf g;

Решение:

а) f  g; 1 3   2 7   3 9   5 13

б) gh; 0 1   1 2   2 3

в) hf; 3 0   7 1   9 2   13

в) hf g; 3 3   7 7   9 9   13 13

4.Установите биективное отображение между множеством
A={1, 6, 11, 16, 21,...} и натуральным рядом чисел.

Решение: поставим в соответствие элементу натурального ряда "n" n↔1+5(n-1), т.е. a_n=1+5(n-1) ÎA

 

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

1. Для отображения f: {10,20,30,40} ® {а,б,в,г}, заданного рисунком, найдите f({10,40}), f({10,20,30}), f ^{- 1}(б), f ^{- 1} ({а,в}), f ^{- 1} ({б,в,г}).

0) 10 а   20 б   30 в   40 г	1) 10 а   20 б   30 в   40 г	2) 10 а   20 б   30 в   40 г	3) 10 а   20 б   30 в   40 г	4) 10 а   20 б   30 в   40 г
5) 10 а   20 б   30 в   40 г	6) 10 а   20 б   30 в   40 г	7) 10 а   20 б   30 в   40 г	8) 10 а   20 б   30 в   40 г	9) 10 а   20 б   30 в   40 г

2. Найдите декартово произведение множеств С = А ´ В:

0)A={1,2,3}; В={7,8,9};	1)A={2,3,4,9}; В={1,7};
2)A= {1,7}; В ={2,4,6,8}	3)A={3,5,10}; В={2,8,9};
4)A={2,3,4,5}; В ={6,10}	5)A={5,6}; В={1,7,9,2};
6)A={10,1,2}; В={1,2,8};	7)A={10,11,12}; В={2,8,9};
8)A={6,9}; В={1,2,3,5};	9)A={2,3,5,6}; В={9,12};

2. Вычислите мощность множеств:

0)В={xÎN | x£41, x–квадрат числа} A={xÎR | (x2 + x +1)×(x2–x–6)=0}	1)В={xÎN | x – делитель 40} A={xÎR | (x2 – x –2)×(x2–x–20)=0}
2)В={xÎN | x – делитель 81} A={xÎR |(x2+x –2)×(x2–7x +6)=0}	3)В={xÎN |x£51, x–квадрат числа} A={xÎR |(x2–3x–4)×(x2–9x+20)=0}
4)В={xÎN |x£65, x–квадрат числа} A={xÎR |(x2–6x+5)×(x2–x–12)= 0}	5)В={xÎN | x – делитель 54} A={xÎR |(x2–5x–6)×(x2–5x+4) = 0}
6)В={xÎN | x – делитель 36} A={xÎR |(x2+3x–4)×(x2+x–12)=0}	7)В={xÎN |x£64, x–квадрат числа} A={xÎR|(x2+4x–5)×(x2–7x+12)= 0}
8)В={xÎN |x£78, x–квадрат числа} A={xÎR |(x2–3x+2)×(x2–4x–5)= 0}	9)В={xÎN | x – делитель 32} A={xÎR | (x2–5x+6)×(x2+x–20)= 0}

 

3. Пусть A = {1, 2, 3}. Установите, является ли каждое из приведенных ни­же отношений R, заданных на множестве А, отношением эквивалентности.

а) R₁ = {(2,2), (1,1), (1,2)};

б) R₂ = {(1,1), (2,2), (3,3)};

в) R₃= {(1,1), (2,2), (3, 3), (1,2), (2,1), (3,1), (1, 3)};

г) R₄ = {(1,1),(2,2),(3,3),(1,2),(3,2),(2,1)};

д) R₅ = {(1,1),(1,2),(3,3),(2,2),(3,2),(2,3),(2,1)};

е) R₆ = {(1,1),(1,3),(2,3),(1,2),(3,2),(2,1),(3,1)};

Размещения без повторений

Размещениями из n элементов по m (m n) называются упорядоченные m -элементные выборки из данных n элементов .

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

0) Составьте все слова из трех букв А, В, С по две буквы.

1) В классе 30 учащихся. Сколькими способами можно выбрать из класса команду из 4 учащихся для участия в олимпиаде по истории?

2) Сколькими способами можно составить двуцветный полоса­тый флаг, если имеется материал 5 различных цветов? Та же за­дача, если одна из полос должна быть красной?

3) Из состава конференции, на которой присутствует 45 чело­века, надо избрать делегацию из 6 человек. Сколькими способами это можно сделать?

4) В турнире принимают участие 8 команд. Сколько различных предположений относительно распределения трех первых мест можно сделать?

5) Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различны и нечетны?

6) Сколькими способами можно сделать трехцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя 6 различных цветов?

7) Сколько существует трехзначных чисел, в записи которых цифры 1, 2, 3 встречаются ровно по одному разу?

8) На полке стоят 5 книг. Сколькими способами можно выложить в стопку несколько из них (стопка может состоять и из одной книги)?

9) У Димы есть 5 шариков: красный, зеленый, желтый, синий и золотой. Сколькими способами он сможет украсить ими 5 елок, если на каждую требуется надеть ровно один шарик?

Размещения с повторениями

Размещениями с повторениями из n по m называются упорядоченные m-элементные выборки, в которых элементы могут повторяться.

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

0) Сколько четырехбуквенных «слов» можно составить из букв "М" и "А"?

1) Сколькими способами можно разместить восемь пассажиров в три вагона?

2) Каждый телефонный номер состоит из семи цифр. Сколько всего телефонных номеров, не содержащих других цифр, кроме 2, 3, 5 и 7?

3) Четверо студентов сдают экзамен. Сколькими способами мо­гут быть поставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки?

4) Сколько различных трехбуквенных слов можно составить из 32 букв алфавита (со смыслом и без)?

5) В селении проживает 2000 жителей. Доказать, что, по край­ней мере, двое из них имеют одинаковые инициалы.

6) Сколькими способами можно покрасить пять елок в серебристый, зеленый и синий цвета, если количество краски неограниченно, а каждую елку можно покрасить только в один цвет?

7) Каждую клетку квадратной таблицы 2 × 2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы?

8) Сколькими способами можно заполнить одну карточку в лотерее «Спортпрогноз»'? Указание: в этой лотерее нужно предсказать итог тринадцати спортивных матчей. Итог каждого матча - победа одной из команд либо ничья; счет роли не играет.

9) Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и В. Словом является любая последовательность, состоящая не более, чем из 4 букв. Сколько слов в языке племени Мумбо-Юмбо? Указание: сосчитайте отдельно количества одно-, двух-, трех- и четырехбуквенных слов.

Перестановки без повторений

Перестановками из n элементов называются размещения из n элементов по n.

Пусть (a₁,a₂,…,a_n), — перестановка элементов множества {1, 2,...,n}.Пара (a_i, a_j) называется инверсией перестановки, если i < j, то a_i > a_j.

Таблицей инверсии перестановки (a₁,a₂,…,a_n) называется последовательность (d₁,d₂,…,d_n),где dj — число элементов, больших j и расположенных левее j.

 

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

0) Сколькими способами можно расставить 7 книг на книжной полке?

1) Сколькими способами можно разложить 8 различных писем по 8 различным конвертам, если в каждый конверт кладется только одно письмо?

2) Сколько ожерелий можно составить из семи бусин раз­ных размеров?

3) Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом?

4) Сколько слов можно получить, переставляя буквы в слове «градус»?

5) Сколькими различными способами можно рассадить 6 человек на 6 креслах в кинотеатре?

6) Сколько всего шестизначных четных чисел можно составить из цифр 1, 3, 4, 5, 7 и 9, если из этих чисел ни одна не повторяется?

7) Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли взять друг друга?

8) Сколько всего семизначных четных чисел можно составить из цифр 0, 2, 3, 5, 7 и 9, если из этих чисел ни одна не повторяется?

9) Как велико число различных отображений, переводящих множество из n элементов в себя?

Сочетания без повторений

Сочетаниями из n элементов по m (m n) называются неупорядоченные m-элементные выборки из данных n элементов.

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

0) Составьте все сочетания из трех букв А, В, С по две буквы.

1) У 6 взрослых и 11 детей обнаружены признаки инфекционного заболевания. Чтобы проверить заболевание, следует взять выборочный анализ у 2 взрослых и 3 детей. Сколькими способами можно это сделать?

2) Сколькими способами можно группу из 20 студентов разделить на две подгруппы так, чтобы в одной группе было 13, а в другой 7 человек?

3) На книжной полке стоят 3 книги по алгебре, 4 книги по геометрии и 5 книг по литературе. Сколькими способами можно взять с полки три книги по математике?

4) Учащийся хочет использовать для раскраски географической контурной карты 4 краски из 6, которые он имеет в своем распоряжении. Сколькими способами он может выбрать 4 краски из 6?

5) Даны две параллельные прямые. На одной из них имеется 10 точек, а на другой - 20. Сколько существует треугольников с вершинами в данных точках?

6) Сколькими способами можно распределить 28 костей домино между 4 игроками так, чтобы каждый получил 7 костей?

7) В классе 12 юношей и 13 девушек. Сколькими способами из них можно выбрать четырех учащихся для дежурства на вечере, если а) освободить девушек; б) юноши и девушки?

8) Сколькими способами абитуриент может выбрать 3 ВУЗа из 5 для подачи документов?

 

Решить задачи:

Задание 1.

0) Из города А в город В ведут пять дорог, а из города В в город С – три дороги. Сколько путей, проходящих через В, ведут из А в С?

1) Из двух спортивных обществ, насчитывающих по 100 фехто­вальщиков каждое, надо выделить по одному фехтовальщику для участия в состязании. Сколькими способами может быть сделан этот выбор?

2) Имеется пять видов конвертов без марок и четыре вида ма­рок одного достоинства. Сколькими способами можно выбрать кон­верт с маркой для посылки письма?

3) Сколькими способами можно выбрать гласную и согласную буквы из слова «камзол»?

4) Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?

5) Бросают игральную кость с шестью гранями и запускают волчок, имеющий восемь граней. Сколькими различными способами они могут упасть?

6) На вершину горы ведут пять дорог. Сколькими способами •турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям.

7) На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?

8) Сколькими способами можно указать на шахматной доске два квадрата – белый и черный? А если нет ограничений на цвет выбранных квадратов?

9) Из 12 слов мужского рода, 9 женского и 10 среднего надо выбрать по одному слову каждого рода. Сколькими способами мо­жет быть сделан этот выбор?

Задание 2.

0) В местком избрано 9 человек. Из них надо выбрать предсе­дателя, заместителя председателя, секретаря и культорга. Сколь­кими способами это можно сделать?

1) Из состава конференции, на которой присутствует 52 чело­века, надо избрать делегацию, состоящую из 5 человек. Сколькими способами это можно сделать?

2) Автомобильные номера состоят из одной, двух или трех букв и четырех цифр. Найти число таких номеров, если используют­ся 32 буквы русского алфавита.

3) Сколько различных перестановок можно получить, переставляя бук­вы в слове «математика»? В слове «парабола»?

4) В почтовом отделении продаются открытки 10 сортов. Сколь­кими способами можно купить в нем 12 открыток? Сколькими спо­собами можно купить 8 открыток?

5) Из группы, состоящей из 7 мужчин и 4 женщин, надо вы­брать 6 человек так, чтобы среди них' было не менее 2 женщин. Сколькими способами это можно сделать?

6) Четверо студентов сдают экзамен. Сколькими способами мо­гут быть поставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки?

7) Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз?

8) Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется ровно один туз?

9) Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется ровно два туза?

 

Рис. 1. Алгоритм определения вида комбинации

Определите тип графа.

 

9)

a

d

c

b

f

e

a

b

c

e

f

0)

3)

6)

1)

4)

7)

2)

5)

8)

a

b

c

e

d

f

a

b

d

f

c

b

c

f

d

a

b

c

d

f

Ориентированные графы

Ориентированный граф (или орграф) G₁ (V, E) – непустое конечное множество узлов (вершин) V и набор упорядоченных пар вершин (дуг) E.

Пусть v ₁, v ₂,... v_n - вершины графа G₁ (V, E), а e ₁, e ₂,... e_m - его дуги.

Матрицей смежности графа G₁ называется матрица A(G₁)= || a_ij ||, i =1,..., n;
j = 1,..., n, у которой элемент a_ij равен числу дуг, соединяющих вершины v_i и v_j (соответственно, идущих из вершины v_i в вершину v_j).

Свойства матрицы смежности:

1) несимметричная, в общем случае, относительно главной диагонали,

2) значениями являются натуральные числа и ноль,

3) количество петель записывается на главной диагонали,

4) сумма значений по строке (столбце) равна валентности вершины.

Матрицей инцидентности для ориентированного графа с n вершинами и m дугами называется матрица В(G₁) = [b_ij], i=1, 2,..., n, j = 1,2,..., m, строки которой соответствуют вершинам, а столбцы - дугам. Ее элемент: b_ij=1, если дуга е_i выходит из вершины v_j; b_ij= -1, если дуга e_i входит в вершины v_j; b_ij=0, если вершина v_j не инцидентна дуге е_i.

Свойства матрицы инцидентности:

1) несимметричная, 2) значениями являются -1, ноль и 1.

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

1. Орграф G₁(V,E) задан геометрически. Постройте для орграфа:

а) матрицу смежности; б) матрицу инцидентности.

b a e c d k g f	Решение а): матрица смежности А(G1)=
Решение б): матрица инцидентности В(G1)=   a b c d e g f k     -1                   -1             -1     -1     -1             -1                   -1

2. Решите следующую задачу по обходу графов:

В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

Решение:

Пусть в столицу входит a дорог. Тогда общее число "входящих" дорог равно 21 · 100 + a, а общее количество "выходящих" дорог не больше 20 · 100 + (100- a). Поэтому 21×100 + а £ 20×100 + (100 – а), то есть 2а £ 0. Таким образом, a = 0.

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

Вычислите центр орграфа.

Решение:

построим матрицу расстояний:

R= r (i, j):