лекция 01-06

1.

Дискретная математика
каф. КТРС
Куратов Константин Александрович

2. Изучаемые разделы

• Элементы теории множеств;
• Элементы теории графов;
• Элементы булевой алгебры.

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

Дискретная математика : учебник / С. В.
Судоплатов, Е. В. Овчинникова. – 4-e изд. –
Новосибирск : Изд-во НГТУ, 2012. – 280 с.
(Серия «Учебники НГТУ»)

4. Бально-рейтинговая система зачет

• Решение задачи на практике – 2 балла
(8 занятий);
• РГЗ – 30 баллов (10 задач по 3б);
• Контрольная работа – 20 баллов (2 работы по 10б);
• Зачет – 40 баллов.

5. Бально-рейтинговая система бонус

• Конспект– 3 б;
• Выступление с презентацией– 5 б.

6. РГЗ

Дискретная математика : учебник / С. В.
Судоплатов, Е. В. Овчинникова. – 4-e изд. –
Новосибирск : Изд-во НГТУ, 2012. – 280 с.
(Серия «Учебники НГТУ»)
Номера задач 1,2,4,9,10,11,12,13,14,15
Срок сдачи 16 неделя

7. Список вопросов

1. Определение множества, элемента множества. Пустое, универсальное множества. Подмножество. Равенство множеств.
2. Операции над множествами. Диаграммы Эйлера-Венна.
3. Упорядоченные наборы. Декартовое произведение и декартовая степень множеств.
4. Отношения. Унарные и бинарные отношения. Тождественное и универсальное отношения.
5. Отношения. Область определения. Область значений. Обратное отношение. Образы и прообразы множеств. Произведение бинарных отношений.
6. Определение функции. Частичная функция. Инъективные, сюръективные и биективные функции.
7. Эквивалентность множеств. Мощность множеств. Типы множеств.
8. Матрица бинарного отношения. Свойства.
9. Рефлексивные, симметричные, антисимметричные и транзитивные бинарные отношения.
10. Метод математической индукции.
11. Объекты комбинаторики. Цели и методы.
12. Перестановки.
13. Размещения и сочетания.
14. Размещения и сочетания с повторением.
15. Объекты теории графов. Цели и методы.
16. Определение графа. Ориентированные и неориентированные графы. Способы задания графов.
17. Подграфы и части графа. Операции над графами.
18. Маршруты и цепи графа. Способы получения маршрутов длины k. Циклы графа. Циклы Эйлера и Гамильтона.
19. Матрицы графа.
20. Числа графа. Цикломатическое число.
21. Числа графа. Число внешней устойчивости.
22. Числа графа. Число внутренней устойчивости.
23. Числа графа. Хроматическое число.
24. Изоморфные графы. Полные графы. Планарные графы. Теор. Понтрягина-Куратовского.
25. Процедура распознавания плоского графа с помощью метода Эйлера.
26. Процедура распознавания плоского графа с помощью цикла Гамильтона.
27. Остовы графа. Дерево. Лес. Нахождение остова минимального веса графа.
28. Фундаментальные циклы.
29. Фундаментальные разрезы.
30. Определение булевой алгебры. Высказывание. Логические переменные.
31. Логические операции. Таблица истинности.
32. Булевы функции. Задание булевых функций.
33. Определение эквивалентности формул. Основные эквивалентности. Тождественная истинность и тождественная ложь. Выполнимость и
опровержимость формул.
34. Понятие ЭК и ЭД. Определение ДНФ и КНФ. Количество ДНФ и КНФ формулы. Простые ЭК и ЭД. Полные ЭК и ЭД. Определение СДНФ и СКНФ.
35. Минимизация ДНФ. Сокращенная, тупиковая и минимальная ДНФ.
36. Минимизация ДНФ. Карты Карно.
37. Минимизация ДНФ. Метод Квайна.
38. Принцип двойственности булевых функций. Самодвойственные функции.
39. Классы функций (Поста).
40. Полином Жегалкина.

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

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

9.

Понятию множества невозможно дать точное определение, поскольку оно
является первичным, предельно широким по содержанию. Его можно
лишь пояснить. О том, какой смысл вкладывал в это понятие сам Георг
Кантор, можно получить представление из следующих цитат, авторы
которых ссылаются на Г. Кантора:
«Под множеством понимают объединение в одно
общее объектов, хорошо различаемых нашей
интуицией или нашей мыслью»
«Под множеством S будем понимать любое
собрание определенных и различимых между
собой объектов, мыслимое как единое целое»
«Множество есть многое, мыслимое
нами как единое целое»

10.

Множество – это совокупность объектов, обладающих
определенным свойством.
Объекты, из которых состоят множества, называются
их элементами.
Принадлежность элемента a множеству P записывают:
a∈P
Если множеству P не принадлежит несколько элементов, например, a, b, c,
то записывают: a, b, c ∉ P.
Множество может содержать любое число элементов, конечное и
бесконечное.
Множество может содержать один элемент и не содержать ни одного.
Множество, не содержащее ни одного элемента, называется пустым
множеством и обозначается символом ∅.
Множество, содержащее один элемент, называется синглетоном
(от англ. single — одиночный).

11.

Способы задания множеств:
1) путем прямого перечисления его элементов
А={2,4,6}, А={a1, a2, а3};
2) с помощью порождающей процедуры
P = { 3,7,11,15, …}
3) при помощи специально сформулированного правила, или свойства,
в соответствии с которым всякий объект либо входит в множество, либо не
входит (интуитивный принцип абстракции)
A = {x | P(x)}.
(иногда такое правило называют формой P(х).)
x={x| x обладает свойством}
множество десятичных цифр
P = { x | 0 ≤ x ≤ 9, x — целое число}
/
и
∙
∧
;
x={x| cos(x)=0}, x= π/2 + πm, m ∊ Z

12.

Примеры множеств:
Z – множество целых чисел;
N,ω – множество натуральных чисел
положительных целых 0
R – множество действительных чисел;
Q – множество рациональных чисел;
дробь
C – множество комплексных чисел.
"тогда и только тогда"
"если..., то ..."
"для любого"
"положим поопределению"
"существует"

13.

Примеры множеств:

14.

Множество А называется подмножеством
множества В ( A B ), если все элементы
множества А принадлежат множеству В
A B x (x A x B)
множество А содержится в В,
имеется включение А в В
A B
Множество В называется
надмножеством множества А
B A
B A.
Множество A называется собственным
подмножеством множества B, если
множество А является подмножеством
множества В и А≠B.

15.

Примеры множеств:

16.

Множества А и В называются равными
(совпадающими) в том случае, когда
множество А является подмножеством В и
множество В является подмножеством А
A=B A B и B A.
Для доказательства равенства множеств,
требуется установить два включения

17.

Множество не содержащее элементов называется
Свойство:
пустым множеством Ø.
Ø⊆∀ А
Множество содержащее в себе все элементы,
находящиеся в рассмотрении, называется
универсальным множеством («универсум» U I).
Совокупность всех подмножеств множества А
называется булеаном Ρ(А) или множеством-степенью
2А.
Пример:
А= {1, 2, 3}
Ρ(А) = {Ø, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A}

18.

Cобственные и несобственные подмножества.

19.

Диаграммы Венна.
Для иллюстрации множеств и отношений между ними, используют
диаграммы Венна (диаграммы Эйлера, круги Эйлера, диаграммы ЭйлераВенна) в виде замкнутых кривых, ограничивающих области, которым
ставятся в соответствие элементы тех или иных множеств.
I - универсальное множество
I = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Q — множество всех простых чисел,
меньших 10
P — множество четных простых чисел

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

1. Объединение
A B {x | x A или x B}
2. Пересечение
A B {x | x A и x B}

21. Операции на множестве:

22. Операции на множестве:

3. Разность
A \ B {x | x A и x B}
4. Кольцевая сумма
A B ( A \ B) ( B \ A)
{x | x A и x B, или x A и x B}
Симметрическая разность,
дизъюнктивная разность
5. Дополнение
A U \ A {x | x U и x A}

23.

A B {x | x A или x B}
если x A B, то x A и x B.
Пр 1 (введение операции объединения) : если x A,
то x A B, где В любое множество.
A B {x | x A и x B}
если x A B, то x A или x B.
Пр 2 (введение операции пересечения ) : если x A,
то x A B, где В любое множество.

24. Пример:

Задача A B C A B A C
1. Показать A B C A B A C
1.1. x A B C
предположение;
1.2. x A и x B C
определение операции " ";
1.3. x A и x B или x C определениеоперации " ";
1.4. x A B
если x B п1.3 и определениеоперации " ";
1.5. x A B A C
правило1;
1.6. x A C
если x C п1.3 и определениеоперации " ";
1.7. x A B A C
правило1;
1.8. x A B C x A B A C A B C A B A C
определение " "

25. Пример:

Задача A B C A B A C
1. Показать A B C A B A C
1.8. x A B C x A B A C A B C A B A C
определение " "
2. Показать A B A C A B C
2.1. x A B A C
предположение;
2.2. x A B или x A C
определениеоперации " ";
2.3. x A B
предположение к пункту 2.2.;
2.4. x A и x B
определение операции " ";
2.5. x A и x B C
правило1;
2.6. x A B C
определениеоперации " ";
2.7. x A С
предположение к пункту 2.2.;
2.8. x A и x С
определение операции " ";
2.9. x A и x B C
правило1;
2.10. x A B C
определениеоперации " ";
2.11. x A B A C x A B C A B A C A B C
определение " "
3. на основании1.8 и 2.11 A B C A B A C

26. Пример:

A \ B A B
x A
x A
1. x A \ B
x A B
1. x A \ B x x ABи x B
B x A и x B
x
xA \ BA
B
A
\
B
A
B
A B
x A
x A
2. x ( A B ) x A и x
B x A \ B
x B
x B
x A и x B x A \ B A B A \ B
A B A\ B
3. из A \ B A B и A B A \ B A \ B A B

27. Свойства операций:

коммутативность объединения
A B B A
коммутативность пересечения
A B B A
ассоциативность объединения
A ( B M ) ( A B) M
ассоциативность пересечения
A ( B M ) ( A B) M
1 й закон дистрибутивности
A ( B M ) ( A B) A M
2 й закон дистрибутивности
A ( B M ) ( A B) A M

28. Свойства операций:

A B A B ( закон де Моргана)
A B A B ( закон де Моргана)
A A B A ( закон поглощения)
A A B A ( закон поглощения)
A B A B A ( закон склеивания )
( A B) ( A B) A ( закон склеивания )
A A A
A A A
( закон тождественноти )
A A ( закон двойного отрицания)
A A A U U
A A U A
( законы 0 и 1)

29.

Операции над множествами имеют приоритеты
(в порядке убывания): 1.дополнение 2. пересечение 3. объединения
Пример:
A B ( A \ B) ( B \ A)
{x | x A и x B, или x A и x B}
пересечение дистрибутивно относительно кольцевой суммы
A ( B C ) ( A B) ( A C ).
( A B C) (D E)
A D A E B D B E C D C E.
! обратное неверно
A ( B C ) ( A B) ( A C ).

30.

A B A B ( закон де Моргана)
Пример:
A B С A B С и т. д.
Пример:
P A B A B B D C D , при С D, B
упрощаем без дополнительных условий
P A B A B B D C D
A ( B B) B D C D A B D C D
при С D
P A B D C
при С D, B
P A D C A C

31. Пример:

A B C A B C есть условие и следствие
1.прямое направление A B C A B C
1.1. x A B
предположение x A и условие A B C ;
1.2. x A и x B
определение операции " ";
1.3. x A
1.4. x С
из п1.2;
п1.1 и условие A B C ;
1.5. x B C
правило 1 и п1.4;
1.6. x A x B C A B C определение " ".
2. обратное направление A B C A B C
2.1. x A B
предположение;
2.2. x A и x B
определение операции " ";
2.3. x A
из п2.2;
2.4. x B С
условие A B C ;
2.5. x C
из п2.4 и согласно п2.2 x B ;
2.6. x A B x C A B C определение " ".
3. A B C A B C из п1.6 и п2.6.

32. Пример:

1. A B C A C и B C
2. A B C A B и A C
3. A B C A B C
Пример:
4. A B C A B C
5. A B B A
A X B
найти X .
A
X
C
3.1. B X и C A X
согласно 1
1. A X B A X B и B A X
1.1. A X B X A B из 3
3.2. X A B и X C
согласно 2
1.2. B A X B A и B X из 2
X A B С
отсюда X A B, B X и условие B A
B C A X
3.3. B C A X A B С
при полученных условиях
2. A X C A X C и C A X
2.1. A X C A C и X C из 1
B A и A C B С
4. A B С A C B C
2.2. C A X C A X из 4
дистрибутивный закон,
отсюда X C и C A X и условие A C.
т.к. B С, то B C B
A C B C A C B
Ответ : X B C A , при B A С

33.

Алгоритм решения системы уравнений
1. Используя известные тождества и условия
X F1 A, B,... и F2 A, B,... X
2. Выражения слева от " ", объединяются
в одно с помощью операции объединения, согласно правилу 1,
а выражения справа с помощью операции пересечения, согласно правилу 2 :
G2 A, B,... F2 F4 X F1 F3 G1 A, B,...
3. Используя условия, налагаемые на известные множества A, B,...
выражения G1 A, B,... и G2 A, B,... приводятся к одному G A, B ,... ,
получив X G A, B,... , т.е.(G A, B,... X G A, B,... )
Если G1 A, B,... и G2 A, B,... не удается привести к одному , то
их упрощают и оставляют решение в виде
G2 упр A, B,... X G1 упр A, B,... .

34. Векторы и прямые произведения

Упорядоченным набором или последовательностью
длиной n x1, x2, … xn называется следующая запись
(x1, x2 … xn)
1,2,…,n индекс позиции, а не имя
вектор
кортеж
n-ка
как обобщение двойка,
тройка, четверка, …
! порядок важен ()
Элементы кортежа называются компонентами или
координатами или разрядами (в машинной арифметике)
Пример: {1, 2} = {2, 1}
(1, 2)≠(2,1)

35.

Элементы вектора (кортежа) могут принадлежать
разным множествам и наоборот множество векторов
возникает в результате операций над множествами.
Декартовым (прямым) произведением множеств А1,
А2, А3, …, Аn называется МНОЖЕСТВО состоящее
из упорядоченных наборов, каждая координата
которых принадлежит соответствующему
множеству.
A1 A2 ... An x1 , x2 ,..., xn x1 A1 , x2 A2 ,..., xn An
A1 A2 ... An
Если A1 A2 ... An , то множество
называется n-ой декартовой степенью множества : A
An A1 A2 ... An .

36. Пример:

1. А = {1, 2}, B ={a, b, c}
A×B = {(1, а), (1, b), (1, c), (2, a), (2, b), (2, c)}
2. R² => R² = {(x, y)| x ∊ R, y ∊ R}
Свойство: Аº=Ø, для любого А.

37.

ОТНОШЕНИЯ.
n-местным отношением (ПРЕДИКАТОМ) Р на множествах
A1 , A2 ,..., An
называется ЛЮБОЕ ПОДМНОЖЕСТВО прямого произведения этих
множеств:
P A1 A2 ... An .
При n=1 такое отношение называется унарным или свойством.
При n=2 такое двухместное отношение
называется бинарным или соответствием.
если P A B и x, y P, то пишут также x P y
Для всякого множества A определены:
тождественное отношение (диагональ)
id ( A) x, x x A ;
универсальное отношение (полное)
U A A2 .

38.

ОТНОШЕНИЯ.
Пример:
A 1, 2
B a, b, c
A B 1, a , 1, b , 1, c , 2, a , 2, b , 2, c ,
A 1,1 , 1, 2 , 2,1 , 2, 2 .
2
P1 1, a , 2, c
P1 A B

39.

Пример:
ОТНОШЕНИЯ.
Отношения иногда удобно изображать графически:
x1, x2, x3
y1, y2

40.

ОТНОШЕНИЯ.
Пример:
A 1, 2,3, 4,5,6,7 ,
P x, y x A, y A, x y 8 ,
P 1,7 , 7,1 , 2,6 , 6, 2 , 5,3 , 3,5 , 4, 4 .

41.

Пример:
A B K M A K B M
1. ( x, y) A B K M x A B и y K M
x A , x B, y K , y M x A, y K , x B , y M
( x, y) A K ,( x, y) B M ( x, y) A K B M
A B K M A K B M ;
2.( x, y) A K B M ( x, y) A K и ( x, y) B M
x A, y K , x B , y M x A , x B, y K , y M
( x, y) A K ,( x, y) B M ( x, y) A K B M
A K B M A B K M ;
3. из1и 2 следует, что A B K M A K B M .

42.

ОТНОШЕНИЯ.
Областью определения отношения Р называется множество:
p x | x, y P для некоторого y
Областью значения отношения Р называется множество:
p y | x, y P для некоторого x
Обратным к Р является отношение:
P 1 y, x | x, y P
Образом множества Х относительно отношения Р является множество:
P X y | x, y P для некоторого x X
Прообразом множества Y относительно отношения Р является множество:
P 1 Y x y, x P 1 для некоторого y Y

43.

Пример:
A 1,2,3,4,5,6,7
ОТНОШЕНИЯ.
P x, y x A, y A, x y 4
P 5,1 , 6, 2 , 7,3
Область определения
p x | x, y P для некоторого y
P 5,6,7
Область значений
P 1,2,3
Обратное к P отношение
1
P 1 1,5 , 2,6 , 3,7
p y | x, y P для некоторого x
P
y, x | x, y P
Образ множества Х относительно отношения Р
P X y | x, y P для некоторого x X
X 6,5
P X 1,2
Прообраз множества Y относительно отношения Р
P 1 Y x y, x P 1для некоторого y Y
Y 2,3
P 1 Y 6,7

44.

P1 A B
Множества A, B, C
P2 B C
Произведением (композицией) бинарных отношений P1 и P2
называется множество:
P1 P2 { x, y | x A, y C и найдется элемент z B такой, что
x, z P1 , z, y P2 }
P1 P2 x, y x A, y C и z B x, z P1 , z , y P2 .
A
x
C
B
P1
z
P2
P1 P2 (также обозначают через PP
1 2)
y

45.

Свойства бинарных отношений:
P 1 P
1
Доказательство :
По определению обратного отношения
условие x, y P равносильно условию y , x P 1 ,
что в свою очередь выполняется тогда и только тогда,
когда x, y P
.
Следовательно, P P .
1 1
1 1

46.

P1 P2 x, y x A, y C и z B x, z P1 , z , y P2 .
Свойства бинарных отношений:
P Q Q 1 P 1
1
Доказательство :
1. Докажем P Q Q 1 P 1
1
Пусть x, y P Q , что
1
равносильно условию y , x P Q.
Следовательно, y , z P и z , x Q для некоторого элемента z.
Значит, z, y P 1 и x, z Q 1 и x, y Q 1 P 1.
2. Включение Q 1 P 1 P Q
1
доказывается аналогично.

47.

P1 P2 x, y x A, y C и z B x, z P1 , z , y P2 .
Свойства бинарных отношений:
ассоциативность произведения бинарных отношений
P Q R P Q R
Доказательство :
1. Докажем P Q R P Q R
Пусть x, y P Q R.
Тогда для некоторых z и v имеем
x, z P, z, v Q, v, y R.
Таким образом, z, y Q R и x, y P Q R .
Следовательно, P Q R P Q R .
2. Включение P Q R P Q R доказывается аналогично.

48.

Свойства бинарных отношений:
1. Бинарное отношение P на множестве X называется
РЕФЛЕКСИВНЫМ, если для любого x X пара x, x P.
2. Бинарное отношение P на множестве X называется
СИММЕТРИЧНЫМ, если для любых x, y X
из принадлежности пары x, y отношению P
следует принадлежность этому отношению пары y, x .

49.

Свойства бинарных отношений:
3. Бинарное отношение P на множестве X называется
АНТИСИММЕТРИЧНЫМ, если для любых x, y X
из принадлежности пар x, y y, x отношению P
следует x y.
4. Бинарное отношение P на множестве X называется
ТРАНЗИТИВНЫМ, если для любых x, y, z X
из принадлежности пар x, y y, z отношению P
следует принадлежность этому отношению пары x, z .

50.

Пример:
A {1, 2,3}
P A
2
P {(1, 2), (2,1), (1,1), (1,3), (3, 2), (3,3)}
1. 2 A, 2, 2 P не рефлексивно;
2. 1,3 P, а 3,1 P не симметрично;
3. 1, 2 P и 2,1 P, а 1 2 не антисимметрично;
4. 3, 2 P, 2,1 P, а 3,1 P не транзитивно.

51.

Матрица бинарного отношения
A {a1 , a2 ...am }, B {b1 , b2 ...bn }, P A B
[ P] ( pij )m n
1, если (ai , b j ) P
pij
0, если (ai , b j ) P
Матрица содержит полную информацию о связях между элементами.

52.

Пример:
P A
2
A {1, 2,3}
P {(1,1), (1, 2), (3,1), (3, 2)}
2
1
3
1 1 0
P 0 0 0
1 1 0
3 3

53.

Основные свойства МБО
1. если P, Q A B, P pij , Q qij , то
P Q pij qij , по правилам 0 0 0, 0 1 1 0 1 1 1
P Q pij qij , перемножение " элемент в элемент "
Пример

54.

Основные свойства МБО
2. если P A B, Q B C , то
P Q P Q по правилу умножения матриц,
но произведение и сумма элементов, как в п.1;
Пример
01
10
010
01
10
010
P Q P Q
11
P , Q 1 0
110
11
110
11
3. Матрица обратного отношения P 1 P
T
4. P, Q A B
P Q pij qij
5. Матрица тождественного отношения единична
id A E

55.

Основные свойства МБО
Пусть P – бинарное отношение на множестве А:
P A2 .
Отношение рефлексивно если:
x A x, x P, id A P, E P .
Отношение симметрично если:
x, y A из x, y P y, x P, P 1 P, P P .
T
Отношение антисимметрично если:
x, y A из x, y P, y, x P x y, P P 1 id A , P * P E.
T
Отношение транзитивно если:
x, y, z A из x, y P, y, z P x, z P,
P P P, P P P .

56.

Пример:
A {1, 2,3}
P A
2
P {(1, 2), (1,3)}
P
x A x, x P, id A P, E P .
не рефлексивно
x, y A из x, y P y, x P,
P
T
P P .
T
P 1 P,
не симметрично
P * P
x, y A из x, y P, y, x P x y,
P P
x, y, z A из x, y P, y, z P x, z P,
T
P P id A , P * P E. антисимметрично
1
T
P P P, P P P .
транзитивно

57.

ФУНКЦИИ.
Отношение
называется функцией
(отображением из множества А в множество В)
если:
область определения f A,
область значений f B и
из x, y1 f ,
x, y2 f следует y1 y2 .
Функция f из А в B обозначается через
f
f : A B или A
B
Если x, y f , то обозначается y f x
( y значение функции f при значении аргумента x)
или
f :x
y ( функция ставит в соответствие
элементу x элемент y )

58.

ФУНКЦИИ.
Пример:
{ 1, 2 , 2,3 , 3,1 } {1, 2,3} функция
2
{ 1, 2 , 2,3 , 1,3 } {1, 2,3}2 не является функцией
Частичная функция
если:
область определения f A,
область значений f B и
из x, y1 f ,
x, y2 f следует y1 y2 .

59.

ФУНКЦИИ.
Инъективная (равнозначная) функция
(инъекция 1-1):
x1 f и x2 f , из x1 x2 следует f x1 f x2
или
f 1 является частичной функцией
Обозначается
1 1
f : A B

60.

ФУНКЦИИ.
Сюръективная функция (сюръекция, функция
на), если:
B
f
Обозначается
на
f : A B
Биективная (взаимно однозначная) функция
(биекция), если она и инъективна и сюръективна.
Обозначается
f :A B
Если функция является биекцией между А и А, то
она называется подстановкой множества А.
Обозначается
f :A A
(пример подстановки id A )

61.

ФУНКЦИИ.
инъекция f : A B : x1 f и x2 f , из x1 x2 следует f x1 f x2
1 1
на
сюръекция f : A B : f B
биекция f : A B : инъективна и сюръективна
Пример
fi : 0,1 0,1
1 – сюръективна, не инъективна;
2 – не сюръективна, инъективна;
3 – биективна и подстановка;
4 – не сюръективна, не инъективна;

62.

Эквивалентности
Множества А и В называются эквивалентными
если существует биекция f : A B.
Обозначается
A
B
Свойства эквивалентных множеств:
1. A
A, т.к. id A : A A;
2. если A
B, то B
A
т.к. из f : A B следует f
3. если A
BиB
C , то A
1
: B A ;
C
т.к. из f : A B, g : B C следует f
g : A C .

63.

Мощность множества
Мощность (кардинальное число, кардинал)
множества А называется класс всех множеств,
эквивалентных А.
Мощность обозначается
A
Свойство: эквивалентные множества называются
равномощными.
A
B | A | | B |

64.

Классификация множеств
.
1. Конечное множество
A
n, для некоторого n N
| A | n
МНОЖЕСТВО НЕ ЯВЛЯЮЩЕЕСЯ КОНЕЧНЫМ, НАЗЫВАЕТСЯ БЕСКОНЕЧНЫМ
2. Бесконечное множество СЧЕТНОЕ
X {x|cos (x) 0},
x
2
A
N
A N
n, n Z
Множество, которое является конечным или счетным, еще называют не
более чем счетным.
3. Бесконечное множество КОНТИНУАЛЬНОЕ (КОНТИНУУМ)
A
2N
A 2
N

65.

Мощность множества А не превосходит мощности множества В: A B ,
если А эквивалентно некоторому подмножеству множества В.
Мощность множества А меньше мощности множества В:
A B , если A B и A B
Теорема Кантора-Бернштейна:
если A B и B A , то A B
Следствие:
Для любых множеств A и B существует
одна и только одна из возможностей
A B или A B или A B

66.

Любое подмножество счетного множества не более чем счетно.
Объединение конечного или счетного числа счетных множеств является
счетным множеством.
Любое бесконечное множество содержит счетное подмножество.
Пусть множество М - несчетно, множество А не более чем счетно и
А М. Тогда множество М\А равномощно множеству М.
Если множество С бесконечно, а В не более чем счетно, то множество
В С равномощно множеству С.
Если множество С является бесконечным, то существует его
подмножество В такое, что В С и В равномощно с С.
Множество рациональных чисел Q является счетным.
Множество точек интервала (0,1) является несчетным.
Пусть для множеств А и В существуют множества А1 А и В1 В такие, что
множество А равномощно с В1, а множество В с А1, то множества А и В
равномощны.

67.

Пример:
Установить эквивалентность множеств
1
1
1 1 1
1 1 1
A , , ,..., ,... , B 0, , , ,..., ,...
n
n
2 3 4
2 3 4
Множества счетны.
Установим взаимно однозначное соответствие следующим образом:
A
N
B
1 1 1
1
...
2 3 4
n
1 2 3 ... n 1
1 1
1
0
...
2 3
n 1
1
...
n 1
n ...
1
...
n

68.

Пример:
(0,1) ~ R
(0,1) ~ (-π/2; π/2)
(-π/2; π/2) ~ R => (0,1) ~ R

69.

Алгебраические структуры
.

70.

Математическая индукция
• Индукция (лат. Inductio - наведение) — процесс
логического вывода на основе перехода от
частного положения к общему. Индуктивное
умозаключение связывает частные предпосылки с
заключением не строго через законы логики, а
скорее через некоторые фактические,
психологические или математические
представления.

71.

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

72. Определение множества натуральных чисел

Аксиоматика Дедекинда-Пеано
Определение множества натуральных чисел
Множество N называется множеством натуральных чисел,
если система
N ;0, удовлетворяет аксиомам :
1. для любого m 0 найдется n N такой, что n m;
2. для любых m, n N, если n m , то n m ;
3. n 0 для любого n N ;
4. P P 0 , n P n P n n N P n .
(для любого свойства P (унарного отношения на множестве N),
если P выполняется на элементе 0 (т.е.0 обладает свойством P),
и для любого n N из выполнимости P на элементе n следует
выполнимость P на элементе n , то свойство P выполняется
на любом элементе n N )

73. Доказательство неравенства Бернулли

Пример:
Доказательство неравенства Бернулли
1 a 1 an
n N , a 1, a R
n
Проверка базиса:
1 a 1 a 0;
n 0
0
Проверка индукционного шага:
Предположим, что 1 a 1 an выполнено
n
Покажем, что 1 a
n 1
1 a n 1
1 a 1 a 1 an 1 a
n 1
2
1
a
1
an
a
n a
n
т.к. a 2 0
1 a
n 1
1 an a 2 n a 1 an a
1 a n 1 n N

74. Комбинаторика

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

75. Комбинаторика

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

76. Правила подсчета комбинаторных конфигураций

Комбинаторика
Правила подсчета комбинаторных конфигураций
Правило суммы:
A m, B n;
A B m n A B ;
A B A B m n.
Правило произведения:
A m, B n;
A B m n.
Правило степени:
А т, B n;
AB m n .

77. Правила подсчета комбинаторных конфигураций

Комбинаторика
Правила подсчета комбинаторных конфигураций
Г , M , K , C множества
Г ,M ,K ,C,
M K , K C , M C ,
M K C известны
М
С
К
Г / (M K C)
M K C M K C M K C M K C
M K C MK MC KC MKC
n
i 1
Ai Ai Aij Aijk ... 1
n 1
Ai...n
i
формула включения и исключения

78.

Комбинаторика
Линейные выборки различаются по 2 признакам:
1. Допускается ли повтор элементов;
2. Порядок важен или нет.
Выборка в которой важен порядок
называется размещением
Выборка в которой порядок не важен
называется сочетанием
Основные виды выборок:
1. Размещение с повторениями;
2. Размещение без повторений;
3. Сочетание без повторений;
4. Сочетание с повторениями.

79.

1. Размещение с повторениями
Постановка задачи.
Дано множество, содержащее n элементов. Из них образуют размещения с
повторениями, т. е. упорядоченные последовательности длины m, причем
одни и те же элементы в любую последовательность могут входить
многократно.
Сколько всего существует таких последовательностей?
M , M n
Размещением с повторением из n элементов по m
или упорядоченной (n,m)-выборкой с возвращением
называется любой набор a1 , a2 ...am элементов
множества М.
Количество размещений с повторением:
A n
m
n
m

80.

2. Размещения без повторений
Постановка задачи.
Дано множество А, содержащее n элементов. Из них образуют
упорядоченные последовательности длины m, в которых каждый элемент
множества А встречается не более одного раза. Эти последовательности
называют размещениями без повторений.
Сколько существует таких последовательностей?
M , M n, m n
Размещением без повторений из n элементов по m
или упорядоченной (n,m)-выборкой называется любой
набор ai1 , ai2 ...aim ,состоящий из m попарно
различных элементов множества М.
Количество размещений без повторений :
n!
A
(n m)!
m
n

81.

Перестановки
M {a1,...,a n}, M n
Перестановкой множества М называется любой
набор a i1,a i 2 ,...,a in из n элементов множества М.
Перестановки без повторений
Постановка задачи. Пусть дано множество вида А = {а1,а2, …, аn }. Зафиксируем
элементы этого множества в каком-либо порядке. Затем переставим местами
некоторые элементы. Получим новую последовательность. Снова переставим
некоторые элементы и т. д.
Сколько существует таких последовательностей (различных!)?
Pn n n 1 ...2 1 n!
Перестановки с повторениями
Постановка задачи. Даны n1 элементов вида A (неразличимых между собой), n2
элементов вида B, …, nk элементов вида Z. Из всех этих элементов образуют nэлементные последовательности, содержащие все перечисленные элементы, т.
е. n = n1 + n2 + … + nk. Ее элементы можно переставлять любым способом.
Сколько существует таких перестановок?
n!
Pn
, n n1 n2 ... nk
n1 !n2 !...nk !

82.

3. Сочетания без повторений
Постановка задачи.
Пусть множество А содержит n элементов. Выделим из множества А некоторое
подмножество, содержащее m элементов (m ≤ n).
Сколько существует таких подмножеств?
M , M n, m n
Сочетанием из n элементов по m или
неупорядоченной (n,m)-выборкой называется любое
подмножество ai , ai ...ai
множества М, состоящее
1
2
m
из m элементов.
Количество сочетаний без повторений:
m
A
n
!
Cnm
n .
(n m)!m! m!

83.

3. Сочетания без повторений
Свойства:
1. Cnm Cnn m
2.
n
x y Cni xi y n i , Cni биномиальные коэффициенты.
n
i 0
(бином Ньютона)
Пример
x y x y x y x y x y
4
сумма произведений 4х букв, каждая из которых из одной скобки
1. Из каждой скобки можно «взять» только x (x4)– 1раз;
2. x – 3, а y – 1 (x3y) – 4раза (С41);
3. x – 2, а y – 2 (x2y2) – (С42);
4. x – 1, а y – 3 (xy3) – (С43);
5. y – 4 (y4).

84.

3. Сочетания без повторений
Пример
Скольков множестве M M n подмножеств
n
Cn0 Cn1 ... Cnn Cni
i 0
Cni количество подмножеств мощности i
n
3. Cni 2n
i 0
4. Cnm 11 Cnm Cnm 1
Пример
треугольник Паскаля
Каждый биномиальный коэффициент можно
выразить суммой «соседних»

85.

4. Сочетание с повторениями
Постановка задачи.
Дано множество А = {а1,а2,…,аn}. Сколько существует выборок по m элементов,
если в них могут входить повторяющиеся элементы и если порядок элементов в
выборках безразличен?
M , M n
Сочетанием с повторением из n элементов по m или
неупорядоченной (n,m)-выборкой с возвращением
называется множество элементов, выбранных m раз
из множества М, причем один и тот же элемент
разрешено выбирать повторно.
Количество сочетаний с повторением:
С C
m
n
m
n m 1
n m 1 !
(n m 1 m)!m!
n m 1 !
.
(n 1)!m!