ВВЕДЕНИЕ 3
1. МНОЖЕСТВА И ИХ СВОЙСТВА 3
1.1. Основные понятия теории множеств 3
1.2. Множества и их спецификации 5
1.3. Операции над множествами 8
1.4. Тождества алгебры множеств 12
2. Отображение и функция 15
2.1. Соответствия 15
2.2. Отображения 16
2.3. Взаимосвязь понятий “отношение”, “соответствие”, “отображение” 17
2.4. Функции 18
2.4.1. Понятие функции 18
2.4.2. Инъективная, сюръективная и биективная функции 19
2.4.3. Обратная функция 19
2.4.4. Понятие функционала 20
2.5 Понятие оператора. 20
Список используемой литературы 21
ВВЕДЕНИЕ
В современной иерархии математических наук дискретная математика является промежуточным звеном между рядом дисциплин естественно-научного и технического профиля. Дискретная математика тесно связана с такими дисциплинами, как алгебра, геометрия, логика. Она также непосредственно связана с технической кибернетикой и информатикой.
Дискретная математика была и остаётся одной из наиболее динамичных математических дисциплин. Она изучается почти во всех ВУЗах естественно-научного, технического и экономического профиля.
На сегодняшний день наиболее значимым направлением развития дис-кретной математики являются информационные технологии. Это объясняет-ся, прежде всего, необходимостью создания и эксплуатации персональных ЭВМ, компьютерных сетей, систем управления, а также автоматизированных средств обработки информации.
Исходным базовым понятием дискретной математики является понятие множества. Исходя из этого понятия, далее можно определить прочие поня-тия конструктивным и математически приемлемым образом.
1. МНОЖЕСТВА И ИХ СВОЙСТВА
1.1. Основные понятия теории множеств
Почти во всех разделах дискретной математики используется понятие множества. Как правило, специалистам-математикам приходится рассматри-вать некоторую совокупность объектов как единое целое.
Создателем теории множеств был немецкий учёный Георг Кантор (1845-1918), утверждавший: “множество есть многое, мыслимое нами как единое”. Это утверждение, разумеется, не может служить математически строгим определением множества; такового на сегодняшний день просто не существует.
Понятие множества определяется, по-видимому, некоторым свойством, которым должен либо обладать, либо не обладать каждый из рассматривае-мых объектов. В свете сказанного, дадим множеству нестрогое определение.
☼ (нестрогое). Множество – это совокупность объектов, обладающих одним и тем же определённым свойством.
Например, можно говорить о множестве стульев в комнате, множестве студентов в группе, множестве натуральных чисел, множестве состояний сис-темы и т. д.
Необходимо отметить, что говорить о множестве корректно лишь то-гда, когда элементы множества различимы между собой. В частности, некор-ректно говорить о множестве капель в стакане воды, поскольку невозможно чётко и ясно указать каждую отдельную каплю.
☼ Отдельные объекты, из которых состоит множество, называются эле-ментами множества.
Например, число 3 – элемент множества натуральных чисел, буква б – элемент множества букв русского алфавита.
Заметим, что элементы множества сами могут являться множествами.
Например, множество групп студентов состоит из элементов, которые, в свою очередь, состоят из студентов.
Общим обозначением множества служит пара фигурных скобок: { }.
Внутри этих скобок перечисляются элементы множества.
Для обозначения конкретных множеств используются заглавные буквы с индексами, например,
A1, A2 ...
Для обозначения элементов множества в общем виде используются раз-личные строчные буквы, например,
a, s, x ...
либо строчные буквы с индексами, например,
a1, a2 ...
Для указания того, что некоторый элемент a является элементом множества S, используется символ принадлежности множеству. Запись
a S
означает, что элемент a принадлежит множеству S, а запись
x S
означает обратное. Запись
x1, x2, ... , xn S
используется в качестве сокращения отдельных записей
x1 S, x2 S, ... , xn S.
Понятия множества, элемента и принадлежности, которые на первый взгляд представляются интуитивно ясными, при ближайшем рассмотрении такую ясность утрачивают.
Во-первых, проблематична отличимость элементов. В частности, возникает вопрос: символы a и - это один элемент множества A или же два разных элемента ?
Во-вторых, проблематична возможность (без дополнительных усилий) указать, принадлежит ли данный элемент данному множеству. В частности, является ли число 87654321048 простым ?
В теории множеств важную роль играют понятия универсального множества (универсума) и пустого множества.
☼ Множество, содержащее все рассматриваемые элементы, природа которых безразлична, называется универсальным или универсумом.
Чаще всего оно имеет обозначение: U.
☼ Пустым называется множество, не содержащее ни одного элемента.
Пустое множество обозначается символом .
Без этого понятия нельзя было бы, например, говорить о множестве всех корней какого-либо данного уравнения, если бы мы заранее не знали о существовании хотя бы одного его корня.
Иногда бывает трудно определить, является ли данное множество пус-тым.
Иначе, к примеру, обстоит дело с множеством Z1 всех решений в целых положительных числах уравнения
.
В этом случае мы знаем метод, с помощью которого мы можем решить вопрос о том, является ли множество Z1 пустым, но необходимые для этого вычисления весьма трудоёмки (деление числа на некоторые числа < ).
Далее, фундаментальными являются также понятия конечного и беско-нечного множества.
☼ Непустое множество называют конечным, если возможно указать число его элементов.
В противном случае множество называется бесконечным.
Например, множество китов в океане конечно, а множество
рациональных чисел бесконечно.
Пустое множество условно будем считать конечным.
В теории множеств также применяется понятие равенства множеств.
☼ Множества, состоящие из одних и тех же элементов, называют равными (совпадающими).
Если два множества A и B равны, то есть состоят из одних и тех же эле-ментов, то пишут
A=B.
В противном случае пишут
AB.
Конкретнее, последняя запись означает, что либо во множестве A есть такой элемент, которого нет в множестве B, либо во множестве B есть такой элемент, которого нет в множестве A, или же имеет место и то, и другое.
Очевидно, что равны два конечных множества, отличающиеся друг от друга лишь порядком их элементов, например:
{a, b, c} = {c, a, b}.
Понятие равенства множеств обладает следующими свойствами:
X=X – рефлексивность;
Если X=Y, то Y=X – симметричность;
Если X=Y и Y=Z, то X=Z – транзитивность.
Как уже упоминалось, во множестве не должно быть неразличимых элемен-тов. Поэтому во множестве не может быть одинаковых элементов. В частности, запись {2, 2, 3, 5} некорректна и её следует заменить на {2, 3, 5}.
В теории множеств существует и понятие равномощных множеств.
☼ Мощностью конечного множества называется число его элементов, и обозначается |M|.
☼ Два конечных множества A и B называются равномощными при условии равенства их мощностей.
Теперь, пользуясь понятием равномощности, дадим определение счётному и несчётному множествам.
☼ Счётное множество – это такое конечное либо перечислимое беско-нечное множество, мощность которого не превосходит мощности множества натуральных чисел. Прочие бесконечные множества называются несчётными.
Тот факт, что алгебраические методы могут быть применены к изуче-нию нечисловых объектов, каковыми являются множества, иллюстрирует большую общность идей современной математики. В последнее время выяс-нилось, что теория множеств бросает новый свет на многие области матема-тики, например, теорию меры и теорию вероятностей; она также полезна при систематизации математических
понятий и выяснении их логических связей.
1.2. Множества и их спецификации
Чтобы оперировать с конкретными множествами, их нужно уметь зада-вать. На сегодняшний день существует 3 способа задания конечных мно-жеств:
1. перечисление;
2. описание;
3. посредством порождающей процедуры.
В отличие от конечных множеств, бесконечные множества не могут быть заданы перечислением их элементов. Их задают обычно описанием, т. е. указанием свойств, которыми обладают все элементы данного множества. Для бесконечных множеств применяется и третий способ.
Остановимся на трёх указанных способах более подробно.
Первый способ удобен при рассмотрении конечных множеств, содержащих небольшое число элементов. В частности, множество отличников группы можно задать, перечислив студентов, учащихся на отлично, например:
{Иванов, Петров, Сидоров}.
Другая сокращённая запись данного способа – вводят множество индексов
I={1, 2,..., n}
и пишут:
A={ai}, i I.
При втором способе применяется запись
A={x M | x – отличник группы},
что читается следующим образом:
“множество A отличников группы состоит из элементов x множества M студентов этой группы, обладающих тем свойством, что x – это отличник
группы”.
Когда нет сомнений, из какого множества берутся элементы x, указание о принадлежности x множеству M можно не делать. Тогда множество A записывается в виде:
A={x | x – отличник группы}.
Приведём ещё примеры ко второму (описательному) способу:
{x | x – чётное} – множество чётных чисел;
{x | x2-1=0} – множество {+1, - 1}.
Третий способ, как уже упоминалось, состоит в использовании порож-дающей процедуры.
☼ Порождающей процедурой называется такая, при запуске которой генерируются некоторые объекты, являющиеся элементами определяемого множества.
Пример для третьего способа:
M={n | for n from 1 to 9}.
Для конечных множеств, заданных перечислением (первым способом), задача нахождения наибольшего и наименьшего элемента множества не представляет труда. Например, для множества T={4, 3, 5, 6}
6 – максимум, а 3 – минимум.
Если же множество задано описательным способом (вторым), т. е. указано лишь правило вычисления числовых значений его элементов, то задача отыскания максимального и минимального его элементов существенно усложняется.
Несколько более простой задачей является нахождение лишь области, внутри которой лежат все элементы множества. При решении этой задачи очень полезными являются понятия верхней и нижней границ множества.
Пусть S – множество вещественных чисел. Верхней границей S являет-ся число C такое, что для любого xS имеет место:
xC.
Чисел, которые могут рассматриваться в качестве верхней границы множества, может быть бесконечно много, а может и не быть вообще.
Пример в множестве
m любое CM является верхней границей.
☼ Точной верхней границей (супремумом) множества называется такая верхняя граница, которая не превосходит любую другую верхнюю границу.
Для множества S обозначение точной верхней границы будет таким:
sup S.
Для примера справедливо
sup S=M.
Множество может иметь только одну верхнюю границу.
Пусть S – множество вещественных чисел. Нижней границей S является число с такое, что для любого xS имеет место:
xc.
☼ Точной нижней границей (инфинумом) множества называется нижняя граница, не меньшая любой другой нижней границы.
Для множества S обозначение точной верхней границы будет таким:
inf S.
Для примера справедливо
inf S=m.
Второй, описательный способ задания множеств, таит некоторые опасности, поскольку “неправильно” заданные свойства могут привести к противоречию. Укажем один из наиболее типичных теоретико-множественных парадоксов – парадокс Рассела.
Рассмотрим множество всех множеств, не содержащих себя в качестве элемента, что можно отразить следующей записью:
Y={X | X X} (*)
Если множество Y существует, то мы должны иметь возможность отве-тить на следующий вопрос:
YY ?
Допустим, что YY, тогда в соответствии с (*)
YY.
Теперь допустим, что YY, тогда в соответствии с (*)
YY.
Таким образом, приходим к противоречию, известному как парадокс Рассела. Существует три способа избежать этого парадокса.
1. Ограничить используемые описания видом
A{xM | Q(x)},
где M – известное, заведомо существующее множество (универсум).
Для Y универсум не указан, а потому Y множеством не является.
2. Использовать типы.
Объекты имеют тип 0, множества имеют тип 1, множества множеств – тип 2 и т. д.
Y не имеет типа и множеством не является.
3. Задавать A(x) в виде вычислимой функции (алгоритма).
Способ вычисления значения XX не задан, а потому Y множеством не является.
В качестве центральных в теории множеств выступают понятия подмножества и надмножества.
☼ Множество A называется подмножеством множества B, если любой элемент множества A принадлежит и множеству B.
B в этом случае называется надмножеством множества A.
☼ Если множество B включает в себя A, что выражается AB,
но при этом AB, то A называется собственным подмножеством B.
Очевидно, что часть собственного подмножества данного множества всегда является собственным подмножеством этого множества.
Если требуется различать собственные и несобственные подмножества, то для обозначения включения собственных подмножеств используется знак , а для несобственных .
Два множества равны, если они являются подмножествами друг друга.
Применительно к введённым понятиям подмножества и надмножества действует следующая Теорема о верхней и нижней границах подмножества.
Если
BA,
то имеет место
inf B inf A, sup B sup A.
Для определения подмножества характерно использование следующих символов:
- символ, называемый квантором и означающий “любой”, “каков бы ни был”, “для всех”;
- символ следствия (импликации), означающий “влечёт за собой”.
При помощи этих двух символов определение подмножества можно сформулировать так:
x [xX xY],
что читается следующим образом: для любого x утверждение “x принадлежит X” влечёт за собой утверждение “x принадлежит Y”.
Отметим некоторые свойства подмножества, вытекающие из его определения:
XX (рефлексивность);
[XY и YZ] XZ (транзитивность).
Для любого множества M справедливо
M.
Естественно, что пустое множество не содержит элементов. Следова-тельно, при добавлении к M пустого множества мы фактически не добавляем ничего. Поэтому всегда считается, что любое множество M содержит в себе пустое в качестве подмножества.
☼ Совокупность всех подмножеств множества A называется его булеаном или множеством-степенью и обозначается 2A:
2A={B | BA}.
Множества удобно изображать графически. В конце XIX века английский учёный Джордж Венн усовершенствовал введённые Эйлером круги для иллюстрации множеств, добавив к изображению объёма рассматриваемого понятия X изображение объёма логически противоположного ему понятия НЕ X (X). Объём понятия X дополняет объём понятия X.
☼ Изображение множества в виде областей в прямоугольнике, представляющем универсальное множество, называется диаграммой Эйлера
……………………………………………………………………..
……………………………………………………………………..
……………………………………………………………………..
---------
ВВЕДЕНИЕ 3
1. МНОЖЕСТВА И ИХ СВОЙСТВА 3
1.1. Основные понятия теории множеств 3
1.2. Множества и их спецификации 5
1.3. Операции над множествами 8
1.4. Тождества алгебры множеств 12
2. Отображение и функция 15
2.1. Соответствия 15
2.2. Отображения 16
2.3. Взаимосвязь понятий “отношение”, “соответствие”, “отображение” 17
2.4. Функции 18
2.4.1. Понятие функции 18
2.4.2. Инъективная, сюръективная и биективная функции 19
2.4.3. Обратная функция 19
2.4.4. Понятие функционала 20
2.5 Понятие оператора. 20
Список используемой литературы 21
ВВЕДЕНИЕ
В современной иерархии математических наук дискретная математика является промежуточным звеном между рядом дисциплин естественно-научного и технического профиля. Дискретная математика тесно связана с такими дисциплинами, как алгебра, геометрия, логика. Она также непосредственно связана с технической кибернетикой и информатикой.
Дискретная математика была и остаётся одной из наиболее динамичных математических дисциплин. Она изучается почти во всех ВУЗах естественнонаучного, технического и экономического профиля.
На сегодняшний день наиболее значимым направлением развития дискретной математики являются информационные технологии. Это объясняется, прежде всего, необходимостью создания и эксплуатации персональных ЭВМ, компьютерных сетей, систем управления, а также автоматизированных средств обработки информации.
Исходным базовым понятием дискретной математики является понятие множества. Исходя из этого понятия, далее можно определить прочие понятия конструктивным и математически приемлемым образом.
1. МНОЖЕСТВА И ИХ СВОЙСТВА
1.1. Основные понятия теории множеств
Почти во всех разделах дискретной математики используется понятие множества. Как правило, специалистам-математикам приходится рассматривать некоторую совокупность объектов как единое целое.
Создателем теории множеств был немецкий учёный Георг Кантор (1845-1918), утверждавший: “множество есть многое, мыслимое нами как единое”. Это утверждение, разумеется, не может служить математически строгим определением множества; такового на сегодняшний день просто не существует.
Понятие множества определяется, по-видимому, некоторым свойством, которым должен либо обладать, либо не обладать каждый из рассматриваемых объектов. В свете сказанного, дадим множеству нестрогое определение.
☼ (нестрогое). Множество – это совокупность объектов, обладающих одним и тем же определённым свойством.
Например, можно говорить о множестве стульев в комнате, множестве студентов в группе, множестве натуральных чисел, множестве состояний системы и т. д.
Необходимо отметить, что говорить о множестве корректно лишь тогда, когда элементы множества различимы между собой. В частности, некорректно говорить о множестве капель в стакане воды, поскольку невозможно чётко и ясно указать каждую отдельную каплю.
☼ Отдельные объекты, из которых состоит множество, называются элементами множества.
Например, число 3 – элемент множества натуральных чисел, буква б – элемент множества букв русского алфавита.
Заметим, что элементы множества сами могут являться множествами.
Например, множество групп студентов состоит из элементов, которые, в свою очередь, состоят из студентов.
Общим обозначением множества служит пара фигурных скобок: { }.
Внутри этих скобок перечисляются элементы множества.
Для обозначения конкретных множеств используются заглавные буквы с индексами, например,
A1, A2 ...
Для обозначения элементов множества в общем виде используются различные строчные буквы, например,
a, s, x ...
либо строчные буквы с индексами, например,
a1, a2 ...
Для указания того, что некоторый элемент a является элементом множества S, используется символ принадлежности множеству. Запись
a S
означает, что элемент a принадлежит множеству S, а запись
x S
означает обратное. Запись
x1, x2, ... , xn S
используется в качестве сокращения отдельных записей
x1 S, x2 S, ... , xn S.
Понятия множества, элемента и принадлежности, которые на первый взгляд представляются интуитивно ясными, при ближайшем рассмотрении такую ясность утрачивают.
Во-первых, проблематична отличимость элементов. В частности, возникает вопрос: символы a и - это один элемент множества A или же два разных элемента ?
Во-вторых, проблематична возможность (без дополнительных усилий) указать, принадлежит ли данный элемент данному множеству. В частности, является ли число 87654321048 простым ?
В теории множеств важную роль играют понятия универсального множества (универсума) и пустого множества.
☼ Множество, содержащее все рассматриваемые элементы, природа которых безразлична, называется универсальным или универсумом.
Чаще всего оно имеет обозначение: U.
☼ Пустым называется множество, не содержащее ни одного элемента.
Пустое множество обозначается символом .
Без этого понятия нельзя было бы, например, говорить о множестве всех корней какого-либо данного уравнения, если бы мы заранее не знали о существовании хотя бы одного его корня.
Иногда бывает трудно определить, является ли данное множество пустым.
Иначе, к примеру, обстоит дело с множеством Z1 всех решений в целых положительных числах уравнения
.
В этом случае мы знаем метод, с помощью которого мы можем решить вопрос о том, является ли множество Z1 пустым, но необходимые для этого вычисления весьма трудоёмки (деление числа на некоторые числа < ).
Далее, фундаментальными являются также понятия конечного и бесконечного множества.
☼ Непустое множество называют конечным, если возможно указать число его элементов.
В противном случае множество называется бесконечным.
Например, множество китов в океане конечно, а множество
рациональных чисел бесконечно.
Пустое множество условно будем считать конечным.
В теории множеств также применяется понятие равенства множеств.
☼ Множества, состоящие из одних и тех же элементов, называют равными (совпадающими).
Если два множества A и B равны, то есть состоят из одних и тех же элементов, то пишут
A=B.
В противном случае пишут
AB.
Конкретнее, последняя запись означает, что либо во множестве A есть такой элемент, которого нет в множестве B, либо во множестве B есть такой элемент, которого нет в множестве A, или же имеет место и то, и другое.
Очевидно, что равны два конечных множества, отличающиеся друг от друга лишь порядком их элементов, например:
{a, b, c} = {c, a, b}.
Понятие равенства множеств обладает следующими свойствами:
X=X – рефлексивность;
Если X=Y, то Y=X – симметричность;
Если X=Y и Y=Z, то X=Z – транзитивность.
Как уже упоминалось, во множестве не должно быть неразличимых элементов. Поэтому во множестве не может быть одинаковых элементов. В частности, запись {2, 2, 3, 5} некорректна и её следует заменить на {2, 3, 5}.
В теории множеств существует и понятие равномощных множеств.
☼ Мощностью конечного множества называется число его элементов, и обозначается |M|.
☼ Два конечных множества A и B называются равномощными при условии равенства их мощностей.
Теперь, пользуясь понятием равномощности, дадим определение счётному и несчётному множествам.
☼ Счётное множество – это такое конечное либо перечислимое бесконечное множество, мощность которого не превосходит мощности множества натуральных чисел. Прочие бесконечные множества называются несчётными.
Тот факт, что алгебраические методы могут быть применены к изучению нечисловых объектов, каковыми являются множества, иллюстрирует большую общность идей современной математики. В последнее время выяснилось, что теория множеств бросает новый свет на многие области математики, например, теорию меры и теорию вероятностей; она также полезна при систематизации математических
понятий и выяснении их логических связей.
1.2. Множества и их спецификации
Чтобы оперировать с конкретными множествами, их нужно уметь задавать. На сегодняшний день существует 3 способа задания конечных множеств:
1. перечисление;
2. описание;
3. посредством порождающей процедуры.
В отличие от конечных множеств, бесконечные множества не могут быть заданы перечислением их элементов. Их задают обычно описанием, т. е. указанием свойств, которыми обладают все элементы данного множества. Для бесконечных множеств применяется и третий способ.
Остановимся на трёх указанных способах более подробно.
Первый способ удобен при рассмотрении конечных множеств, содержащих небольшое число элементов. В частности, множество отличников группы можно задать, перечислив студентов, учащихся на отлично, например:
{Иванов, Петров, Сидоров}.
Другая сокращённая запись данного способа – вводят множество индексов
I={1, 2,..., n}
и пишут:
A={ai}, i I.
При втором способе применяется запись
A={x M | x – отличник группы},
что читается следующим образом:
“множество A отличников группы состоит из элементов x множества M студентов этой группы, обладающих тем свойством, что x – это отличник
группы”.
Когда нет сомнений, из какого множества берутся элементы x, указание о принадлежности x множеству M можно не делать. Тогда множество A записывается в виде:
A={x | x – отличник группы}.
Приведём ещё примеры ко второму (описательному) способу:
{x | x – чётное} – множество чётных чисел;
{x | x2-1=0} – множество {+1, - 1}.
Третий способ, как уже упоминалось, состоит в использовании порождающей процедуры.
☼ Порождающей процедурой называется такая, при запуске которой генерируются некоторые объекты, являющиеся элементами определяемого множества.
Пример для третьего способа:
M={n | for n from 1 to 9}.
Для конечных множеств, заданных перечислением (первым способом), задача нахождения наибольшего и наименьшего элемента множества не представляет труда. Например, для множества T={4, 3, 5, 6}
6 – максимум, а 3 – минимум.
Если же множество задано описательным способом (вторым), т. е. указано лишь правило вычисления числовых значений его элементов, то задача отыскания максимального и минимального его элементов существенно усложняется.
Несколько более простой задачей является нахождение лишь области, внутри которой лежат все элементы множества. При решении этой задачи очень полезными являются понятия верхней и нижней границ множества.
Пусть S – множество вещественных чисел. Верхней границей S является число C такое, что для любого xS имеет место:
xC.
Чисел, которые могут рассматриваться в качестве верхней границы множества, может быть бесконечно много, а может и не быть вообще.
Пример в множестве
m любое CM является верхней границей.
☼ Точной верхней границей (супремумом) множества называется такая верхняя граница, которая не превосходит любую другую верхнюю границу.
Для множества S обозначение точной верхней границы будет таким:
sup S.
Для примера справедливо
sup S=M.
Множество может иметь только одну верхнюю границу.
Пусть S – множество вещественных чисел. Нижней границей S является число с такое, что для любого xS имеет место:
xc.
☼ Точной нижней границей (инфинумом) множества называется нижняя граница, не меньшая любой другой нижней границы.
Для множества S обозначение точной верхней границы будет таким:
inf S.
Для примера справедливо
inf S=m.
Второй, описательный способ задания множеств, таит некоторые опасности, поскольку “неправильно” заданные свойства могут привести к противоречию. Укажем один из наиболее типичных теоретико-множественных парадоксов – парадокс Рассела.
Рассмотрим множество всех множеств, не содержащих себя в качестве элемента, что можно отразить следующей записью:
Y={X | X X} (*)
Если множество Y существует, то мы должны иметь возможность ответить на следующий вопрос:
YY ?
Допустим, что YY, тогда в соответствии с (*)
YY.
Теперь допустим, что YY, тогда в соответствии с (*)
YY.
Таким образом, приходим к противоречию, известному как парадокс Рассела. Существует три способа избежать этого парадокса.
1. Ограничить используемые описания видом
A{xM | Q(x)},
где M – известное, заведомо существующее множество (универсум).
Для Y универсум не указан, а потому Y множеством не является.
2. Использовать типы.
Объекты имеют тип 0, множества имеют тип 1, множества множеств – тип 2 и т. д.
Y не имеет типа и множеством не является.
3. Задавать A(x) в виде вычислимой функции (алгоритма).
Способ вычисления значения XX не задан, а потому Y множеством не является.
В качестве центральных в теории множеств выступают понятия подмножества и надмножества.
☼ Множество A называется подмножеством множества B, если любой элемент множества A принадлежит и множеству B.
B в этом случае называется надмножеством множества A.
☼ Если множество B включает в себя A, что выражается AB,
но при этом AB, то A называется собственным подмножеством B.
Очевидно, что часть собственного подмножества данного множества всегда является собственным подмножеством этого множества.
Если требуется различать собственные и несобственные подмножества, то для обозначения включения собственных подмножеств используется знак , а для несобственных .
Два множества равны, если они являются подмножествами друг друга.
Применительно к введённым понятиям подмножества и надмножества действует следующая Теорема о верхней и нижней границах подмножества.
Если
BA,
то имеет место
inf B inf A, sup B sup A.
Для определения подмножества характерно использование следующих символов:
- символ, называемый квантором и означающий “любой”, “каков бы ни был”, “для всех”;
- символ следствия (импликации), означающий “влечёт за собой”.
При помощи этих двух символов определение подмножества можно сформулировать так:
x [xX xY],
что читается следующим образом: для любого x утверждение “x принадлежит X” влечёт за собой утверждение “x принадлежит Y”.
Отметим некоторые свойства подмножества, вытекающие из его определения:
XX (рефлексивность);
[XY и YZ] XZ (транзитивность).
Для любого множества M справедливо
M.
Естественно, что пустое множество не содержит элементов. Следовательно, при добавлении к M пустого множества мы фактически не добавляем ничего. Поэтому всегда считается, что любое множество M содержит в себе пустое в качестве подмножества.
☼ Совокупность всех подмножеств множества A называется его булеаном или множеством-степенью и обозначается 2A:
2A={B | BA}.
Множества удобно изображать графически. В конце XIX века английский учёный Джордж Венн усовершенствовал введённые Эйлером круги для иллюстрации множеств, добавив к изображению объёма рассматриваемого понятия X изображение объёма логически противоположного ему понятия НЕ X (X). Объём понятия X дополняет объём понятия X.
☼ Изображение множества в виде областей в прямоугольнике, представляющем универсальное множество, называется диаграммой Эйлера
|
