Дискретная_математика-Сборник_задач

УДК 519.1 (075.8)

Работа выполнена на кафедре автоматизированных систем управления для студентов I курса заочного факультета и II курса Института социальной реабилитации НГТУ, обучающихся по направлению бакалаврской подготовки

230100 – Информатика и вычислительная техника

Ренин, С.В.

Дискретная математика. Сборник задач и упражнений. – Новосибирск: 2013.

Сборник содержит задачи и упражнения по первым разделам курса "Спецгла-

вы математики", а именно, по теории множеств, теории графов и комбинаторике, и

предназначается студентам заочного факультета и Института социальной реабили-

тации НГТУ, обучающимся по направлению 230100 "Информатика и вычисли-

тельная техника", для использования при выполнении контрольных работ, подго-

товке к практическим занятиям и при самостоятельной работе над курсом.

УДК 519.1 (075.8)

© С.В. Ренин, 2013

© Новосибирский государственный технический университет, 2013 г.

Курс "Дискретная математика" призван дать студентам знания в области ма-

тематических методов, необходимых для освоения ряда дисциплин учебного плана для направления "Информатика и вычислительная техника". В результате изучения курса студенты должны, в частности, овладеть основными понятиями и методами теории множеств, теории графов и комбинаторного анализа, а также получить твердые навыки решения задач, относящихся к указанным разделам математики.

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

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

предназначенными для решения на практических занятиях, а также для самостоя-

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

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

дач. Задачник рассчитан на использование совместно с конспектом лекций [1]. При составлении сборника были частично использованы задачи из литературных ис-

точников, приведенных в конце пособия.

-3-

1. МНОЖЕСТВА. ОТНОШЕНИЯ НА МНОЖЕСТВАХ

Для решения задач из этого раздела необходимо проработать материал, изло-

женный в [1] на стр. 4 – 34. В тексте задач использованы следующие обозначения:

N – множество натуральных чисел;

Z – множество целых чисел;

Q – множество рациональных чисел;

E – множество вещественных чисел.

Пример 1.1. Используя диаграммы Эйлера-Венна, показать справедливость равенства A \ B A B .

Решение. Изобразим с помощью диаграмм Эйлера-Венна левую и правую части этого равенства:

Рис. 1.1 Рис. 1.2

На рис. 1.1 заштриховано изображение левой части равенства (A\B). На рис. 1.2 штриховкой с наклоном вправо выделено множество A, а штриховкой с накло-

ном влево – дополнение множества B. Правой части равенства ( A B ) соответст-

вует двойная штриховка. Из сопоставления рисунков видно, что фигуры, изобра-

жающие A\B и A B , одинаковы, что и требовалось показать.

Пример 1.2. Используя основные тождественные соотношения алгебры мно-

жеств ([1], стр. 14-15) и равенство из примера 1.1, упростить следующее выраже-

ние: ((A B С) (A B)) \ ((A (B \ C)) A) .

Решение.

((A B С) ( A B)) \ (( A (B \ C)) A) ( A B) \ A (A B) A

Цифрами здесь обозначено, какие тождественные соотношения применены для преобразования соответствующих частей формул: 1 и 2 – первый закон погло-

щения; 3 – соотношение из примера 1.1; 4 – первый дистрибутивный закон; 5 – тождественное соотношение 15 ([1], стр. 15); 6 – соотношение из примера 1.1;

7 – тождественное соотношение 16 ([1], стр. 15).

ЗАДАЧИ

1.1.Перечислите все элементы и все подмножества множества {1,2,{3,4}}.

1.2.Пусть A – множество букв русского алфавита. Укажите среди следующих вы-

сказываний истинные: а) б A; б) ю A; в) z A; г) t A; д) 33 A.

1.3.Укажите, какие из следующих утверждений справедливы:

1.4.Известно, что A B C и x C. Верно ли, что: а) x A; б) x B; в) x A; г) x B;

д) x A и x B; е) x A и x B?

1.5.Известно, что A B C и x C. Можно ли на основании этого утверждать, что:

а) x A; б) x B; в) x A; г) x B; д) x A или x B; е) x A и x B?

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

а) (А В) С = (А С) (В С); б) (А В) С = (А С) (В С);

в) A B A B ; г) A B A B .

1.7.Упростите следующие выражения, если A B: а) A B ; б) A B ; в) A\B.

1.8.A – множество прямоугольников; B – множество квадратов. Установите, в ка-

ком отношении находятся эти множества, изобразите их с помощью диаграмм Эйлера-Венна и среди следующих высказываний укажите истинные:

а) A B – множество квадратов; б) A B – множество прямоугольников;

в) A B – множество квадратов; г) A B – множество прямоугольников.

-5-

1.9.Запишите результаты объединения, пересечения и разности множеств A и B

(для вычитания – A\B и B\A), если:

а) A = {k, l, f, t, u}, B = {k, l, m, n, o, p};

б) A = {6, 3, 2, 5, 13}, B = {13, 3, 2, 5, 6};

в) A = {5, 10, 15, 20, 25, 30}, B = {10, 20, 30}.

1.10.Используя свойства операций над множествами, упростите выражения:

а) (A B) B ; б) (A B) B ; в) (A B) A; г) (A B) B ;

д) (A B) (A B) .

1.11.Был проведен опрос группы телезрителей, чтобы выяснить их реакцию на од-

ну из передач. Результаты опроса приведены в следующей таблице:

Обозначим: М – множество зрителей мужского пола; В – множество взрослых телезрителей; П – множество телезрителей, которым передача понравилась; О – множество телезрителей, которым передача очень понравилась или очень не понравилась.

Дайте содержательное описание следующих множеств и определите, сколько элементов входит в каждое из них:

а) М ; б) П; в) О; г) М В П; д) М В П; е) (М В) (П О); ж) М В; з) М В; и) М \ В; к) М \ (В П О) ?

1.12.При опросе 100 студентов колледжа были получены данные о девушках, с

которыми они знакомы, приведенные в следующей таблице:

Обозначим: БЛ – блондинки; БР – брюнетки; РЖ – рыжие; КР – красивые;

ГЛ – глупые.

Дайте содержательное описание следующих множеств и определите, сколько элементов входит в каждое из них: а) БЛ КР ГЛ; б) БР; в) РЖ ГЛ;

г) (БР РЖ) (КР ГЛ ); д) БЛ (КР ГЛ).

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

а) БЛ БР или РЖ; б) ГЛ КР или БЛ \ (ГГ КР) ; в) или РЖ КР ГЛ .

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

a) Z Q; б) Z E; в) E \ Q; г) Z \ Q; д) Z \ E;

е) A B, A B, A \ B, если A {x | x 2 y, y Z}, B {x | x 3y, y Z};

ж){x|x 10 y, y Z} \{x | x 5y, y Z}?

1.15.Пусть A – множество всех решений уравнения sin x = 1, а B – множество всех чисел вида /2 ± k , где k Z. Найдите объединение, пересечение и разность этих множеств.

1.16. Изобразите на координатной плоскости элементы множества Х Y, если:

а) X = {x | x N, x = 3}, Y = {y | y E, 3 y 6};

б) X = {x | x E, 1 x 3}, Y = {y | y N, y = 3};

в) X = {x | x N, x 3}, Y = {y | y E, 3 y 6};

г) X = {x | x E, 1 x 3}, Y = { y | y N, y 3}.

1.17.Пусть [a, b], [c, d] – отрезки действительной прямой. Дайте геометрическую интерпретацию множеств: а) [a, b] [c, d]; б) [a, b]2; в) [a, b]3.

1.18.Дайте геометрическую интерпретацию множества A B , где

A= {(x, y)| | x | 4; | y | 4; x, y E}; B = {(x, y)| x2 + y2 25; x, y E}.

1.19.Используя основные тождественные соотношения алгебры множеств, упро-

стите выражения:

а) ((A C) (B D)) \ ((A B) (C D));

б) (A\C) \ ((A\B) (B\C));

-7-

в) ((A\C) \ ((B\C) \ (B\A))) C;

г) ((A B) \ C) \ (A (B\C));

д) (((A B C) ( A B)) \ (( A (C\B)) A)) B;

е) (A C (A\B) (C\B)) \ (A C);

ж) ( A C ( A\B) (C\B)) \ ( A C);

з) ((A B C) (A B C)) (B C);

и) ( A B C D) ( A C) (B C) (C D);

к) A\B ( A B);

1.20.Приведите известные вам соответствия между элементами следующих множеств:

а) множество людей и множество городов;

б) множество студентов и множество преподавателей;

в) множество треугольников и множество вещественных чисел;

г) множество треугольников и множество окружностей;

д) множество многоугольников и множество натуральных чисел.

Укажите, к какому типу относятся эти соответствия.

1.21. Представьте графически и в виде матрицы соответствие (X, Y, Q), если:

а) X = {2, 4, 6}, Y = {1, 3, 5}, Q = {(x, y)| x X; y Y; x > y};

б) X = {25, 16, 7, 6}, Y = {2, 5, 3, 9, 1}, Q = {(x, y)| x X; y Y; x делится на y без остатка};

в) X = {ромб, круг, куб, угол}, Y = {о, у, л, г, б, к, р, м}; Q = {(x, y)| x X; y Y; в слово х входит буква у};

г) X = {x1, x2, x3, x4}, Y = {y1,y2,y3,y4}, Q = {(x1,y4),(x2,y2),(x3,y3),(x4,y1)}.

Постройте соответствия, обратные данным.

1.22. Обратно ли соответствие «х – брат у» соответствию «у – сестра х», если:

а) X = Y – множество всех людей;

б) Х – множество мужчин; Y – множество женщин?

-8-

1.23.Что означает композиция соответствий (X, Y, R) и (Y, Z, S), если:

а) X – множество точек плоскости; Y – множество окружностей;

Z – множество треугольников, R = {(x, y)| точка х – центр окружности у};

S = {(y, z)| окружность у вписана в треугольник z};

б) X – множество деталей; Y – множество технологических операций;

Z – множество рабочих; R = {(x, y)| над деталью х выполняется операция у};

S = {(y, z)| операцию у выполняет рабочий z};

в) X – множество преподавателей университета; Y – множество читаемых дисциплин; Z – множество учебных групп; R = {(x, y)| преподаватель х ведет занятия по дисциплине у}; S = {(y, z)| дисциплина у преподается студентам группы z};

г) X – множество мужчин; Y – множество людей; Z – множество женщин;

R = {(x, y)| х – отец у}; S = {(y, z)| y – родитель z}?

Что означает для этих примеров соответствие (R○S)–1?

1.24.X = {x1, x2, x3, x4}, Y = {y1, y2, y3, y4}, Z = {z1, z2, z3}, R = {(x1, y2), (x2, y1), (x3, y1), (x3, y3)}; S = {(y1, z1), (y1, z2), (y2, z1), (y3, z3), (y4, z1)}.

Матричным и графическим способом найдите соответствия R○S, (R○S)–1,

S–1○R–1.

1.25.Для следующих соответствий найдите область определения, область значений и определите тип соответствия; сделайте то же самое для соответствий, об-

ратных заданным.

а) (N, Y, R), R N Y; Y – множество многочленов; N – множество натураль-

ных чисел; R = {(n, y)| n – степень многочлена у};

б) (С, E, R), C – множество комплексных чисел; Е – множество действитель-

ных чисел; R = {(х, у)| x C; y E; модуль х равен у};

в) (Х Y, P, S), S (Х Y) Z; X – множество прямых на плоскости, параллель-

ных заданной прямой ; Y – множество прямых на той же плоскости, не па-

раллельных ; P – множество точек этой плоскости;

S = {((x, y), p)| прямая х Х пересекается с прямой у Y в точке p P}.

-9-

1.26.Пусть A – множество всех слов английского языка, B – множество всех слов русского языка. Англо-русский словарь определяет некоторое соответствие между словами этих языков. Является ли это соответствие отображением?

функцией?

1.27.Пусть A – множество слов английского языка, содержащихся в некотором англо-русском словаре, B – множество слов русского языка, содержащихся в этом словаре. Является ли соответствие между словами английского и рус-

ского языков, определяемое этим словарем, отображением? функцией? Если это отображение, то будет ли оно отображением A на B или отображением A

в B?

1.28.Известно, что с помощью азбуки Морзе, состоящей из всевозможных комби-

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

щее все буквы русского алфавита, цифры и знаки препинания, передаваемые с помощью азбуки Морзе, а B – множество всех возможных комбинаций точек и тире в азбуке Морзе. Является ли соответствие между множествами A и B

отображением? функцией? Если это отображение, то будет ли оно отображе-

нием A на B или отображением A в B?

1.29. Назовите известные вам отношения на следующих множествах:

а) множество натуральных чисел;

б) множество треугольников;

в) множество государств;

г) множество морей;

д) множество людей;

е) множество уравнений.

Какими свойствами обладают эти отношения, к какому виду относятся?

1.30. Найдите область определения и область значений для отношений «быть от-

цом» и «быть братом» на множестве людей.

1.31.Запишите график R следующих отношений, заданных на множестве

Х = {0, 2, 4, 6, 8, 9}. Дайте их графическое и матричное представление, найди-

-10-