Презентация, доклад Дискретная математика


Вы можете изучить и скачать доклад-презентацию на тему Дискретная математика. Презентация на заданную тему содержит 81 слайдов. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций в закладки!
Презентации» Математика» Дискретная математика
Дискретная математика
 Гр. ИВТ-25Д
 Хаиртденов Т.К
 СФТИ НИЯУ МИФИ
 г.Снежинск
 2016Справочные данные
 Кафедра АИВС (Автоматизированных информационных и вычислительных систем)
 Преподаватель МякушкоВведение
 Дискре́тная матема́тика — часть математики, изучающая дискретные математические структуры, такие, как графыВведение
 Дискретная математика – математический аппарат, заложенный в основу работы всехИнформационно - измерительная система ЧеловекИнформационно - измерительная система ТехническаяВосприятие внешнего мира информационно – измерительными системами
 Объекты который присутствуют вокругМое личное определение, что есть множество.
 Множество – это совокупность различныхВосприятие внешнего мира роботомФормальное представление множеств
 А = {a, b, c, d}
 a ∈Пустое множество. Универсум.
 |A| = 0, множество А – пустое множество,Множество. Вектор.
 A= {a,b,c,d},элементы множества можно перемещать. Важно наличие элемента, аОперации над множествами.
 Взаимодействие множеств можем показать через операции над ними.
Пример пересечения множеств.
 |U| = 10, |A| = 8, |B| =Объединение множеств.
 |U| = 10, |A| = 8, |B| = 5Дополнение.
 Дополнение – это элементы которые не достают до универсума
 |U|Разность множеств.
 |U| = 10, |A| = 8, |B| = 5
Симметрическая разность.
 |U| = 10, |A| = 8, |B| = 5
Самостоятельная работа.Множество подмножеств.(Булеан)
 A = {x,y,z}
 β(A) – множество подмножеств
 β(A) =Взаимно – однозначные соответствия Булеана и множества двоичных векторов
 β(A) =Пример
 A = {a,b,c,d}
 β(A) = Ø↔(0,0,0,0,)
 {a,b,c,d} ↔(1,1,1,1)
 {a,b} ↔(1,1,0,0)
Взаимодействие объектов показывается через операции над подмножествами
 β(A) = Ø↔(0,0,0) 
Пример №2
 A = {a,b,c,d}
 β(A) = Ø↔(0,0,0,0)
 {a,b,c,d} ↔(1,1,1,1)
 Опреации над множествами(подмножествами) обладают определенными свойствамиВзаимно – однозначные соответствия для построения цифровых технических систем
 (β(A), U,Операции над переменными логических функций.ОтношенияГрафическое изображение отношений (граф)
 .   .   .Граф – топологический объект, расположение вершин графа не фиксировано, а фиксированоОтношение на прямом произведении A×B×CПримеры отношения на прямом произведении A×B×C
 R⊆A×B×C
 |R|=8, R ={(a,x,p),(a,x,o),(a,x,h),(b,x,p),(b,x,o),
 (b,x,h),(c,x,p),(c,x,o)}Операции над отношениями
 R1⊆A×B, |A| = 5, |B| = 5, AОбратное отношение.
 R-1 – обозначение обратного отношения.
 R = {(a,b),(c,d),(e,f),(i,j)}
 R-1Композиция отношений.
 R1⊆A×B
 R3⊆B×C
 R1⊆A×B
 R1 ◦ R3 - обозначение операции.
|C|= 5, C = {q,w,e,r,t}, |R3|= 14Графическое изображение операции композиция.Отношения на прямом произведении Булеана.
 R⊆β(A) × β(A), где А =Контрольная работа №2
 R1⊆A×B
 R2⊆A×B
 R3⊆B×C
 |A|=|B|=|C|=10;| R1 | = 70,Переменные логических функций. Операции над переменными логических функций.Любую операцию над переменными логических функций мы можем представить через БулевыйСхемное изображение логических элементов.Операция эквивалентность реализованная в Булевом базисе с помощью релейно-контактной схемы.Таблица истинности(переключательная таблица)
 С помощью таблиц истинности получаем результат логической функцииРешение функций с помощью таблицы истинности.
 F(x,y,z)=x•(y→¬z)+(x≡¬y)Решение функций с помощью таблицы истинности.
 F(x,y,z)=x•(y→¬z)+(x≡¬y)Схемная реализация вычисления логической функции от 3х переменных с помощью рэлейноМинимизация СДНФ с использованием карты Карно.
 Имеем логическую функцию F(x,y,z,c)=(⌐(x+c))→((z•y)))≡((⌐c)+(⌐y))Логические элементы с большим количеством входов.Графы.
 Граф состоит из множества вершин и множества ребер (ребра соединяютНеориентированный граф.
 A={x,y,z,c,a,b,d,e} – множество вершин.
 B={{x,z},{x,c},{c,b},{b,e},{e,y},{y,d},{d,a},{a,z},{c,a}} – множество ребер.При изменении вершин топология графа не изменяется.Задание графа с помощью отношения смежности.
 Отношение смежности отношение между вершинамиЗададим неориентированный граф через отношение смежности.Неориентированный мульти-граф, отношении смежности.Неориентированный псевдо-граф, отношении смежности.Ориентированный граф.
 A={x,y,z,c,a,b,d,e} – множество вершин.
 B={(z,x),(x,c),(c,b),(b,e),(e,y),(y,d),(d,a),(a,z),(c,a)(b,d)} – множество ребер.Зададим ориентированный граф через отношение смежности.Неориентированный граф. Можем задать через отношение инцидентности.
 A={x,y,z,c,a,b,d,e} – множество вершин.
Зададим граф с помощью отношения инцидентности.
 R - отношение инцидентности.
 R⊆A×B(отношениеОриентированный граф 
 A={x,y,z,c,a,b,d,e} – множество вершин.
 B={(z,x),(x,c),(c,b),(b,e),(e,y),(y,d),(d,a),(a,z),(c,a)(b,d)} – множество ребер.Зададим орграф через отношение инцидентности.Числа характеризующие граф.
 Степенью вершины называется количество ребер, выходящих из этой вершины.Теорема о степенях вершин в теории графов.
 Сумма степеней всех вершин графа равнаЦикломатическое число.
 Цикломатическим числом графа - называется число u=N-n+p, где N-Найдем путь орг. графа
 (x,c,b,e,y,d,a,z,x)
 (x,c,a,z,x)
 (x,c,b,d,a,z,x)Цикломатическое число позволяет перейти к графу который называется деревом.
 Цикломатическое числоГраф дерево используется для моделирования операций над переменными логических функций
 F(x,y)=xДанная схема, граф – дерево представляется как вершина графа в которойРассмотрим функцию сложения по модулю 2.
 f:An→B
 A – область определенияПредставим функцию F(x1, x2 , … , xn) = x1 ⊕Мажоритарная функция.
 Major – главный, функция принимает значение одни на тех



Слайды и текст этой презентации
Слайд 1
Описание слайда:
Дискретная математика Гр. ИВТ-25Д Хаиртденов Т.К СФТИ НИЯУ МИФИ г.Снежинск 2016


Слайд 2
Описание слайда:
Справочные данные Кафедра АИВС (Автоматизированных информационных и вычислительных систем) Преподаватель Мякушко Эдуард Валерьевич Заведующий кафедрой Крушный Валерий Васильевич

Слайд 3
Описание слайда:
Введение Дискре́тная матема́тика — часть математики, изучающая дискретные математические структуры, такие, как графы и утверждения в логике. Дискретная математика – область математики, занимающаяся изучением дискретных структур (конечного характера), возникающие как в пределах математики, так и в ее приложениях.

Слайд 4
Описание слайда:
Введение Дискретная математика – математический аппарат, заложенный в основу работы всех основных цифровых устройств. Студент изучающий информатику и вычислительные устройства, не может не знать дискретной математики.

Слайд 5
Описание слайда:
Информационно - измерительная система Человек

Слайд 6
Описание слайда:
Информационно - измерительная система Техническая

Слайд 7
Описание слайда:
Восприятие внешнего мира информационно – измерительными системами Объекты который присутствуют вокруг нас (внешний мир), будем воспринимать используя математический объект – множество. Мно́жество — одно из ключевых понятий математики, в частности, теории множеств и логики. Множество – соединение в некое «М» определенных, хорошо различимых предметов «m» нашего созерцания или нашего мышления (которое будет называться «Элементами множества «М»»)

Слайд 8
Описание слайда:
Мое личное определение, что есть множество. Множество – это совокупность различных объектов, объединенное в единое целое.

Слайд 9
Описание слайда:
Восприятие внешнего мира роботом

Слайд 10
Описание слайда:

Слайд 11
Описание слайда:
Формальное представление множеств А = {a, b, c, d} a ∈ A, b ∈ A, c ∈ A, d ∈ A –принадлежность элементов множеству f ∉ A, g ∉ A, h ∉ A – не принадлежность элементов множеству |А|= количество элементов множества (мощность множества) |А|= 4

Слайд 12
Описание слайда:
Пустое множество. Универсум. |A| = 0, множество А – пустое множество, т.к у него отсутствуют элементы. Обозначение Ø. Универсум – универсальное множество. Обозначается U, показывает границы в которых находятся все остальные множества.

Слайд 13
Описание слайда:
Множество. Вектор. A= {a,b,c,d},элементы множества можно перемещать. Важно наличие элемента, а не его положение. A = {b,c,a,d} A= (a,b,c,d),A – вектор, элементы вектора находятся каждый в своем месте, поэтому они называются координатами. Координаты нельзя перемещать со своего места.

Слайд 14
Описание слайда:
Операции над множествами. Взаимодействие множеств можем показать через операции над ними. Пересечение множеств A∩B = общие элементы

Слайд 15
Описание слайда:
Пример пересечения множеств. |U| = 10, |A| = 8, |B| = 5, |A ∩ B| = 3 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} B = {a,b,c,u,d} A∩B = {a,b,c}

Слайд 16
Описание слайда:
Объединение множеств. |U| = 10, |A| = 8, |B| = 5 |A ᴜ B| = 10 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} B = {a,b,c,u,d} A ᴜ B = {a,b,c,t,r,e,y,q,d,u}

Слайд 17
Описание слайда:
Дополнение. Дополнение – это элементы которые не достают до универсума |U| = 10, |A| = 8 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} ¬A = {d,u}

Слайд 18
Описание слайда:
Разность множеств. |U| = 10, |A| = 8, |B| = 5 U = {a,b,c,d,e,r,t,y,u,q} A = {a,b,c,t,r,e,y,q} B = {a,b,c,u,d} A\B = {t,r,e,y,q} B\A = {u,d}

Слайд 19
Описание слайда:
Симметрическая разность. |U| = 10, |A| = 8, |B| = 5 A ᴜ B = {a,b,c,t,r,e,y,q,d,u} A ∩ B = {a,b,c} A ∆ B = {t,r,e,y,q,d,u}

Слайд 20
Описание слайда:
Самостоятельная работа.

Слайд 21
Описание слайда:
Множество подмножеств.(Булеан) A = {x,y,z} β(A) – множество подмножеств β(A) = {Ø,{x},{y},{z},{xy},{xz},{yz},{x,y,z}} | β(A) | = 8 = 2n,где n – число элементов множества. Множество подмножеств - это объекты, окружающие информационно - измерительную систему(роботы) Робот воспринимает эти объекты через двоичные вектора

Слайд 22
Описание слайда:
Взаимно – однозначные соответствия Булеана и множества двоичных векторов β(A) = Ø↔(0,0,0) {x} ↔(1,0,0) {y} ↔(0,1,0) {z} ↔(0,0,1) {xy} ↔(1,1,0) {xz} ↔(1,0,1) {yz} ↔(0,1,1) {x,y,z} ↔(1,1,1)

Слайд 23
Описание слайда:
Пример A = {a,b,c,d} β(A) = Ø↔(0,0,0,0,) {a,b,c,d} ↔(1,1,1,1) {a,b} ↔(1,1,0,0) {a,c} ↔(1,0,1,0) {a,d} ↔(1,0,0,1) {b,c} ↔(0,1,1,0) {b,d} ↔(0,1,0,1) {c,b} ↔(0,1,1,0) {a} ↔(1,0,0,0) {b} ↔(0,1,0,0) {c} ↔(0,0,1,0) {d} ↔(0,0,0,1) {a,b,c} ↔(1,1,1,0) {a,b,d} ↔{1,1,0,1} {d,b,c} ↔(0,1,1,1) {a,c,d} ↔(1,0,1,1)

Слайд 24
Описание слайда:
Взаимодействие объектов показывается через операции над подмножествами β(A) = Ø↔(0,0,0) {x} ↔(1,0,0) {y} ↔(0,1,0) {z} ↔(0,0,1) {xy} ↔(1,1,0) {xz} ↔(1,0,1) {yz} ↔(0,1,1) {x,y,z} ↔(1,1,1) {x}∩{y} = Ø ↔ (1,0,0)*(0,1,0) = (0,0,0) {x,y}U{z,x} = {x,y,z} ↔(1,1,0)+(1,0,1) = (1,1,1) (дизъюнкция -max) ¬{z} = {x,y} ↔¬(0,0,1)=(1,1,0)(отрицание) Операции пересечения, объединения и дополнения являются Булевыми операциями над подмножествами.

Слайд 25
Описание слайда:
Пример №2 A = {a,b,c,d} β(A) = Ø↔(0,0,0,0) {a,b,c,d} ↔(1,1,1,1) {a,b}∩{c,d} = Ø↔(1,1,0,0)*(0,0,1,1)=(0,0,0,0) {a,c}U{b,d} = {a,b,c,d} Ø↔(1,0,1,0)*(0,0,1,1)=(0,0,0,0) ¬{d} = {a,b,c} ↔¬(0,0,0,1)=(1,1,1,0)

Слайд 26
Описание слайда:
Опреации над множествами(подмножествами) обладают определенными свойствами

Слайд 27
Описание слайда:
Взаимно – однозначные соответствия для построения цифровых технических систем (β(A), U, ∩, -) ↕ ↕ ↕ ↕ (Bn, +, *, ⌐) ↕ ↕ ↕ ↕ (P(n), +, *, ⌐) где β(A) – множество подмножеств; Bn -множество двоичных векторов длины n; P(n) - множество переменных логических функций где n - количество переменных.

Слайд 28
Описание слайда:
Операции над переменными логических функций.

Слайд 29
Описание слайда:
Отношения

Слайд 30
Описание слайда:
Графическое изображение отношений (граф) . . . . . . . . . . . . . . . .

Слайд 31
Описание слайда:
Граф – топологический объект, расположение вершин графа не фиксировано, а фиксировано лишь связь между вершинами (элементами множеств)являющимися отношением

Слайд 32
Описание слайда:
Отношение на прямом произведении A×B×C

Слайд 33
Описание слайда:
Примеры отношения на прямом произведении A×B×C R⊆A×B×C |R|=8, R ={(a,x,p),(a,x,o),(a,x,h),(b,x,p),(b,x,o), (b,x,h),(c,x,p),(c,x,o)}

Слайд 34
Описание слайда:
Операции над отношениями R1⊆A×B, |A| = 5, |B| = 5, A ={a,b,c,d,e}, B = {f,i,j,h,k} R2 ⊆A×B, | R1 | = 12, | R2 | = 13

Слайд 35
Описание слайда:
Обратное отношение. R-1 – обозначение обратного отношения. R = {(a,b),(c,d),(e,f),(i,j)} R-1 = {(b,a),(d,c),(f,e),(j,i)} Т.о отношение осуществляется в «обратную» сторону

Слайд 36
Описание слайда:
Композиция отношений. R1⊆A×B R3⊆B×C R1⊆A×B R1 ◦ R3 - обозначение операции. R1 ◦ R3⊆A×С, таким образом операция композиция позволяет перейти в другой универсум («расширить» действие отношений).

Слайд 37
Описание слайда:
|C|= 5, C = {q,w,e,r,t}, |R3|= 14

Слайд 38
Описание слайда:
Графическое изображение операции композиция.

Слайд 39
Описание слайда:
Отношения на прямом произведении Булеана. R⊆β(A) × β(A), где А = {x,y,z}, R - пересечение

Слайд 40
Описание слайда:

Слайд 41
Описание слайда:
Контрольная работа №2 R1⊆A×B R2⊆A×B R3⊆B×C |A|=|B|=|C|=10;| R1 | = 70, | R2| = 80 | R3 | = 60 Выполнить операции над отношениями Сформировать отдельный файл (в свою папку группы) Единицы в произвольном порядке

Слайд 42
Описание слайда:
Переменные логических функций. Операции над переменными логических функций.

Слайд 43
Описание слайда:

Слайд 44
Описание слайда:
Любую операцию над переменными логических функций мы можем представить через Булевый базис(•, +,¬).

Слайд 45
Описание слайда:
Схемное изображение логических элементов.

Слайд 46
Описание слайда:

Слайд 47
Описание слайда:
Операция эквивалентность реализованная в Булевом базисе с помощью релейно-контактной схемы.

Слайд 48
Описание слайда:
Таблица истинности(переключательная таблица) С помощью таблиц истинности получаем результат логической функции для любого числа переменных. Пример: F(x,y,z)=x•(y→¬z)+(x≡¬y)

Слайд 49
Описание слайда:
Решение функций с помощью таблицы истинности. F(x,y,z)=x•(y→¬z)+(x≡¬y)

Слайд 50
Описание слайда:
Решение функций с помощью таблицы истинности. F(x,y,z)=x•(y→¬z)+(x≡¬y)

Слайд 51
Описание слайда:
Схемная реализация вычисления логической функции от 3х переменных с помощью рэлейно – контактной схемы (веник).

Слайд 52
Описание слайда:
Минимизация СДНФ с использованием карты Карно. Имеем логическую функцию F(x,y,z,c)=(⌐(x+c))→((z•y)))≡((⌐c)+(⌐y))

Слайд 53
Описание слайда:

Слайд 54
Описание слайда:

Слайд 55
Описание слайда:

Слайд 56
Описание слайда:

Слайд 57
Описание слайда:

Слайд 58
Описание слайда:
Логические элементы с большим количеством входов.

Слайд 59
Описание слайда:
Графы. Граф состоит из множества вершин и множества ребер (ребра соединяют вершины или одну вершину). Если ребра имеют ориентацию (вход и выход),значит граф ориентированный, если не имеют, значит граф не ориентированный. Граф – есть топологический объект – расположение вершин не фиксировано(располагаются где угодно), фиксируются лишь соединения вершин ребрами.

Слайд 60
Описание слайда:
Неориентированный граф. A={x,y,z,c,a,b,d,e} – множество вершин. B={{x,z},{x,c},{c,b},{b,e},{e,y},{y,d},{d,a},{a,z},{c,a}} – множество ребер.

Слайд 61
Описание слайда:
При изменении вершин топология графа не изменяется.

Слайд 62
Описание слайда:
Задание графа с помощью отношения смежности. Отношение смежности отношение между вершинами графа. Если вершины графа соединены ребром, они связаны отношением смежности. R - отношение смежности. R⊆A×B

Слайд 63
Описание слайда:
Зададим неориентированный граф через отношение смежности.

Слайд 64
Описание слайда:
Неориентированный мульти-граф, отношении смежности.

Слайд 65
Описание слайда:
Неориентированный псевдо-граф, отношении смежности.

Слайд 66
Описание слайда:
Ориентированный граф. A={x,y,z,c,a,b,d,e} – множество вершин. B={(z,x),(x,c),(c,b),(b,e),(e,y),(y,d),(d,a),(a,z),(c,a)(b,d)} – множество ребер.

Слайд 67
Описание слайда:
Зададим ориентированный граф через отношение смежности.

Слайд 68
Описание слайда:
Неориентированный граф. Можем задать через отношение инцидентности. A={x,y,z,c,a,b,d,e} – множество вершин. B={{x,z},{x,c},{c,b},{b,e},{e,y},{y,d},{d,a},{a,z},{c,a}} – множество ребер.

Слайд 69
Описание слайда:
Зададим граф с помощью отношения инцидентности. R - отношение инцидентности. R⊆A×B(отношение инцидентности -отношение между вершинами и ребрами).

Слайд 70
Описание слайда:
Ориентированный граф A={x,y,z,c,a,b,d,e} – множество вершин. B={(z,x),(x,c),(c,b),(b,e),(e,y),(y,d),(d,a),(a,z),(c,a)(b,d)} – множество ребер.

Слайд 71
Описание слайда:
Зададим орграф через отношение инцидентности.

Слайд 72
Описание слайда:
Числа характеризующие граф. Степенью вершины называется количество ребер, выходящих из этой вершины. Если это количество четно, то вершина называется четной, в противном случае вершина называется нечетной.

Слайд 73
Описание слайда:
Теорема о степенях вершин в теории графов. Сумма степеней всех вершин графа равна удвоенному количеству всех ребер. Доказательство. Степень вершины — это количество концов ребер, сходящихся в этой вершине. Поэтому сумма степеней всех вершин графа равна количеству всех концов ребер, которые есть в графе. Но у каждого ребра ровно два конца, значит общее количество ребер в два раза меньше количества концов всех ребер, откуда и получаем утверждение теоремы. Проверим на примере. Сумма степеней = 20, количество ребер умноженное на 2 = 20.

Слайд 74
Описание слайда:
Цикломатическое число. Цикломатическим числом графа - называется число u=N-n+p, где N- число ребер графа, n – число его вершин, P – число компонент связности. Для связного графа u=N-n+1. Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества. Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Слайд 75
Описание слайда:
Найдем путь орг. графа (x,c,b,e,y,d,a,z,x) (x,c,a,z,x) (x,c,b,d,a,z,x)

Слайд 76
Описание слайда:
Цикломатическое число позволяет перейти к графу который называется деревом. Цикломатическое число связного графа можно определить как число ребер, которое нужно удалить, чтобы граф стал деревом. Дерево — это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

Слайд 77
Описание слайда:
Граф дерево используется для моделирования операций над переменными логических функций F(x,y)=x ⊕ y = ¬((¬X+Y) •(X+¬Y)) = = ¬(¬x + y)+ ¬( x+ ¬y)=(¬ ¬ x • ¬y)+(¬ x • ¬ ¬ y)= =(x • ¬y)+(¬ x • y) – выход графа – дерево.

Слайд 78
Описание слайда:
Данная схема, граф – дерево представляется как вершина графа в которой выполняется операция сложения по модулю 2 (неравнозначность). - вершина графа неравнозначности.

Слайд 79
Описание слайда:
Рассмотрим функцию сложения по модулю 2. f:An→B A – область определения функции B - область значений функции Если A=B, то f – функция, есть операция где A = {0,1} B = {0,1} F(x1, x2 , … , xn) = x1 ⊕ x2 ⊕ x3 ⊕ … ⊕ xn

Слайд 80
Описание слайда:
Представим функцию F(x1, x2 , … , xn) = x1 ⊕ x2 ⊕ x3 ⊕ … ⊕ xn в виде графа.

Слайд 81
Описание слайда:
Мажоритарная функция. Major – главный, функция принимает значение одни на тех и только тех наборах, в которых единиц больше чем нулей(функция голосования).


Скачать презентацию на тему Дискретная математика можно ниже:

Похожие презентации