Задания

СОДЕРЖАНИЕ

Задание 1. 3

Задание 2. 4

Задание 4. 4

Задание 6. 4

Задание 8. 4

Задание 9. 4

Задание 11. 4

Задание 13. 4

Задание 14. 4

Задание 15. 4

Литература. 4

Задание 1

Для заданных множеств

найдите мощность следующих множеств:

.

Решение

Пусть А, В – произвольные множества.

Объединением двух множеств А и В называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств. Обозначение: .

Пересечением двух множеств А и B называется множество, состоящее из всех элементов, принадлежащих одновременно обоим множествам. Обозначение: .

Разностью множеств А и В (дополнением множества В до множества А или, иначе говоря, А без В) называется множество всех элементов множества А, не принадлежащих множеству В. Обозначение: .

Дополнением (до универсального множества U) множества А называется множество всех элементов, не принадлежащих множеству А. Обозначение: . В некоторых случаях запись означает разность не с универсальным множеством, а с множеством, определенным в условии задачи как множество, содержащее А.

Симметрической разностью (или кольцевой суммой) множеств А и В называется множество, состоящее из всех элементов, принадлежащих в точности одному из множеств А или В, т. е.

.

Используя эти определения, находим элементы искомых множеств:

Число элементов в конечном множестве называется его мощностью. Обозначение: m(A) или |A|.

Находим мощности найденных множеств:

.

Ответ: .

Задание 2

Докажите тождество с помощью диаграмм Эйлера-Венна.

Решение

Построим множество , соответствующее левой части заданного тождества.

Последовательно показываем:

:

:

Построим множество , соответствующее правой части заданного тождества.

Последовательно показываем:

:

:

:

Множества и совпадают, поэтому равенство является тождеством.

Ответ: равенство является тождеством.

Задание 4

Дано декартово произведение множеств . Выпишите множества А и D.

Решение

Декартовым или прямым произведением двух множеств А и В (обозначается А ´ В) называется множество всех таких упорядоченных пар (a, b), что a Î A и b Î В.

Исходя из этого произведения, делаем вывод, что множества А и D имеют вид:

.

Ответ: .

Задание 6

Отображение действует по правилу . Найдите образ .

Решение

Отрезок [0,3] можно представить как объединение двух множеств:

. Отрезок [0,2] отображается аналитическим выражением , поэтому . Полуинтервал (2,3] отображается аналитическим выражением , поэтому .

Окончательно, образ имеет следующий вид:

.

Ответ: .

Задание 8

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

«Регулярное выполнение домашних заданий есть необходимое и достаточное условие для того, чтобы я сдал этот экзамен».

Решение

Выделим простые высказывания Х=«регулярное выполнение домашних заданий», Y=«я сдам этот экзамен».

Исходное высказывание символически изображается как .

Составим таблицу истинности этого высказывания:

Х	Y
0	0	1
0	1	0
1	0	0
1	1	1

Ответ: , где Х=«регулярное выполнение домашних заданий», Y=«я сдам этот экзамен»

Задание 9

Определите вид логической формулы (тавтология, противоречие или выполнимая) :

а) с помощью таблицы истинности.

Решение

Составим таблицу истинности для заданной формулы

х	у
0	0	1	1	1	1
0	1	1	1	1	1
1	0	0	0	1	1
1	1	1	0	0	1

Поскольку формула принимает значение 1 («истина») при всех значениях входящих в нее переменных, то она является тавтологией или тождественно истинной.

Ответ: формула является тавтологией.

Задание 11

Три девочки – Роза, Маргарита и Анюта – представили на конкурс цветоводов корзины выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов.

Какие цветы вырастила каждая из девочек?

Решение

Решим эту задачу с помощью рассуждений.

Из высказывания девочки, вырастившей маргаритки, следует что:

– Аня вырастила не анютины глазки;

– Маргарита вырастила не маргаритки;

– Роза вырастила не розы.

Поскольку девочка, вырастившая маргаритки, обращалась к Розе, то Роза не вырастила маргаритки.

Таким образом, Роза вырастила анютины глазки.

Тогда Маргарита вырастила розы, а Анюта вырастила маргаритки.

Ответ: Роза вырастила анютины глазки, Маргарита вырастила розы, Анюта вырастила маргаритки.

Задание 13

Нарисуйте граф G(V,E) с множеством вершин и ребер .

Решение

Искомый граф может иметь вид, представленный на рис.1.

Рис.1

Ответ: искомый граф изображен на рис.1.

Задание 14

Даны графы G1 и G2. Выпишите для каждого графа множества вершин и ребер. Определите степень каждой вершины. Найдите матрицы смежности и инцидентности. Укажите для графа G1 какой-либо маршрут из вершины 1. Укажите для графа G2 подграфы.

Решение

Граф G1 является неориентированным, граф G2 – ориентированным. Выпишем для каждого графа множества вершин и ребер (дуг):

граф G1: , ;

граф G2: , .

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

Выписываем степени графов:

граф G1: ;

граф G2:

Построим матрицу смежности графа G1. Данный граф является неориентированным, имеет 3 вершины, поэтому матрица смежности является квадратной матрицей 3-го порядка, в которой элемент матрицы aij равен количеству ребер, соединяющих i-ю и j-ю вершины. Получим матрицу смежности

Формируем матрицу инцидентности графа. Граф имеет 3 вершины и 4 ребра, поэтому матрица инциденций В является матрицей размерности 3х4. Заполняем таблицу по столбцам, соответствующим ребрам графа: в j-м столбце ставим i-й строке «1», если ребро (i;j) инцидентно вершине i и ставим «0», если ребро (i;j) не инцидентно вершине i.

Получим матрицу инциденций

Для построения матрицы смежности орграфа составим таблицу. Так как граф ориентированный, то элемент матрицы равен количеству дуг с началом в i-ой вершине, а концом в j-ой вершине.

Получим матрицу смежности:

.

Для построения матрицы инцидентности орграфа составим таблицу. Заполняем таблицу по столбцам, соответствующим дугам орграфа: в j-ом столбце ставим i-ой строке “-1”, если вершина i является началом дуги(i;j), ставим “1”, если вершина i является концом дуги (i;j) и ставим “0”, если вершина i и дуга (i;j) не инцидентны.

Получим матрицу инцидентности:

.

Чередующаяся последовательность вершин и ребер в графе (или только ребер), в которой любые два элемента инцидентны, называется маршрутом.

Укажем для графа G1 маршрут из вершины 1:

1,3,2.

Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).

Покажем пример подграфа для графа G2:

Задание 15

Из пункта А в пункт В можно доехать либо автобусом (4 рейса), либо самолетом (2 рейса). Сколько всего способов добраться до пункта В?

Решение

По правилу суммы в комбинаторике общее количество способов добраться до пункта В равно 4+2=6.

Ответ: 6 способов.

Литература

1.  1.Азарнова, указания для решения задач по курсу «Дискретная математика» / , . – Воронеж : Изд-во ВГУ, 2000. – 50 с.

2.  Акимов, математика: логика, группы, графы / . – М. : Лаборатория базовых знаний, 2001. – 352 с.

3.  Алексеев, задач по дискретной математике : задачник/ , , . – Н. Новгород : Нижегородский гос. ун-т, 2010. – 53 с.

4.  Андерсон, математика и комбинаторика / . – М. : Вильямс, 2004. – 960 с.

5.  Аристов, заданий и упражнений по дискретной математике : практикум / , . – Омск : Изд-во ОмГТУ, 2006. – 52 с.

6.  Балабко, математика. Алгебра логики (Алгебра высказываний) : метод. указания к выполнению самостоятельных и контрольных работ / . – Архангельск : Изд-во ФГАОУ ВПО «Северный (Арктический) федер. ун-т им. », 2011. – 42 с.

7.  Баранов, по дискретной математике / , , . – Ростов на/Д : Издат. центр ДГТУ, 2001. – 16 с.

8.  Белоусов, математика / , . М. : Изд-во МГТУ им. , 2004. – 744 с.

9.  Булгакова, математика. Элементы теории. Задачи и упражнения : учеб. пособие / , . – Воронеж :Изд-во ВГУ, 2004. – 62 с.

10.  Гаврилов, и упражнения по дискретной математике :учеб. пособие. – 3-е изд., перераб. / , . – М. :ФИЗМАТЛИТ, 2005. – 416 с.