Введение в дискретную математику. Множества

1. Введение в ДМ. Множества

ВВЕДЕНИЕ В ДМ.
МНОЖЕСТВА
Лекция №1

2.

МАТЕМАТИКА
Дискретная математика
Непрерывная математика
2

3.

▪ Дискретная
математика – область математики,
занимающаяся изучением свойств структур конечного
характера, которые возникают как внутри математики, так
и в её приложениях.
- теория функциональных систем
- теория графов
- теория автоматов
- теория кодирования
- комбинаторика
- целочисленное программирование.
▪ Дискретная (конечная) математика – это раздел
математики, не связанный с понятиями предела,
непрерывности и бесконечности.
3

4. ЕГИПЕТСКИЙ СЧЕТ

4

5. ЕГИПЕТСКИЙ СЧЕТ (умножение)

ЕГИПЕТСКИЙ СЧЕТ
(УМНОЖЕНИЕ)
5

6. ЕГИПЕТСКИЙ СЧЕТ (умножение)

ЕГИПЕТСКИЙ СЧЕТ
(УМНОЖЕНИЕ)
6

7.

Основоположники:
▪ чешский философ, математик и логик, профессор теологии (г. Прага)
Бернард Больцано (1781—1848)
▪ немецкий математик Рихард Дедекиндом (1831—1916)
▪ немецкий математик, профессором (с 1872 г.) Галльского
университета Георгом Кантором (1845—1918)
Официальное признание 1897:
▪ Ж. Адамар и Гурвиц на Первом международном конгрессе
математиков в своих докладах привели многочисленные примеры
применения теории множеств в различных разделах математики.
7

8. Теория Множеств

ТЕОРИЯ
МНОЖЕСТВ

9. Логические Символы

ЛОГИЧЕСКИЕ СИМВОЛЫ
9

10. Логические Символы

ЛОГИЧЕСКИЕ СИМВОЛЫ
10

11. Основные определения и понятия

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ
▪ Понятие множества считается первоначальным, неопределяемым
через другие математические объекты.
▪ Определение 1.1. Под множеством понимают совокупность
определенных и отличных друг от друга объектов, объединенных
общим характерным признаком в единое целое и способных
находиться между собой в определенных отношениях, а также
вступать в соотношение с элементами других множеств. В
математике вместо термина "множество" часто говорят "система",
"класс", "семейство", "совокупность".
▪ Определение 1.2. Элементами множества называются объекты и
предметы, образующие данное множество.
▪ Множества и их элементы обозначают обычно буквами латинского
алфавита : множества – прописными А,В,С..., их элементы строчными a,b,c,...
11

12. Основные определения и понятия

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ
▪ Если элемент а принадлежит множеству А, то пишут а ∈ А; если а не
принадлежит множеству А, пишут а ∉ А.
▪ Если множество А состоит из элементов a,b,c,d, то пишут А = { a , b , c ,
d }.
▪ Если множество А задается указанием характерного признака Р(х)
его элементов, то пишут А = {х : Р(х)}.
▪ Определение 1.3. Множество, состоящее из одного элемента,
называется одноэлементным множеством и обозначается { а }.
▪ Определение 1.4. Множество, не содержащее ни одного элемента,
называется пустым и обозначается символом ∅.
Пример: Множество действительных корней уравнения х2 + 1 = 0 пусто.
12

13. Основные определения и понятия

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ
▪ Определение 1.5. Множества, состоящие из конечного числа
элементов, называются конечными.
Пример: Множество студентов потока, множество микросхем на
плате, множество битов в байте, множество вершин многоугольника
конечны.
▪ Определение 1.6. Множество, не являющееся конечным, называется
бесконечным.
Пример: Множество натуральных чисел, множество всех прямых,
проходящих через фиксированную точку плоскости, бесконечны.
▪ Определение 1.7. Если А – конечное множество, то число его
элементов обозначают через |А| и называют мощностью множества
А.
13

14. Основные определения и понятия

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ
▪ Определение 1.8. Непустое множество, на котором зафиксирован
некоторый порядок, т. е. любой элемент множества занимает
определенное положение, называется упорядоченным множеством
или кортежем.
▪ Количество элементов в кортеже носит название длины.
Пример: (а1,а2) – кортеж - двойка; (а1,а2,а3) – кортеж - тройка.
14

15. Способы задания множества

СПОСОБЫ ЗАДАНИЯ МНОЖЕСТВА
▪ а) перечислением (списком своих элементов) (только для конечных множеств);
Пример: A = {a,b,c,d,h} – множество А состоит из элементов a,b,c,d,h. |А |= 5.
▪ б) порождающей процедурой;
Порождающая процедура описывает способ получения элементов множества из уже
полученных элементов либо из других объектов. Элементами множества считаются все
объекты, которые могут быть построены с помощью такой процедуры.
Примеры:
В – множество всех чисел вида π/2 ± кπ где к ∈ N.
Операции над множествами
▪ в) описанием характеристических свойств, которыми должны обладать его
элементы.
Примеры:
С – множество всех натуральных чисел, не превышающих 100.
R – множество всех действительных чисел.
M = {x| P(x)}, которое читается так: «М – множество всех х, обладающих свойством Р»).
В = {x|π/2 ± кπ где к ∈ N}.
15

16. Основные определения и понятия

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ
▪ Определение
1.9. Универсальным множеством U называется
множество, включающее в себя все другие множества в качестве
подмножества.
16

17. Отношения между множествами

ОТНОШЕНИЯ МЕЖДУ МНОЖЕСТВАМИ
▪ Определение 1.10. Множества А и В называются равными, если каждый элемент
множества А является элементом множества В, и, наоборот, каждый элемент
множества В является элементом множества А. Равенство множеств А и В
обозначают А = В.
Пример: Если А – множество корней уравнения (х-1)(х-2) (х-3) = 0 , т. е. А = {х|(х1)(х-2)(х-3) = 0 }, и В – множество натуральных чисел, меньших 4, т. е. В = { х ∈ N |
x<4} , то А=В.
▪ Если множество А не равно множеству В ,то пишут А ≠ В.
▪ Определение 1.11. Непустое множество А называется подмножеством непустого
множества В, если каждый элемент множества А является элементом множества В.
Пишут в этом случае А ⊆ В
▪ Определение 1.12. Если А ⊆ В и А ≠ В, то А называют собственным подмножеством
множества В и обозначают А ⊂ В и называют строгим включением.
Пример: Известно, что натуральные числа являются целыми, а целые числа
являются рациональными; всякое рациональное число является действительным.
Следовательно, N ⊂ Z ⊂ Q ⊂ R.
17

18. Операции над множествами

ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
▪ Определение 1.13. Объединением множеств А и В называется множество А ∪ В,
содержащее те и только те элементы, которые принадлежат хотя бы одному из
множеств А или В (или обоим одновременно): А ∪ В = {x |x ∈ A или х ∈ В или х ∈ А и х
В}.
Объединение множеств удовлетворяет следующим законам:
1) коммутативному А ∪ В = В ∪ А ;
2) ассоциативному А ∪ (В ∪ С) = (А ∪ В) ∪ С;
3) очевидно, что А ∪ А = А, А ∪ ∅ = А, А ⊂U ⇒А ∪ U = U.
4)дистрибутивному А ∪ (В ∪ С) = (А ∪ В) ∪ (А ∪ С)
▪ Определение 1.14. Пересечением множеств А и В называется множество А ∩ В,
состоящее из всех тех элементов, каждый из которых принадлежит обоим множествам
одновременно: А ∩ В = {х|х ∈ А и х ∈ В}.
Пересечение множеств удовлетворяет следующим законам:
1) коммутативному А ∩ В = В ∩ А ;
2) ассоциативному А ∩ (В ∩ С) = (А ∩ В) ∩ С;
3) очевидно, что А ∩ А = А, А ∩ ∅ = ∅ , А ∩ U = А.
4)дистрибутивному А ∩ (В ∩ С) = (А ∩ В) ∩ (А ∩ С)
18

19. Операции над множествами

ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
Определение 1.15. Разностью двух множеств А и В называется множество В \ А,
состоящее из всех и только тех элементов, которые принадлежат В, но не
принадлежат А: В \ А = {х|х ∈ В, но х ∉ А }.
Определение 1.16. Разность U \ A называется дополнением множества А до
ഥ:А
ഥ = U \ A = { x |x∉A }.
универсального множества U и обозначается А
Определение 1.17. Симметрической разностью двух множеств А и В называется
множество А ÷ В , которое состоит из тех и только тех элементов, которые не
принадлежат пересечению множеств А и В: А ÷ В=А \ В ∪ В \ А .
19

20. Операции над множествами

ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
Определение 1.18. Совокупность из двух предметов называется упорядоченной
парой, если она удовлетворяет двум свойствам:
1) для любых двух данных предметов x и y существует объект, который можно
обозначить через ‹x,y›, называемый упорядоченной парой x и y и однозначно
определяемый предметами x и y;
2) если ‹x,y› и ‹u,v› – две упорядоченные пары, то ‹x,y› =‹u,v› в том и только в том
случае, когда x=u, y=v.
Определение 1.19. Декартовым произведением двух множеств А и В называется
множество, обозначаемое А х В, состоящее из всех возможных упорядоченных пар
‹x,y› : A x B = {‹x,y›|x ∈ A , y ∈ B }.
20

21. КОМБИНАТОРИКА

22. Основные законы комбинаторики

ОСНОВНЫЕ ЗАКОНЫ КОМБИНАТОРИКИ
▪ Правило суммы. Если некоторый элемент a может быть выбран из множества
элементов m способами, а другой элемент b может быть выбран n способами,
причем любой выбор элемента b отличен от любого выбора элемента a, то
выбрать либо a, либо b можно m + n способами.
А ∩В = ∅ ⇒ | А ∪ В | = |A| + |B|
Пример:
Среди студентов первого курса 40 человек имеют дома ноутбук, 25 – учебник по
информатике; оказалось, что 14 студентов имеют и ноутбук, и учебник по
информатике. Сколько студентов на первом курсе?
22

23. Основные законы комбинаторики

ОСНОВНЫЕ ЗАКОНЫ КОМБИНАТОРИКИ
▪ Правило произведения. Если элемент a можно выбрать из множества элементов
m способами и после каждого такого выбора элемент b можно выбрать n
способами, то два элемента (упорядоченную пару) a и b можно выбрать m•n
способами.
если множества А и В конечны, то |A B| = |A| • |B|.
Пример:
Сколько номеров, состоящих из двух букв, за которыми идут три цифры можно
составить, если использовать 29 букв и 10 цифр.
23

24. Формулы комбинаторики

ФОРМУЛЫ КОМБИНАТОРИКИ
▪ Перестановки без повторений
Перестановки - это комбинации, состоящие из одних и тех же элементов и
отличающиеся только порядком расположения этих элементов.
Возьмем n различных элементов a1, a2, a3, … an; будем переставлять эти элементы
всевозможными способами, оставляя без изменения число элементов и меняя
только порядок их расположения.
Составив таблицу перестановок для n элементов и применив (n - 1) раз правило
произведения, получим число всех возможных перестановок:
P(n) = n • (n -1) • (n - 2) • … • 3 • 2 • 1 = n!
Такие перестановки называются перестановками без повторений (один и тот же
элемент не может повториться в комбинации, все элементы различны).
24

25. Формулы комбинаторики

ФОРМУЛЫ КОМБИНАТОРИКИ
▪ Перестановки с повторениями.
Перестановки с повторениями. Рассматривая различные перестановки, мы
предполагали, что все n элементов различны. Если же некоторые элементы
повторяются, то в этом случае комбинации с повторениями вычисляют по другим
формулам.
Если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и
т.д., nk элементов к-го вида, то имеем перестановки с повторениями, их число:
25

26. Формулы комбинаторики

ФОРМУЛЫ КОМБИНАТОРИКИ
▪ Размещения без повторений.
Размещениями называют комбинации, составленные из n данных элементов по k
элементов (k<=n, k>0), которые отличаются либо составом элементов, либо
порядком расположения элементов. Обозначаются размещения