Дискретная математика презентация

Дискретная математика Гр. ИВТ-25Д Хаиртденов Т.К СФТИ НИЯУ МИФИ г.Снежинск 2016

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

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

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

Информационно - измерительная система Человек

Информационно - измерительная система Техническая

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

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

Восприятие внешнего мира роботом

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

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

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

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

Пример пересечения множеств. |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}

Объединение множеств. |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}

Дополнение. Дополнение – это элементы которые не достают до универсума |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}

Разность множеств. |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}

Симметрическая разность. |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}

Самостоятельная работа.

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

Взаимно – однозначные соответствия Булеана и множества двоичных векторов β(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)

Пример 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)

Взаимодействие объектов показывается через операции над подмножествами β(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)(отрицание) Операции пересечения, объединения и дополнения являются Булевыми операциями над подмножествами.

Пример №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)

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

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

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

Отношения

Графическое изображение отношений (граф) . . . . . . . . . . . . . . . .

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

Отношение на прямом произведении 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 ={a,b,c,d,e}, B = {f,i,j,h,k} R2 ⊆A×B, | R1 | = 12, | R2 | = 13

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

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

|C|= 5, C = {q,w,e,r,t}, |R3|= 14

Графическое изображение операции композиция.

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

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

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

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

Схемное изображение логических элементов.

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

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

Решение функций с помощью таблицы истинности. 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}} – множество ребер.

При изменении вершин топология графа не изменяется.

Задание графа с помощью отношения смежности. Отношение смежности отношение между вершинами графа. Если вершины графа соединены ребром, они связаны отношением смежности. 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)} – множество ребер.

Зададим ориентированный граф через отношение смежности.

Неориентированный граф. Можем задать через отношение инцидентности. 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}} – множество ребер.

Зададим граф с помощью отношения инцидентности. 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)} – множество ребер.

Зададим орграф через отношение инцидентности.

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

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

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

Найдем путь орг. графа (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 ⊕ y = ¬((¬X+Y) •(X+¬Y)) = = ¬(¬x + y)+ ¬( x+ ¬y)=(¬ ¬ x • ¬y)+(¬ x • ¬ ¬ y)= =(x • ¬y)+(¬ x • y) – выход графа – дерево.

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

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

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

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