Дискретная математика (Конспекты 15 лекций)

  • Просмотров 6817
  • Скачиваний 296
  • Размер файла 55
    Кб

Московский государственный институт радиотехники, электроники и автоматики (технический университет) Лекции по 1 курс Москва 2000 Лекция 1 Множество. Алгебра множеств. Введем обозначения. R – множество действительных чисел. X e R – элемент X принадлежит множеству R. Равные множества – множества, состоящие из одинаковых элементов. A = B – множество А равно множеству B. 0 – пустое множество. A<= C – Множество А является подмножеством

множества С. Если А не равно С и А <= C, то А < С. (строго). Если A <= C и C <= А, то А = С. Пустое множество 0 является подмножеством любого множества. Существуют конечные и бесконечные множества. Пусть n – число элементов данного множества А. Это число называется мощностью данного множества. У множества рациональных чисел мощность является счетной (т.е. все элементы можно пронумеровать). У множества иррациональных чисел мощность –

континиум. Обозначается (С). Основное правило комбинаторики (показано на примере) Пусть имеется палочка, разделенная на 3 части. Первую ее часть можно раскрасить n способами, вторую – m, третью – k. Всего способов раскраски палочки – n*m*k. Аналогично с множествами U = {a1,a2… an-1, an} Пусть U = {a1, a2, a3} Выпишем множество всех подмножеств множества U. P(U) = {0, a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3}. Мощность множества U равна 3, а мощность P(U) равна 8. Методом

математической индукции доказывается, что при произвольной мощности n множества U, мощность множества P(U) равна 2n. Операции над множествами 1.      2.      3.      А ) – не А. Все элементы, принадлежащие универсальному множеству, не принадлежат множеству А. Свойства операций над множествами. 1.      . A n B = B n A 2.      (A U B) U C = A U (B U C), A n (B n C) = (A n B) n C – ассоциативность.

3.      (A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) – дистрибутивность. 4.      A U A = A, A n A = A. 5.      А U 0 = A A n 0 = 0 A u U = U A n U = A 6. Двойное дополнение A = A 7. A U A = U A n A = 0 8. Законы двойственности или закон Де – Моргана (AUB) = A n B (AnB) = A U B Пересечение множеств Объединение множеств Дополнение множества Лекция 2 Теория булевых функций. Булева алгебра. Определение. Множество M с двумя введенными бинарными операциями (& V),