Основные обозначения

ОГЛАВЛЕНИЕ

Предисловие ……...………………………………………………... 4

1. Множества ………………………………………………..…..…. 5

1.1 Основные понятия ……………………………………..…..… 6

1.2 Операции над множествами …………………………..…..… 8

1.3 Диаграммы (круги) Эйлера-Венна …………………......…… 10

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

1.5 Векторы, прямые произведения, проекции векторов …....... 15

2. Отношения ………………………………………………..…...… 20

2.1 Бинарные отношения. Основные определения …………..... 20

2.2 Свойства бинарных отношений …………………………….. 26

2.3Эквивалентность и порядок ……………………………….… 31

2.4Операции над бинарными отношениями …………………... 34

3. Соответствия ……………………………………….…………… 43

3.1 Соответствия и их свойства. Основные определения …….. 43

3.2Функции и отображения …………………………………….. 46

3.3 Операции …………………………………………..…………. 50

3.4Гомоморфизмы и изоморфизмы ……………………………. 55

Список литературы ………………………………….……….…… 65

Предисловие

Теория множеств составляет фундаментальную основу современной дискретной математики.

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

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

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

Материал практикума представляет студентам возможность самостоятельно освоить основные положения курса “Дискретная математика” (Часть I. Введение в теорию множеств), приобрести и закрепить практические навыки решения задач.

Пособие содержит задачи для аудиторных занятий, расчетно-графических работ и самостоятельной работы студентов.

Рекомендуемая литература представляет информационную и учебно-методическую базу дискретной математики для углубления и расширения приобретенных навыков в решении рассматриваемых задач по теории множеств.

1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ*

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

Основные обозначения

1. Множество:

N – всех натуральных чисел;

Z – всех целых чисел;

Z ⁺ – целых неотрицательных чисел (Z ⁺ = N È{0});

Z ^– – целых неположительных чисел (Z ^– = Z \ N);

Q – всех рациональных чисел;

Á – всех иррациональных чисел;

R – всех действительных чисел;

R ⁺ – неотрицательных действительных чисел;

R ^– – неположительных действительных чисел.

2. x Î A (x Ï A) – элемент x принадлежит (не принадлежит) множеству A;

A ={ x | P (x)} – множество элементов x, удовлетворяющих свойству P;

A = B Û (A Í B и B Í A) – равенство множеств A и B;

A Í B Û (" x) (x Î A ® x Î B) – множество A (нестрого) включается в множество B (А есть подмножество B);

A Ì B Û A Í B и А ≠ B – множество А (строго) включается в множество B;

U – универсальное множество (универсум);

Æ={ x | x ≠ x } – пустое множество.

3. А Ç B ={ x | x Î A и x Î B } – операция пересечения множеств A, B;

А È B ={ x | x Î A или x Î B } – операция объединения множеств A, B;

А \ B ={ x | x Î A и x Ï B } – операция разности множеств A, B;

А ∆ B =(A \ B)È(B \ A) – симметрическая разность множеств A, B;

X ´ Y – декартово (прямое) произведение множества X на Y;

Xⁿ – n -ая декартова степень множества X;

P (U)={ A | A Í U } – множество (булеан) всех подмножеств универсума U;

| A | – мощность – число элементов (конечного) множества A;

card A – мощность бесконечного множества A;

À₀ – мощность счетного множества;

C – мощность континуума;

@ – символ изоморфизма алгебраических систем.

4. Логические операции (союзы) с высказываниями P, Q:

Ø – отрицание: Ø P означает: “не P ”, ”неверно, что P ”;

& – конъюнкция, P & Q:=” P и Q ”;

Ú – дизъюнкция, P Ú Q:=” P или Q ”;

Þ – импликация, P ® Q:=”если P, то Q ”;

Û – эквиваленция (равнозначность), P Û Q:=” P тогда и только тогда, когда Q ”.

Основные понятия

Множество – состоит из элементов. Принадлежность элемента a множеству M обозначается a Î M (“ a принадлежит M ”), непринадлеж-ность – a Ï M или a M. Множество A называется подмножеством множества B (обозначается A Í B):

1. (A Í B) Û (" а) (а Î A ® а Î B);

2. (A Ì B) Û (A Í B) & А ≠ B;

Отношение равенства множеств A и B:

(A = B) Û (A Í B) & (B Í A).

Множество, состоящее из конечного числа элементов, называется конечным, в противном случае – бесконечным (например, множества N, R – бесконечные множества). Число элементов в конечном множестве M называется его мощностью или кардинальным числом M – card M.

Множество мощности 0, т.е. не содержащее элементов, называется пустым (обозначается Æ): |Æ|=0.

Способы задания множеств:

1. Перечислением, т.е. списком своих элементов.

Например. A ={ a, B } или A ={ a, b, c, d }.

2. Порождающей процедурой, которая описывает способ получения элементов множества из уже полученных элементов либо других объектов. Например, множество всех целых чисел, являющихся степенями двойки M ₂ n, n Î N, где N – множество натуральных чисел, может быть представлено порождающей процедурой, заданной двумя правилами, называемыми рекурсивными (индуктивными):

а) 1Î M ₂ n; б) если m Î M ₂ n, то 2 m Î M ₂ n.

3. Описанием характеристических свойств, которыми должны обладать его элементы; обозначается:

M ={ x | P (x)} или M ={ x: P (x)}.

Пример 1. Задать различными способами множество N всех нату-ральных чисел: 1, 2, 3, …

1. Списком множество N задать нельзя ввиду его бесконечности.

2. Порождающая процедура содержит два правила:

а) 1Î N; б) если n Î N, то n +1Î N;

3. Описание характеристического свойства элементов множества N: N ={ x: x – целое положительное число}.

Пример 2. Задать различными способами множество M всех четных чисел 2, 4, 6, …, не превышающих 100.

M ₂ n ={2, 4, 6, …, 100}.

а) 2Î M ₂ n; б) если n Î N, то (n +2)Î M ₂ n; в) n £98.

M ₂ n ={ n: n – целое четное положительное число, не превышающее 100} или M ₂ n ={ n: n Î N и n /2Î N, n £100).

Пример 3. Пусть U ={ a, b, c }. Определить в явном виде (перечислением своих элементов) булеан b( U ) – множество всех подмножеств, состоящих из элементов множества U. Какова мощность множества b(U)?

b(U)={Æ, { a },{ b },{ c },{ a, b },{ a, c },{ b, c },{ a, b, c }}.

Мощность |b(U)|=8.

Пример 4. Какие из приведенных определений множеств A, B, C, D являются корректными:

a) A ={1, 2, 3}, в) C ={ x: x Î A },

б) B ={5, 6, 6, 7}, г) D ={ A, C }?

Принадлежит ли число 1 множеству D?

а) Определение множества A ={1, 2, 3} – корректно.

б) Корректное определение B ={5, 6, 7}, так как не следует указывать один и тот же элемент несколько раз.

в) Определение множества C ={ x: x Î A } – корректно.

г) Определение списком множества D ={ A, C } – корректно. Однако, 1Ï D, так как элемент 1 не перечислен в списке.

Вопросы для самопроверки и упражнения:

1. Пусть X – множество {1, 2}, а Y – множество { x: x = y + z; y, z Î X }. Определить в явном виде (списком) множество Y. Каковы множества Y ¢={ y: y = x + z; x, z Î X } и Y ²={ x: x = y + z; y, z Î Y }?

2. Задать различными способами множество M ₂ n всех чисел, явля-ющихся степенями двойки: 2, 4, 8, 16, …, не превышающих 300?

3. Задать различными способами множество натуральных чисел, кратных пяти: 5, 10, 15, 20 …

4. Задать в явном виде (списком) множество b(U) всех подмножеств множества U, если U ={1, 2, 5, 7}. Какова мощность множества b(U)?

1.2 Операции над множествами

Объединением множеств A и B (обозна-чается A È B):

A È B ={ x: x Î A или x Î B }.

Объединение произвольной совокупности множеств:

Пересечением множеств A и B (обозна- чается A Ç B):

A Ç B ={ x: x Î A и x Î B }.

Пересечение произвольной совокупности множеств:

Разность множеств A и B (обозначается A \ B):

А \ B ={ x: x Î A и x Ï B }.

Симметрическая разность множеств A и B (обозначается A \ ^. B, A ¸ B, A D B):

A D B ={ x | x Î A и x Ï B или x Ï A и x Î B }= = (A \ B)È(B \ A).

Пусть U – универсальное множество.

Дополнение (до U ) множества A (обозначается ):

= U \ A.

Операции объединения, пересечения, дополнения {È, Ç, –} часто называют булевыми операциями над множествами.

Пример 1. Пусть универсальное множество U – множество всех сотрудников некоторой фирмы; A – множество всех сотрудников данной организации старше 35 лет; B – множество сотрудников, имеющих стаж работы более 10 лет; С – множество менеджеров фирмы. Каков содержательный смысл (характеристическое свойство) каждого из следующих множеств:

а) б) Ç B Ç C; в) A È(B Ç ); г) B \ C; д) C \ B?

а) – множество сотрудников организации, стаж работы которых не превышает 10 лет.

б) Ç B Ç C – множество менеджеров фирмы не старше 35 лет, имеющих стаж работы более 10 лет.

в) A È(B Ç ) – множество всех сотрудников фирмы старше 35 лет, а также сотрудников, не являющихся менеджерами, стаж работы которых более 10 лет.

г) B \ C – множество сотрудников организации со стажем работы более 10 лет, не работающих менеджерами.

д) C \ B – множество менеджеров со стажем работы не более 10 лет.

Пример 2. Пусть U ={1, 2, 3, 4}, A ={1, 3, 4}, B ={2, 3}, C ={1, 4}. Найти:

а) È б) в) А Ç г) (B \ A) È .

а) È =(U \ A)È(U \ B)=({1, 2, 3, 4}\{1, 3,4})È({1, 2, 3, 4}\{2, 3})= ={2}È{1, 4}={1, 2, 4}.

б) = U \(A Ç B)={1, 2, 3, 4}\({1, 3, 4}Ç{2, 3}={1, 2, 3, 4}\{3}= ={1, 2, 4}.

в) А Ç = A Ç(U \ B)={1, 3,4}Ç({1, 2, 3, 4}\{2, 3})={1, 3, 4}Ç{1, 4}= ={1, 4}.

г) (B \ A) È = ({2, 3}\{1, 3, 4})È({1, 2, 3, 4}\{1, 4})={2}È{2, 3}={2, 3}.

Вопросы для самопроверки и упражнения:

1. Пусть A ={1, 2, 3}, B ={2, 3, 4, 5}, C ={2, 5, 6}, U ={1, 2, 3, 4, 5, 6, 7, 8, 9}. Найти:

а) A È B È C; б) A Ç B Ç C; в) A \(B È C); г) (A \ B)È C;

д) (A È B)\(A Ç B) е) (A D B)Ç C; ж) (A D B)D C; з) (A D B)\ C;

и) A Ç(B D C); к) Ç(A D B); л) Ç C; м) (A Ç B)\

2. Указать, какие из следующих утверждений справедливы:

а) 0ÎÆ; б) Æ={0}; в) |{Æ}|=0; г) |Æ|=0?

3. Пусть U ={ a, b, c, d }, X ={ a, c }, Y ={ a, b, d }, Z ={ b, c }. Найти множества:

а) б) в) X È(Y Ç Z);

г) (X È Y)Ç(X È Z); д) X È Y; е)

ж) з) (X È Y)È Z; и) X È(Y È Z);

к) л) (X \ Z)È(Y \ Z).

4. Даны два произвольных множества A и B такие, что A Ç B =Æ. Что представляют собой A \ B и B \ A?

5. Даны два произвольных множества С и D такие, что С Ç =Æ. Что можно сказать о C Ç D, C È D?