Презентации по дисциплине "Дискретная математика"
презентация к уроку по теме
Презентации по дисциплине "Дискретная математика"
Скачать:
| Вложение | Размер |
|---|---|
 Общие понятия теории множеств | 155.5 КБ |
| Основные операции над множествами | 310.5 КБ |
| Соответствие между множествами. Отображения | 452.5 КБ |
| Классификация множеств. Мощность множества. | 99.5 КБ |
| Отношения. Бинарные отношения и их свойства. | 234 КБ |
| Основные понятия и определения графа и его элементов | 248.5 КБ |
Предварительный просмотр:
Подписи к слайдам:
Совокупность элементов, объединённых некоторым признаком, свойством, составляет понятие множество . Например, множество книг в библиотеке, множество студентов в группе, множество натуральных чисел N и т.д. Запись означает: элемент a принадлежит множеству М , т. е. элемент a обладает некоторым признаком. Аналогично читается: элемент a не принадлежит множеству М . 1.1. Общие понятия теории множеств
Множества удобно изображать с помощью кругов Эйлера . Множество K на рис. 1.1 называют подмножеством множества М и обозначают . Множество K называется подмножеством множества M ( ), если для любого выполняется . Изображение множеств
Универсальным называется множество U , состоящее из всех возможных элементов, обладающих данным признаком. Если множество не содержит элементов, обладающих данным признаком, то оно называется пустым и обозначается . Равными называют два множества A и B , состоящие из одинаковых элементов: . Число элементов множества A называется мощностью множества и обозначается или .
Множество, элементами которого являются подмножества множества М , называется семейством множества М или булеаном этого множества и обозначается В(М). Мощность булеана множества М вычисляется по формуле , где n – это мощность множества М. Пример .
Множество считается заданным , если перечислены все его элементы, или указано свойство , которым обладают те и только те элементы, которые принадлежат данному множеству. Само свойство называется характеристическим . В качестве характеристического свойства может выступать указанная для этого свойства порождающая процедура , которая описывает способ получения элементов нового множества из уже полученных элементов или из других объектов.
Примеры задания множества Множество всех чисел, являющихся неотрицательными степенями числа 2 можно задать: а) перечислением элементов: ; б) указанием характеристического свойства: ; в) с помощью порождающей процедуры по индуктивным правилам: ; если , то .
Вместо выражения «любое х из множества Х» можно писать , где перевёрнутая латинская буква А взята от начала английского слова Any – любой. Вместо выражения «существует элемент х из множества Х» кратко пишут: , где перевёрнутая латинская буква Е является начальной в английском слове Existence – существование.
1.4. Классификация множеств. Мощность множества Множество, содержащее конечное число элементов, называется конечным . Пустое множество является конечным и имеет мощность, равную нулю, т.е. Множество, не являющееся конечным, называется бесконечным . Бесконечное множество, эквивалентное множеству натуральных чисел N, называется счётным . В противном случае бесконечное множество будет несчётным .
Основная теорема о конечных множествах Теорема. Любое конечное множество не эквивалентно никакому его собственному подмножеству, кроме самого себя. Следствие. Всякое непустое конечное множество эквивалентно одному и только одному отрезку натурального ряда чисел . Счётными являются множество Z целых чисел и Q рациональных чисел. Множество R действительных чисел несчётно . Множество действительных чисел называется множеством мощности континуума (от лат. continuum – непрерывный).
Предварительный просмотр:
Подписи к слайдам:
Основные операции над множествами Суммой или объединением двух множеств Х и Y называется множество, состоящее из элементов, входящих или во множество Х , или во множество Y , а может в оба множества одновременно (рис. 1.2). Обозначение:
Пересечением множеств Х и Y называется множество, состоящее из элементов, входящих одновременно и во множество Х , и во множество Y (рис. 1.3). Обозначение: Разностью множеств X и Y называется множество Z , содержащее все элементы множества X , не содержащиеся в Y (рис. 1.4); эта разность обозначается
Дополнением множества до универсального множества U (рис. 1.6) является множество
Симметрической разностью множеств X и Y называется множество Z , содержащее либо элементы множества X , либо элементы множества Y , но не те и другие одновременно ( рис. 1.6 ); эта разность обозначается Х Y . = X Y Рис. 1.6 .
Вместо выражения «любое х из множества Х» можно писать , где перевёрнутая латинская буква А взята от начала английского слова Any – любой. Вместо выражения «существует элемент х из множества Х» кратко пишут: , где перевёрнутая латинская буква Е является начальной в английском слове Existence – существование.
Для операций над множествами справедливы следующие тождества: законы коммутативности объединения и пересечения законы ассоциативности объединения и пересечения
законы дистрибутивности пересечения относительно объединения и объединения относительно пересечения законы поглощения законы склеивания законы Порецкого Операция имеет преимущество перед операцией . Скобки - для наглядности.
законы идемпотентности объединения и пересечения законы действия с универсальным ( U ) и пустым ( ) множествами законы де Моргана закон двойного дополнения
Универсальное ( U ) и пустое ( ) множества являются дополнениями друг друга
В повседневной жизни и математике нам часто приходится иметь дело с упорядоченными множествами — кортежами. Слово кортеж переводится с французского cortege как торжественная процессия (например, свадебный кортеж). Кортежи. Декартовы произведения
Треугольник АВС на плоскости задается кортежем из 6 чисел Где — координаты вершин. Слова в предложении, буквы в слове, предложения в тексте — все это примеры кортежей. Двоичный код является кортежем, состоящим из цифр 0 и 1.
Кортежем длины n из элементов множества А называется упорядоченная последовательность элементов этого множества . Кортежи и называются равными , если они имеют одинаковую длину и их элементы с одинаковыми номерами совпадают, т. е. = , если и для
Например, равны кортежи так как оба кортежа длины 5 и равны все пары соответствующих элементов данных множеств
В отличие от элементов множества элементы кортежа могут совпадать. Например, в прямоугольной системе координат координаты точек являются кортежами. Операция, с помощью которой из двух кортежей длиной k и m можно составить новый кортеж длиной k + m , в котором сначала идут подряд элементы первого кортежа, а затем – элементы второго кортежа, называется соединением кортежей .
Пусть А - конечное множество, элементами которого являются некоторые символы, например цифры, буквы, знаки препинания. Такие множества принято называть алфавитом над заданным множеством символов. Алфавит есть кортеж попарно различимых символов, называемых буквами алфавита. Элементы множества А п принято называть словами длины n в алфавите А . Слово над алфавитом есть просто некоторая конечная последовательность символов. Так, шестизначный телефонный номер является словом длины 6 над алфавитом цифр {0, 1, 2, ..., 9}.
Существуют кортежи, элементы которых являются только нулями или единицами. Кортеж из нулей и единиц можно рассматривать как двоичное представление натурального числа . Кортеж, состоящий из единиц и нулей, описывает состояние памяти вычислительных машин , причём память может содержать числа, тексты, команды и т.д. Кортежи используются в штрих-кодах для сообщения нужной информации о характеристике объекта (белая полоска определённой ширины – 0, чёрная -1).
Декартовым (прямым) произведением множеств называется множество , состоящее из всех кортежей длины k , в которых , где Поскольку для задания кортежа важен порядок, то порядок множителей важен в декартовом произведении. Например декартовым произведением множеств и будет являться множество пар Декартово произведение
Если множества конечны, то их декартово произведение может быть представлено в общем виде таблицей из m столбцов и к строк. Например, декартово произведение X х Y, где можно представить в виде табл.
Число элементов в декартовом произведении конечных множеств А и В равно произведению числа элементов множества А на число элементов множества В . Варианты записи: | А х В | = | А | • | В | или n (А х В) = n (А) • n (В). Если , то пишут . называют n -й декартовой степенью множества А .
Примерами декартовых произведений являются таблицы сложения и умножения, все возможные наборы пар координат на плоскости, троек координат некоторой точки в пространстве. Железнодорожный билет тоже является кортежем, а совокупность всех билетов — декартовым произведением множеств паспортов, посадочных станций, станций прибытия, времени и других множеств.
Свое название декартово произведение получило в честь выдающегося французского математика и философа Рене Декарта (1596—1650), являющегося автором знаменитого метода координат.
Вспомните выражение «прямоугольная декартова система координат», причем координаты точек в этой системе также являются кортежами. На плоскости двумерные кортежи — это пара вида (х;у), а в пространстве — трехмерные кортежи в виде тройки чисел ( x ; у; z), где элементами кортежа являются соответствующие координаты точки.
В программировании декартово произведение встречается в некоторых способах представления данных (массивы, одно-, двух-, трех- и многомерные таблицы и др.).
Предварительный просмотр:
Подписи к слайдам:
Основные понятия. Пусть даны два множества А={а 1 , а 2 ,...} и В={ b 1 , b 2 , ...}. Тогда пары (a i , b j ) задают соответствие между множествами А и В, если указано правило R, по которому для элемента a i множества А выбирается элемент b j из множества В. Например, соответствие между элементами множеств и задает точечное множество ( x i , y j ) координат точек на плоскости; русско-английский словарь устанавливает соответствие значений и написаний слов русского и английского языков.
Пусть задано соответствие R между множествами А и В, т. е. R: (a; b), Для некоторого элемента а множества А поставлен в соответствие некоторый элемент b из множества B, который называется образом элемента а и записывается b = R(a).
Тогда а = R -1 (b) — прообраз элемента который обладает свойствами единственности и полноты: • каждому прообразу соответствует единственный образ; • образ должен быть полным, так же как полным должен быть и прообраз.
Например , если А — множество парабол, В — множество точек плоскости, R — соответствие «вершина параболы», то R(a) — точка, являющаяся вершиной параболы a, a R -1 (b) состоит из всех парабол а i с вершиной в точке b
Образ множества А при соответствии R называется множеством значений этого соответствия и обозначается R(A), если R(A) состоит из образов всех элементов множества А. Запись: Прообраз множества В при некотором соответствии R называют областью определения этого соответствия и обозначают R -1 (B), т.е. R -1 является обратным соответствием для R.
Для описания соответствий между множествами используют понятие отображения (функции) одного множества на другое. Функцией f , действующей из множества X в множество Y ( f: X Y ) называется правило или закон, по которому каждому элементу x X ставится в соответствие один или несколько y Y .
Задание отображений. Для задания отображения необходимо указать: • множество, которое отображается ( область определения данного отображения D(f)); • множество, в (на) которое отображается данная область определения ( множество значений этого отображения E(f)); • закон или соответствие между этими множествами, по которому для элементов первого множества (прообразов, аргументов) выбраны элементы (образы) из второго множества. Приняты записи или f: A В.
Способ задания отображений в виде формул называется аналитическим . Существуют еще табличный и графический способы. Для задания отображения множеств табличным способом принято строить таблицу, в которой первую строку составляют элементы области определения (прообразы вида а), а вторую строку — их образы, т. е. элементы вида (х) при отображении : а (а), где Такой способ удобен при достаточно малой мощности прообраза (не более 10).
Графическое представление отображения связано со стрелочными схемами (диаграммами или графами) . Пример графического задания отображения множества А ={а 1 , а 2 , а 3 } в В = { b 1 , b 2 , b 3 , b 4 , b 5 }.
Отображения f : А В и g: A В называются равными , если Отображения называются однозначными , если каждому аргументу поставлено в соответствие не более одного образа.
Виды отображений. Различают два основных вида однозначных отображений (функций). По мощности они делятся на сюръективные и инъективные
Инъекция
Суръекция
Отображение множества А на множество В, при котором каждому элементу множества В соответствует единственный элемент множества А, называется взаимно-однозначным соответствием между двумя множествами, или биекцией .
Два множества эквивалентны , если между их элементами можно установить биективное отображение. Это обозначается следующим образом: A ~ B.
Пусть множество А отображается взаимно-однозначно на множество В, т.е f :А В . Тогда отображение f -1 , при котором каждому элементу множества В ставится в соответствие его прообраз из множества А, называется обратным отображением для f и записывается или f -1 :В А. Так как одному образу при биекции соответствует в точности один прообраз, обратное отображение будет определено всюду на В и однозначно (отсюда название). Для биекции принята запись:
Если между элементами множеств установлено взаимно-однозначное соответствие, то эти множества имеют одинаковое количество элементов. Говорят, что они равносильны , равномощны , или эквивалентны .
Рассмотрим примеры отображений . 1 ) Каждому действительному числу поставим в соответствие его квадрат. Отображение х х 2 не является взаимно-однозначным соответствием, так как для любого образа у=х 2 можно найти два прообраза в области определения: х = + у и х = - у.
Рассмотрим примеры отображений. 2 ) Англо-русский словарь устанавливает соответствие между множествами слов английского и русского языков. Такое соответствие не является однозначным, так как каждому английскому понятию соответствуют различные варианты перевода на русский язык, и наоборот.
Рассмотрим примеры отображений . 3 ) Различные виды кодирования (азбука Морзе, представление чисел в различных системах счисления, шифрованные сообщения) являются чаще всего примерами взаимно-однозначного соответствия между множествами.
Композиция функций. Пусть заданы отображения f 1 : А В и f 2 : B C . Отображение f : А C , при котором каждому элементу х А соответствует определенный элемент z С, такой, что z = f 2 (y) , где y =f 1 (x), называется произведением, композицией, или суперпозицией отображений f 1 и f 2 .
Отображение е: А А называется тождественным ( единичным ), если каждому аргументу оно ставит в соответствие себя. Очевидно, такое отображение можно задать на любом непустом множестве. Если е(х) = х, то Е(е) = D(e) = А. Очевидно, что отображение, обратное единичному, также единичное.
Предварительный просмотр:
Подписи к слайдам:
Основной характеристикой множеств является количество элементов, содержащихся в этом множестве. Число элементов множества М называется его мощностью и обозначается | М | . Множества А и В называются эквивалентными , или равномощными , А ~ В, если между их элементами можно установить взаимно-однозначное соответствие (биекцию). Тогда |A| = |B|.
Пусть даны два множества А и В. Если они конечны, то сравнивают их мощности, т.е. количество элементов этих множеств. Множества можно классифицировать в зависимости от количества элементов (их мощности) и характера соответствия натуральному ряду чисел .
Множество, содержащее конечное число элементов, называется конечным . Например, конечным является множество однозначных натуральных чисел {1, 2, 3, 4, 5, 6, 7, 8, 9}. Мощность конечного множества из n элементов равна n . Пустое множество по определению не содержит элементов. Оно также является конечным и имеет мощность, равную нулю, т.е. |0| = 0.
Множество, не являющееся конечным, называется бесконечным . Бесконечное множество, эквивалентное множеству натуральных чисел N, называется счетным . Говорят, что все элементы счетного множества можно пронумеровать. В противном случае бесконечное множество будет несчетным.
Классификация множеств в зависимости от их мощности и характера соответствия натуральному ряду чисел
Предварительный просмотр:
Подписи к слайдам:
Соответствие между равными множествами А = В называется отношением на данном множестве (А). Отношения в некоторых числовых множествах могут выражаться терминами: «быть равным», «быть больше», «быть не меньше», «быть делителем» и т.д. Отношения во множестве линий на плоскости могут выражаться терминами: «быть параллельными», «пересекаться», «касаться» и т.д.
Подмножество называется n -местным отношением R на непустом множестве М . При n =2 отношение R называется бинарным . То есть бинарным отношением между элементами множеств А и В называют любое подмножество R множества АхВ и записывают R АхВ. Для отношения R обратным является отношение R - 1 BxA.
Композиция отношений
Бинарные отношения принято записывать в виде aRb , где а, b М . Запись читается как « а и b находятся в отношении R ». Например, а ||b (параллельные прямые), а b (действительные числа), а = log c b и т.д. Рассмотрим примеры бинарных отношений . Бинарное отношение R: х у показано на рис. Заштриховано множество точек, для координат которых это отношение выполняется (истинно).
Графики прямых и обратных бинарных отношений, определенных на множестве действительных чисел, симметричны относительно биссектрисы I и III квадрантов. Это свойство обратных бинарных отношений используют при построении графиков обратных функций, например: у = log 2 x и у=2 х Пример 1. у = х 2 и у = x, где х О (рис. a );
Пример 2. у = sin x и у = arcsin x, где 0 х /2 (рис. б).
Свойства бинарных отношений : 1) рефлексивность: Например: «быть не больше»; «быть делителем» на множестве N ; «быть коллинеарным» на множестве векторов;
Свойства бинарных отношений : 2) антирефлексивность: Это отношение имеет место, когда оно не обладает свойством 1 для любых а, например: «быть больше», «быть младше», «быть перпендикулярной» на множестве прямых и др.
Свойства бинарных отношений : 3) симметричность: Отношение R на множестве М называется симметричным , если для любых a, b M одновременно справедливо aRb и bRa (т.е.R=R -1 ). Например: Симметрична параллельность прямых, так как если а || b , то b || а. Симметрично отношение «быть равным» на любом множестве или «быть взаимно-простым» на N.
Свойства бинарных отношений : 4) антисимметричность: Если для несовпадающих элементов а b верно отношение aRb, то ложно bRa. Антисимметричными являются отношения «быть больше», «не меньше» на множестве R, «быть делителем» на множестве N и др.
Свойства бинарных отношений : 5 ) транзитивность: Если aRb и bRc, то aRс для любых a, b, c M. Транзитивны отношения «быть больше», «быть параллельным», «быть равным» и др.
Свойства бинарных отношений : 6 ) антитранзитивность: Имеет место, когда отношение не обладает свойством 5 . Например, «быть перпендикулярным» на множестве прямых плоскости ( а b, b с, но неверно a с).
Свойства бинарных отношений : 7 ) асимметричность: Ни для одной пары а и b не выполняется одновременно aRb и bRa. Например: «быть больше»; «быть меньше»; «быть отцом».
Свойства бинарных отношений : 8) связность: Для любых а и b , если а b , то aRb или bRa. Например: «быть больше», «быть меньше» на множестве N, R ; «быть больше или равным», «быть меньше или равным» на множестве обыкновенных дробей. Каждое конкретное отношение может обладать или не обладать указанным свойством. или
Свойства бинарных отношений
Основные виды бинарных отношений. Бинарное отношение R называется отношением эквивалентности , если оно одновременно обладает тремя свойствами: рефлективностью, симметричностью и транзитивностью, т.е. если для любых х, у, z выполняется: • xRx (рефлективность); • если xRy, то у R х (симметричность); • если xRy, a yRz, то xRz (транзитивность).
Примеры отношений эквивалентности: Отношение «быть равным на множестве чисел», быть подобным на множестве геометрических фигур. Обозначение эквивалентных отношений : a Q b или а ~ b , что означает «а эквивалентно b в отношении Q» рефлексивность симметричность транзитивность Отношение эквивалентности
Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности, называются классами эквивалентности . На множестве обыкновенных дробей все классы эквивалентности по отношению равенства состоят из дробей, равных по своей величине. На множестве треугольников все классы эквивалентности по отношению подобия состоят из треугольников, подобных между собой.
Отношение эквивалентности – частный случай отношения толерантности. Отношения «быть другом», «быть знакомым», - отношения толерантности, так как они рефлексивны, симметричны, но не транзитивны. Отношение «иметь непустое пересечение» для множеств – отношение толерантности. Отношение толерантности рефлексивность симметричность
Множество М, которое обладает отношением порядка, называется упорядоченным . Отношение порядка антисимметричность транзитивность + рефлексивность + антирефлексивность Отношение нестрогого порядка ≤ Отношение строгого порядка <
Отношение называется отношением полного порядка , если сравнимы все элементы множества, на котором задано это отношение. Пример. Отношения «больше» и «меньше» на множестве действительных чисел. Отношение называется отношением частичного порядка , если сравнимы не все элементы множества, на котором задано это отношение. Пример. Отношение «быть подмножеством» на множестве В( U) ( булеан).
Предварительный просмотр:
Подписи к слайдам:
По теме: методические разработки, презентации и конспекты
Презентации по теме "Математики и математика в годы ВОВ"
Творческая работа...
Презентация к уроку математики."Повторение. Занимательная математика". 6 класс
Цель урока закрепить познавательный интерес к изучению математики и развить познавательные возможности учащихся....
Творческая работа студентов, математика. Презентация (2 части).Математика узоров.
Работа касается одного из самых интересных вопросов геометрии - классификации орнаментов. Восхищаясь рукотворной красотой орнаментов, воплощенных в предметах декоративно-прикладного искусства...
Конспект и презентация к уроку математики по теме "Площадь треугольника" к учебнику С.А. Козловой Математика, 5 класс
Данная разработка содержит конспект урока и презентацию к уроку математики по теме "Площадь треугольника", а так же тест по изученному материалу....
Презентация интегрированного урока математики в 7-х классах "За здоровьем и экологией на урок математики".
Презентация к уроку с физминуткой, упражнением для глаз, разбита на четыре файла: 1- 5 слайды, 6- 10 слайды, 11- 34 слайды, 35- 36 слайды....
Конспект урока математики в 9 классе по теме: «Системы рациональных неравенств». Презентация к уроку математики в 9 классе по теме: «Системы рациональных неравенств».
Материал данного урока предназначен для повторения решения линейных неравенств; формирования понятия «системы рациональных неравенств», «решение рациональных неравенств»; форм...
Презентация к уроку математики в 6 классе по теме: «Задачи на движение» к учебнику «Математика. Арифметика. Геометрия. 6класс» (авторы: : Е.А Бунимович, Л. В. Кузнецова, Г.В Дорофеев, С. Б. Суворова, С.С. Минаева, Л. О. Рослова-М. Просвещение .)
Презентация к уроку математики в 6 классе по теме: «Задачи на движение» к учебнику «Математика. Арифметика. Геометрия. 6класс» (авторы: : Е.А Бунимович, Л. В. Кузнецова, ...