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

vk.com/club152685050 | vk.com/id446425943

2. Это бинарное отношение можно задать перечислением элементов подмножества Х Y :

Px1, y1 , x1, y3 , x3 , y1 , x3 , y3 , x2 , y2 , x4 , y2

2.Матрица смежности этого бинарного отношения имеет вид:

4. Графический способ задания бинарного отношения:

Количество единиц в матрице смежности равно количеству дуг в графе и равно количеству элементов в отношении P .

Опр. Пусть P – бинарное отношение на множестве X Y . Обратным

vk.com/club152685050 | vk.com/id446425943

Опр. Дуга, соединяющая вершину с собой, называется петлей.

Замечание 1. Чтобы получить матрицу смежности обратного отношения P 1 , надо транспонировать матрицу смежности отношения P ;

Замечание 2. Графы прямого и обратного отношения отличаются лишь направлением стрелок дуг.

Простейшие бинарные отношения

1. Пустое отношение – матрица смежности состоит из одних нулей, а граф – из одних вершин.

Пример. Х={1, 2, 3}, Y={4, 5} и P (x, y) : x y . Тогда P = , R=

0 0

0 0 .0 0

2. Полное отношение U – матрица смежности состоит из одних единиц, а в соответствующем графе все вершины связаны между собой и имеют петли.

Пример. P (x, y) :"x родственник y" x, y X ;

1 1 1 R= 1 1 1 1

1 1 1

Двусторонние дуги можно заменить ребрами.

3. Отношение равенства – матрица смежности является единичной матрицей; граф не содержит ни дуг, ни ребер, но каждая вершина имеет петлю.

22

vk.com/club152685050 | vk.com/id446425943

III.Транзитивность

Опр. Бинарное отношение P называют транзитивным на множестве X,

xPy

если для любых x, y, z X из того, что xPz . yPz

Примеры. Отношение параллельности прямых, отношения > и < на множестве вещественных чисел.

§9. Отношение эквивалентности. Разбиение на классы Опр. Бинарное отношение называется отношением эквивалентности на

множестве Х, если оно рефлексивно, симметрично и транзитивно. Обозначается символами ~ либо .

Отношение эквивалентности означает “одинаковость”, т.е. взаимозаменяемость, неразличимость объектов по отношению к заданному свойству.

Примеры:

1.В анализе – множество эквивалентных функций при x x0 .

2.В электротехнике – эквивалентные схемы, которые, несмотря на различие в структуре (топологии), ведут себя функционально одинаково.

3.В геометрии – подобные треугольники.

Из данных примеров понятно, что отношение эквивалентности разбивает

отношению P называется фактор-множеством множества X по отношению

P : X / P .

В качестве примера разбиения множества на классы эквивалентности рассмотрим отношение сравнимости двух чисел по модулю m.

24

vk.com/club152685050 | vk.com/id446425943

Пример. Проверим, что отношение сравнимости целых чисел по mod 4 есть отношение эквивалентности P x y(mod 4), x, y .

транзитивно. Эквивалентность отношения P доказана.

Данное отношение разбивает все множество целых чисел на 4 класса эквивалентности:

p(0) y : y 4k, k z p(1) {y : y 4k 1, k z} p(2) {y : y 4k 2, k z} p(3) {y : y 4k 3, k z}

Фактор – множество множества целых чисел по отношению сравнимости по mod 4 состоит из 4-х элементов:

X / P { p(0), p(1), p(2), p(3)}.

Замечание. Граф отношения эквивалентности представляет собой

Множество X называют линейно упорядоченным множеством

Пример:

1. Отношение x y на множестве является отношением линейного порядка.

25

vk.com/club152685050 | vk.com/id446425943

2. Отношение включения множеств “ ”, заданное на булеане B(U), является отношением частичного порядка, но не является отношением линейного порядка, так как существуют подмножества, для которых не выполняется ни Т S, ни S Т, например, пересекающиеся подмножества.

Опр. Пусть на множестве X задано отношение частичного порядка “ ”; элементы 0 и называются нижней и верхней универсальными границами множества X , если для x Х справедливо 0 x и x I .

Замечания:

1.Частично упорядоченное множество может не иметь

2.В отношении включения, заданном на булеане B(U): 0=Ø, I=U.

§11. Понятие булевой алгебры

Джордж Буль (1815-1864) – английский математик, логик. Развитие булевой алгебры используется в вычислительной технике, программировании, в теоретико-вероятностных расчетах и др.

Бинарные операции: сложение и умножение чисел, объединение множеств.

Опр. Булевой алгеброй называют совокупность основного множества

Mс заданными на нем бинарными операциями " " и " ", унарной операцией

"" и двух выделенных элементов 0 и 1 множества М. Здесь " " и " " - булево произведение и булева сумма, – " " булево дополнение.

Замечание: Под " " и " " можно понимать все, что угодно, лишь бы это удовлетворяло аксиомам, приведенным ниже.

Для любых x, y, z M выполняются следующие аксиомы, аналогичные свойствам операций , над алгеброй подмножеств:

26

Список аксиом А1-А10 является избыточными, например А5следует из А6 и А1, аксиома А6 – из аксиом А2-А5. Набор независимых аксиом, например: { A2,A3,A4,A6,A7,A8}. Избыточность аксиом упрощает доказательство теорем о свойствах булевых алгебр.

Утверждение: Алгебра подмножеств является булевой алгеброй с операциями , , и элементами 0 = и 1 = U.

Доказательство следует из свойств операций , - приведенных в §3. Важное свойство булевых алгебр приведено в следующей теореме:

Теорема (принцип двойственности).

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

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

Пример. Упростить, проверить выполнение принципа двойственности:

A2 A4 A1

x ((x y) x) x (x (x y)) x x x

27

vk.com/club152685050 | vk.com/id446425943

A2 A4 A1

Поменяем знаки: x ((x y) x) x (x (x y)) x x x .

§12. Изоморфизм булевых алгебр

Для сравнения булевых алгебр введем понятие “изоморфизма” т.е. в некотором смысле эквивалентности булевых алгебр.

справедливо:

F (x y) F (x) F ( y) F (x y) F (x) F ( y)

F (x) F (x) , при этом биекция F называется изоморфизмом. Замечание. Из определения изоморфизма следует правило отображение

универсальных границ:

F(O1) O2 ; F(11) 12

Докажем это: F (O1 ) F (x x) F (x) F (x) F (x) F (x) O2 ,

F (11 ) F (x x) F (x) F (x) F (x) F (x) 12 .

Теорема Стоуна

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

Теорема (о наследование свойств булевой алгебры).

Если алгебра B M , , , изоморфна некоторой булевой алгебре B1 M1 , , , , то она сама также является булевой алгеброй.

Доказательство вытекает из свойств изоморфизма. Теорема (об отношении частичного порядка в алгебре).

Пусть в алгебре <M, , > бинарным операции удовлетворяют аксиомы А1-А4, тогда отношение, введенное на М следующим образом: xPy, если x=x y, является отношением частичного порядка.

Доказательство. Докажем рефлексивность, антисимметричность, транзитивность.

1.по А1 x x x xPx рефлексивно,

A2

x x y y x y x y антисимметрично

28

vk.com/club152685050 | vk.com/id446425943

алгеброй Буля. Заданные подобным образом операции удовлетворяют всем аксиомам булевой алгебры.

Контрольные вопросы.

1.Что такое множество? Как его обозначить? Как можно задать множество?

2.Какое множество называют счетным? Какое пустым?

3.Что такое подмножество?

4.Сформулируйте основные свойства счетных множеств.

5.Определите понятие булеана.

6.Сформулируйте основные аксиомы теории множеств.

7.Какие соотношения (действия) между множествами вы знаете, как они обозначаются?

8.Какое множество можно назвать универсальным?

9.Что такое диаграмма Эйлера? Проиллюстрируйте с помощью диаграмм Эйлера объединение и пересечение трех множеств.

10.Дайте определение декартова произведения множеств; какие теоремы о декартовом произведении вы знаете?

11.Поясните термин «мощность множества».

12.Сформулируйте основные тождества алгебры множеств.

13.Что понимается под соответствием между множествами?

14.Какое соответствие называется инъективным, сюръективным, биективным?

15.Какие множества называют эквивалентными? Каковы основные свойства эквивалентных множеств?

16.Какова мощность булеана конечного множества.

17.Дайте определение бинарного отношения. Какие типы бинарных

29

vk.com/club152685050 | vk.com/id446425943

отношений вы знаете?

18.Дайте определение отношения эквивалентности.

19.Что такое отношение частичного порядка?

30