Курс содержит четыре раздела элементы теории множеств, алгебра логики, элементы комбинаторики и теория графов

• Название: Курс содержит четыре раздела элементы теории множеств, алгебра логики, элементы комбинаторики и теория графов
• Дата: 08.07.2018
• Размер: 2 Mb.
• Имя файла: Lektsii_diskr_matem_konspekt.doc
• Тип: Документы; #48405
• страница: 2 из 8

П р и м е р на дополнение множества:
Пусть С = {(x,y): x² + y² ≤ 1} – множество точек плоскости, находящихся в круге радиуса 1, тогда - область за пределами единичного круга.

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


Рис. 1. Графическое изображение алгебраических операций над множествами А и В.
Введенные нами ранее операции над множествами обладают следующими свойствами:



11. А\В=А;
12.
13.
14.
15.
Любое из этих тождеств может быть доказано методом двух включений.

Докажем, например, тождество 11. Сначала установим , что Пусть x– произвольный элемент множества . Тогда по определению разности множеств имеем

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

. На основании включений и делаем вывод, что
А\В=А.
В качестве другого примера докажем тождество 12. Пусть . Тогда согласно определению симметрической разности . Это означает, что

или . Если , то и , т.е. и при этом . Если же , то и , откуда и . Итак, в любом случае из следует и , т.е . Таким образом, доказано, что

.

Покажем теперь обратное включение .

Пусть . Тогда и . Из следует, что или . Если , то с учетом имеем , и поэтому . Если же

, то опять-таки в силу получаем, что и . Итак, или

. Следовательно,



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

Докажем методом эквивалентных преобразований тождество 15, пользуясь тождествами 1-12. Преобразуем левую часть к правой:
=

∅

.

Тождество доказано.

3. 
   Отображение множеств.
   

1. 
   Декартово произведение множеств
   

Пусть А и В произвольные множества. Неупорядоченная пара на множествах А и В – это любое множество {a,b}, где или . Если А=В, то говорят о неупорядоченной паре на множестве А.

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

Простейший и важнейший пример упорядоченной пары дает аналитическая геометрия. Если на плоскости введена некоторая прямоугольная система координат, то каждая точка плоскости однозначно задается упорядоченной парой действительных чисел – координатами этой точки. (Точка, заданная координатами (1,3), совсем не то же самое, что точка с координатами (3,1).

Обобщением понятия упорядоченной пары является упорядоченный n-набор, или кортеж. В отличие от конечного множества {a₁,a₂,…,a_n} кортеж (a₁,a₂,…,a_n) на множествах А₁,А₂,…,А_n характеризуется не только входящими в него элементами , но порядком, в котором перечисляются.
Определение. Два кортежа (a₁,a₂,…,a_n) и (b₁,b₂,…,b_n)на множествах А₁,А₂,…,А_n равны,

тогда и только тогда, когда a₁=b₁, a₂=b₂,…, a_n=b_n. Последнюю систему равенств более коротко принято записывать так a_i=b_i, i= . Число nназывается длиной кортежа (или размерностью кортежа).

Проекцией кортежа на i-ую компоненту называется его i-ая компонента, что принято обозначать так:

Пр_i(x₁;x₂;...;x_n)=(x_i)
Проекцией кортежа на i-ую, j-ую,m-ую компоненты называется кортеж, компоненты которого принимают значения i-ой, j-ой,m-ой компонент исходного кортежа, что принято обозначать так:

Пр_i;j;...m (x₁;x₂;...x_i;...x_j;...x_m;...x_n)=(x_i;x_j;...x_m).

Определение. Декартовым (прямым) произведением множеств А и В и называется множество всех упорядоченных пар (a,b) таких, что .
В частности, если А=В то обе координаты принадлежат множеству А и такое произведение обозначается А².
П р и м е р.
Пусть A={1,2,3} и B={2,3,4}. Тогда множество A×B состоит из следующих девяти элементов: (1,4), (2,4), (3,4), (1,3), (2,3), (3,3), (1,2), (2,2), (3,2). Графически элементы произведения множеств A.B удобно помещать на «координатной плоскости», считая, что первый множитель A расположен на горизонтальной полуоси, а второй множитель B – на вертикальной. Например,

(1,4) (2,4) (3,4)

(1,3) (2,3) (3,3)

(1,2) (2,2) (3,2)
Аналогично, можно дать определение декартова произведения множеств А₁,А₂,…,А_n.
Определение. Декартовым произведением множеств А₁,А₂,…,А_n называется множество всех упорядоченных наборов (кортежей) (a₁,a₂,…,a_n) длины nтаких, что и обозначают. Таким образом:

= {(a₁,a₂,…,a_n): }.

Если же все множества А_i, i = равны между собой , т.е. А₁=А₂=…=А_n, то указанное декартово произведение называют n – ой декартовой степенью множества А и обозначают Аⁿ. В частности, при n=2 получаем декартов квадрат, а приn=3 – декартов куб множества А. Если одно из множеств произведения пусто, то пусто и все прямое произведение.

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

{(a₁; a₂;...; a_n)| a₁A₁, a₂A₂, ...,a_nA_n}(A₁×A₂×...×A_n).
По определению полагают, что первая декартова степень любого множества А есть само множество А, т.е. А¹ = А.
Т е о р е м а 1. Пусть - конечные множества и Тогда мощность множества равна произведению мощностей множеств А_],А₂,...,А_п, т.е.



Доказательство.

Для доказательства применим метод математической индукции.

Для п = \ теорема верна. Предположим, что теорема верна для п= k. Докажем, что утверждение теоремы справедливо для п = k+1.

По предположению . Возьмем любой набор

Припишем справа к нему элемент a_k+1из A^k+1. Это можно сделать т_k+1разными способами. При этом получится m_k+1 различных наборов из A₁ х А₂х... х A_k+1. Таким образом, из всех наборов можно получить путем приписывания справа элементов m₁,m₂,…,m_k+1 всевозможных различных наборов из . Значит, теорема верна для п = k + \ и, следовательно, верна для любого п.

Таким образом, |А₁×А₂×…×А_n|=m₁m₂...m_n, что определяет максимальное число кортежей.
Следствие.

При обработке данных на компьютере прямое произведение множеств широко используют в формировании составных типов данных. Например, на алгоритмическом языке Фортран предложение INTEGER*2VECT(10) описывает составное данное (кортеж) с именем VECT, содержащим 10 компонент типа INTEGER, причем для каждой компоненты в памяти выделено поле размером 2 байта. В базах данных такой кортеж называют записью(record).
Свойства декартова произведения :

1)

2)

3) ∅ = ∅ ∅
Эти свойства нетрудно доказать методом двух включений.

Докажем, например, первое тождество. Если , то и . Из того что , следует или . Если , то , а если ,то . Итак, или , т.е. Следовательно,
Доказательство обратного включения аналогично.

Обратим теперь внимание на третье тождество. Из него вытекает, что пустое множество при построении декартовых произведений множеств играет ту же роль, что и нуль при умножении чисел. Докажем справедливость этого тождества. В самом деле, множество ∅ (для любого А) есть множество всех упорядоченных пар (x,y), таких, что ∅ и . Но таких элементов x, что ∅, не существует, и, следовательно, упорядоченных пар (x,y), принадлежащих декартову произведению ∅ , не существует, т.е. ∅= ∅. Аналогично доказывается, что∅ = ∅ .