Раздел 2. Отношения

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

По выполнению контрольной работы по дисциплине

«Дискретная математика»

Направление подготовки:

050100.62 Педагогическое образование

Профиль подготовки: Информатика

Квалификация выпускника: бакалавр

Бузулук 2012

Оглавление

Рекомендации по выполнению и оформлению контрольной работы.. 3

Контрольные задания по курсу "Дискретная математика ". 4

Содержание разделов, изучаемых в семестре. 16

Материалы для самоподготовки. 18

Вопросы для самоконтроля. 91

Тесты для самоконтроля. 92

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

Основная литература. 99

Дополнительная литература. 99

Приложение 1. 100

Рекомендации по выполнению и оформлению контрольной работы

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

Если студент испытывает затруднения в усвоении теоретического или практического материала, то он может получить устную консультацию у преподавателя (13³⁰ до 14³⁰ ч., по понедельникам; адрес: ул. 1 Мая, 31, каб. 11).

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

Контрольная работа выполняется в тетради. На тетрадь наклеивается титульный лист в формате А5, образец которого приведен в Приложении 1. Задания записываются в той же последовательности, что и в условиях задач. Замечания и недоработки устраняются в той же тетради после рецензии преподавателя. Исправленная работа отправляется на повторную рецензию.

Работа выполняется только в рукописном варианте

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

Раздел1. Множества

Вариант № 1

1. Все грибники вернулись домой с полными корзинами. У десятерых из них в корзинах были белые грибы, у восемнадцати – подберезовики, у двенадцати – лисички. Белые и подберезовики были в шести корзинах, белые и лисички – в четырех, Подберезовики и лисички – в пяти. Все три вида грибов были у двух грибников. Сколько было грибников?

2. Верно или неверно равенство: (A È B) \ (A B) = A È B?

3. Доказать, что множество точек A = {(x, y): y = ½ x ½, – 1 £ x £ 1} несчетно.

4. Нарисовать диаграмму Эйлера-Венна для множества (B È C).

5. Пусть A – множество точек отрезка [0, 1], а B – множество всех точек числовой оси. Какие из следующих отношений справедливы: а) A = B; б) A ~ B; в) A ÉB; г) A ÊB; д) A ËB; е) A Î B.

Вариант № 2

1. Все туристы взяли в поход консервы. Шесть человек взяли тушенку, пять – сгущенку, восемь – кашу (с мясом). У троих в рюкзаках была тушенка и сгущенка, у двоих – тушенка и каша, у троих – сгущенка и каша, и только в одном рюкзаке лежали все три вида консервов. Сколько было туристов?

2. Верно или неверно равенство: С = С \ (С (A È B))?

3. Пусть A – множество решений уравнения x ² – 3 x + 2 = 0. Записать это множество двумя различными способами.

4. Нарисовать диаграмму Эйлера-Венна для множества (B C) \ A.

5. Эквивалентны ли множества A = { x: x ² –3 x + 2 = 0} и B = {2, 3}?

Вариант № 3

1. Было опрошено 70 человек. В результате опроса выяснили, что 45 человек знают английский язык, 29 – немецкий и 9 – оба языка. Сколько человек из опрошенных не знает ни английского, ни немецкого языков?

2. Верно или неверно равенство: (A È B) \ (A B) = A È B?

3. Найти все подмножества множества A = { x, y, z }.

4. Нарисовать диаграмму Эйлера-Венна для множества С.

5. Счетно ли множество {(x, y): y = 3 ^x, 0< x < ¥}?

Вариант № 4

1. В туристической группе 10 человек знают английский язык, 10 – итальянский, 6 – испанский. По два языка знают: 6 человек – английский и итальянский, 4 – английский и испанский, 3 – итальянский и испанский. Один человек знает все три языка. Сколько туристов в группе?

2. Упростить .

3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Нарисовать диаграмму Эйлера-Венна для множества С \ (С (AÈB)).

5. Эквивалентны ли множества A = { 2 ⁿ, n = 1, 2, …} и B = { n ², n = 1, 2, …}?

Вариант № 5

1. Предприятие объявило набор рабочих на должности токаря, слесаря и сварщика. В отдел кадров обратились 25 человек. Из них 10 человек владели профессией токаря, 15 – слесаря, 12 – сварщика. Профессией и токаря и слесаря владели 6 человек, и токаря, и сварщика – 5 человек, и слесаря и сварщика – 3 человека. Сколько человек владеют всеми тремя профессиями?

2. Верно или неверно равенство: \ = \ ?

3. Привести примеры множеств А, В и С, для которых одновременно выполняются равенства А È В È С = А и А В С = С.

4. Нарисовать диаграмму Эйлера-Венна для множества \ .

5. Можно ли построить взаимно-однозначное соответствие между множеством рациональных чисел отрезка [0, 1] и множеством рациональных чисел из этого интервала? Ответ обосновать.

Вариант № 6

1. Оказалось, что в группе туристов 15 человек были раньше во Франции, 19 – в Италии, 8 – в Германии. 9 туристов были во Франции и в Италии, 7 – во Франции и в Германии, 6 – и в Италии, и в Германии. 4 туриста были во всех трех странах. Сколько туристов были хотя бы в одной из трех стран?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В  С) = (А \ В)  ?

3. Привести примеры множеств А и В, для которых равенство È В =

а) выполняется; б) не выполняется.

4. Нарисовать диаграмму Эйлера-Венна для множества А (В È ).

5. Найти мощность множества точек окружности с центром в точке (0, 0) и радиусом 1.

Вариант № 7

1. Группе студентов из 30 человек была предложена контрольная работа из трех задач. Первую задачу решили 15 студентов, вторую – 13, третью – 12. Первую и вторую задачи решили 7 человек, первую и третью – 6, вторую и третью – 5 человек. Все три задачи решили 2 студента. Сколько студентов из группы не решили ни одной задачи?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В È С) = (А \ В) ?

3. Привести пример двух бесконечных множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Нарисовать диаграмму Эйлера-Венна для множества А В .

5. Найти мощность множества точек гиперболы y = при x Î (3, ¥).

Вариант № 8

1. Анализ историй болезней группы из 20 детей показало, что 10 детей болели ветрянкой, 6 – корью, 5 – свинкой. Ветрянкой и корью болели 3 ребенка, ветрянкой и свинкой – 3, корью и свинкой – 2. Всеми тремя болезнями болел один ребенок. Сколько детей не болели ни одной из перечисленных болезней?

2. Верно или неверно равенство: С) = С?

3. Доказать, что множество точек A = {(x, y): y = ½ x +1½, – 1 £ x £ 1} несчетно.

4. Нарисовать диаграмму Эйлера-Венна для множества (B C) \ A.

5. Пусть A – множество точек отрезка [1, 2], а B – множество точек интервала (0, 3). Какие из следующих отношений справедливы: а) A = B; б) A ~ B; в) A Ì B; г) A Ê B; д) A ËB; е) A Î B.

Вариант № 9

1. В книжный киоск привезли для продажи 100 книг Пушкина, Лермонтова и Тургенева. Книги Пушкина купили 60 человек, книги Лермонтова – 50, книги Тургенева – 30 человек. Книги Пушкина и Лермонтова купили 40 человек, книги Пушкина и Тургенева – 20, книги Лермонтова и Тургенева – 10 человек. Пять человек купили книги всех трех писателей. Сколько человек не купили ни одной из перечисленных книг?

2. Верно или неверно равенство: \ = \ ?

3. Привести примеры множеств А, В и С таких, что равенство А È В È С = С

а) справедливо; б) несправедливо.

4. Нарисовать диаграмму Эйлера-Венна для множества \ .

5. Можно ли построить взаимно-однозначное соответствие между множеством натуральных чисел N и множеством действительных чисел отрезка [0, 1]? Ответ обосновать.

Вариант № 10

1. Группа научных работников состоит из 100 человек. Из них 70 человек владеют английским языком, 50 – немецким, 40 – французским, 30 – английским и немецким, 25 – английским и французским, 15 – французским и немецким. Хотя бы один язык знает каждый научный работник. Сколько человек владеют всеми тремя языками?

2. Упростить: (A \ (A B)) È В.

3. Привести примеры множеств А, В и С так, чтобы A Î B, В Ì С.

4. Нарисовать диаграмму Эйлера-Венна для множества \ .

5. Можно ли утверждать, что множество всех положительных пятизначных чисел счетно? Ответ обосновать.

Раздел 2. Отношения

Вариант № 1.

Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 3>, <4, 4>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не рефлексивного, не симметричного и не транзитивного.

3. Дана функция f (x) = x ³ e^x, отображающая множество действительных чисел R во множество действительных чисел, R ® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 2.

Задано бинарное отношение r = {<1, 3>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения частичного порядка на множестве треугольников на плоскости.

3. Привести пример функции f (x), отображающей множество действительных чисел R во множество действительных чисел, R ® R и не являющейся сюръективной, инъективной, биективной.

Вариант № 3.

Задано бинарное отношение r = {<1, 2>, <2, 2>, <2, 1>, <2, 3>, <3, 2>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x = – y?

3. Дана функция f (x) = lnx + , отображающая множество положительных действительных чисел во множество всех действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 4

Задано бинарное отношение r = {<1, 1>, <2, 2>, <2, 1>, <2, 3>, <3, 2>, <3, 3>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Будет ли отношением частичного полрядка на множестве действительных чисел отношение xry, задаваемое неравенством x ² – y ² £ 0?

3. Дана функция f (x) = e^x + , отображающая множество положительных действительных чисел на множество положительных действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 5.

Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 1>, <3, 2> <1, 3>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.

3. Привести пример функции f (x), отображающей множество действительных чисел R во множество неотрицательных действительных чисел, R ® [0, ¥) и являющейся сюръективной, но не инъективной.

Вариант № 6

Задано бинарное отношение r = {<1, 2>, <2, 1>, <2, 3>, <1, 3>, <3, 1>, <3, 2>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое неравенством x £ y?

3. Дана функция f (x) = lnx + 2 x, отображающая множество действительных чисел R во множество действительных чисел, R ® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 7.

Задано бинарное отношение r = {<2, 2>, <2, 4>, <1, 4>, <4, 1>, <4, 2>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не транзитивного, не рефлексивного и не симметричного.

3. Привести пример функции f (x), отображающей множество действительных чисел R во множество действительных чисел, R ® R и являющейся сюръективной и неинъективной.

Вариант № 8.

Задано бинарное отношение r = {<1, 1>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством xy = 100?

3. Привести пример функции f (x), отображающей множество действительных чисел R во множество действительных чисел, R ® R и не являющейся сюръективной, инъективной, биективной.

Вариант № 9.

Задано бинарное отношение r = {<1, 1>, <2, 2>, <3, 3>, <3, 1>, <1, 3>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.

3. Привести пример функции f (x), отображающей множество действительных чисел R во множество действительных чисел, R ® R и являющейся сюръективной, но не инъективной.

Вариант № 10.

Задано бинарное отношение r = {<1, 1>, <2, 2>, <4, 4>, <2, 1>, <2, 4>, <4, 2>}.

Найти D (r), R (r), r r, r ^-1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения частичного порядка.

3. Дана функция f (x) = x ² , отображающая множество действительных чисел R во множество действительных чисел, R ® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?