Презентация Дискретная математика. Основные понятия теории множеств онлайн

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

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

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

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

Содержание слайда: Основные понятия теории множеств

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание слайда: Рис. 5. Пересечение множеств

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

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

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

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

Содержание слайда:

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

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

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

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

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

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

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

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

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

Содержание слайда:

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

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

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

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

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

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

Содержание слайда: Тогда мощность их прямого произведения равна произведению мощностей множеств – сомножителей, т.е. А1А2…Аn=m1m2  …  mn.

Содержание слайда: A