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

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

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

Множество – основное математическое понятие. В обычной жизни его смысл заложен в словах: «совокупность», «класс», «стая», «табун», «стадо» и т.п. Теория множеств как математическая дисциплина создана немецким математиком Г. Кантором, которая получила признание в качестве самостоятельного раздела математики к 1890 году, когда были получены ее приложения в анализе и геометрии. Главная заслуга Георга Кантора заключается в установлении того факта, что понятие бесконечность является не абстракцией, придуманной философами, а реальностью; бесконечные совокупности предметов существуют наравне с конечными.

Множество относится к математическим объектам, для которых нет строго определения. Мы можем лишь в какой-то мере дать описание основных его свойств.

Кантор описывает множество следующим образом:

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

Мы под множеством будем понимать следующее:

Определение.

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

Для того, чтобы указать, что х – элемент множества А, записывают и читают «х принадлежит А». Чтобы указать, что х не является элементом множества А, записывают и читают «х не принадлежит множеству А».

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

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

Рисунок 1. Способы задания множеств

Множества можно разделить на конечные и бесконечные.

Пример 1.

· Конечные множества: множество букв алфавита, множество студентов 2 курса специальности «Юриспруденция» и т.д.

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

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

Пример 2.

Ø = , поскольку среди действительных чисел нет решения данного уравнения.

Определение.

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

Пример 3.

Множество , , тогда , т.е. .

Основные свойства включений: 1) Каждое множество есть подмножество самого себя: . 2) Если , , то . 3) Пустое множество есть подмножество любого множества: Ø . 4) Каждое не пустое множество Ø имеет по крайней мере два различных подмножества: само А и пустое множество Ø. 5) Каждый элемент множества А определяет некоторое подмножество множества А: если , то .

Определение.

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

Если множества не равны, то пишут .

Пример 4.

Множества и , где и удовлетворяют уравнению , т.е. , значит .

Определение.

Множество всех подмножеств множества А называется множеством-степенью множества А.

Пример 5.

Пусть , тогда { Ø}, т.е. если множество состоит из двух элементов, то множество-степень состоит из четырех подмножеств.

Пусть , тогда { {4}, {2,3}, {3,4}, {2,4}, Ø}, т.е. если множество состоит из трех элементов, то множество-степень состоит из восьми подмножеств.

Таким образом, если конечное множество А состоит из n элементов, то число всех его подмножеств равно .

Определение.

Множество U называется универсальным для системы множеств А, B, C, …, если каждое множество системы является подмножеством U, т.е. , , , …. .

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

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

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

На Диаграммах Эйлера-Венна универсальное множество U изображается в виде прямоугольника, его подмножества – в виде кругов (реже прямоугольников), а элементы принадлежащие данным подмножествам в виде точек (см. Рисунок 2).

Рисунок 2. Пример диаграммы Эйлера-Венна

Рассмотрим операции над множествами, некоторые из которых (объединение и пересечение) аналогичны операциям сложения и умножения целых чисел.

Операции пересечение и объединение множеств выполняются для любой пары множеств. Операция дополнение имеет смысл для тех множеств, когда второе является подмножеством первого.

Следует провести аналогию между логическими операциями и операциями над множествами.

Высказывание	Множество
(конъюнкция)	Пересечение
(дизъюнкция)	Объединение
(импликация)	Разность
(отрицание)	( дополнение)
тавтология	(универсальное множество)
противоречие	Ø (пустое множество)

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

¢ Основные законы над множествами

Законы: 1) Закон идемпотентности: a) б) 2) Закон коммутативности: a) б) 3) Закон ассоциативности: a) б) 4) Закон дистрибутивности: a) б) 5) Закон поглощения: a) б) 6) Закон де Моргана: a) б) 7) Закон двойного отрицания: 8) Ø 9) Законы для объединения, пересечения и дополнения: а) ; б) ; в) Ø = A; г) Ø = Ø; д) ; е) Ø 10) 11) Законы для разностей: а) ; б) Ø; в) Ø = A; г) Ø Ø; д) Ø

Доказательство каждого из перечисленных законов основано на определении равенства множеств и определений операций над множествами. Чтобы доказать некоторое тождество A = B, нужно доказать, что, во-первых, если xÎ А, то xÎВ и, во-вторых, если xÎВ, то xÎ А. Докажем один из этих законов: .

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

И действительно это так, проиллюстрируем это на диаграммах Эйлера-Венна (см. Рисунок 3).

Рисунок 3. Пример иллюстрации равенства множеств на диаграммах Эйлера-Венна

Пример 6.

Пусть А, В и С произвольные множества. Докажите, что (закон дистрибутивности).

Пусть

,т.е. .

Пусть

, т.е. .

Так как и , значит .

Основные законы алгебры множеств можно использовать для доказательства других тождеств.

Пример 7.

Докажите равенство .

Решение.

, что и требовалось доказать.

¢ Формула включений и исключений

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

Пусть дано конечное не пустое множество А, т.е. Ø, состоящее из n элементов. Закрепим за каждым элементом множества А соответствующий номер 1, 2, 3, …, n. Тогда элементы множества А предстанут в занумерованном виде: , где номер последнего элемента и означает число элементов множества А. Значит число n, соответствующее количеству элементов множества , будет количественной характеристикой данного множества. Число элементов конечного множества А будем обозначать . Число элементов пустого множества Ø равно нулю, т.е. .

Пусть существуют множества А и В, количество элементов которых и , тогда общее количество элементов А и В вычисляет формула, называемая формулой включений и исключений[2] (ее можно обобщить на три и более множества), которая позволяет решать многие задачи теории множеств (см. Рисунок 4).

Рисунок 4. Формула включений и исключений.

Пример 7.

Из 16 студентов группы, изучающих английский или китайский язык, 11 – изучают китайский. Сколько студентов изучают оба языка, если английский язык изучают 9 из них?