Дискретная математика. Основные понятия теории множеств

Нажмите для полного просмотра!

Дискретная математика. Основные понятия теории множеств, слайд №2

Дискретная математика. Основные понятия теории множеств, слайд №3

Дискретная математика. Основные понятия теории множеств, слайд №4

Дискретная математика. Основные понятия теории множеств, слайд №5

Дискретная математика. Основные понятия теории множеств, слайд №6

Дискретная математика. Основные понятия теории множеств, слайд №7

Дискретная математика. Основные понятия теории множеств, слайд №8

Дискретная математика. Основные понятия теории множеств, слайд №9

Дискретная математика. Основные понятия теории множеств, слайд №10

Дискретная математика. Основные понятия теории множеств, слайд №11

Дискретная математика. Основные понятия теории множеств, слайд №12

Дискретная математика. Основные понятия теории множеств, слайд №13

Дискретная математика. Основные понятия теории множеств, слайд №14

Дискретная математика. Основные понятия теории множеств, слайд №15

Дискретная математика. Основные понятия теории множеств, слайд №16

Дискретная математика. Основные понятия теории множеств, слайд №17

Дискретная математика. Основные понятия теории множеств, слайд №18

Дискретная математика. Основные понятия теории множеств, слайд №19

Дискретная математика. Основные понятия теории множеств, слайд №20

Дискретная математика. Основные понятия теории множеств, слайд №21

Дискретная математика. Основные понятия теории множеств, слайд №22

Дискретная математика. Основные понятия теории множеств, слайд №23

Дискретная математика. Основные понятия теории множеств, слайд №24

Дискретная математика. Основные понятия теории множеств, слайд №25

Дискретная математика. Основные понятия теории множеств, слайд №26

Дискретная математика. Основные понятия теории множеств, слайд №27

Дискретная математика. Основные понятия теории множеств, слайд №28

Дискретная математика. Основные понятия теории множеств, слайд №29

Дискретная математика. Основные понятия теории множеств, слайд №30

Дискретная математика. Основные понятия теории множеств, слайд №31

Дискретная математика. Основные понятия теории множеств, слайд №32

Дискретная математика. Основные понятия теории множеств, слайд №33

Дискретная математика. Основные понятия теории множеств, слайд №34

Дискретная математика. Основные понятия теории множеств, слайд №35

Дискретная математика. Основные понятия теории множеств, слайд №36

Дискретная математика. Основные понятия теории множеств, слайд №37

Дискретная математика. Основные понятия теории множеств, слайд №38

Дискретная математика. Основные понятия теории множеств, слайд №39

Дискретная математика. Основные понятия теории множеств, слайд №40

Дискретная математика. Основные понятия теории множеств, слайд №41

Дискретная математика. Основные понятия теории множеств, слайд №42

Дискретная математика. Основные понятия теории множеств, слайд №43

Дискретная математика. Основные понятия теории множеств, слайд №44

Дискретная математика. Основные понятия теории множеств, слайд №45

Дискретная математика. Основные понятия теории множеств, слайд №46

Дискретная математика. Основные понятия теории множеств, слайд №47

Дискретная математика. Основные понятия теории множеств, слайд №48

Дискретная математика. Основные понятия теории множеств, слайд №49

Дискретная математика. Основные понятия теории множеств, слайд №50

Дискретная математика. Основные понятия теории множеств, слайд №51

Дискретная математика. Основные понятия теории множеств, слайд №52

Дискретная математика. Основные понятия теории множеств, слайд №53

Дискретная математика. Основные понятия теории множеств, слайд №54

Дискретная математика. Основные понятия теории множеств, слайд №55

Дискретная математика. Основные понятия теории множеств, слайд №56

Дискретная математика. Основные понятия теории множеств, слайд №57

Дискретная математика. Основные понятия теории множеств, слайд №58

Дискретная математика. Основные понятия теории множеств, слайд №59

Дискретная математика. Основные понятия теории множеств, слайд №60

Дискретная математика. Основные понятия теории множеств, слайд №61

Дискретная математика. Основные понятия теории множеств, слайд №62

Дискретная математика. Основные понятия теории множеств, слайд №63

Дискретная математика. Основные понятия теории множеств, слайд №64

Дискретная математика. Основные понятия теории множеств, слайд №65

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Дискретная математика. Основные понятия теории множеств. Доклад-сообщение содержит 65 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Дискретная математика Доцент каф. ВТ Поляков Владимир Иванович ауд. 369 а

Слайд 2

Описание слайда:

Учебные пособия по курсу «Дискретная математика»:

Слайд 3

Описание слайда:

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Разделы курса «Дискретная математика»: Теория множеств - тест; Булева алгебра - тест; Синтез комбинационных схем – тест, КР; Арифметические основы ЭВМ (целочисленная арифметика) - тест, ДЗ; Арифметические основы ЭВМ (арифметика с плавающей запятой) - тест, ДЗ. ЭКЗАМЕН

Слайд 9

Описание слайда:

Основные понятия теории множеств

Слайд 10

Описание слайда:

Г. Кантору принадлежит следующая формулировка понятия множества: «Множество — это объединение определённых, различных объектов, называемых элементами множества, в единое целое». Г. Кантору принадлежит следующая формулировка понятия множества: «Множество — это объединение определённых, различных объектов, называемых элементами множества, в единое целое».

Слайд 11

Описание слайда:

В основе теории множеств лежат первичные понятия: В основе теории множеств лежат первичные понятия: множество и отношение «быть элементом множества».

Слайд 12

Описание слайда:

Объекты, образующие некоторое множество, называются его элементами. Принадлежность некоторого элемента x множеству A обозначается как xA — «x есть элемент множества A» или «x принадлежит множеству A» . Непринадлежность некоторого элемента а множеству М обозначается: а  М. Множества принято обозначать заглавными буквами латинского алфавита, а элементы множеств – строчными буквами.

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Пустое множество является подмножеством любого множества. Универсальное множество. Обычно, в конкретных рассуждениях элементы всех множеств берутся из некоторого одного, достаточно широкого множества, своего для каждого случая, которое называется универ-сальным множеством (универсумом).

Слайд 15

Описание слайда:

Мощность множества можно рассматривать как числовую характеристику (метрику) любого множества. Мощностью некоторого конечного множества А является число его элементов. Мощность множества А принято обозначать |А|, например, мощность множества А={a, b, c} равна |А|=3. Мощность пустого множества равна нулю: ||=0.

Слайд 16

Описание слайда:

Конечные и бесконечные множества. Множества, имеющие конечное число эле-ментов и, соответственно, конечное значе-ние мощности, называются конечными, а множества с бесконечным числом элементов и, соответственно, с бесконечной мощностью – бесконечными.

Слайд 17

Описание слайда:

Счетные и несчетные множества. Бесконечные множества разделяются на счётные и несчетные. Бесконечное множество называется счетным, если его элементы можно пронумеровать, в противном случае, бесконечное множество называется несчетным. Простейшим примером счетного множества является множество всех натуральных чисел, в связи с чем можно дать другое определение счетного множества: множество называется счетным, если оно равномощно множеству натуральных чисел, т.е. его можно представить в виде {x0, x1, x2, …}, где хi – элемент множества, однозначно соответствующий его номеру i. Счетные и несчетные множества. Бесконечные множества разделяются на счётные и несчетные. Бесконечное множество называется счетным, если его элементы можно пронумеровать, в противном случае, бесконечное множество называется несчетным. Простейшим примером счетного множества является множество всех натуральных чисел, в связи с чем можно дать другое определение счетного множества: множество называется счетным, если оно равномощно множеству натуральных чисел, т.е. его можно представить в виде {x0, x1, x2, …}, где хi – элемент множества, однозначно соответствующий его номеру i.

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

Булеан множества. Любое конечное множество содержит и конечное число подмножеств. Связь между произвольным множеством и всеми его подмножествами определяется булеаном.

Слайд 20

Описание слайда:

Булеан, как множество всех подмножеств множества А, должен включать в себя: Булеан, как множество всех подмножеств множества А, должен включать в себя: пустое множество; само множество А; отдельные элементы множества А; всевозможные комбинации различных элемен-тов множества А.

Слайд 21

Описание слайда:

Пример. Записать булеан (множество – степень) для множества А={a, b, c}. B(A)={, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Слайд 22

Описание слайда:

Способы задания множеств 1. Задание множеств списком предполагает перечисление элементов. Например, множество А состоит из букв a, b, c, d : A={a, b, c, d} или множество L включает цифры 0, 2, 3, 4: L={0, 2, 3, 4}.

Слайд 23

Описание слайда:

3. Задание множества описанием свойств элементов. Например, M - это множество чисел, являющихся степенями двойки. К описанию свойств естественно предъявить требования точности и недвусмысленности.

Слайд 24

Описание слайда:

Например: S - множество успевающих студентов. Разрешающей процедурой включения во множес-тво S является отсутствие неудовлетворительных оценок в последней сессии. 4. Графическое задание множеств осуществляют с помощью диаграмм Эйлера-Венна. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов, представля-ющих рассматриваемые множества.

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

Отношения между множествами Два множества A и B могут вступать друг с другом в различные отношения. Множество A включено в B, если каждый элемент множества A принадлежит также и множеству B (рис. 2 а). Частным случаем отношения включения может быть и равенство множеств A и B (рис. 2 б), что отражается символом : AB  aAa B.

Слайд 27

Описание слайда:

Подобное отношение можно называть нестрогим включением. Довольно часто требуется исключить равенство множеств из отношения включения, в связи с чем, вводится отношение строгого включения. Множество A строго включено в B, если A включено в B, но не равно ему (рис. 2а), что отражается символом : AB  (AB) и (AB). В этом случае множество А называют собственным (строгим, истинным) подмно-жеством множества В. Примерами использования строгого включения могут являться: AU, BU, А, B.

Слайд 28

Описание слайда:

Отношения между множествами могут обладать следующими свойствами: рефлексивностью, симметричностью и транзитивностью. Отношения между множествами могут обладать следующими свойствами: рефлексивностью, симметричностью и транзитивностью. Свойство рефлексивности является унарным, т.е. применительно к единственному объекту (в данном случае к множеству) и означает, что отношение применимо к «себе самому».

Слайд 29

Описание слайда:

Свойство симметричности является бинарным (двухместным), т.е. применимо к двум объектам. Отношение является симметричным, если оно выполняется в обе стороны по отношению к паре объектов (в данном случае множеств). Примерами свойства симметричности являются различные геометрические объекты, для которых понятие «симметрии» является наиболее наглядным. Например, отношение: «быть симметричными относительно оси х» в отношении точек плоскости является симметричным. Действительно, если первая точка симметрична второй, то вторая точка обязательно симметрична первой.

Слайд 30

Описание слайда:

В свою очередь, отношение между двумя объек-тами не обладает свойством симметричности, т.е. является антисимметричным, если его выполне-ние в обе стороны имеет место только в случае равенства объектов.

Слайд 31

Описание слайда:

Свойство транзитивности является тернарным, т.е. применяется к трем объектам. Отношение R между объектами a, b, с является транзитивным, если из aRb и bRс следует aRс, т.е. из выполне-ния отношения R между парами объектов (a, b) и (b, с) следует его выполнение и для пары (a, с).

Слайд 32

Описание слайда:

Отношение нестрогого включения обладает свойствами: рефлексивности: А  А; антисимметричности: (A  В и B  A)  (A=B); транзитивности: (A  В и B  C)  (A  C).

Слайд 33

Описание слайда:

Для комбинации отношений строгого и нестрогого включений: (A  В и B  C)  (A  C); (A  В и B  C)  (A  C). Множество A равно множеству B, если A и B включены друг в друга или, иначе, между ними существует отношение взаимного включения: A=B  (AB) и (BA). Вторая часть равенства указывает на наиболее ти-пичный метод доказательства равенства множеств A и B, который заключается в доказательстве сначала утверждения АВ, а затем ВА.

Слайд 34

Описание слайда:

Равные множества содержат одинаковые элемен-ты, причем порядок элементов в множествах не существенен: A={1, 2, 3} и В={3, 2, 1}  A=B.

Слайд 35

Описание слайда:

Множества A и B находятся в общем положении, если существуют элемент, принадлежащий исклю-чительно множеству A, элемент, принадлежащий исключительно множеству B, а также элемент, принадлежащий обоим множествам (рис. 3 б): A и B находятся в общем положении  a, b, c: [(aA) и (a B)] и [(b B) и (b A)] и [(c A) и (c B)].

Слайд 36

Описание слайда:

Рассмотрим отношения между числовыми мно-жествами, для которых будем использовать следующие обозначения: S – множество простых чисел; N – множество натуральных чисел (т. е. N = {1, 2, 3, … }); Z – множество целых чисел; Z+ – множество целых неотрицательных чисел (иногда обозначается N0 (т. е. N0 = {0, 1, 2, 3, … })); Z– – множество целых неположительных чисел; R – множество действительных чисел; R+ – множество неотрицательных действительных чисел;

Слайд 37

Описание слайда:

R– – множество неположительных действительных чисел; V – множество рациональных чисел; W – множество иррациональных чисел; К – множество комплексных чисел.

Слайд 38

Описание слайда:

Алгебра множеств Множество всех подмножеств универсального множества U вместе с операциями над множест-вами образуют так называемую алгебру подмно-жеств множества U или алгебру множеств.

Слайд 39

Описание слайда:

Операции над множествами Над множествами определены следующие операции: объединение, пересечение, разность (относительное дополнение), симметрическая разность и дополнение (абсолютное).

Слайд 40

Описание слайда:

Операцию объединения можно распространить на произвольное, в том числе и бесконечное количество множеств, например, М=АВСD. В общем случае используется обозначение , которое читается так: “объединение всех множеств А, принадлежащих совокупности S ”.

Слайд 41

Описание слайда:

2. , если S – бесконечная совокупность пронумерованных множеств; 3. , если набор индексов множеств задан ...............множеством I.

Слайд 42

Описание слайда:

Рис. 5. Пересечение множеств

Слайд 43

$Разностью множеств А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 6): A \ B = {x | x A и xB}.$

Описание слайда:

Разностью множеств А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 6): A \ B = {x | x A и xB}.

Слайд 44

Описание слайда:

Симметрической разностью множеств А и В называется множество, состоящее из элементов, которые принадлежат либо только множеству А, либо только множеству В (рис. 7). Симметрическую разность обозначают как AΔB, A – B или A  B: AΔB = {x | (x A и xB) или ( x В и xА)}.

Слайд 45

Описание слайда:

Пример 4. (для множеств из примера 1.) AΔB ={a}{d}={a,d}. Дополнением (абсолютным) множества А называется множество всех тех элементов х универсального множества U, которые не принадлежат множеству А (рис. 8). Дополнение множества А обозначается: = {x xA} = U \ A. С учетом введенной операции дополнения, разность множеств А и В можно представить в виде: A \ B = A .

Слайд 46

Описание слайда:

Операции над множествами используются для получения новых множеств из уже существующих. Порядок выполнения операций над множествами определяется их приоритетами в следующем порядке: ,  , , \ , Δ.

Слайд 47

Описание слайда:

Слайд 48

Описание слайда:

15. Дополнительные тождества для операции симметрической разности: AΔ(BΔC) = (AΔB) ΔC; A(BΔC) = (AB) Δ(AC).

Слайд 49

Описание слайда:

Способы доказательства тождеств Убедиться в справедливости тождеств можно с помощью диаграмм Эйлера-Венна. Для этого необходимо изобразить на диаграммах левую и правую части тождеств и сравнить их. Такой способ доказательства принято называть геометрическим.

Слайд 50

Описание слайда:

Пример 5. Проверим первый дистрибутивный закон: А(ВС)=(АВ)(АС) (рис.9).

Слайд 51

Описание слайда:

Доказательство справедливости проверяемых тождеств можно проводить одним из двух методов: - методом взаимного включения; - алгебраическим методом.

Слайд 52

Описание слайда:

В соответствии с принятым методом доказательство разделяется на две части:

Слайд 53

Описание слайда:

б) Если элемент хВС, то, по определению операции пересечения множеств, (хВ) и (хС), отсюда, по определению операции объединения, (хАВ) и (хАС), следовательно х(АВ)(АС), т.е. хDr. Так как для любого хDl следует, что хDr, то, по определению отношения включения, DlDr.

Слайд 54

Описание слайда:

2. Пусть элемент хDr, т.е. (хАВ) и (хАС), откуда по определению операции объединения, (хА или хВ) и (хА или хС), следовательно, хА или (хВ и хС), откуда, хА или (хBС), т.е. х А(ВС) или хDl, откуда DrDl.

Слайд 55

Описание слайда:

1. Пусть элемент xDl , т.е. x . Тогда xU и (xАВ), значит x  А и х  В (тонкий момент в доказательстве: х не принадлежит ни А, ни В), следовательно Значит Dl  Dr .

Слайд 56

Описание слайда:

Проверим справедливость этого тождества на диаграммах Эйлера-Венна (рис. 10).

Слайд 57

Описание слайда:

Слайд 58

Описание слайда:

Элементы, образующие вектор, называются координатами или компонентами вектора. Число координат вектора называется его длиной или размерностью. Синонимом понятия «вектор» является «кортеж».

Слайд 59

Описание слайда:

Векторы длины два называются упорядоченными парами (или просто парами), длины три – тройками, …, длины n – n-ками и т.д.

Слайд 60

Описание слайда:

В связи с этим множества, содержащие одинако-вые элементы, но в различном порядке, равны {a, b} = {b, a}, а вектора – нет (a, b)  (b, a).

Слайд 61

Описание слайда:

Замечание. Из рассмотренного примера видно, что АВ  ВА, т.е. коммутативный закон для прямого произведения множеств не действует.

Слайд 62

Описание слайда:

Точка на плоскости может быть задана упорядо-ченной парой координат, т.е. двумя точками на координатных осях. Так как координаты представ-ляются множеством действительных чисел R, то прямое произведение RR = R2 представляет собой множество координат точек плоскости.

Слайд 63

Описание слайда:

Пример 11. Х – множество точек отрезка [0;1]; Y – множество точек отрезка [1;2]; Z – множество точек отрезка [0;0,5]. XYZ – множество точек пространства, ограниченного параллелепипедом.