Множества и его элементы

Коломенский институт (филиал)

Государственного образовательного учреждения высшего профессионального образования

Московский государственный открытый университет

«УТВЕРЖДЕНО»

Учебно-методическим
советом КИ(ф) МГОУ

Председатель совета
к.т.н., профессор А.М.Липатов

«____» февраля 2007 г.

Е.И. Балабан

Сборник задач и упражнений
по дискретной математике

Учебное пособие для студентов специальностей

210100 – Управление и информатика в технических системах

220400 – Программное обеспечение
вычислительной техники и автоматизированных систем

г. Коломна

2007 г.

УДК 519.1(075.8) ББК 22.176я73 Б 20

Печатается в соответствии с решением учебно-методического совета Коломенского института (филиала) Московского государственного открытого университета
от _____ . ___. 2007 г. № ___

Балабан Е.И. «Сборник задач и упражнений по дискретной математике» – Коломна: КИ(Ф) МГОУ, 2007 г., 40 с.

Рецензент: к.т.н., доц. Родионов К.А.

«Сборник задачи упражнений по дискретной математике» одобрен кафедрой «Высшая и прикладная математика» Коломенского института (филиала) Московского государственного открытого университета, протокол № ____ от______________ 2007 г.

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

Пособие предназначено для студентов специальностей 210100 – Управление и информатика в технических системах и 220400 – Программное обеспечение вычислительной техники и автоматизированных систем

.

.

УДК 519.1(075.8) ББК 22.176я73 Балабан Е.И. КИ МГОУ, 2007

Содержание

Введение. 4

1. Элементы теории множеств. 5

1.1. Множества и его элементы.. 5

1.2. Алгебра множеств. 6

1.3. Мощность множества. 7

1.4. Бинарные отошения. 10

1.5. Свойства отношений. 11

1.6. Отношения эквивалентности и разбиения. 12

2. Комбинаторика. 13

2.1. Перестановки и подстановки. 13

2.2. Размещения и сочетания. 13

2.3. Перестановки с повторениями. 15

2.4. Размещения и сочетания с повторениями. 15

2.5.Комбинированные задачи. 16

3. Элементы теории графов. 19

3.1. Виды и способы задания графов. 19

3.2. Нахождение кратчайших маршрутов. 23

3.3. Обходы графов. 26

3.4. Разрезы. Задача о максимальном потоке. 28

4. Алгебра логики.. 29

4.1. Функции и формулы алгебры логики. 29

4.2. Дизъюнктивные и конъюнктивные нормальные формы.. 31

4.3. Минимизация булевых функций. 31

4.4. Полные системы булевых функций. 35

4.5. Анализ и синтез логических сетей. 36

Список литературы.. 39

Введение

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

Для изучения необходимого теоретического материала, а также методов и примеров решения задач решения требует от студентов обращения к фундаментальным учебным пособиям [1]-[7] и конспекту лекций.

Элементы теории множеств

Множества и его элементы

1. Укажите множество действительных чисел, соответствующих записи:

а) А = {х| Зх-2 > 0};

б) В={х| х² + х+ 1 >0};

в) Х= {х| -3 <х< 9, х ÎZ};

г) М={х | 5<х<6, х Î N};

д) С = {х | х² -5х+6=0};

е) Y= {x| х² -5х+6£ 0}.

2. Опишите множество М точек плоскости, заданных характеристическим свойством:

а) Х= {М |АМ| < 4};

б) А = {М |МО| ³ 5};

в) В = {М |МК| =|МQ|};

г) Y={M| |AМ|=|МB| =|МC|};

д) C={M | MK| + |ML|£ 6};

е) Z={M | MQ| =| MP|=3}.

3. Дано множество М_i:

а) M₁={n² +1│n N} ;

б) M₂={ n^3. - 2│ n N};

в) M₃={ 1/n │n N};

г) M₄={ 1/n² │n N};

д) M₅={ 1/(n+1)│n N};

е) M₆={ 1/(2+n²)│n N}.

Приведите по три примера элементов каждого из множеств М_i.Укажите, каким из множеств принадлежат, а каким не принадлежат числа 3, 4, 5, 13, 25, 1/9, 1/6,1/4. Запишите эти утверждения символически.

4. Задайте характеристическим свойством множество:

а) всех параллелограммов;

б) всех прямоугольников;

в) всех квадратов;

г) всех равнобедренных треугольников;

д) всех ромбов;

е) всех прямоугольных треугольников.

5. Дано множество А = {а, b, с, {a, b}, {a}, {a, b, с, d}, {a, b, с}}. Какие из следующих записей верны:

а) а ÎА;

б) {а}ÎА;

в) а A;

г) {а} А;

д) {а, b, с, d} A;

е) {а, b, с, d}Î A?

6. Пусть X – множество {1, 2}, a Y - множество {х: х = y+z; y,z Î X}. Определить в явном виде (списком) множество Y. Каковы множества Y`= {у: у =x+z; х, zÎХ}и Y``= {у: х= y+z;x,zÎX}?

7. Задать различными способами множество М₂nвсех чисел, являющихся степенями двойки: 2,4, 8,16,..., не превышающих 300?

8. Задать различными способами множество натуральных чисел, кратных пяти: 5,10,15,20,...

9. Задать в явном виде (списком) множество β(U) всех подмножеств множества U, если U= {1,2, 5,7}.

Алгебра множеств

10. Пусть А = {1, 2}, В = {2, 3}, С= {1, 3}. Найти и изобразить их диаграммами Эйлера-Венна:

а) А B C;

б) А B C;

в) A \ (B C);

г) (A \ B) C;

д) (А B) \ (А B);

е) (А B) ∆ (B C).

11. Пусть U= {а, b, с, d},X= {а, с}, Y= {а, b, d},Z= {b, с}. Найти множества и изобразить их диаграммами Эйлера-Венна:

а) ;

б) (X Z) ;

в) X (Y Z);

г) (X Y) (X Z) ;

д) ;

е) ;

ж) ;

з) (X Y) Z ;

и) X (Y Z );

к) X \ ;

л) (X \ Y) ( Y \ Z);

м) (X ∆ Y) ( Y ∆ Z);

н) (X ∆ Z) ( Y ∆ Z);.

12. На множестве U всех букв русского алфавита заданы множества А, В, С: А = {ё, к, л, м, н}; В = {к, о, з, ё, л}; С = {б, ы, ч, о, к}. Найдите следующие множества и изобразите их диаграммами Эйлера-Венна:

а) АÇВ; в) ( АÇВ ) ÈС; д) D = U \ (AÈBÈ С);

б) AÈ В; г) (AÈC) Ç B; е) D = U \ (AÇBÇ С )

13. Даны отрезки А = [-4; 5], В = (2; 6], С = (5; 10]. Найдите следующие множества и изобразите их диаграммами Эйлера-Венна:

a) (AÈ В) È С; в) A Ç B; д) (СÈВ) \ (АÇВ);

б) (AÇ В) È С; г) (AÈ В) \(AÇ В); е) ((AÈ С ) \ (AÇ В).

14. Докажите, используя определения и диаграммы Эйлера-Венна:

а) AÇ(AÈB) = A; б) AÈ (AÇB) = A

15. Докажите тождества:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж);

з) ;

и);

к) ;

л) ;

м) .

16. Пусть [0,1], [0,2] — отрезки на числовой прямой. Дать геометрическую интерпретацию множеств [0,1] ´[0,2], [0,1]², [0,2]³.

17. Пусть X= {0, 1 }, Y= {а, b}. Найти Х´Y, Y´X, Х², Х´Y´Х.

18. Пусть Х= {а, с}, Y= {a, d, f}. Найти Х´Y, Y´X, Y², Y´Х´Y.

Мощность множества

19. Выполните действия и определите мощность полученного множества:

а) А = {5, 7, 9} È{12, 15}, В = {5, 7, 9} Ç{12, 15};

б) А = {5, 7, 9} Ç{5, 57, 59}, В = {5, 7, 9} È{5, 57, 59};

в) {1, 2, 3} \ {2, 3};

г) {1, 2, 3} \ {4, 5};

д) {х² + у² £1} \ {х² + у² = 1}.

20. Задать в явном виде (списком) множество β(U) всех подмножеств множества U, если U= {a, b, c, d}. Какова мощность множеств U, β(U)?

21. Пусть А – алфавит, т.е. конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т.д.). Словом длины n в алфавите А (обозначается последовательностью из n символов без скобок и запятых) называют любой элемент множества Аⁿ. Множество всех слов в алфавите - это множество А ^* = А ¹ ÈА ² ÈА ³ È… . Пусть алфавит А состоит из трех символов, например, А ={a, b, c}. Определить мощность множества всех слов длины 1, 2, 3, 4 в этом алфавите.

22. В книжном шкафу стоят девятитомник Ф.Купера, восьмитомник, В.Скотта, шеститомник М.Рида и пятитомник Р.Кипнинга. Сережа выбирает одну книгу для внеклассного чтения. Сколькими способами он может это сделать?

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

24. Лекции по физике посещают 20 студентов, а лекции по астрономии – 30. Сколько студентов посещают лекции по физике или астрономии, если: а) эти лекции происходят в одно и то же время; б) эти лекции происходят в различное время и 10 студентов слушают оба курса?

25. Решите задачу Льюиса Кэрролла, автора книг «Алиса в стране чудес» и «Алиса в Зазеркалье»: «В ожесточенном бою из 100 пиратов потеряли по одному глазу — 70, по одному уху — 75, по одной руке — 80, по одной ноге — 85 пиратов. Каково минимальное число пиратов, потерявших одновременно глаз, ухо, ногу и руку?»

26. В классе обучаются 42 ученика. Из них 16 участвуют в секции по легкой атлетике, 24 – в футбольной секции, 15 – в шахматной секции, 11 – и в секции по легкой атлетике и в футбольной, 8 – и легкоатлетической и в шахматной, а 6 – во всех трех секциях. Остальные школьники увлекаются только туризмом. Сколько школьников являются туристами?

27. Из 67 студентов 47 знают английский, 35 – немецкий, 23 – оба языка. Сколько студентов не знает ни одного языка? Сколько только немецкий? Сколько только английский?

28. Из 100 студентов 28 знают английский, 30 – немецкий, 42 - французский, 8 - английский и немецкий, 10 – английский и французский, 5 – немецкий B французский, 3 – все три языка. Сколько студентов не знают ни одного языка?

29. Каждый студент либо девушка, либо блондин, либо любит математику. На курсе 20 девушек, 12 блондинок, из которых одна девушка любит математику. Всего 34 блондина, из них 12 любят математику. Всего на курсе любящих математику – 24, из них 6 девушек. Сколько студентов на курсе?

30. Из 35 студентов, побывших на каникулах в Москве, все, кроме двоих, делились впечатлениями. О посещении Большого театра с восторгом вспоминали 14 человек, Кремля – 15, а 17 – о концерте. Пятеро студентов запомнили посещение театра и Кремля, шестеро – театра и концерта, четверо – концерта и пребывания в Кремле.

а) Сколько студентов сохранили воспоминания одновременно о театре, концерте и Кремле?

б) Сколько студентов сохранили воспоминания о посещении театра, но не вспоминали о посещении Кремля?

в) Сколько студентов вспоминали о посещении либо концерта, либо театра?

г) Сколько студентов делилось впечатлениями только о посещении Кремля?

д) Сколько студентов не вспоминало о посещении Кремля?

31. Доказать, что:

а) если А – конечное множество, В –подмножество множества А, то множество В конечно;

б) если A₁,...,A_n – конечные множества, то множества A₁ÈА₂È …ÈА_п и A₁´А₂´ …´А_п конечны.

32. Доказать, что если А –счетное множество, В –конечное множество, то множество А \ В счётно.

33. Доказать, что множество всех многочленов от одной переменной с рациональными коэффициентами счётно.

Бинарные отошения

34. Объясните, будут ли выполнимы свойства отношений на заданном множестве людей и почему:

а) «быть знакомым»;

г) «встречаться»;

б) «быть отцом»;

д) «быть другом»;

в) «поздравлять с праздником»;

е) «быть ровесником».

35. Существует ли взаимно-однозначное соответствие между:

а) множеством букв и множеством звуков русского языка;

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

в) множеством чисел и множеством студентов вашей группы;

г) словом на русском языке и его значением;

д) автором и литературным произведением;

е) названием и музыкальным произведением

36. Пусть М= {1,2,3,4,5,6}. Задать в явном виде (списком) и матрицей отношение RÍM´M, если R означает - "быть строго меньше".

37. Пусть М= {1, 2, 3, 4, 5, 6}. Составить матрицы отношения R₁, R₂, R₃ ÍM´M´M, если:

а) R₁- "быть делителем";

б) R₂- "иметь общий делитель, отличный от единицы";

в) R₃ - "иметь один и тот же остаток от деления на 3".

38. Составить матрицы отношений, заданных на системе множеств β(М), М= {а, b, с}:

а) R₁ – «пересекаться с» (иметь непустое, пересечение);

б) R₂ – «являться строгим включением».

39. Пусть отношение R задано на М= { 1 , 2, 3, ..., 9} . Выписать все элементы R, если:

a) R = {(а, b)}: а,bÎ М; (а + 1) -делитель (а + b)};

6) R = {(a, b)}: a, bÎ М; а - делитель (а + b), а ¹ 1}.

Свойства отношений

В задачах 41-45 исследовать отношения на рефлексивность, антирефлексивность, симметричности, антисимметричность и транзитивность.

40. Каковы свойства отношений, заданных на множестве натуральных чисел N:

а) R₁ – «быть не больше»;

б) R₂ – «быть делителем»;

в) R₃ – «быть равным»;

г) R₄ – «быть меньше»;

д) R₅ – «иметь один и тот же остаток от деления на 5»;

е) R₆ – «иметь общий делитель, отличный от единицы».

41. Каковы свойства отношений, заданных на множестве точек координатной плоскости R´R:

а) R₇ – «находиться на одинаковом расстоянии от начала координат»;

б) R₈ – «быть симметричным относительно оси X».

42. Каковы свойства отношений, заданных на системе множеств β(М):

а) R₉ – «пересекаться с» (иметь непустое пересечение);

б) R₁₀ – «являться строгим включением»;

в) R₁₁– «являться нестрогим включением»;

г) R₁₂ – «быть дополнением к».

43. Каковы свойства отношений, заданных на множестве людей:

а) R₁₃ – «быть сыном»;

б) R₁₄ – «жить в одном городе»;

в) R₁₅– «быть моложе»;

г) R₁₆ – «быть знакомым».

44. Составить матрицы отношений, заданных в задачах 37-40, определив произвольно множество М, RÍM´M таким образом, чтобы по матрице отношений можно было судить о свойствах отношений.