Лекция 1 Множества




НазваниеЛекция 1 Множества
Дата конвертации07.02.2013
Размер445 b.
ТипЛекция


Дискретная математика

  • Преподаватель

  • Белгородцева

  • Наталия Александровна


Лекция 1 Множества

  • Цель лекции – познакомить студентов:

  • 1) с общими понятиями теории множеств;

  • 2) с основными операциями над множествами;

  • 3) с соответствиями между множествами и с отображениями;

  • 4) с классификацией множеств и с мощностью множества;



5) с кортежами и с декартовыми произведениями;

  • 5) с кортежами и с декартовыми произведениями;

  • 6) с отношениями, с бинарными отношениями и их свойствами;

  • 7) с элементами комбинаторики;

  • 8) с подстановками.



Введение

  • Дискретная математика – направление в математике, объединяющее отдельные её разделы, ранее сформированные как самостоятельные теории. К ним относятся математическая логика и теории множеств, графов, кодирования, автоматов.

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



Дискретная математика использует средства, разработанные в классической математике. Однако характер объектов, исследуемых дискретной математикой, настолько разнообразен, что методов классической математики не всегда достаточно для их изучения. Поэтому те специфические методы, которые применяют для очень широкого класса конечных дискретных (имеющих прерывный характер) объектов, и были объединены в общее направление – дискретную математику.

  • Дискретная математика использует средства, разработанные в классической математике. Однако характер объектов, исследуемых дискретной математикой, настолько разнообразен, что методов классической математики не всегда достаточно для их изучения. Поэтому те специфические методы, которые применяют для очень широкого класса конечных дискретных (имеющих прерывный характер) объектов, и были объединены в общее направление – дискретную математику.

  • В настоящее время знание дискретной математики необходимо специалистам в различных областях деятельности.



1.1. Общие понятия теории множеств

  • Совокупность элементов, объединённых некоторым признаком, свойством, составляет понятие множество. Например, множество книг в библиотеке, множество студентов в группе, множество натуральных чисел N и т.д.

  • Запись означает: элемент a принадлежит множеству М, т. е. элемент a обладает некоторым признаком. Аналогично читается: элемент a не принадлежит множеству М.



Изображение множеств

  • Множества удобно изображать с помощью кругов Эйлера.

  • Множество K на рис. 1.1 называют подмножеством множества М и обозначают

  • .

  • Множество K называется

  • подмножеством множества

  • M ( ), если для любого

  • выполняется .



Универсальным называется множество U, состоящее из всех возможных элементов, обладающих данным признаком.

  • Универсальным называется множество U, состоящее из всех возможных элементов, обладающих данным признаком.

  • Если множество не содержит элементов, обладающих данным признаком, то оно называется пустым и обозначается .

  • Равными называют два множества A и B, состоящие из одинаковых элементов: .

  • Число элементов множества A называется мощностью множества и обозначается или .



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

  • Множество, элементами которого являются подмножества множества М, называется семейством множества М или булеаном этого множества и обозначается В(М).

  • Мощность булеана множества М вычисляется по формуле

  • ,

  • где n – это мощность множества М.

  • Пример.



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

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

  • В качестве характеристического свойства может выступать указанная для этого свойства порождающая процедура, которая описывает способ получения элементов нового множества из уже полученных элементов или из других объектов.



Примеры задания множества

  • Множество всех чисел, являющихся неотрицательными степенями числа 2 можно задать:

  • а) перечислением элементов: ;

  • б) указанием характеристического свойства:

  • ;

  • в) с помощью порождающей процедуры по индуктивным правилам:

  • ;

  • если , то .



1.2. Основные операции над множествами

  • Суммой или объединением двух множеств Х и Y называется множество, состоящее из элементов, входящих или во множество Х, или во множество Y, а может в оба множества одновременно (рис. 1.2). Обозначение:



Пересечением множеств Х и Y называется множество, состоящее из элементов, входящих одновременно и во множество Х, и во множество Y (рис. 1.3). Обозначение:

  • Пересечением множеств Х и Y называется множество, состоящее из элементов, входящих одновременно и во множество Х, и во множество Y (рис. 1.3). Обозначение:

  • Разностью множеств X и Y называется множество Z, содержащее все элементы множества X, не содержащиеся в Y (рис. 1.4); эта разность обозначается



Дополнением множества до универсального множества U (рис. 1.6) является множество

  • Дополнением множества до универсального множества U (рис. 1.6) является множество



Симметрической разностью множеств X и Y называется множество Z, содержащее либо элементы множества X, либо элементы множества Y, но не те и другие одновременно (рис. 1.6); эта разность обозначается Х Y.

  • Симметрической разностью множеств X и Y называется множество Z, содержащее либо элементы множества X, либо элементы множества Y, но не те и другие одновременно (рис. 1.6); эта разность обозначается Х Y.

  • =



Вместо выражения

  • Вместо выражения

  • «любое х из множества Х»

  • можно писать , где перевёрнутая латинская буква А взята от начала английского слова Any – любой.

  • Вместо выражения

  • «существует элемент х из множества Х»

  • кратко пишут: , где перевёрнутая латинская буква Е является начальной в английском слове Existence – существование.



Множество A можно разбить на классы (непересекающиеся подмножества) Ai, если:

  • Множество A можно разбить на классы (непересекающиеся подмножества) Ai, если:

  • объединение всех подмножеств совпадает с множеством A: ;

  • пересечение любых двух различных подмножеств пусто, т.е. для любых выполняется .



Для операций над множествами справедливы следующие тождества:

  • Для операций над множествами справедливы следующие тождества:

  • законы коммутативности объединения и пересечения

  • законы ассоциативности объединения и пересечения



законы дистрибутивности пересечения относительно объединения и объединения относительно пересечения

  • законы дистрибутивности пересечения относительно объединения и объединения относительно пересечения

  • законы поглощения

  • законы склеивания

  • законы Порецкого

  • Операция имеет преимущество перед операцией . Скобки - для наглядности.



законы идемпотентности объединения и пересечения

  • законы идемпотентности объединения и пересечения

  • законы действия с универсальным (U) и пустым (  ) множествами

  • законы де Моргана

  • закон двойного дополнения



1.3. Соответствия между множествами. Отображения

  • Пары задают соответствие между множествами A и B, если указано правило R, по которому для элемента множества A выбирается элемент из множества B.

  • Пусть для некоторого элемента a множества A поставлен в соответствие некоторый элемент b из множества B, который называется образом элемента a и записывается . Тогда - прообраз элемента .



Образ множества A при соответствии R называется множеством значений этого соответствия и обозначается , если состоит из образов всех элементов множества А:

  • Образ множества A при соответствии R называется множеством значений этого соответствия и обозначается , если состоит из образов всех элементов множества А:

  • Прообраз множества B при некотором соответствии R называют областью определения этого соответствия и обозначают т.е.

  • является обратным соответствием для R.



Для описания соответствий между множествами используют понятие отображения.

  • Для описания соответствий между множествами используют понятие отображения.

  • Для задания отображения f необходимо указать:

  • множество, которое отображается (область определения отображения, обозначается );

  • множество, в (на) которое отображается область определения (множество значений этого отображения, обозначается );

  • закон или соответствие между этими множествами, по которому для элементов первого множества выбраны элементы из второго.



При записи подразумевается, что отображение f определено всюду на A, т.е. A – полный прообраз отображения f, хотя для B такое свойство полноты не подразумевается.

  • При записи подразумевается, что отображение f определено всюду на A, т.е. A – полный прообраз отображения f, хотя для B такое свойство полноты не подразумевается.

  • Однозначным называется отображение, где каждому аргументу поставлено в соответствие не более одного образа.

  • Отображения можно задавать:

  • а) аналитически ( с помощью формул);

  • б) графически ( с помощью стрелочных схем);

  • в) с помощью таблиц.



Классификация отображений по мощности

  • На множество

  • «сюръекция»;

  • На множество

  • «биекция»;

  • Во множество

  • «инъекция».



На множество - «сюръекция»

  • Соответствие. при котором каждому элементу множества А указан единственный элемент множества В, а каждому элементу множества В можно указать хотя бы один элемент множества А, называется отображением множества А на множество В



На множество - «биекция»

  • Отображение множества А на множество В, при котором каждому элементу множества В соответствует единственный элемент множества А, называется взаимно-однозначным соответствием между двумя множествами, или биекцией.



Во множество - «инъекция»

  • Соответствие. при котором каждому элементу множества А указан единственный элемент множества В, а каждому элементу В соответствует не более одного прообраза из А, называется отображением множества А во множество В.



Пусть множество А отображается взаимно-однозначно на множество В, т.е. . Тогда отображение , при котором каждому элементу множества В ставится в соответствие его прообраз из множества А, называется обратным отображением для f и записывается или .

  • Пусть множество А отображается взаимно-однозначно на множество В, т.е. . Тогда отображение , при котором каждому элементу множества В ставится в соответствие его прообраз из множества А, называется обратным отображением для f и записывается или .

  • Если между элементами множеств установлено взаимнооднозначное соответствие, то эти множества равносильны, равномощны, или эквивалентны.



1.4. Классификация множеств. Мощность множества

  • Множество, содержащее конечное число элементов, называется конечным. Пустое множество является конечным и имеет мощность, равную нулю, т.е. Множество, не являющееся конечным, называется бесконечным.

  • Бесконечное множество, эквивалентное множеству натуральных чисел N, называется счётным. В противном случае бесконечное множество будет несчётным.



Основная теорема о конечных множествах

  • Теорема. Любое конечное множество не эквивалентно никакому его собственному подмножеству, кроме самого себя.

  • Следствие. Всякое непустое конечное множество эквивалентно одному и только одному отрезку натурального ряда чисел .

  • Счётными являются множество Z целых чисел и Q рациональных чисел. Множество R действительных чисел несчётно.

  • Множество действительных чисел называется множеством мощности континуума (от лат. continuum – непрерывный).



1.5. Кортежи. Декартовы произведения

  • Кортежем длины n из элементов множества А называется упорядоченная последовательность элементов этого множества.

  • Кортежи и

  • называются равными, если они имеют одинаковую длину и их элементы с одинаковыми номерами совпадают, т. е. = , если и для



В отличие от элементов множества элементы кортежа могут совпадать.

  • В отличие от элементов множества элементы кортежа могут совпадать.

  • Например, в прямоугольной системе координат координаты точек являются кортежами.

  • Операция, с помощью которой из двух кортежей длиной k и m можно составить новый кортеж длиной k + m, в котором сначала идут подряд элементы первого кортежа, а затем – элементы второго кортежа, называется соединением кортежей.



Существуют кортежи, элементы которых являются только нулями или единицами.

  • Существуют кортежи, элементы которых являются только нулями или единицами.

  • Кортеж из нулей и единиц можно рассматривать как двоичное представление натурального числа.

  • Кортеж, состоящий из единиц и нулей, описывает состояние памяти вычислительных машин, причём память может содержать числа, тексты, команды и т.д.

  • Кортежи используются в штрих-кодах для сообщения нужной информации о характеристике объекта (белая полоска определённой ширины – 0, чёрная -1).



Декартово произведение

  • Декартовым (прямым) произведением множеств называется множество , состоящее из всех кортежей длины n, в которых , где

  • Если , то пишут .

  • называют n-й декартовой степенью множества А.



1.6. Отношения. Бинарные отношения и их свойства

  • Подмножество называется n-местным отношением R на непустом множестве М. При n=2 отношение R называется бинарным.

  • Свойства бинарных отношений:

  • рефлексивность:

  • антирефлексивность:



симметричность:

  • симметричность:

  • антисимметричность:

  • асимметричность:



транзитивность:

  • транзитивность:

  • антитранзитивность:

  • связность:



Каждое конкретное отношение может обладать или не обладать указанным свойством.

  • Каждое конкретное отношение может обладать или не обладать указанным свойством.

  • Примеры рефлексивных отношений:

  • «быть не больше»; «быть делителем» на множестве N; «быть коллинеарным» на множестве векторов;

  • Примеры антирефлексивных отношений:

  • «быть больше»; «быть младше»; «быть перпендикулярной» на множестве прямых;

  • Примеры симметричных отношений:

  • «быть перпендикулярным»; «быть равным»; «быть параллельным»;



Примеры антисимметричных отношений:

  • Примеры антисимметричных отношений:

  • «быть меньше или равным»; «быть делителем»;

  • «быть подмножеством»;

  • Примеры асимметричных отношений;

  • «быть больше»; «быть меньше»; «быть отцом»;

  • Примеры транзитивных отношений:

  • «быть больше»; «быть меньше»; «быть равным»;

  • Примеры антитранзитивных отношений:

  • «быть перпендикулярным» на множестве прямых плоскости; «быть сыном»; «жить этажом выше» для жильцов дома.



Примеры отношений связности:

  • Примеры отношений связности:

  • «быть больше», «быть меньше» на множестве N, R; «быть больше или равным», «быть меньше или равным» на множестве обыкновенных дробей.

  • Примеры отношений эквивалентности:

  • Отношение «быть равным», «иметь один и тот же остаток от деления на конкретное число»



Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности, называются классами эквивалентности.

  • Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности, называются классами эквивалентности.

  • На множестве обыкновенных дробей все классы эквивалентности по отношению равенства состоят из дробей, равных по своей величине.

  • На множестве треугольников все классы эквивалентности по отношению подобия состоят из треугольников, подобных между собой.



  • Отношение эквивалентности – частный случай отношения толерантности.

  • Отношения «быть другом», «быть знакомым», - отношения толерантности, так как они рефлексивны, симметричны, но не транзитивны.

  • Отношение «иметь непустое пересечение» для множеств – отношение толерантности.



  • Множество М, которое обладает отношением порядка, называется упорядоченным.



Отношение называется отношением полного порядка, если сравнимы все элементы множества, на котором задано это отношение.

  • Отношение называется отношением полного порядка, если сравнимы все элементы множества, на котором задано это отношение.

  • Пример. Отношения «больше» и «меньше» на множестве действительных чисел.

  • Отношение называется отношением частичного порядка, если сравнимы не все элементы множества, на котором задано это отношение.

  • Пример. Отношение «быть подмножеством» на множестве В(U) (булеан).



1.7. Элементы комбинаторики

  • Раздел математики, занимающийся подсчётами количества различных комбинаций между объектами, называется комбинаторикой.

  • Все комбинаторные задачи сводятся к подсчёту мощности конечных множеств и их отображений.

  • Правило суммы. Пусть элемент α можно выбрать k способами, а элемент  - m способами, причём, если любой способ выбора α отличается от любого способа выбора , то выбор «α или » можно сделать k+m способами.



Правило произведения. Если элемент α можно выбрать k способами, а элемент  - m способами, то пару (α, ) можно выбрать k  m способами.

  • Правило произведения. Если элемент α можно выбрать k способами, а элемент  - m способами, то пару (α, ) можно выбрать k  m способами.

  • Пример. Если в группе 16 юношей и 14 девушек, то преподаватель может вызвать к доске одного учащегося 16 + 14 = 30 способами.

  • Частный случай правила произведения – число размещений с повторениями для подсчёта кортежей длины k, составленных из элементов множества Х мощности m.



Перестановки. Упорядоченные множества (кортежи), состоящие из n различных элементов, называются перестановками (без повторений). Обозначение : .

  • Перестановки. Упорядоченные множества (кортежи), состоящие из n различных элементов, называются перестановками (без повторений). Обозначение : .

  • Формула для нахождения числа перестановок: .

  • Задачи:

  • Сколькими способами можно переставлять элементы множества, чтобы получить различные кортежи длины n ?

  • Сколькими способами можно расфасовать n шаров разного цвета в ящик с n свободными местами ?



Пример. Из цифр 3, 5, 7, 9 можно составить 4! кортежей, так как n=4, то Р4=4!=4321=24, т.е. существует 24 различных четырёхзначных числа, составленных из этих цифр: 5379, 7359, 9375, … .

  • Пример. Из цифр 3, 5, 7, 9 можно составить 4! кортежей, так как n=4, то Р4=4!=4321=24, т.е. существует 24 различных четырёхзначных числа, составленных из этих цифр: 5379, 7359, 9375, … .

  • Формула называется рекуррентной и даёт возможность подсчитывать число перестановок во множестве n+1 элемента через перестановки во множестве n элементов.

  • Р1=1!, Р0=0!=1. Если во множестве один элемент, то кортеж единственный; если нет элементов, то вариант один – «нет кортежа».



Размещения (без повторений). Упорядоченное подмножество m элементов (кортеж), составленное из всего множества, содержащего n элементов, называется размещением (без повторения). Обозначение: .

  • Размещения (без повторений). Упорядоченное подмножество m элементов (кортеж), составленное из всего множества, содержащего n элементов, называется размещением (без повторения). Обозначение: .

  • Формула для нахождения числа размещений:

  • Задачи.

  • Сколькими способами из всего множества можно выбрать различные кортежи (упорядоченные подмножества) длиной m (m < n)?



Сочетания без повторений.

  • Сочетания без повторений.

  • Сочетаниями из n элементов по m называется неупорядоченное подмножество (выборка), состоящее из m элементов, взятых из множества, состоящего из n элементов.

  • Обозначение: .

  • Формула для подсчёта числа сочетаний:

  • Задачи.

  • Сколькими способами из всего множества можно выбрать различные подмножества длиной m (m < n)?



Перестановки с повторениями. Кортеж, имеющий повторяющиеся элементы, называется перестановкой с повторениями.

  • Перестановки с повторениями. Кортеж, имеющий повторяющиеся элементы, называется перестановкой с повторениями.

  • Пусть в кортеже длины n первый элемент встречается n1 раз, второй элемент – n2 раз и так далее, элемент под номером mnm раз: n1+n2+…+nm =n. Тогда число перестановок с повторениями из этих n элементов обозначается

  • и вычисляется по формуле:



1.8. Подстановки

  • Дано множество .

  • Взаимнооднозначное отображение

  • множества на себя называется подстановкой степени n.

  • Если прообразы (аргументы) расположены в порядке возрастания, запись подстановки такого вида называется канонической.

  • Например,



Чтобы из подстановки получить обратную, нужно поменять местами образы и прообразы, т.е. верхнюю и нижнюю строчки, и, если требуется, привести к каноническому виду.

  • Чтобы из подстановки получить обратную, нужно поменять местами образы и прообразы, т.е. верхнюю и нижнюю строчки, и, если требуется, привести к каноническому виду.

  • Например, если , то

  • Обратная подстановка единственная.

  • Если подстановка записана в каноническом виде, то первую строчку можно не писать.



Подстановку вида называют тождественной, так как она каждый элемент множества отображает в этот же элемент.

  • Подстановку вида называют тождественной, так как она каждый элемент множества отображает в этот же элемент.

  • Произведением подстановок σ1 и σ2 называется подстановка , где сначала выполняется подстановка σ1, а затем подстановка σ2 действует на результат первой.

  • Натуральной степенью подстановки σ называется подстановка , т.е. произведение n подстановок σ.



Порядком подстановки называется наименьшее натуральное число λ, такое что .

  • Порядком подстановки называется наименьшее натуральное число λ, такое что .

  • Например, для подстановки λ=3.

  • В подстановке любая перемена двух элементов второй строки местами называется транспозицией.

  • Подстановка называется чётной, если число транспозиций, приводящих эту подстановку к тождественной, чётно. В противном случае подстановка называется нечётной.



Пример.

  • Пример.

  • Приведём подстановку σ к тождественной подстановке с помощью транспозиций.

  • Чётное число транспозиций (n = 4) указывает на чётность подстановки.



Похожие:

Лекция 1 Множества iconЛекция Множества. Элементы теории множеств. Принцип включения- исключения
Множества Совокупность объектов, определяемых некоторым свойством, присущим каждому из них, называется множеством
Лекция 1 Множества iconНечеткие множества Основные понятия, функция принадлежности
Характеристическая функция множества A⊆U это функция μA, значения которой указывают, является ли x∈U элементом множества A
Лекция 1 Множества iconЛекция Нечеткая логика понятие нечеткого множества
Л. А. Заде из Калифорнийского университета. В основе нечеткой логики лежит теория нечетких множеств
Лекция 1 Множества iconКомбинаторика Определение множества
Множество есть совокупность объединенных по некоторым признакам различных объектов, называемых элементами множества
Лекция 1 Множества iconЛекция 6 Трансляторы автоматных языков, регулярные множества и выражений
Основной операцией, выполняемой над языками программирования, является их трансляция сопоставление каждой цепочке языка некоторого...
Лекция 1 Множества iconЛекция raise specification Language: базовые типы, логика, декартовы произведения, множества и операции с множествами План лекции Описания Базовые типы

Лекция 1 Множества iconВыбор конкретной специальности в конкретном вузе мы решили рассмотреть как выбор из множества Х множества возможных решений, одного элемента ХI, называемого решением

Лекция 1 Множества iconЛекция 1 Алфавит, цепочки, операции над цепочками Определение 1
Алфавитом (или словарем) называется любое непустое конечное множество ; элементы этого множества называются символами (буквами или...
Лекция 1 Множества iconКомбинаторика Сочетания Определение 1
А называется неупорядоченный набор попарноразличных элементов множества а длины k. Другими словами k-сочетание это k-элементное подмножество...
Лекция 1 Множества iconРазновидности объектов и их классификация
Объекты подмножества обязательно обладают всеми признаками объектов множества (наследуют признаки множества) и кроме них имеют еще...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница