ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

––––––––––––––

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

“МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ”

––––––––––––––––––––––

Кафедра “Персональные компьютеры и сети”

Федоров В.Н.

ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ

Учебное пособие

(конспект лекций)

Москва

2005

УДК: 519.1(075.8)

ББК 32.973.3

Введение в теорию множеств / В.Н. Федоров – М.: МГАПИ, 2005. – с.

Рекомендовано Ученым Советом МГАПИ в качестве учебного пособия для специальности 2201.

Понятие множества относится к первоначальным понятиям, не подлежащим определению. Считается, что множество задается свойством, обладание которым делает объект принадлежащим этому множеству. При исследовании систем различной физической природы довольно часто они представляются как множества взаимосвязанных или взаимодействующих частей – элементов. Связи между элементами задаются через соответствия или отношения.

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

Предназначено для студентов, обучающихся по направлению “Информатика и вычислительная техника”. Для специальности 2201 учебное пособие предназначено для использования в курсе “Дискретная математика ”.

Печатается по решению Редакционно–издательского совета Московской государственной академии приборостроения и информатики.

Научный редактор: д.т.н., проф. Михайлов Б.М.

Рецензенты: к.т.н., проф. Рощин А.В.,

к.т.н., проф. Степанова Т.А.

Работа рассмотрена и одобрена на заседании кафедры ИТ4 “Персональные компьютеры и сети” ____________2005г., протокол № ___.

 Федоров, 2005

СОДЕРЖАНИЕ

1. МНОЖЕСТВА 4

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

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

1.3. Диаграммы Эйлера–Венна 12

1.4. Законы и тождества алгебры множеств 14

1.5. Семейства множеств 15

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

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

2. СООТВЕТСТВИЯ 23

2.1. Соответствия и их свойства 23

2.2. Функции 31

2.3. Отображения 35

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

3. ОТНОШЕНИЯ 40

3.1. Бинарные отношения 41

3.2. Свойства бинарных отношений 43

3.3. Эквивалентность и порядок 47

3.4. Операции над бинарными отношениями и их свойства 49

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

ЛИТЕРАТУРА 59

1. МНОЖЕСТВА

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

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

Множество – состоит из элементов. Принадлежность элемента а множеству М обозначается ("а принадлежит М"), не принадлежность – .

Множество А называется подмножеством множества В (обозначается ), если всякий элемент из А является элементом В (рис 1.1). Если и , то А называется строгим подмножеством (обозначается ).

Р
исунок 1.1

Содержательные примеры множеств и их возможные обозначения:

М₁ – множество всех операций (работ) по сборке компьютера;

М₂ – множество видов услуг, предоставляемых фирмой "Formoza";

N – множество натуральных чисел 1, 2, 3,...;

N₁ – множество натуральных чисел, не превосходящих 100;

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

Два определения равенства множеств:

Определение I: Множества А и В равны (А = В), если их элементы совпадают.

Определение II: Множества А и В равны, если и .

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

Число элементов в конечном множестве М называется его мощностью и обозначается |М|.

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

В множестве можно задать нижнюю и верхнюю границы, обозначаемые

inf A = m и sup A = M,

соответственно. Здесь A – множество, а m и M некоторые элементы множества (не обязательно числа).

Если , то inf A inf B, а sup A sup B

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

• Перечислением, т.е. списком своих элементов. Списком можно задать лишь конечные множества. Обозначение списка – в фигурных скобках. Например, множество А устройств домашнего компьютера, состоящего из процессорного блока a, а также периферийных устройств В (монитора b, клавиатуры с и принтера d), может быть представлено списком:

А = {а, В} или А = {а, b, с, d}.

Уточнения:

1) В списке, задающем множество, одинаковые элементы представляются одним элементом.

2) Перестановка элементов в списке не изменяет множество.

3) Задание типа N = 1, 2, 3, ... – не список, но лишь допустимое условное обозначение.

• Порождающей процедурой, которая описывает способ получения элементов множества из уже полученных элементов либо других объектов. В таком случае элементами множества являются все объекты, которые могут быть построены с помощью такой процедуры. Например, множество всех целых чисел, являющихся степенями двойки , , где N – множество натуральных чисел, (допустимое обозначение = 1, 2, 4, 8, 16,...) может быть представлено порождающей процедурой, заданной двумя правилами, называемыми рекурсивными:

а) ; б) если , то .

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

М = {х|Р(х)} или М = {х:Р(х)}

("Множество М состоит из элементов х таких, что х обладает свойством Р") Например, множество А периферийных устройств персонального компьютера PC может быть определено:

А = {х: х – периферийное устройство персонального компьютера PC}.

Надежным способом точно описать свойство элементов данного множества является задание распознающей процедуры. Она должна устанавливать для любого объекта x, обладает ли он данным свойством Р (и, следовательно, принадлежит множеству) или нет. Например, распознающей процедурой для множества А всех студентов МГАПИ, имеющих студенческие билеты академии, является проверка его наличия. Тогда множество А может быть представлено более точно: "А – множество всех студентов, имеющих студенческие билеты МГАПИ".

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

Тогда , если, а = 1 или если, а = 2 х 2 х ... х 2 = 2ⁿ, .

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

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

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

а) ; б) если , то .

Описание характеристического свойства элементов множества N:

N = {x: х – целое положительное число}.

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

• ={2, 4, 6, ...,100}.

а) ; б) если , то ; в) п 98.

={n: и }.

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

• (U)={ ,{a},{b}, {с}, {а, b}, {а, с}, {b, с}, {а, b, с}}.

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

Обратите внимание на . Пустое множество является элементом любого множества.

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

а) А = {1, 2, 3}, в) С = {х: х А},

б) В = {5, 6, 6, 7}_, г)D ={A, С}?

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

• а) Определение множества А = {1, 2, 3} списком своих элементов формально корректно.

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

в) Определение множества С = {х:х А} заданием характеристического свойства его элементов "принадлежать множеству А" корректно,

А = {1, 2, 3}.

г) Определение списком множества D = {А, С} корректно: элементами множества D являются множества А и С. Однако 1 не принадлежит D, так как элемент 1 не перечислен в списке.

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

Объединением множеств А и В (обозначается ) называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств A, B (рис. 1.2):

= {x: или }.

Пересечением множеств A и В (обозначается ) называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и А, и В (рис. 1.3):

= {x: и }.

Р
исунок 1.2 Рисунок 1.3 Рисунок 1.4

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