Похожие презентации:
Дискретная математика
1. Дискретная математика
Лекция 1Цель лекции: введение в курс
дискретной математики, теория
множеств
2. Рекомендуемая литература
• Баврин И.И. Дискретная математика: учебники задачник для прикладного бакалавриата.М.: Издательство Юрайт, 2015.- 208 с.
• Селезнев С.Н. Основы дискретной
математики.- М.: МГУ, 2010.- 59 с.
• Романов В.Ф. Основы дискретной
математики. Методические указания к
практическим занятиям.- Владимир.: Изд-во
ВлГУ, 2008 г. – 39 с.
• Интернет ресурс. Интернет университет
информационных
технологий.http://www.intuit.ru
3. Введение
МАТЕМАТИКАУсловное деление
Непрерывная математика
Теория пределов и непрерывности
числа
Дискретная математика
Прерывная.
Основа информатики
Являются основами для создания систем
Аналоговые электронные системы
Числа и другие
объекты
Цифровые электронные системы
Программные и аппаратные
4. Разделы дискретной математики
Теория множеств.
Комбинаторика
Теория графов.
Алгебра логики.
Матрицы.
Разностные уравнения.
Дискретная вероятность.
5. Задачи курса
• УМЕТЬ• Правильно употреблять математическую
символику и оперировать математическим
инструментарием.
• Классифицировать задачу. Выбирать модель
представления задачи.
• ВЛАДЕТЬ
• Основами математического моделирования.
6. Раздел 1. Элементы теории 1.1 Множества и операции над ними
• Множество – это совокупность, собраниекаких-либо объектов, объединенные
общими признаками.(A,B,С…)
• Элементы множества – это объекты,
которые образуют множество. (а,b,c..)
• Если элементами множества являются
цифры – это числовое множество
a A a A
Принадлежит, содержится, а из А, а входит в А
7. Примеры
• Учебник –страницы.• Группа ВТ-115 – ФИО студентов.
• Серия микросхем – состав серии.
8. Обозначения числовых множеств
N – множество натуральных чисел;N0 – множество неотрицательных
целых чисел;
Z – множество целых чисел;
R – множество действительных
чисел;
C – множество комплексных
чисел.
9. Названия и обозначения числовых множеств
Множество действительных чисел удовлетворяющих условию:a x b
a; b
Обозначение в теории множеств
a x b
a; b
10. Названия и обозначения числовых множеств
Множество действительных чисел удовлетворяющих условию:a x b
[a; b)
Альтернативное обозначение
a x b
(a; b]
11. Названия и обозначения числовых множеств
Множество действительных чисел удовлетворяющих условию:x a
; a
Альтернативное обозначение
x a
( ; a]
12. Названия и обозначения числовых множеств
Множество действительных чисел удовлетворяющих условию:x b
b;
Альтернативное обозначение
x b
[b; )
13. Названия и обозначения числовых множеств
• Множество всех действительных чиселобозначается:
;
ИЛИ
ИЛИ
x
R
Множество всех положительных чисел называют
натуральным рядом или множеством натуральных чисел
и обозначают ,буквой N
14. Множества конечные и бесконечные
• Множество содержащее конечное числоэлементов называют конечным, в
противоположном случае множество называю
бесконечным.
• ПРИМЕР: Множество студентов в группе –
конечное множество.
• ПРИМЕР: Множество транзисторов в ИС –
конечное множество.
• ПРИМЕР: N, R – бесконечные множества.
15. Формы задания множества 1 способ
• Например: А = {1,2,3} – означает, чтомножество А состоит из элементов
1,2,3. Это конечное множество.
• Например: N = {1,2,3,…} . Бесконечное
множество.
Первый способ задания множества заключается в явном перечислении
его элементов. При этом порядок перечисления элементов не имеет
значения.
ВАЖНО – порядок перечисления будет важен в разделе
КОМБИНАТОРИКА.
16. Формы задания множества 2 способ
• Заключается в описании элементовопределяющим свойством P (x), общим
для всех элементов множества.
• Например: A= {x: P (x)}
• Например: A = {x: x=2k, k N
А - Множество положительных четных
чисел 2,4,6,…и до бесконечности.
• B= {x:0<x<10 и x – четное}, B={2,4,6,8}
17. Формы задания множества 2 способ
• C = {x: x – пациент больницы №4г.Владимир}
• D = {x: x – студент группы ВТ-115 ВлГУ}
18. Формы задания множества 3 способ
• Порождающая процедура описываетспособ получения элементов множества
из других объектов или уже полученных
элементов множества.
19. Равенство множеств
• Если множество А и множество В состоит изодних и тех же элементов, то такие множества
называют равными. Равные множества
обозначаются:
А=В
Например:
{1,2} = {2,1}
или А={1<x<4, x – целое}
2
5x 6 0
С={ x :
x
A=C
?
Докажите
20. Подмножество множества
• Если имеется два множества А и В иизвестно, что каждый элемент множества В
является элементом множества А, то
множество В является подмножеством
множества А.
B A
Знак включения
В содержит А
Говорят, что А содержит В или В включено в А
21. Подмножество множества
• Пример 1: Множество четных чисел,есть подмножество множества целых
чисел.
• Пример 2: А={x: x – группа студентов
ВТ}
B={b: b – факультет ИТ},
то А подмножество В
22. ТЕОРЕМА 1
• ЕслиB A
A B
а
то
А=В
ДОКАЗАТЕЛЬСТВО
1.Любой элемент из множества В является
элементом множества А.
2.Любой элемент из множества А является
элементом множества В.
ТО есть множество А и В состоят из одних и тех же
элементов - это означает, что А=В
23. Определение - булеан
• Элементами множества могут бытьподмножества.
• Множество всех подмножеств множества А
называется его булеаном или множествомстепенью и обозначается: Р(А) или
2
А
24. Универсальное множество
DH
S
B
A
C
U
Множество U – универсальное множество, которое задает область
исследования
25. Пустое множество
• Множество, не содержащее ни одногоэлемента называется пустым и обозначается
знаком:
Пример1: множество людей на солнце.
Пример 2: множество действительных
корней уравнения:
2
x
1 0
26. ТЕОРЕМА 2
• Пустое множество являетсяподмножеством любого множества.
ДОКАЗАТЕЛЬСТВО
Из определения подмножества следует, что В является
подмножеством А, если В не содержит элементов не
являющихся элементами множества А.
Но пустое множество не содержит ни одного элемента,
поэтому оно не содержит и элементов не
принадлежащих А.
ВЫВОД: пустое подмножество, есть подмножество любого множества.
27. Операции над множествами Объединение или сумма
• ОПРЕДЕЛЕНИЕ: если даны два множества Аи В, то их объединением или суммой будет
называться множество С, состоящее из всех
элементов, принадлежащих хотя бы одному
из множеств А и В.
С A B
Знак объединения
(С=A+B)
28. Пример операции объединения
• ПРИМЕР 1: {1,2,3}{2,3,4}= {1,2,3,4}
ПРИМЕР 2: А – множество компонентов резисторов,
В – множество компонентов диодов, тогда
объединение А и В – это множество С
компонентов, которые являются либо резисторами
либо диодами
А
B
29. Следствие операции объединения
A A AA A B
B A B
30. Объединение N множеств
• Операция объединения может бытьраспространена на N множеств. Тогда
записывают:
С
А1
...
А2
АN
n
или C
k 1
A
k
31. Задача
A ?32. Операция пересечения или умножения
• ОПРЕДЕЛЕНИЕ: если даны два множества А и В, топересечением их будет называться множество С,
которое будет состоять из элементов принадлежащих
одновременно множеству А и множеству В.
С А В
Знак пересечения
С=А В
33. Пример операции пересечения
• ПРИМЕР:{1,2,3} {2,3,4} ={2, 3}
А
С
В
34. СЛЕДСТВИЯ операции пересечения
1.2.
3.
A A A
( A B) A
( A B) B
Для некоторой пары множеств может оказаться, что их пересечение
равно пустому множеству. НАПРИМЕР А={1,2,3} В={4,5,6}, то пересечение
А с В равно пустому множеству.
А
В
А В
35. Непересекающиеся множества
• Множества, пересечение которых,является пустым множеством
называются непересекающимися.
• ПРИМЕР 1: А – множество целых
положительных чисел, В – множество целых
отрицательных чисел. А и В –
непересекающиеся множества.
• ПРИМЕР 2: А – множество людей старше 20
лет, В – множество людей младше 15 лет.
36. Пересечение N множеств
• Операция пересечения может бытьраспространена на N множеств. Тогда
записывают
А А ... А
или С A
С
1
2
N
n
k 1
а
с
k
в
н
37. Вычитание множеств
• ОПРЕДЕЛЕНИЕ: Разностью множеств Аи В называется совокупность тех
элементов множества А, которые не
являются элементами множества В.
B
А\В
Обозначение разности
A
38. Варианты вычитания множеств
12
3
А
В
А
В
А
В
39. Симметричная разность или кольцевая сумма
• ОПРЕДЕЛЕНИЕ: Симметричной разностью множествА и В называется совокупность тех элементов
множества А и В, которые не являются
одновременно элементами множества А и В.
А Вили
Обозначение кольцевой суммы
А В
А
В
40. Дополнение
• Дополнением множества А до универсальногомножества U, является частный случай
разности:
А U \ A
__
А
A
41. Диаграммы Эйлера-Венна
• Применяются для наглядного изображения соотношений междуподмножествами какого либо универсального множества.
42. Декартово произведение множества А на множество В
• ОПРЕДЕЛЕНИЕ: это множество всехупорядоченных пар элементов из А и В.
А В {( x, y); x A, y B}
ПРИМЕР: А={x.у.z} B={1,2,3}
Напишите элементы произведения множеств
Графическое представление декартова
произведения множества X и множества Y
43. Декартова степень
ЗАДАЧА; дано множество X={0,1,2} вычислитьX
3
44. Порядок выполнения операций над множествами
• Дополнение – (пересечение- объединение) иразность - умножение.
• Изменить порядок выполнения можно
заданием скобок.
___
А В С D\ X
45. Мощность множества
• Это характеристика количества элементовмножества. Используется как класс
эквивалентности над множествами, между
которыми можно установить взаимно
однозначное соответствие.
А
0
46. Законы алгебры множеств или алгебра Буля
• 1. ЗАКОН. Свойство двойного дополнения.Двойное дополнение множества А равно множеству А
А А
47. Законы алгебры множеств или алгебра Буля
• 2 ЗАКОН. Свойство идемпотентностиобъединения или пересечения множества А.
А А А
А А А
48. Законы алгебры множеств или алгебра Буля
• 3 ЗАКОН. Дополнения.А А
А А U
49. Законы алгебры множеств или алгебра Буля
• 4. ЗАКОН. Свойство единицы.А U А
А U U
50. Законы алгебры множеств или алгебра Буля
• 5 ЗАКОН. Свойство нуля.А
А А
51. Законы алгебры множеств или алгебра Буля
• 6 ЗАКОН. де Моргана.А В А В
А В А В
52. Законы алгебры множеств или алгебра Буля
• 7 ЗАКОН. Коммутативность пересечения илиобъединения множеств.
А В В А
А В В А
53. Законы алгебры множеств или алгебра Буля
• 8 ЗАКОН. Ассоциативности пересечения илиобъединения.
А (В С) А В С
А (В С) А В С
54. Законы алгебры множеств или алгебра Буля
• 9 ЗАКОН. Дистрибутивность объединенияотносительно пересечения и пересечения
относительно объединения
А ( В С ) ( А В) ( А С )
А ( В С ) ( А В) ( А С )
55. Проверка закона де Моргана
• Пустьx A B
тогда x U и x A B, следовател ьно
x A и x B, отсюда x A и x B
поэтому x A B
следовател ьно A B A B
56. Проверка закона де Моргана
• Пустьx A B, ттогдаx A и x B
отсюда x U и x A и x B
Значит x A B т есть x A B
Следовательно A B A B