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

булевой алгебры к синтезу комбинационных схем
Учебное пособие по дисциплине
«Дискретная математика»

Санкт-Петербург
2013

дисциплине "Дискретная математика"
Санкт- Петербург
2009

заданий по дисциплине "Дискретная математика".
Санкт-Петербург
2010

теория алгоритмов»
Санкт-Петербург
1013

логика и теория алгоритмов»
Санкт-Петербург
2012

– тест, КР;
Арифметические основы ЭВМ (целочисленная арифметика) - тест, ДЗ;
Арифметические основы ЭВМ (арифметика с плавающей запятой) - тест, ДЗ.
ЭКЗАМЕН

-1918)

Ему принадлежит заслуга привнесения в математику самого понятия "множества" (или "совокупности").

различных объектов, называемых элементами множества, в единое целое».

 множества».

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

множеству A обозначается как x∈A — «x есть элемент множества A» или «x принадлежит множеству A» .

Непринадлежность некоторого элемента а множеству М обозначается: а ∉ М.
Множества принято обозначать заглавными буквами латинского алфавита, а элементы множеств – строчными буквами.

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

Подмножество и надмножество. Множество A 
называется подмножеством множества B, если любой элемент, принадлежащий A, также принадле-жит B. Это записывается в виде отношения включе-ния: A ⊆ B. Таким образом, (A⊆B) ⇔ (x∈A → x∈B). Множество B, в свою очередь, называется надмножеством множества A, что записывается в виде отношения обратного включения: B ⊇ A.

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

Универсальное множество обычно обозна-чается U (от англ. universe, universal set),
реже E.

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

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

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

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

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

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

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

Булеаном множества А называется множество всех его подмножеств. Булеан множества А будем обозначать В(А). Иначе булеан множества А называют множеством - степенью множества А.

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

Если множество А содержит n элементов, то число его подмножеств из k элементов представляет собой число сочетаний из n по k и определяется по формуле:

{c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Утверждение. Если множество А состоит из n элементов, то множество B(A) всех его подмножеств состоит из 2n элементов, т.е.
|А|= n → |B(A)|= 2n = 2|А|.

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

2. Задание множеств порождающей процедурой означает описание характеристических свойств элементов множества: X = { x | H (x) }, т. е. множество X содержит такие элементы x, которые обладают свойством H (x).
Например: B = { b | b = π / 2 ± k π, k ∈ N },
N - множество всех натуральных чисел.

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

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

S является отсутствие неудовлетворительных оценок в последней сессии.

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

должны быть соответствующим образом обозначены.

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

A включено в B, если каждый элемент множества A принадлежит также и множеству B (рис. 2 а). Частным случаем отношения включения может быть и равенство множеств A и B (рис. 2 б), что отражается символом ⊆: A⊆B ⇔ ∀a∈A→a ∈B.

а

б

Рис. 2

множеств из отношения включения, в связи с чем, вводится отношение строгого включения.

Множество A строго включено в B, если A включено в B, но не равно ему (рис. 2а), что отражается символом ⊂: A⊂B ⇔ (A⊆B) и (A≠B).
В этом случае множество А называют собственным (строгим, истинным) подмно-жеством множества В.
Примерами использования строгого включения могут являться: A⊂U, B⊂U, ∅⊂А, ∅⊂B.

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

Простым примером рефлексивного отношения для чисел могут служить отношения «≥» или «≤», т.к. для любого числа d можно записать d ≥ d или
d ≤ d. В свою очередь отношения «>» и «<» этим свойством не обладают, в связи с чем, они называются антирефлексивными.

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

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

Если записать бинарное отношение между объектами a и b в общем виде aRb, где R – символ отношения, то для симметричного отношения: aRb → bRa при любых a и b, а для антисимметрич-ного aRb → bRa, только, если a = b.

Примером антисимметричного отношения могут служить отношения «≥» или «≤» между числами. Действительно, (a ≤ b)→(b ≤ a), только, если a = b.

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

Примерами транзитивного отношения для чисел являются отношения «>», «≥», «<», «≤». Отноше-ние, не обладающее свойством транзитивности, называется нетранзитивным.

Примером нетранзитивного отношения может слу-жить отношение «пересекаться». Действительно для множеств: A={a, b}, B={b, c}, C={c, d} A пересе-кается с B, B - с C, но A не пересекается с C.

и B ⊆ A) → (A=B); транзитивности: (A ⊆ В и B ⊆ C) → (A ⊆ C).

Отношение строгого включения обладает свойствами:
антирефлексивности: А ⊄ А;
транзитивности : (A ⊂ В и B ⊂ C) → (A ⊂ C).
Свойства симметричности или несимметричности для отношения строгого включения не рассматри-ваются, так как их рассмотрение предполагает случай равенства между объектами отношения.

⊂ 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 не пересекаются, если у них нет общих элементов (рис.3 а): A и B не пересекаются ⇔ ∀a∈A→ 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+ – множество неотрицательных действительных чисел;

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

Для этих множеств очевидными являются следующие цепочки отношений включения: S ⊂ N ⊂ Z+ ⊂ Z ⊂ V ⊂ R ⊂ К; W ⊂ R ⊂ К.

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

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

дополнение), симметрическая разность и дополнение (абсолютное).

Рис. 4. Объединение множеств

Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис. 4): A∪B = {x | x∈ A или x∈B}.

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

Если же все множества совокупности индекси-рованы (пронумерованы с помощью индексов), то используются другие варианты обозначений: 1. , если S = {A1, A2, …, Ak};

набор индексов множеств задан ...............множеством I.

Пример 1. А={a,b,c}, B={b,c,d}, C={c,d,e}. A∪B={a,b,c,d}; A∪C={a,b,c,d,e}; B∪C={b,c,d,e}; A∪B∪C={a,b,c,d,e}.

Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат одновременно как множеству А, так и множеству В (рис. 5): A∩B = {x | x∈ A и x∈B}.

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

Пример 2. (для множеств из примера 1):
А∩В = {b, c}; A∩C = {c}; B∩C = {c, d}; A∩B∩C = {c}.

элементов А, которые не содержатся в В (рис. 6): A \ B = {x | x∈ A и x∉B}.

Рис. 6. Разность множеств

Пример 3. (для множеств из примера 1.)
А\В = {а, b, c} \ {b, c, d} = {a}.

Разность множеств А и В иначе называется дополнением множества А до множества В (относительным дополнением).

принадлежат либо только множеству А, либо только множеству В (рис. 7). Симметрическую разность обозначают как AΔB, A – B или A ⊕ B: AΔB = {x | (x∈ A и x∉B) или ( x∈ В и x∉А)}.

Рис. 7. Симметрическая разность множеств

Таким образом, симметрическая разность множеств A и B представляет собой объединение разностей (относительных дополнений) этих множеств: AΔB = (A \ B) ∪ (B \ A).

называется множество всех тех элементов х универсального множества U, которые не принадлежат множеству А (рис. 8). Дополнение множества А обозначается: = {x ⎜x∉A} = U \ A.
С учетом введенной операции дополнения, разность множеств А и В можно представить в виде: A \ B = A∩ .

Рис. 8. Дополнение множества

Порядок выполнения операций над множествами определяется их приоритетами в следующем порядке: , ∩ , ∪, \ , Δ.

3. Дистрибутивные (распределительные) законы:
A ∪ (B∩C) = (A∪B) ∩ (A∪C);
A ∩ (B∪C) = (A∩B) ∪ (A∩C).

Основные тождества (законы) алгебры множеств

1.Коммутативные (переместительные) законы:
A∪B = B∪A; A∩B = B∩A.

2. Ассоциативные (сочетательные) законы:
A ∪ (B∪C) = (A∪B) ∪ C; A ∩ (B∩C) =(A∩B) ∩ C.

Моргана):

Следствия из законов двойственности:

6. Законы поглощения: А∪ (А∩В)=А; А∩(А∪В)=А.

7. Закон инволютивности:

8. Закон противоречия:

9. Закон «третьего не дано»:

10. Свойства универсального множества: А∪U=U; А∩U=А.

11. Свойства пустого множества: А∪∅=А; А∩∅=∅.

= (A∩B) Δ(A∩C).

Дополнительные тождества для операций объединения, пересечения и дополнения:

12. Законы склеивания:

13. Законы сокращения (законы Порецкого):

14. Дополнительные тождества для операции разности множеств: A \ (B \ C)=(A \ B) ∪ (A∩C); (A \ B) \ C=(A \ C) \ (B \ C); A \ (B∪C)=(A \ B) \ C; A \ (B∪C)=(A \ C) \ (B \ C).

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

Замечание. Практически все основные тождества (законы) множеств представлены парами, которые характеризуются своей симметричностью в отно-шении операций объединения и пересечения. Подобное свойство законов называется дуальностью (двойственностью).

частей тождества
совпадают,
значит оно
справедливо.

Этот способ является наглядным, но не обладает достаточной строгостью.

взаимного включения; - алгебраическим методом.

Пример 6. Докажем первый дистрибутивный закон: А∪(В∩С)=(А∪В)∩(А∪С). Обозначим левую часть тождества А∪(В∩С) через Dl, а правую – (А∪В)∩(А∪С) через Dr .

Метод взаимного включения базируется на определении равенства двух множеств, между которыми существует отношение взаимного включения: А=В ⇔А⊆В и В⊆А.

элемент х∈ Dl, т.е. х∈ А∪(В∩С), тогда по определению операции объединения, (х∈А) или (х∈В∩С).

1. берется произвольный элемент множества Dl (х∈Dl) и доказывается, что он принадлежит также и множеству Dr, откуда следует: Dl⊆Dr;

2. берется произвольный элемент множества Dr и доказывается, что он принадлежит также и множеству Dl, откуда следует: Dr⊆ Dl.

и (х∈С), отсюда, по определению операции объединения, (х∈А∪В) и (х∈А∪С), следовательно х∈(А∪В)∩(А∪С), т.е. х∈Dr. Так как для любого х∈Dl следует, что х∈Dr, то, по определению отношения включения, Dl⊆Dr.

а) Если элемент х∈А, то, по определению операции объединения множеств, (х∈А∪В) и (х∈А∪С), следовательно х ∈ (А∪В)∩(А∪С), т.е. х∈Dr;

операции объединения, (х∈А или х∈В) и (х∈А или х∈С), следовательно, х∈А или (х∈В и х∈С), откуда, х∈А или (х∈B∩С), т.е. х∈ А∪(В∩С) или х∈Dl, откуда Dr⊆Dl.

обозначим

Таким образом, между множествами Dl и Dr существуют отношение взаимного включения, значит Dl=Dr, что и требовалось доказать.

Пример 7. Докажем первый закон двойственности:

(x∉А∪В), значит x ∉ А и х ∉ В (тонкий момент в доказательстве: х не принадлежит ни А, ни В), следовательно Значит Dl ⊆ Dr .

2. Пусть теперь элемент х∈Dr , т.е Тогда значит x∈U и x одновременно не принадлежит ни А, ни В, т.е. х∉(А или В), следовательно х∉А∪В, т.е. Из этого следует, что Dr ⊆ Dl.

Таким образом, между множествами Dl и Dr существуют отношение взаимного включения, значит Dl = Dr, что и требовалось доказать.

и правой частей тождества
совпадают,
значит оно
справедливо.

А∩(А∪В) = А путем преобразования левой части тождества к правой с использованием других тождеств:

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

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

Для обозначения вектора обычно используются скобки, например (1, 2, 1, 3). Иногда скобки и даже запятые в обозначении вектора опускаются. Примером векторов могут служить целые числа, при этом отдельные цифры числа являются координатами этого вектора.

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

– тройками, …, длины n – n-ками и т.д.

Два вектора равны, если они имеют одинаковую длину и соответствующие их координаты равны, т.е. (а1, а2, …, аm) = (b1, b2,…,bn), если m = n и a1 = b1, a2 = b2, …, am = bm.

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

порядке, равны {a, b} = {b, a}, а вектора – нет (a, b) ≠ (b, a).

Прямое (декартово) произведение множеств

Прямым (декартовым) произведением множеств А и В называется множество всех пар (а, b), таких, что а∈А и b∈В. Прямое произведение множеств А и В обозначает-ся в виде А×В: А×В = {(a, b)⏐a∈A и b∈B}.

Пример 9. А = {a, b, c}; B ={b, c}. A×B = {(a, b), (a, c), (b, b), (b, c), (c, b), (c, c)}; B×A = {(b, a}, (b, b), (b, c), (c, a), (c, b), (c, c)}.

закон для прямого произведения множеств не действует.

Пример 10. Х – множество точек отрезка [0;1]; Y – множество точек отрезка [1;2]. Тогда Х×Y – множество точек квадрата с вершинами в точках (0,1), (0,2), (1,1), (1,2).

Декартова степень множества Прямое (декартово) произведение одинаковых множеств называется декартовой степенью множества: если В = А, то А×В = А×А = А2.

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

Прямым (декартовым) произведением множеств А1, А2, …, Аn называется совокупность всех упорядоченных n-ок (векторов длиной n) (a1, a2, …, an) таких, что ai∈Ai (i=1,2,…,n). В случае, если А1=А2=…=Аn=А, то А1×А2×…×Аn = Аn - n-ая декартова степень множества А.

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

Замечание. Декартово произведение R×R×R= R3 представляет собой множество координат точек пространства.

т.е. ⏐А1×А2×…×Аn⏐=m1⋅m2 ⋅ … ⋅ mn.

Мощность прямого произведения множеств

Теорема. Пусть А1, А2, …, Аn – конечные множества мощностью m1, m2, …, mn. соответственно, т.е. ⏐А1⏐= m1,⏐A2⏐= m2, …,⏐An⏐= mn.

Основные тождества для операции прямого произведения множеств

(А∩В) × (C∩D) = (А×C) ∩ (B×D); (А∪В) × C = (А×C) ∪(B×C); (А\В) × C = (А×C) \(B×C); А×(В\C) = (А×B) \(A×C).