Дискретная математика Выполнили студенты I курса Петросьянц Юрий Гилёв Никита Руководитель Мирзаханян Рузанна Эдуардовна

Периоды развития математики В истории цивилизации можно выделить три крупных периода: сельскохозяйственный, или аграрный до XVII в.; индустриальный с XVII по XX в.; информационный с XX в. Эти периоды определялись научно-техническими революциями и, следовательно, характером тех систем и явлений природы, которые вовлекались в сферу главных производственных интересов и потребностей людей. В каждый период создавались новые технологии производства, новая картина реального мира, новые системы знаний (науки) и, в частности, новая математика. 2

Периоды развития математики Аграрный период Индустриальный период Материальная картина мира Информационный период Энергетическая картина мира Информационная картина мира Элементарная математика Высшая математика Дискретная математика 3

Дискретной математикой называют совокупность математических дисциплин, изучающих свойства абстрактных дискретных объектов. Фундаментом дискретной математики являются: Теория множеств; Математическая логика; Теория графов; Теория кодирования; Теория автоматов. Новый период развития математики 4

Стимулы развития дискретной математики: растущий поток информации и проблемы ее передачи, обработки и хранения привели к возникновению и развитию теории кодирования; различные экономические задачи, задачи электротехники стимулировали создание и развитие теории графов; связь релейно-контактных схем с формулами алгебры логики и их использование для описания функционирования автоматов дали начало развитию и применению математической логики и теории автоматов. Новый период развития математики 5

Обозначения Кванторы: Квантор общности: - «любой», «всякий», «каждый»; Квантор существования: - «существует», «найдется», «можно найти»; «тогда и только тогда», «необходимо и достаточно»; «следует», «выполняется»; : или «такой, что» Пример: ( х М) ( y N: у х) «для любого х из множества М существует у из множества N такой что у меньше, чем х» 6

Теория множеств Дискретная математика

Основные понятия «Под многообразием, или множеством, я понимаю вообще всякое многое, которое можно мыслить как единое, то есть всякую совокупность определённых элементов, которая может быть связана в одно целое с помощью некоторого закона…» Георг Кантор 8

Понятие множества является одним из наиболее общих и наиболее важных математических понятий. Оно было введено в математику немецким ученым Георгом Кантором. Множество, элементы множества – первичные базисные неопределяемые понятия, на которых строится теория множеств. Объекты, составляющие множество, называются элементами множества. Георг Кантор ( ) Основные понятия 9

Примеры множеств: Множество решений уравнения; Множество студентов в группе; Множество предметов мебели в кабинете; Множество натуральных чисел. Пустое множество Среди множеств выделяют особое множество - пустое множество. Пустое множество - множество, не содержащее ни одного элемента. Примеры неочевидных пустых множеств: множество четырехугольников, все углы которых прямые и одновременно диагонали различной длины. Множество решений уравнения Множество чудовищ озера Лох-Несс… 10

Универсальное множество Множество U, содержащее все возможные элементы, обладающие некоторым признаком, называется универсальным (универсумом).. Пример: В математическом анализе: Все действительные числа. Все непрерывные функции на отрезке. В алгебре: Все определители второго порядка, Все трехмерные векторы 11

Множества удобно изображать с помощью кругов Эйлера (диаграмм Венна). Леонард Эйлер (1707 – 1783 г.) Диаграммы Эйлера-Венна – геометрические представления множеств, где множества изображаются в виде совокупностей точек на плоскости ограниченных некоторой замкнутой кривой, а универсум – в виде большого прямоугольника. a, b A d, e A Диаграммы Эйлера-Венна 12

Определение равенства множеств. Два множества называются равными (А=В) в том и только в том случае, когда они состоят из одних и тех же элементов. Примеры: Множества решений уравнений 4 х-8=16 и х/15=2/5 равны, так как их решением является одно и то же число 6. Равны множества букв, из которых составлены слова «навес» и «весна». Равные множества 13

Множество A называют подмножеством множества B (обозначается A B ), если всякий элемент множества A является элементом множества B:. Подмножество (A B) ( a A a B) Множество A называется собственным подмножеством множества B, если A B и А В. Обозначение: А В. Пустое множество является подмножеством любого множества. Все рассматриваемые в задаче множества являются подмножествами универсального множества. 14

Булеаном множества М называется множество (М), элементами которого являются все возможные подмножества множества М. Булеан множества 15

Множество, состоящее из конечного числа элементов называется конечным множеством. Бесконечное множество- непустое множество, не являющееся конечным. Мощностью конечного множества называется число его элементов. Обозначение: А, В. = 0 Конечные и бесконечные 16

Математическая логика Дискретная математика

Основные понятия Математическая логика, как и классическая логика, исследует процессы умозаключений и позволяет из истинности одних суждений делать выводы об истинности или ложности других, независимо от их конкретного содержания. 18

Высказывания и операции над ними Высказыванием называется всякое утверждение, о котором можно вполне определенно и объективно сказать истинно оно или ложно. Отрицание Конъюнкция Дизъюнкция Импликация Эквивалентность 19

Теория графов Дискретная математика

Основные понятия Теория графов - это раздел математики, изучающий системы связей между различными объектами, точно так же как это делается с помощью понятия отношения. Однако независимое определение графа упрощает изложение теории и делает её более понятной и наглядной. Виды графов: неориентированный ориентированный 21

История возникновения теории графов Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Термин «граф» впервые ввел Сильвестр Джеймс Джозеф в 1878 году. Леонард Эйлер ( ) 22 Сильвестр Джеймс Джозеф ( )

Теория кодирования Дискретная математика

Основное понятие Кодирование – преобразование дискретного сообщения в последовательность кодовых символов по заданному правилу. Множество всех кодовых последовательностей (кодовых комбинаций или слов), возможных при данном правиле кодирования, образует код. 24

Теория автоматов Дискретная математика

Основное понятие Теория автоматов раздел дискретной математики, изучающий абстрактные автоматы вычислительные машины, представленные в виде математических моделей и задачи, которые они могут решать. 26

27 Спасибо за внимание