- •Контрольные вопрсы и задания
- •2. Множества. Операции над множествами
- •Контрольные вопросы и задания
- •3. Отображения
- •Контрольные вопросы и задания
- •4. Мощность множества
- •Контрольные вопросы и задания
- •5. Бинарные отношения и операции над ними
- •Контрольные вопросы и задания
- •6. Свойства бинарных отношений
- •Контрольные вопросы и задания
- •8. Нечеткие множества.
- •Примеры записи нечеткого множества
- •Примеры нечетких множеств
- •Контрольные вопросы и задания
- •8. Комбинаторные объекты и числа
- •Контрольные вопросы и задания
- •9. Свойства комбинаторных объектов и чисел
- •Контрольные вопросы и задания
ГОУВПО
“Воронежская государственная технологическая академия”
Кафедра информационных технологий,
моделирования и управления
ДИСКРЕТНАЯ МАТЕМАТИКА
Методические указания к практическим занятиям
по дисциплине "Математика",
раздел "Дискретная математика"
Для специалистов и бакалавров,
обучающихся по направлениям
230400 – "Информационные системыи технологии ",
230700 – "Прикладная информацика"
дневной и сокращенной формы обучения
1. Метод математической индукции
Метод математической индукции – универсальный способ доказательства утверждений, зависящих от натурального аргумента n. Он основан на следующем принципе математической индукции: утверждение справедливо для любого натурального n, если: 10 оно справедливо для n = 1;
20 из того, что оно верно для всех n k (k 1) следует его справедливость для n = k + 1.
Задача 1. Найти сумму .
Решение. Имеем:;;;. Есть подозрение, что. Докажем эту формулу.
10. При n = 1 – формула верна.
20. Предположим, что для произвольного k 1 для всех n k . В частности, дляn = k . Найдем. Имеем. По предположению это равно
= ==,
что и требовалось доказать.
Задача 2. “Докажем”, что все натуральные числа равны между собой. Предположим, что k = k + 1. Прибавим по 1 к обеим частям этого равенства. Получим k + 1 = k + 2, что и требовалось доказать. Ошибка этого “доказательства” состоит в отсутствии проверки утверждения при n = 1.
Задача 3. Доказать неравенство 2n > 2n + 1 при n 3.
Решение.
10. 23 > 7.
20. 2k + 1 = 2×2k > 2(2k + 1) = 4k + 2 = (2k + 3) + (2k – 1) > 2k + 3.
Задача 4. Доказать, что для любого n 0 число 11n + 2 + 122n + 1 делится на 133.
Решение.
10. 112 + 121 = 133 – верно при n = 0.
20. 11k +3 + 122(k + 1) +1 = 1111k + 2 + 144122k + 1 = (144–133) 11k + 2 + 144122k + 1 = 144 (11k + 2 + 122k + 1) – – 13311k + 2.
В полученной разности уменьшаемое делится на 133 по предположению, а вычитаемое содержит множетель 133. Следо-вательно, все выражение делится на 133.
Контрольные вопрсы и задания
1. Доказать формулу Sn = 12 + 22 + 32 + … + n2 =
= n(n+1)(2n+1) /6.
2. Обозначим Hn = 1 + 1/2 + 1/3 +…+ 1/n – гармонические числа. Доказать, что Нn неограниченно сверху, т.е. что Нn + ().
3. Доказать, что любую сумму денег более 7 копеек можно уплатить монетами достоинством 3 и 5 копеек.
4. Найти формулы для вычисления:
а)
б)
Доказать формулы и утверждения (5 – 13).
5.
6. .
7. При любом х 1, .
8. Сумма кубов трех последовательных натуральных чисел n3 + (n + 1)3 + (n + 2)3 делится на 9.
9. Выражение делится без остатка на 9.
10. Число диагоналей выпуклого n-угольника k = n(n –2) /2.
11. Последовательность аn = (n корней) возрастает.
12. cos cos 2… cos 2n = .
13.
14. .
15. .
16.
17.
18.
2. Множества. Операции над множествами
Множеством называется совокупность некоторых предметов, объединенных общим признаком. Элементы множества – это те предметы, из которых состоит множество.
Если какой-то элемент а принадлежит множеству А, то это обозначается аА, а если b не принадлежит А, то – bА. Например, пусть А – множество четных натуральных чисел, тогда 6А, а 3А.
Пусть имеется два множества А и В, причем все элементы множества А принадлежат множеству В, т.е. если хА, то хB. В этом случае говорят, что множество А включено в множество В. Обозначается: АВ ( – символ нестрогого включения, т.е. возможно совпадение множеств). Множество А совпадает с множеством В (А = В), если все элементы множества В являются элементами множества В и все элементы множества В являются элементами множества А. Это можно записать в виде
(АВ и ВА) (А = В).
Большинство утверждений теории множеств связано с равенством двух множеств и включением одного множества в другое. Поэтому надо детально разобраться в методах доказательства этих фактов.
1. Доказательство включения АВ. Для этого нужно доказать, что любой элемент x, принадлежащий множеству А одновременно является элементом множества В, т.е.
( x А) (x В).
2. Доказательство равенства А = В. Оно сводится к доказательству двух включений А В и В А.
Определим следующие операции над множествами.
1. Объединение. Пусть А и В – произвольные множества. Их объединением называется множество С = А В, которое состоит из всех элементов, принадлежащих хотя бы одному из множеств А или В.
2. Пересечение. Пересечением множеств А и В называется множество С, состоящее из элементов, одновременно принадлежащих А и В. Обозначается так: C = A B.
3. Разность. Разность множеств А и В – это множество С (С = А \ В), состоящее из элементов множества А, не принадлежащих множеству В. Если В А, то разность С = А \ В называется дополнением В до А.
Считается, что все множества включены в некоторое множество U, которое называют универсальным множеством. В этом случае дополнение какого-либо множества А до U обозначается С(А) или .
4. Симметричная разность. По определению симметричная разность двух множеств А и В – это множество
С = А В = (А \ В) (В \ А).
Задача 1. Доказать, что для любых множеств A1, A2, . . . , An если справедливы включения A1 A2 ... An A1, то A1 = A2 = ... =An.
Решение.
Задача 2. Доказать тождество
(AB) \ C = (A \ C)(B \ C) = A(B \ C) = (AB)\(AC).
Решение.
1) Пусть x(AB)\C, тогда xAB и xC. Так как x принадлежит пересечению, то он принадлежит каждому из множеств. Следовательно, xA и xC, что означает xA\C. Аналогично из xB и xC следует, что xB\C. Так как x принадлежит обоим множествам, то x(A\C)(B\C). Следовательно, (AB)\C (A\C)(B\C).
2) Покажем теперь, что (A\C) (B\C) A (B\C). Так как x(A\C)(B\C), то xA\C и xB\C, а, следовательно, xA, xB и xC. Поэтому xB\C и xA, что и означает требуемое.
3) Пусть xA(B\C), тогда xA, xB и xC. Следовательно, xAB и xAC. Но тогда по определению разности x(AB)\(AC).
4) Пусть теперь x(AB)\(AC), покажем, что x(AB)\C. Из условия следует, что xAB и xAC. Первое свойство означает, что xA и xB, второе - xA или xC. Так как при xA получим противоречие, то остается лишь случай xC. Поэтому имеем xA, xB и xC. Но тогда xAB и xC и, следовательно, x (AB)\C.
Таким образом, доказана цепь включений
(AB)\C (A\C)(B\C) A(B\C) (AB)\(AC) (AB)\C.
Для завершения доказательства остается воспользоваться результатами задачи 1.
Задача 3. Доказать тождество
A (B C) = (A B) (A C).
Решение. Воспользовавшись свойством дистрибутивности и результатами задачи 2, получим
A(BD) = A((B\D)(D\B)) = (A(B\D))(A(D\B)) =
= ((AB)\(AD))((AD)\(AB)) = (AB) (AD).
Задача 4. Доказать, что A (B C) A B и A C;
Решение. Докажем, что из A(BC) следует AB и AC. Для этого необходимо показать, что если выполнено включение посылки, т.е. ABC, то выполняются и оба включения следствия.
Пусть xA, тогда по условию xBC, а, следовательно, xB и xC. Поэтому справедливы включения AB и AC.
Докажем обратное следствие. Пусть выполнены оба включения AB и AC. То есть из xA вытекает, что xB и xC. Но это означает, что xBC. Следовательно, требуемое включение доказано.
Задача 5. Решить систему уравнений .
Решение. Так как A\X=B, то BA, XB=, A\BX и AXB. Выполнение первых двух свойств очевидно.
Докажем справедливость третьего включения. Пусть xA\B, тогда xA и xB. Покажем, что xX. Предположим противное, т.е. xX, тогда из B=A\X получим xB, что противоречит условию. Следовательно, xX.
Так как BA, то A=(A\B)B. Из этого равенства и условия A\BX следует, что AXB.
Аналогично из X\B=A следует, что CX, AC=, XAC и X\CA. Так как A\BX и CX, то (A\B)CX. Кроме того, из XAC, BA и XB= следует, что X(A\B)C. Поэтому X=(A\B)C, где BA и AC=.