Основы дискретной математики
Костанайский Государственный Университет им. Ахмета Байтурсынова Автор презентации: ст. преподаватель кафедры ИиМ Ермагамбетова Гульмира Нурлановна “Теперь в математике остаются только целые числа и конечные...системы целых чисел...” Анри Пуанкаре. Основное отличие дискретной математики от классической заключается в отсутствии понятия бесконечности, предела и непрерывности, а основным носителем является, например, целые числа, многочлены, матрицы, слова и т. п., которые находятся между собой в каких-то отношениях. В свою очередь, эти отношения изменяются в дискретные моменты времени. Тема: Основы дискретной математики Цель: Цель: Рассмотреть основные понятия множества, основ логики, теории графов. Задачи Лекции: 1 Дать определение множеств, отношений и функций 2 Рассмотреть способы задания функций 3 Классифицировать функции 4 Рассмотреть основные понятия графов 5 Классифицировать основные логические операции 6 Изучить основные понятия о деревьях План Лекции: 1. Функции, отношения и множества 2. Основы логики 3. Графы и деревья I. Функции, отношения и множества X и Y – некоторые числовые множества. Если каждому элементу множества X единственным образом соответствует элемент множества Y, то это соответствие называется Функцией. Обозначение: f : x →y; y = f(x) Здесь Y – зависимая переменная, X – независимая переменная (аргумент) Понятие функции Способы задания функции: Аналитический Табличный Графический Аналитический При аналитическом способе задания функция задается с помощью формул: В явном виде Функция разрешена относительно y : y = х2 В неявном виде Функция не разрешена относительно y: F(x,y) = 0 При аналитическом способе функцию можно задать: Несколькими выражениями Параметрически В полярной системе координат Графический Соответствие между аргументом и функцией задается посредством графика. у x Табличный Данный способ формирует соответствие между аргументом и функцией посредством табличных значений X X1 X2 … Xn Y Y1 Y2 … Yn Классификация элементарных функций Тригонометрическая: Y=sin x,y=cos x,y=tg x,y=ctg x; Обратно тригонометрическая: Y=arcsin X, Y=arccos X, Y =arctg X, X= arcctg Y Степенная: Y=xa; Показательная: Y=ax; Логарифмическая: Y=logax Логическая: Y = true; X = false; Совокупность каких-либо объектов, обладающих общими свойствами, называют Множеством. Понятие множества Обозначение: пара фигурных скобок ”{”, “}” между которыми перечисляют элементы множества. Например: {1, 3, 5, 7} или {a, b, c, d}. Для обозначения множества в тексте используют прописные буквы латинского алфавита A, B, C, ...X, Y, Z, а для его элементов - строчные буквы a, b, c,...x, y, z. Иногда эти буквы используют с индексами. ““ ““ Например: xA Например: хA Принадлежность элемента X множеству A Принадлежность множества Элемент Х не принадлежит множеству A Основное отношение между элементами и множеством - это отношение принадлежности элемента множеству. Понятие множества Счетное - Множество, каждый элемент которого можно индексировать целым числом 1,2,... N. Если N конечно, то множество называют конечным. Число элементов счетного конечного множества A называют его мощностью и обозначают так: |A|=n. Если все элементы множества A являются также элементами множества B, то множество A является подмножеством множества B. Понятие подмножества А={1, 2, 3} B={1, 2, 3, 4, 5} ““ A B подмножество Обозначение: знак включения: AB. знак невключения AB ““ Пустое и универсальное множество Множество, не содержащее ни одного элемента, называют пустым множеством. Пустое множество является подмножеством любого множества. Обозначение: Множество, содержащее все элементы всех подмножеств, принимающих участие в решении каких-либо задач, называют универсальным множеством. ={ } (нет элементов) Обозначение: U U ={a, b, c, d} А={a, b} B={b, c, d} Множество, элементами которого являются подмножества, называют семейством подмножеств. Семейства и классы. Булеан. Множества, элементами которых являются другие множества, часто называют семействами или классами. Например, A{{a, b}, {b, c, d}}, B{{a, b}, {b, c, d}}. Максимально возможное число подмножеств универсального множества называют булеаном. Булеан включает в себя пустое подмножество и множества, сформированные из одного, двух, трех и т.д. до общего числа элементов универсального множества. Алгебра множеств Функции, область определения и область значения которых принадлежит одному множеству, называют операцией. fi: XX или fi: XnX. Множество X вместе c заданным множеством операций F={f1, f2, ..} называют Алгеброй. Законы алгебры множеств Коммутативности: (AB)=(BA) и (AB)=(BA);Ассоциативности: A(BC)=(AB)C и A(BC)=(AB)C;Идемпотентности: AA=A и AA=A;Поглощения: A(AB)=A и A(AB)=A;Дистрибутивности: A(BC)=(AB)(AC) и A(BC)=(AB)(AC);“Третьего не дано” AA=U;Противоречия: AA=.Двойного отрицания: (A)=A. - символ унарной операции – дополнения, - символ бинарной операции – объединения, -символ бинарной операции - пересечения. Объединение множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному множеству А или В, т.е. С=(АВ)={x| xA или xB}. Если В=, то АВ=А=А.Если B=U, то АВ=АU=U. Если АС и ВС, то АВС. Обозначение: Объединение множеств Пересечение множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат множеству А и принадлежат множеству В, т.е. (АВ)={x|xA и xB}. Если В=, то АВ=А=. Если B=U, то АВ=АU=А.Если СА и СВ, то САВ.Если А и В, то при АВ= множества A и B не имеют общих элементов Обозначение: Пересечение множеств Обозначение: Разность множеств Разность множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат множеству А и не принадлежат множеству В. “\” С=(А\В)= {x|xА и xВ}, Обозначение: Симметрическая Разность множеств Симметрическая разность множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат разности (А\В) или (В\А). “” С=(АВ)=(АВ)(ВА) (АВ)=(АВ)(ВА)=, то А=В. *Это правило будет часто использоваться при доказательстве тождеств и поиске неизвестных множеств. Отображение, заданное между элементами одного множества Х, называют Отношением. Между математическими объектами такими отношениями могут быть {=, , , , <, }.Между “нематематическими” объектами {“x принадлежит y”, “x часть y”, “x смежный y”, “x родственник y”, “x родитель y”, “x находится рядом с y”,..}. Отношение Бинарным или двуместным отношением между элементами множеств A и B называется любое подмножество R их декартова произведения A Ч B . Говорят также, что R является отношением из A в B. При A = B отношение R называется бинарным отношением на A. Вместо (x,y) R часто пишут xRy.) R часто пишут xRy. Бинарное отношение Бинарные отношения между элементами множества X удобно описывать матрицами (ХХ), строки и столбцы которых есть элементы множества.На пересечении i-ой строки и j-го столбца ставят знак “1”, если задано отношение r(i, j) между i-м и j-м элементами и “0” в противном случае Симметричность Антисимметричность Асимметричность Транзитивность Антирефлексивность Свойства отношений Рефлексивность Бинарное отношение рефликсивно, если для каждого хiХ имеем r(xi; xi)=1. Такими отношениями являются “..=..”, “..быть похожим..”, “..быть изоморфным..”, и т.п. При матричном описании такого отношения на главной диагонали матрицы будут только “1”, т.е. r(xi, xi)=1. Рефлексивность Антисимметричность Бинарное отношение антисимметрично, если для любой пары (xi, xj) при ij имеем r(xi, xi)r(xj, xi), а при i=j имеем r(xi, xi)=1. Такими отношениями являются “....”, “....” и т.п.. При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали и наличие “1” на главной диагонали. Симметричность Бинарное отношение симметрично, если для любой пары (xi, xj)R имеем r(xi, xi)=r(xj, xi)=1. Такими отношениями являются “....”, “..быть похожим..”, “..быть эквивалентным..”, “..быть родственником..” и т.п.. При матричном задании такого отношения будет симметричное расположение “1” относительно главной диагонали, т.е. r(xi, xi)=r-1(xj, xi). Антирефлексивность Бинарное отношение антирефлексивно, если для каждого хiХ имеем r(xi, xi)=0. Такими отношениями являются “.... ”, “..<..”, “быть родителем” и т.п.При матричном описании такого отношения на главной диагонали матрицы будут только “0”, т.е. r(xi, xi)=0. Транзитивность Бинарное отношение транзитивно, если для любых элементов xi, xj, xkХ существует r(xi, xi)=1 тогда и только тогда, когда существует r(xi, xk)=1 и r(xk, xi)=1. Такими отношениями являются “....”, “..<..”, “быть родителем”, “быть родственником” и т.п.. Асимметричность Бинарное отношение асимметрично, если для любой пары (xi, xj) при i j имеем r(xi, xi) r(xj, xi), а при i=j имеем r(xi, xi)=0. Такими отношениями являются “.. ..”, “..<..”, “быть родителем” и т.п. При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали и наличие “0” на главной диагонали. Бинарное отношение, удовлетворяющее условиям рефлексивности, симметричности и транзитивности называют Отношением Эквиваленции. Симметричность Асимметричность Рефлексивность Отношения Эквиваленций = + + Отношения Эквиваленций Отношение эквиваленции обозначают r~(xi, xi) или ~(xi, xi). II. Основы логики Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные в 4 веке до нашей эры древне-греческими мыслителями . История логики Первым этапом на пути в развитии логики заложил Аристотель, создав основы формальной логики, где впервые отделил логические формы речи от ее содержания. Вильгельм Готфрид Лейбниц (1646 - 1716) Второй этап – математическая логика, основы которой заложил в своей работе "Об искусстве комбинаторики" (1666) великий немецкий философ, математик, физик и языковед Готфрид Вильгельм Лейбниц. Джордж Буль (1815-1864) Основоположник математической логики считается Джордж Буль (1815-1864),английский математик. Поэтому начальный раздел математической логики часто называют булевой алгеброй или алгеброй логики. В современное время для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании решения задач широко используется математический аппарат алгебры логики. Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операции над ними. Формальная система, носителем которой являются символы и последовательности символов формального языка, а множество операций используется для формирования и вывода новых суждений формального языка. Типы формальных систем Логика высказываний Логика предикатов Логика отношений Нечеткая логика Логика предикатов Логика предикатов (predicate calculus) есть формальная система, предметом которой являются предложения с учетом их внутренних состава и структуры. Логика высказываний Логика высказываний (prepositional calculus) есть модель формальной системы, предметом которой являются повествовательные предложения, взятые целиком без учета их внутренней структуры. Логическое высказывание – это любое повествовательное предложение, в отношении которого можно сказать, истинно оно или ложно. Например, предложение «6-четное число» следует считать высказыванием, так как оно истинное. Предложение «Рим – столица Франции» тоже высказывание, так как оно ложное. Нечеткая логика Логика нечеткая (fuzzi calculus) есть формальная система, предметом которой являются предложения при нечетком задании характерных признаков отдельных составляющих элементов или отношений между ними. Логика отношений Логика отношений (relation calculus) есть формальная система, предметом которой являются отношения в виде множества однородных предложений, существенно расширяющие логику предикатов. Также эту логику называют реляционной. Любое повествовательное предложение, которое может быть признано истинным или ложным, называют высказыванием. Высказывания, которые получаются из простых предложений с помощью грамматических связок “не”, “и”, “или”, “если…, то…”, “… тогда и только тогда, когда…” и т.п., называют сложными. Для обозначения грамматических связок в формальном языке вводят дополнительные символы, которые называют логическими связками. :=”или”, &:=“и”, :=”не”, :=“если…, то…”, :=“…тогда и только тогда, когда …”.Для построения сложных высказываний используют также вспомогательные символы “(“, “)” - скобки. Высказывание Алгебра высказываний Модель алгебры высказываний. Множество T={A, B, C,…} с заданными над ним логическими операциями F={; ; ; ; } формируют модель алгебры высказываний Aв=
. Сложное высказывание, которое может быть получено из элементарных высказываний посредством применения логических связок, называют формулой алгебры логики. Логические операции Логические операции бывают унарные (или одноместные) и бинарные (или двухместные). Это определяется наличием одного или двух операндов у операции. Символы логических операций заданы логическими связками: - отрицание, - конъюнкция, - дизъюнкция, - импликация, - эквиваленция. Различные значения логической формулы в зависимости от значений входящих в нее элементарных высказываний, могут быть полностью описаны с помощью таблицы истинности. Отрицание Логические операции Конъюнкция Дизъюнкция Импликация Эквиваленция Отрицание Отрицание (операция НЕ) есть одноместная операция, посредством которой ее значение есть отрицание значения операнда. ( F) Обозначение: Таблица логического отрицания А Х 0 1 1 0 Конъюнкция Конъюнкция есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F=(F1F2), описывающую сложное высказывание. Значение этого высказывания истинно тогда и только тогда, когда истинны значения двух операндов F1 и F2. (F1F2) Обозначение: Таблица логического умножения А В Х 0 0 0 0 1 0 1 0 0 1 1 1 Дизъюнкция есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F=(F1F2), описывающую сложное высказывание. Значение этого высказывания ложно тогда и только тогда, когда ложны значения двух операндов F1 или F2. (F1F2) Обозначение: Дизъюнкция А В Х 0 0 0 0 1 1 1 0 1 1 1 1 Таблица логического сложения Эквиваленция А В Х 0 0 1 0 1 1 1 0 0 1 1 1 Таблица логической эквивалентности Обозначение: Эквиваленция есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F=(F1F2), описывающую сложное высказывание. Значение этого высказывания истинно тогда и только тогда, когда оба операнда F1 и F2 имеют одинаковые значения. (F1F2) Импликация есть двуместная операция, посредством которой отражающую сложное высказывание. Значение этого высказывания ложно тогда и только тогда, когда истинно значение F1 и ложно F2. (F1F2) Обозначение: Импликация А В Х 0 0 1 0 1 0 1 0 0 1 1 1 Таблица логического следования Законы Алгебры Логики Законы Алгебры Логики Наименование закона Равносильные формулы Fi=Fj Коммутативности (F1F2)=(F2F1); (F1F2)=(F2F1) Ассоциативности F1(F2F3)=(F1F2)F3; F1(F2F3) = (F1F2) F3 Дистрибутивности F1(F2F3)=(F1F2)(F1F3); F1(F2F3)=F1F2F1F3 Идемпотентности FF = F; FF = F Исключенного третьего FF = и; Противоречия FF = л Де Моргана (F1F2) = F1F2; (F1F2) = F1F2. Поглощения F1(F1F2) = F1; F1(F1F2) = F1 Дополнения (F) = F Свойства констант Fл = F; Fи = и; Fл= л; Fи = F III.Графы и деревья Теория графов находит самое широкое применение в моделировании информационных процессов, в программировании и в решении экономических задач. Она позволяет просто описывать сложные явления и дает им графическую интерпретацию. ”Картинка” графа позволяет быстро понять проблему и на интуитивном уровне разработать рациональный алгоритм решения. Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый Графом. Первая работа по теории графов была опубликована математиком Л. Эйлером в 1736г. в Трудах Академии наук Санкт-Петербурга в виде задачи о Кенигсбергских мостах. Суть задачи сводилась к следующему: мог ли житель Кенигсберга, выйдя из дома, находящегося на части суши A, B, С или D, пройти по семи мостам через реку Прегель в точности по одному разу и вернуться домой? Ответ на этот вопрос был отрицательным. История графов Для пояснения задачи представлена модель, где каждый участок суши замещен точкой на плоскости, а мосты – линиями, связывающими участки. Совокупность объектов произвольной природы и отношений между каждой парой этих объектов может быть изображена на плоскости в виде множества точек, являющихся образом множества объектов, и множества отрезков линий, соединяющих пары точек, что является образом множества отношений. Такой образ объектов и отношений принято называть графом. Множество точек, являющихся образом множества объектов, называют вершинами графа, а множество отрезков линий, являющихся образом множества отношений, - рёбрами или дугами графа. Вершинами графа могут быть операторы программы или команды операционной системы, контактные площадки на плате компьютера, узлы транспортной или электрической сети, события в любой сфере человеческой деятельности.Рёбрами или дугами – связи операторов программы, команд операционной системы, контактных площадок на плате компьютера, узлов в транспортной или в электрической сети или причинно-следственные связи событий в любой сфере человеческой деятельности. Вершина Ребро Ориентированный граф - это пара (V, E), где V - конечное множество вершин (узлов, точек) графа, а E - некоторое множество пар вершин, т.е. подмножество множества V Ч V или бинарное отношение на V. Элементы E называют ребрами (дугами, стрелками, связями). Для ребра e=(u,v) E вершина u называется началом e, а вершина v - концом e, говорят, что ребро e ведет из u в v. V1={ a,b,c,d}, E1={ (a,b), (a,c), (b,b), (b,d), (d,a)}, G1=(V1, E1) Ориентированный граф Неориентированный граф G=(V, E) - это ориентированный граф, у которого для каждого ребра (u,v) E имеется противоположное ребро (v,u) E, т.е. отношение E симметрично. Для его задания можно использовать обозначение для множества концов: {u, v}, но чаще используется указание одной из пар в круглых скобках. Если e= (u,v) E, то вершины u и v называются смежными в G, а ребро e и эти вершины называются инцидентными. Степенью вершины в неориентированном графе называется число смежных с ней вершин. Вершина степени 0 называется изолированной. Такая пара (u,v), (v,u) называется неориентированным ребром G2=(V2, E2 ) V2={ a,b,c,d}, E2={ (a,b), (a,c), (a,d), (b,d)} Неориентированный граф Деревья Деревья являются одним из интереснейших классов графов, используемых для представления различного рода иерархических структур. Неориентированный граф называется деревом, если он связный и в нем нет циклов. Ориентированный граф G=(V,E) называется (ориентированным) деревом, если: в нем есть одна вершина, в которую не входят ребра; она называется корнем деревав каждую из остальных вершин входит ровно по одному ребру;все вершины достижимы из корня. Способы обхода деревьев. Часто при обработке представленной в дереве информации требуется обойти некоторым регулярным способом все его вершины. Способы позволяют линейно упорядочить вершины дерева и тем самым представить его "двумерную структуру" в виде линейной последовательности вершин. Способы обхода деревьев Прямой Обратный основан на принципе: "сначала родитель, затем дети" основан на противоположном принципе: "сначала дети, затем родитель". Литература:1.Информатика Учеб. для студентов эконом. спец. вузов/под ред.Макаровой.-3-е изд., - М.: Финансы и статистика, 2007.-с.124-1272.Угринович Н.Д. Практикум по информатике и информационным технологиям. Учебное пособие для общеобразовательных учреждений. Изд.2-е, испр.-М.: БИНОМ. Лаборатория знаний, 2004, с.84-1083.Дехтярь М.И. Лекции по дискретной математике. БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2007 4.Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2006 5.Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов. БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2007 ??? Контрольные вопросы: Что такое множества?Что такое функция?Какие существуют функции?Способы заданий функций?Какие существуют операции над множествами?Что такое отношение?Что такое математическая логика?Перечислите логические операции?Что такое графы?Как представлены деревья?Как классифицируются графы? Спасибо За Внимание!!!