2

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

Шептунов М. В.

ДИСКРЕТНАЯ МАТЕМАТИКА

Часть I

ТЕОРИЯ МНОЖЕСТВ

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

Москва 2004

УДК 519.1(075.8)

ББК 32.973.3

Дискретная математика, часть 1: Теория множеств: Учеб. пособие / М. В. Шептунов; МГАПИ. Москва, 2004. 64 с. ISBN 5-8068-0284-1

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

Для специальности 2201 «Вычислительные машины, комплексы, системы и сети» это издание может быть использовано в качестве учебного пособия по дисциплине «Дискретная математика».

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

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

Рецензенты: к. т. н., проф. Зеленко Г. В.

к. т. н., проф. Рощин А. В.

 Шептунов М. В., 2004

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...........................................................................…...................………4

1. МНОЖЕСТВА И ИХ СВОЙСТВА………………………………………….5

1.1. Основные понятия теории множеств...................................................……5

1.2. Множества и их спецификации...........................................................…….9

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

1.4. Тождества алгебры множеств...............................................................…..22

1.5. Вопросы для самоконтроля……………………………………………….28

2. ОТНОШЕНИЯ И ФУНКЦИИ………………………………………………30

2.1. Отношения.................................................................................................….30

2.2. Матрица бинарного отношения и её применение………………….….35

2.3. Соответствия ……………………………………………………………..…40

2.4. Отображения……………………………………………………………...…42

2.5. Взаимосвязь понятий “отношение”, “соответствие”, “отображение”…..43

2.6. Функции……………………………………………………………………..44

2.6.1. Понятие функции………………………………………………………...44

2.6.2. Инъективная, сюръективная и биективная функции………………...46

2.6.3. Обратная функция………………………………………………………..47

2.6.4. Понятие функционала……………………………………………………48

2.7. Понятия о неразрешимых вычислительных проблемах……..……...…49

2.8. Однонаправленные функции………………………………………………52

2.9. Вопросы для самоконтроля……………………………………………….58

3. ВЫПУКЛЫЕ МНОЖЕСТВА………………………………………………..60

3.1. Ограниченные, открытые и замкнутые множества……………………60

3.2. Гиперплоскости и полупространства…………………………………….61

3.3. Средневзвешенное по элементам множества…………………………...62

3.4. Выпуклые множества………………………………………………………63

3.5. Вопросы для самоконтроля……………………………………………….63

ЛИТЕРАТУРА……………………………………………………………….…..64

ВВЕДЕНИЕ

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

Дискретная математика была и остаётся одной из наиболее динамичных математических дисциплин. Она изучается почти во всех ВУЗах естественно-научного, технического и экономического профиля.

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

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

В данном учебном пособии рассматриваются вопросы так называемой “конечной математики”, т. е. математики, непосредственно не связанной с понятиями бесконечности, предела и непрерывности. Пособие рассчитано на семестровый лекционный курс и соответствует требованиям государственного образовательного стандарта по специальности 2201 “Вычислительные машины, комплексы, системы и сети”. Учебное пособие также может быть полезным для ряда смежных специальностей.

1. МНОЖЕСТВА И ИХ СВОЙСТВА

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

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

Создателем теории множеств был немецкий учёный Георг Кантор (1845-1918), утверждавший: “множество есть многое, мыслимое нами как единое”. Это утверждение, разумеется, не может служить математически строгим определением множества; такового на сегодняшний день просто не существует.

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

Определение 1.1. (нестрогое). Множество – это совокупность объектов, обладающих одним и тем же определённым свойством.

Например, можно говорить о множестве стульев в комнате, множестве студентов в группе, множестве натуральных чисел, множестве состояний системы и т. д.

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

Определение 1.2. Отдельные объекты, из которых состоит множество, называются элементами множества.

Например, число 3 – элемент множества натуральных чисел, буква б – элемент множества букв русского алфавита.

Заметим, что элементы множества сами могут являться

множествами.

Например, множество групп студентов состоит из элементов, которые, в свою очередь, состоят из студентов.

Общим обозначением множества служит пара фигурных скобок:

{ }.

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

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

A₁, A₂ ...

Для обозначения элементов множества в общем виде используются различные строчные буквы, например,

a, s, x ...

либо строчные буквы с индексами, например,

a₁, a₂ ...

Для указания того, что некоторый элемент a является элементом множества S, используется символ  принадлежности множеству. Запись

a  S

означает, что элемент a принадлежит множеству S, а запись

x  S

означает обратное. Запись

x₁, x₂, ... , x_n  S

используется в качестве сокращения отдельных записей

x₁ S, x₂ S, ... , x_n S.

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

Во-первых, проблематична отличимость элементов. В частности,

возникает вопрос: символы a и  - это один элемент множества A или

же два разных элемента ?

Во-вторых, проблематична возможность (без дополнительных

усилий) указать, принадлежит ли данный элемент данному множеству. В частности, является ли число 87654321048 простым ?

В теории множеств важную роль играют понятия универсального множества (универсума) и пустого множества.

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

Чаще всего оно имеет обозначение: U.

Определение 1.4. Пустым называется множество, не содержащее ни одного элемента.

Пустое множество обозначается символом .

Без этого понятия нельзя было бы, например, говорить о множестве всех корней какого-либо данного уравнения, если бы мы заранее не знали о существовании хотя бы одного его корня.

Иногда бывает трудно определить, является ли данное множество пустым.

Иначе, к примеру, обстоит дело с множеством Z₁ всех решений в целых положительных числах уравнения

.

В этом случае мы знаем метод, с помощью которого мы можем решить вопрос о том, является ли множество Z₁ пустым, но необходимые для этого вычисления весьма трудоёмки (деление числа

на некоторые числа < ).

Далее, фундаментальными являются также понятия конечного и бесконечного множества.

Определение 1.5. Непустое множество называют конечным, если возможно указать число его элементов.

В противном случае множество называется бесконечным.

Например, множество китов в океане конечно, а множество

рациональных чисел бесконечно.

Пустое множество условно будем считать конечным.

В теории множеств также применяется понятие равенства множеств.

Определение 1.6. Множества, состоящие из одних и тех же элементов, называют равными (совпадающими).

Если два множества A и B равны, то есть состоят из одних и тех же элементов, то пишут

A=B.

В противном случае пишут

AB.

Конкретнее, последняя запись означает, что либо во множестве A есть такой элемент, которого нет в множестве B, либо во множестве B есть такой элемент, которого нет в множестве A, или же имеет место и то, и другое.

Очевидно, что равны два конечных множества, отличающиеся друг от друга лишь порядком их элементов, например:

{a, b, c} = {c, a, b}.

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

1. X=X – рефлексивность;

2. Если X=Y, то Y=X – симметричность;

3. Если X=Y и Y=Z, то X=Z – транзитивность.

Как уже упоминалось, во множестве не должно быть неразличимых

элементов. Поэтому во множестве не может быть одинаковых элементов.

В частности, запись {2, 2, 3, 5} некорректна и её следует заменить на {2, 3, 5}.

В теории множеств существует и понятие равномощных множеств.

Определение 1.7. Мощностью конечного множества называется

число его элементов, и обозначается |M|.

Определение 1.8. Два конечных множества A и B называются

равномощными при условии равенства их мощностей.

Теперь, пользуясь понятием равномощности, дадим определение счётному и несчётному множествам.

Определение 1.9. Счётное множество – это такое конечное либо перечислимое бесконечное множество, мощность которого не превосходит мощности множества натуральных чисел.

Прочие бесконечные множества называются несчётными.

Тот факт, что алгебраические методы могут быть применены к изучению нечисловых объектов, каковыми являются множества, иллюстрирует большую общность идей современной математики. В последнее время выяснилось, что теория множеств бросает новый свет на многие области математики, например, теорию меры и теорию вероятностей; она также полезна при систематизации математических

понятий и выяснении их логических связей.

1.2. Множества и их спецификации

Чтобы оперировать с конкретными множествами, их нужно уметь задавать. На сегодняшний день существует 3 способа задания конечных множеств:

1. перечисление;

2. описание;

3. посредством порождающей процедуры.

В отличие от конечных множеств, бесконечные множества не могут