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

vk.com/club152685050 | vk.com/id446425943

Примеры:

A ( ; 4] (5; ).

A B {( x; y) : x ( 4; 5) и y (2; )}.

§ 3. Алгебра подмножеств

Рассмотрим непустое множество U . Определим на нем три операции:

объединение, пересечение и дополнение (до универсального множества U ). Опр. Алгеброй подмножеств или алгеброй Кантора называется

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

Свойства операций над алгеброй подмножеств.

Пусть А, В, С – произвольные подмножества универсального множества U . Операции объединения, пересечения и дополнения множеств удовлетворяют следующим законам:

1.А А А; А А А – законы идемпотентности (повторения),

2.А А В А; А В В А – законы коммутативности,

множеством,

7.А A U ; A A – законы действия с дополнением,

8.A A – иволютивный закон (закон двойного дополнения),

10. Если А C, то А (В С) ( А В) С – модулярный закон.

11

vk.com/club152685050 | vk.com/id446425943

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

Докажем 2-й закон дистрибутивности А ( А С) ( А В) ( А С) . Для этого покажем, что любой элемент x, принадлежащий множеству в одной части равенства, также принадлежит множеству из другой части.

( А В) ( А B ) (двойного отрицания) = ( А В) ( А В) (закон дистрибутивности) = ( А А) В В В .

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

Французский математик и философ Рене Декарт ввел координатное представление точек плоскости как упорядоченные пары вещественных чисел

M (x, y) .

Опр. Прямым (иначе декартовым) произведением множеств А и В называется множество, состоящее из всех упорядоченных пар (a,b) таких, что

12

R3 R R R – множество координат всех точек пространства вида (x, y, z) ;

3. Если A {x : x ( 4, 2)}, B {y : y (3, 5)} A B ( 4, 2) (3, 5)

прямоугольная область на плоскости.

Рис.

Теорема (о количестве элементов декартова произведения конечных

элементов.

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

1. Пусть m = 2. Ясно, что все элементы декартова произведения A1 A2

vk.com/club152685050 | vk.com/id446425943

2.Пусть утверждение справедливо для m = k , т.е. количество элементов множества A1 A2 ... Ak равно n1 n2 ... nk .

3.Докажем справедливость теоремы для m = k+1. Все элементы

4. Согласно принципу математической индукции теорема справедлива для любого количества конечных множеств.

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

Опр. Отображением F множества Х во множество Y называется правило, которое каждому элементу х Х сопоставляет единственный(!) элемент у Y и пишут F : X Y или y F (x) . При этом y называют образом элемента х , а x – прообразом элемента y.

F 1 ( y) x : F (x) y полный прообраз элемента y. F 1 (Y ) x : F(x) Y

Если F ( X ) Y , то говорят об отображении «в»,

Если F ( X ) Y , то говорят об отображении «на».

0,1 0,1 . Постройте прообраз единичного квадрата.

Опр. 1. Отображение F : X Y называется инъекцией, если для любого

одновременно инъективное и сюръективное отображение, т.е. биекция – это взаимно-однозначное отображение.

14

vk.com/club152685050 | vk.com/id446425943

Пример.

Рассмотрим отображение F: y = sin x

1.Пусть Х х : х ; ;

2 2

Y y : y 1;1 F : X Y – биекция

образа y существует бесконечно много прообразов x)

отображением, т.к. не всем элементам из Х найдется элемент из

Y.

Пример. х2 у2 1 – не отображение, т.к. любому элементу х 1;1 сопоставляется 2 элемента из Y 1; 1 .

Опр. Рассмотрим отображение F : X Y . Отображение F 1 называется обратным для отображения F , если любому элементу у Y отображение F 1 сопоставляет единственное х Х .

Замечание.

1.Пусть F – биекция существует F 1 – тоже биекция.

2.Биекция задает взаимно-однозначное соответствие между множествами

X , Y : X Y .

15

vk.com/club152685050 | vk.com/id446425943

§ 6. Мощность множества

По числу элементов различают конечные и бесконечные множества. Опр. Два множества Х и Y называются равномощными (или

эквивалентными), если каждому элементу одного множества можно поставить в соответствие один и только один элемент другого множества, т. е. если существует биекция F : X Y .

Примеры: 1. Два любых конечных множества равномощны тогда и только тогда когда они совпадают количественно, т.е. X Y :

2.Множества X x : x [0,1] , Y y : y [ 4,1] – равномощны ( X Y ) , так как существует биекция y 5x 4 .

3.Множество точек полуокружности эквивалентно множеству точек вещественной прямой (доказательство следует из ниже приводимого рисунка)

существует биекция y tgx .

Рассмотрим множества, с помощью которых можно «сравнивать» число элементов других множеств.

Опр 1. 1. Если Х – конечное множество, то мощностью множества Х называется число его элементов; пусть Х состоит из n элементов Х n ;

2. Бесконечное множество Х называется счетным, если оно равномощно (эквивалентно) множеству натуральных чисел N, т.е. элементы множества Х можно перенумеровать. Мощность множества натуральных чисел обозначается 0 : N 0 .

16

vk.com/club152685050 | vk.com/id446425943

3. Бесконечное множество называется множеством мощности континуума, если оно равномощно множеству всех вещественных чисел из промежутка 0; 1 . Мощность чисел из отрезка 0; 1 обозначается 1 .

Примеры: 1) множество целых чисел счетно:

2)множество нечетных (четных) чисел – счетно,т.к. n 2n 1 ( n 2n) .

3)множество натуральных чисел, делящихся на 3 – счетное множество. Теорема Кантора. Множество всех вещественных чисел отрезка 0; 1

не является счетным.

Доказательство. Предположим, что дано какое-то счетное множество всех или только некоторых вещественных чисел m 0, 1 . Иначе говоря, мы предполагаем, что числа отрезка [0,1] представляют собой счетное множество.

Представим каждое вещественное число m бесконечной десятичной дробью:

1 0, 11 12 13... 1т...

2 0, 21 22 23... 2т...

3 0, 31 32 33... 3т...

……………

т 0, т1 т2 т3... тт ...

………….

Построим следующую дробь (диагональная процедура Кантора)

цифру не совпадающую с mm . Таким образом, наша дробь не совпадает ни с одним числом множества m , следовательно, никакое счетное множество, лежащее внутри отрезка [0, 1] не исчерпывает всех чисел этого отрезка.

Справедливы следующие утверждения.

Теоремы.

1. Пусть А и В – конечные множества с числом элементов m и n соответственно. Тогда мощность их декартова произведения А В m n .

Доказательство теоремы следует из утверждения о числе элементов декартова произведения конечных множеств.

2. Множество N m (напоминаем, что N m N N ... N ) является счетным при любом натуральном m.

17

3.Декартово произведение конечного числа счетных множеств является счетным множеством – следует из утверждения 2.

4.Любое множество и его булеан не являются равномощными.

того, мощность булеана любого множества А больше мощности множества А:

2 A A .

6. Булеан счётного множества – континуальное множество:

A 0 ( A) 1.

§7. Бинарные отношения

Рассмотрим некоторые множества Х , Y и их декартово произведение

Х Y x, y : x X , y Y .

Опр. Бинарным отношением P между множествами Х и Y называется правило, которое из декартова произведения Х Y выделяет некоторое подмножество упорядоченных пар (x, y) . Выделенное подмножество также называется бинарным отношением.

Замечание. Часто бинарным отношением называется упорядоченная тройка ( Х ,Y , P) , при этом P называют графиком бинарного отношения.

18

vk.com/club152685050 | vk.com/id446425943

Если пара элементов x, y X Y удовлетворяет бинарному отношению P , то будем писать xPy или x, y P , в противном случае xPy или x, y P .

Опр. n-арным отношением (или n-местным) между множествами X1 , X 2 , ..., X n называется некоторое выделенное подмножество декартова произведения X1 X 2 ... X n .

Замечание. Любое отображение F : Х Y задает бинарное отношение

на Х Y , обратное – неверно.

отношение;

3.P x, y, z : x2 y2 z2 1 – 3-х местное (3-х – арное) отношение

заданное в R3 .

4. Пусть Х 1, 2, 3 , Y r, s , так что декартово произведение имеет

вид

Х Y (1,r), (1, s), (2,r), (2, s), (3,r), (3, s) .

Тогда P (1,r), (1, s), (3, s) - бинарное отношение множеств Х и Y .

Множество Х Y включает 6 элементов. Следовательно, существует 26 64 различных подмножеств множества Х Y , а значит и 64 бинарных отношений. Само множество Х Y также является бинарным отношением.

5.Пусть Х множество товаров в магазине, а Y множество вещественных чисел. Тогда (x, y) X Y : y цена x – отношение множеств

Хи Y .

6.Пусть Х множество женщин, а Y множество мужчин. Тогда

Способы задания бинарных отношений

Отношение, как и любое множество, может быть задано:

1.Семантическим (смысловым) условием, например x y ,

19

vk.com/club152685050 | vk.com/id446425943

2. Простым перечислением его элементов (для конечных множеств), например, как это сделано в примере 4.

1, если xPy, 3. Заданием характеристической функции p x, y

0, если x P y. Если множества Х и Y конечны, то характеристическая функция может

быть задана в виде таблицы, называемой матрицей смежности R отношения

P .

множеств Х и Y изображаются точками на плоскости, причем, если элементы xi

ребром.

Пример.

1.Пусть имеются 4 узла связи, образующие множество

Хх1, x2 , x3 , x4

итри спутника, образующие множество

Y y1, y2 , y3 .

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

20