Контрольная работа по дискретной математике

1.  а) Доказать  равенство (A\B) Ç (A\C) = A \ (BÈC)

В первом действии мы использовали тождество , во втором действии , в третьем действии использовали правило Моргана и тождество . В последнем действии снова использовали . 

На первом рисунке  горизонтальными линями изображено множество A\C, вертикальными множество A\B. Пересечение, т.е. (A\B) Ç (A\C) закрашено решеточкой.

На втором рисунке  более темным цветом (красным) изображено множество BÈC, светлым (желтым) изображено множество = A \ (BÈC).

По обоим рисункам видно графическое доказательство равенства (A\B) Ç (A\C) = A \ (BÈC)

б) Доказать равенство (AÇB)´C=(A´C)Ç(B´C).

 

2.  А={a,b,c}, B={1,2,3,4}; P₁ = {(a,1),(a,2),(b,3),(c,2),(c,3),(c,4)};  P₂ = {(1,1),(2,1),(2,2),(2,3),(2,4),(3,3),(4,4)}.

Изобразим P₁

Изобразим P₂

P₁ : область определения - {a,b,c}, область значений - {1,2,3,4}.

P₂ : область определения - {1,2,3,4}, область значений - {1,2,3,4}.

: область определения - {1,2,3,4}, область значений - {a,b,c}. 

Матрица :

По матрице видно, что отношение симметрично (на главной  диагонали только единицы), отношение  не симметрично, т.к. матрица не симметрична, отношение антисимметрично, т.к. при  транспонировании матрицы единицы, не стоящие на главной диагонали, все переходят на место нолей.

Для проверки транзитивности возведем матрицу в квадрат

Все элементы бывшее нулевыми в матрице, в новой матрице  также ноли, следовательно отношение транзитивно.

Отношение P₂ является отношением порядка.

3. P Í R², P = {(x,y) | x² + y² = 1}.

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

Отношение не  является рефлексивным, так как например (0,0) не принадлежит отношению.

Отношение является симметричным, так как если , то x² + y² = 1. Но тогда y² + x²  = 1, и следовательно .

Отношение не является антисимметричным, так как, например, точки (0,1) и (1,0) принадлежат отношению, хотя 0 не равен 1.

Отношение не является транзитивным, так как точки (0,1) и (1,0) принадлежат отношению, а точка (0,0) не принадлежит.

4. доказать математической  индукцией, что (7ⁿ – 1) кратно 6 для всех целых n ³ 1.

База индукции n = 1: кратно 6.

Индуктивный переход: предположим, что  и покажем, что также кратно 6.

.  Полученное выражение кратно 6. Доказательство завершено.

5. Необходимо разбить  группу из семи человек на 3 подгруппы, в каждой из которых  не менее 2 человек. Это означает, что будет две подгруппы по  два человека и одна подгруппа  из трех человек. Число вариантов,  какая из подгрупп будет из  трех человек (костровые, повара  или строители) равно  .

Число вариантов  выбора 3 человек из 7 (в любом порядке) равно  , число вариантов выбора следующей подгруппы из 2 человек из оставшихся четырех равно , число вариантов выбора последней подгруппы . Число вариантов разбиения на три подгруппы - вариантов.

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

6. НОК(6,9,15)=90 . Всякое натуральное число можно рассматривать в виде 90k+t, где t- принимает значение от 0 до 89. Число трехзначных чисел равно 999-99=900, - кратно 90. Это означает, что множество трехзначных чисел покрывается целым числом циклов длины 90 (всего 10 циклов). Поэтому нам достаточно исследовать на делимость остатки t, а затем полученное число умножать на 10.

а) число чисел  не делящихся ни на 6, ни на 9, ни на 15. Можно посчитать по формуле включений  и исключений. От числа всех t отнять число t, делящихся хотя бы на одно из чисел, прибавить число остатков t, делящихся хотя бы на два числа, и отнять число t, делящихся на все 3 числа.

Окончательно, число  трехзначных чисел не делящихся  ни на 6, ни на 9, ни на 15 равно 680.

б) число остатков, делящихся ровно на одно из этих чисел, равно число остатков t, делящихся хотя бы на одно из чисел минус число остатков t, делящихся хотя бы на два числа, умноженное на два (т.к. числа делящиеся ровно на два числа, мы посчитали два раза, а нам нужно чтобы они вообще не были посчитаны в сумме), плюс число остатков t, делящихся на три числа, умноженное на три (эти числа три раза были посчитаны со знаком плюс и 3*2 раз со знаком минус):

=

Окончательно, число  трехзначных чисел  делящихся  либо только на 6, любо только на 9, либо только на 15, равно 140.

7. Найти коэффициенты  при  a=x²·y²·z⁴,  b=x²·y·z³, c=x⁴·y²  в разложении (5·x+4·y+z²)⁶.

Переменная z может входить в мономы только в четной степени. Значит, коэффициент при мономе b равен 0.

Заменим для наглядности  z² на t. Тогда задача перепишется, как найти коэффициенты при a=x²·y²·t²,  c=x⁴·y²  в разложении (5·x+4·y+t)⁶. С помощью формулы мультиномиальных коэффициентов находим коэффициент при a:

С помощью формулы  мультиномиальных коэффициентов находим коэффициент при с:

8. Найти последовательность {a_n}, удовлетворяющую рекуррентному соотношению 2·a_n+2 + 5·a_n+1 + 3·a_n = 0· и начальным условиям   a₁=1, a₂=2.

Задача решается с применением производящего  экспоненциального ряда.

Составляется характеристическое уравнение последовательности:

.

Следовательно , . Коэффициенты a и b находятся из начальных условий:

Находим a=-7, b=4.

Получаем ответ  .

9.

А) Нарисуем граф

Б) Выделим компоненты сильной связности:

Из вершин 1 и 2 нельзя попасть ни в одну из других вершин, но при этом из 1 в 2 и из 2 в 1 есть дуги. Следовательно, первая компонента сильной  связности, - подграф образованный множеством вершин {1,2}.

В вершину 6 нельзя попасть ни из какой другой вершины. Следовательно, вторая компонента сильной связности, - подграф образованный множеством вершин {6}.

Вершины 3,4,5 образуют компоненту сильной связности, т.к. из любой из них существует путь в любую другую из них. Следовательно, третья компонента сильной связности, - подграф образованный множеством вершин {3,4,5}.

В) Изобразим граф, получающийся из ориентированного заменой дуг ребрами. Вершины 1 и 6 имеют порядок 3, вершина 2 имеет порядок 2, вершины 3,4 и 5 имеют порядок 4. Это означает, что в графе есть Эйлерова цепь, соединяющая вершины 1 и 6. Эйлеровых циклов нет.

На рисунке изображен  порядок обхода (красными цифрами) графа по Эйлеровой цепи, начинающейся в вершине 1.

10. Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса;   
б) кратчайшее расстояние от вершины v₁ до остальных вершин графа, используя алгоритм Дейкстры. 

Нарисуем граф

А) остовное дерево строится по алгоритму Краскала. Шаги алгоритма изображены на рисунках.

 

На последнем рисунке  полученное остовное дерево минимального веса. Добавление любого ребра приведет к появлению цикла.

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

Вес вершины v1 принимаем равным нолю и находим расстояния до смежных ей вершин v2, v4 и v5, после чего помечаем вершину v1 посещенной.

Из оставшихся вершин, минимальный вес имеет v4. Рассматриваем расстояния до смежных с ней непосещенных точек v2, v3 и v5. Расстояние до v2 от вершины v1 через v4 оказывается меньше, чем то, что в ней записано, поэтому приписываем его вершине. Помечаем вершину v4 посещенной.

Из оставшихся непосещенными вершин, минимальный вес имеют вершины v2 и v5. Рассматриваем смежные с v2 вершины v3 и v6. Расстояние до v3 от вершины v1 через v2 оказывается меньше, чем то, что в ней записано, поэтому приписываем его вершине. Помечаем вершину v2 посещенной.

Вершиной минимального веса из оставшихся является v5. Рассматриваем смежную с ней точку v6. Расстояние до v6 от вершины v1 через v5 оказывается меньше, чем то, что в ней записано, поэтому приписываем его вершине. Помечаем вершину v5 посещенной.

Вершинами минимального веса из оставшихся являются v3 и v6. Рассматриваем смежную с вершиной v3 точку v6. Помечаем вершину v3 посещенной.

Следующей вершиной рассматриваем v6. Помечаем вершину v6 посещенной.

Алгоритм завершен.

Получили следующие  минимальные расстояния от вершины  v1.

до v2 – 3 (v1-v4-v2), до v3 – 4 (v1-v4-v2-v3), до v4 – 2 (v1-v4), до v5 – 3 (v1-v5), до v6 – 4 (v1-v5-v6).