Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Теория
Основные понятия и обозначения
Понятие множества является одним из наиболее общих математических понятий и как любое другое исходное понятие математической теории оно не определяется точно. Поэтому вместо строгого определения понятия «множество» обычно принимается некоторое основное положение о множестве и его элементах, дается описательное определение, содержание и смысл которого раскрываются при изучении теории множеств. Рассматривая основное положение о множестве и его элементах, чаще всего пользуются определением, предложенным основателем теории множеств немецким математиком Георгом Кантором, который определил множество как «объединение в одно целое объектов, хорошо различимых нашей интуицией и мыслью».
Математическое понятие «множество» связано с абстракцией. Сущность этой абстракции множества заключается в том, что действительно существующие связи объединяемых объектов между собой и с другими объектами игнорируются, а вместо них объединяемым объектам приписываются новые связи друг с другом, выражающие их принадлежность множеству. При этом считается, что два объекта, ничем не отличающиеся друг от друга, являются одним и тем же объектом.
Определение. Рассмотрим множество как совокупность объектов произвольной природы, которые удовлетворяют двум свойствам:
Определение. Объекты, которые образуют множество, называются элементами (членами) этого множества.
Пример.
- множество натуральных чисел с нулем;
- множество натуральных чисел;
- множество всех действительных чисел;
- множество всех решений уравнения , то есть ;
A - множество прямых, проходящих через заданную точку.
Пример. В качестве признака принадлежности объекта некоторой совокупности (множеству) могут быть следующие свойства (признаки): «быть цифрой», «быть буквой», «быть числом», «быть словом», «быть служебным символом», «быть идентификатором данного», «быть кодом операции» и т.п.
Для обозначения конкретных множеств в общем виде используются различные заглавные буквы или заглавные буквы с индексами, например, . Для обозначения элементов множеств в общем виде используются различные строчные буквы или строчные буквы с индексами .
Утверждение, что множество состоит из различных элементов (и только из этих элементов), условно записывается , т.е. множество обозначается скобками {…}, внутри которых либо просто перечисляются элементы, либо описываются их свойства.
Пример. ; .
Элементами множеств могут быть другие множества, тогда эти элементы обозначаются заглавными буквами.
Пример. , где , , .
. Множество состоит из трех элементов: .
Определение. Множество, элементами которого являются множества, обычно называются классом или семейством.
Семейства множеств обычно обозначают прописными «рукописными» буквами латинского алфавита, чтобы отличить их от множеств, не содержащих множеств в качестве элементов.
Если есть один из объектов множества , то говорим, что есть элемент , или принадлежит . Принадлежность элемента множеству записывается как . Если не является элементом , это записывается как . Символ называется символом принадлежности.
Пример. , но .
Поскольку множество однозначно определяется только элементами, которые оно содержит, порядок перечисления элементов между фигурными скобками произвольный, т.е. , но многократная запись одного и того же элемента – не желательна, т. е. .
Определение. При многократной записи одного и того же элемента множество называют мультимножеством и применяют особые методы анализа.
С точки зрения теории множеств, множество и его мультимножество – это один и тот же объект, и они могут между собой не различаться. Однако часто, особенно когда речь идет о представлении множества в памяти вычислительной машины, возникает потребность отличать мультимножество от множества.
Определение. Множество, в котором важны не только его элементы, но и порядок их следования во множестве, называется упорядоченным.
Определение. Конечное множество называется упорядоченным, если его элементы пронумерованы.
Упорядоченное множество обозначают, как правило, либо круглыми, либо треугольными скобками.
Определение. Кортеж (вектор) это упорядоченный набор элементов . Элементы, образующие кортеж, называются координатами или компонентами. Координаты нумеруются слева направо.
Определение. Число координат кортежа (вектора) называется длиной или размерностью кортежа (вектора).
Пример.
упорядоченное множество, состоящее из 4-х элементов (кортеж длины 4);
, где
Пример. Пусть множество географических координат долготы и широты . Если поменять местами долготу и широту, то в результате можно попасть в другую точку света.
Конечные, бесконечные, счетные множества
Множество может содержать любое число элементов – конечное или бесконечное.
Определение. Если множество содержит конечное число элементов, его называют конечным, в противном случае множество называется бесконечным.
Пример. Множество действительных решений квадратичного неравенства конечно, если , и бесконечно, если .
Примеры конечных множеств:
Примеры бесконечных множеств:
Определение. Множество называется счетным, если его объекты можно пересчитывать (каждому объекту множества присвоить натуральное число, которое было бы номером лишь одного элемента множества).
Пример. Множество цифр счетно и конечно, а множество целых чисел – счетно, но не конечно.
Пустое и универсальное множества
В теории множеств используются понятия «пустого множества» и «универсального множества».
Определение. Множество, не содержащее ни одного элемента, называется пустым и обозначается специальным символом .
Пример. Пусть – множество действительных решений квадратного уравнения . Множество конечно, Если дискриминант отрицателен, множество пусто.
Пример. Множество выигрышей в следующем тираже спортлото на купленные билеты может оказаться пустым.
Пример. Неизвестно, является ли пустым или нет множество всех решений в целых числах уравнения .
Пустое множество введено в математике для удобства и единообразия языка. Роль пустого множества аналогична роли числа нуль. Если исследуется множество объектов, обладающих каким-либо свойством, и впоследствии выясняется, что таких объектов не существует, то гораздо удобнее сказать, что исследуемое множество пусто, чем объявлять его несуществующим. Понятие пустого множества может быть использовано для определения заведомо несуществующей совокупности элементов. Пустое множество будем условно относить к конечным счетным множествам.
Пример. Множество действительных корней уравнения является пустым множеством.
Введем понятие универсального множества.
Определение. Универсальное множество (или универсум), которое обозначают символом , есть множество, содержащее все элементы, принимающие участие в решении определенного класса задач.
Обычно уже в самом определении конкретного множества явно или неявно ограничивается совокупность допустимых объектов, однако данную совокупность удобнее зафиксировать явным образом, определив её в качестве универсума в рамках решаемой задачи.
Примеры. Так, множество слонов следует искать среди млекопитающихся, а не среди рыб.
Если речь идет о множестве чисел, делящихся на 3, то ясно, что оно является множеством целых чисел.
В теории чисел универсум обычно совпадает с множеством всех целых или натуральных чисел.
В математическом анализе универсум может быть множеством всех действительных чисел или множеством всех точек -мерного пространства.
Универсумом зоологии является мир животных; универсумом лингвистики – слова и т.д.
Мощность множества
При сравнении множеств по числу содержащихся в них элементов возникает понятие мощности множества.
Определение. Мощность конечного счётного множества есть число его элементов , которое обозначают как .
Пример. Мощность множества цифр десятичной системы счисления равна 10.
Мощность множества строчных букв латинского алфавита – 26.
Мощность пустого множества равна нулю (), а мощность множества равна 1, т.е. .
Определение. Если , то множества и называются равномощными.
Способы задания множеств
Чтобы задать множество, нужно указать, какие элементы ему принадлежат.
Существует несколько основных способов задания (описания) множеств:
Рассмотрим каждый из перечисленных способов.
Словесное (вербальное) описание элементов множеств и их характеристик используется чаще всего для пояснения и осуществления доказательств основных положений данной теории при решении конкретных задач (применяется в разговорной речи, оформлении различного рода научной и технической документации и т.п.).
Пример. Спецификация задает множество деталей изделия.
Каталог – множество книг в библиотеке.
Простое перечисление элементов множества (неупорядоченного) между фигурными скобками используется, в основном, для описания конечных множеств.
Пример.
есть множество, содержащее натуральные числа 1, 2, 3 и 4.
есть множество продуктов питания.
Множество гласных букв можно представить как .
– множество решений уравнения .
– множество остатков при делении целых чисел на 7.
Иногда перечислением элементов задают и бесконечное множество. Это делают в тех случаях, когда ясен алгоритм последовательного порождения элементов.
Пример.
Множество положительных целых чисел можно обозначить как .
Множество первых n положительных целых чисел обозначается , где точками показано продолжение перечисления элементов.
описывает множество квадратов всех положительных чисел, которые меньше или равны .
описывает множество кубов всех положительных чисел.
Очевидно, что перечисление элементов удобно (целесообразно) только в том случае, когда множество элементов имеет их ограниченное количество или произвольный элемент характеризуется свойством, которое легко описать.
Если же множество имеет хотя и конечное, однако большое количество элементов, такое задание множества достаточно громоздко, а в случае бесконечного множества его применение вообще невозможно.
Пример. Используя способы перечисления не так легко описать, например, множество граждан Украины и совершенно немыслимо описать множество действительных чисел.
В общем случае множества можно задавать (описывать) по так называемой схеме свертывания. Схема свертывания может быть реализована при помощи:
При заданном характеристическом (определяющем) свойстве и заданном классе элементов (универсальном множестве для решаемой задачи) множество определяется как множество, которое содержит все элементы из , обладающие свойством . Для определения по схеме свертывания используется следующая запись .
Пример. Множество четных чисел можно определить как или как , где через обозначено множество целых чисел.
– множество граждан Украины.
– множество слонов.
Свойства, которыми должны обладать элементы формируемого множества , можно описать характеристической функцией (характеристическим предикатом) . Обычно – это высказывание, в котором что-то утверждается об , или некоторая функция переменной . Тогда множество можно представить как . Если класс указан явно, то в этом случае используется запись . Если при замене на высказывание становится истинным или функция в заданной области определения удовлетворяется, то есть элемент данного множества. Таким образом , если истинно.
Пример.
а) – множество чисел, квадрат которых равен двум;
б) – множество чисел, квадрат которых плюс единица больше нуля.
Множество может быть также задано при помощи порождающей процедуры (рекурсивно) .
Определение.
Порождающая процедура – это процедура, которая, будучи запущенной, порождает некоторые объекты, являющиеся элементами определенного множества.
Пример. Множество нечетных чисел можно задать порождающей процедурой .
Множество можно задать рекурсивной процедурой .
При задании множеств могут возникать ошибки и противоречия, поэтому к описанию свойств множеств и их элементов естественно предъявлять требование точности и недвусмысленности. Множество задано корректно, если для любого элемента можно определить, принадлежит он множеству или нет.
Пример. Определение множества как множества, содержащего любые пять натуральных чисел, не является корректным, поскольку невозможно определить точно элементы .
Множество всех простых чисел определено корректно. Для любого натурального числа можно проверить, является ли оно простым, хотя практически на это может потребоваться очень много времени.
Пример. Множество всех хороших фильмов 2011 года разные люди зададут разными списками (может быть пустыми). Сами критерии, по которым производится отбор, при этом будут различны. Такое множество нельзя считать строго заданным.
Неограниченное применение схемы свертывания, некорректность задания множества, свободное использование понятий интуитивного теоретико-множественного универсума иногда ведет к противоречиям, которые называются логическими парадоксами (парадокс Рассела, парадокс Кантора, парадокс Банаха-Тарского) и изучаются в математической логике.
Пример.
Можно получить «множество всех множеств» . Если считать множеством, то получаем .
Множество и подмножество
Определение. Множество , все элементы которого принадлежат и множеству , называется подмножеством (частью) множества . При этом говорят, что содержит или покрывает .
Это отношение между множествами называют включением и обозначают символом Í, т.е. ( включено в ) или ( включает ).
Если не является подмножеством , это записывается как . Таким образом, , если существует элемент , не принадлежащий .
Пример:
а) множество конденсаторов электронной цепи является подмножеством всех её компонентов;
б) множество положительных чисел – это подмножество множества действительных чисел.
в) ;
г) .
Пример. Книга из множества книг в шкафу может рассматриваться как множество страниц. Следует обратить внимание на то, что речь идет об элементах множества, а не о подмножествах, т.к. никакая совокупность страниц не может рассматриваться как подмножество множества книг.
Множества и равны , если их элементы совпадают. Иначе говоря, тогда и только тогда, когда и .
Пример.
Если есть множество , а есть множество , тогда и – равные множества.
Определение.
Если и , то часто называется собственным, строгим или истинным подмножеством .Записывается данное отношение как , где знак строгого включения.
Пример. Пусть ; , тогда ясно, что и – собственное (истинное) подмножество .
В частности, каждое множество есть подмножество самого себя. Принято также считать, что пустое множество является подмножеством любого множества. Поэтому, любое непустое множество имеет, по крайней мере, два различных подмножества: само и пустое множество .
Эти подмножества называются несобственными, а все другие подмножества называются собственными. Если требуется различать собственные и несобственные подмножества, то для обозначения включения собственных подмножеств используется знак (), а для несобственных – ().
Конечно, собственные подмножества образуются всевозможными сочетаниями по одному, два, три и т.д. элементов данного множества.
Пример: ; ; ; ; ; ; . , где .
Определение. Множество всех подмножеств множества , или булеан множества , обозначаемый (или ), есть множество, состоящее из всех подмножеств множества . Множество называется также множеством-степенью.
Пример. Так, для трёхэлементного множества булеан имеет вид .
В случае конечного множества , состоящего из n элементов, множество подмножеств содержит элементов, т.е. .
Пустое множество имеет только одно подмножество – само пустое множество, поэтому .
Геометрическая интерпретация множеств
Для наглядного представления отношений между подмножествами универсального множества используются диаграммы Венна и круги Эйлера.
Построение диаграммы Венна заключается в разбиении плоскости на ячеек с помощью фигур, каждая из которых представляет на диаграмме отдельное множество, а – число изображаемых множеств.
Плоскость, на которой изображаются фигуры, представляет универсальное множество. Чаще всего универсальное множество при этом изображают в виде прямоугольника, а его подмножества изображают в виде кругов (кругов Эйлера), находящихся внутри прямоугольника.
С помощью диаграмм Эйлера-Венна можно графически показать, принадлежит ли некоторый элемент рассматриваемым множествам или нет, однако реальные отношения включения, установленные между множествами, отразить нельзя. Можно рассматривать отношения включения только в общем случае.
Пример.
На рис. 1.1 элемент принадлежит и не принадлежит ; принадлежит и ; принадлежит и не принадлежит ; не принадлежит ни , ни . Любой элемент принадлежит универсальному множеству .
Рисунок 1.1 – Диаграмма Венна для двух множеств и
Индивидуальные отношения между заданными множествами изображают с помощью кругов Эйлера. В этом случае множества, не имеющие общих элементов, изображают фигурами (чаще кругами), которые не пересекаются (рис. 1.2).
Рисунок 1.2 – Изображение множеств, не имеющих общих элементов, с помощью кругов Эйлера
Множества, имеющие общие элементы, изображают пересекающимися фигурами (рис. 1.3).
Рисунок 1.3 – Изображение множеств, имеющих общие элементы, с помощью кругов Эйлера
Отношение включения на множествах изображают, располагая одну фигуру вложенной в другую (рис. 1.4).
Рисунок 1.4 – Изображение отношения включения на множествах с помощью кругов Эйлера
Операции на множествах
В теории множеств определяются способы конструирования новых множеств из уже имеющихся при помощи операций над множествами. К таким основным (базовым) операциям на множествах относятся следующие операции: объединение, пересечение, разность, дополнение.
Рассмотрим операции на множествах.
Пусть имеются два множества и .
Определение. Объединением (суммой) множеств и называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств или . Объединение множеств и обозначается . Данное определение можно записать .
Пример:
а) если , а , тогда . Объединение образовано из и путем соединения вместе элементов и .
б) если , , то .
Аналогично определяется объединение произвольной (в том числе бесконечной) совокупности множеств. Если совокупность содержит небольшое количество множеств, то объединение данных множеств описывается явно, т.е. и т.д.
В общем случае используется обозначение , которое читается так: «объединение всех множеств , принадлежащих совокупности».
Если же все множества совокупности занумерованы индексами, то используются другие варианты обозначений:
а) - для случая, когда ;
б) - для случая, когда – бесконечная совокупность и её множества занумерованы подряд натуральными числами;
в) - для случая, когда набор индексов множеств задан множеством .
Определение. Пересечением множеств и называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и , и . Пересечение множеств и обозначается .
Сформулированное определение можно записать как . Если , то и – непересекающиеся множества.
Пример:
1. Если и , тогда .
2. Если и
,
тогда .
Аналогично определяется пересечение произвольной (в том числе бесконечной) совокупности множеств. Обозначение для пересечения системы множеств аналогичны приведенным выше обозначениям для объединения.
Определение. Система множеств, в которой все попарные пересечения множеств пусты, называется разбиением множества всех элементов этих множеств, а множества такой системы называются классами или блоками разбиения. Всякий элемент множества входит только в один класс разбиения.
Пример:
Множество всех групп направления (потока) «Компьютерные науки» является разбиением множества всех студентов, поступивших в университет на направление «Компьютерные науки». Классы этого направления – группы. Всякий студент может входить только в одну группу.
Определение. Разность и (обозначается или ) - это множество, состоящее из тех и только тех элементов, которые принадлежат и не принадлежат , т.е. .
Пример: ; ; тогда , .
Определение. Если , то множество называется дополнением (абсолютным дополнением, отрицанием) множества .
Дополнение множества , обозначаемое (читается «не »), – это множество элементов универсума, которые не принадлежат , следовательно, . Дополнение определяется отрицанием свойства , с помощью которого определяется .
Пример:
Если – множество положительных целых чисел, а – множество всех положительных четных чисел, то – множество всех положительных нечетных чисел.
Определение. Дизъюнктивная сумма (симметрическая разность) – это множество, состоящее из всех элементов , не принадлежащих , и всех элементов , не принадлежащих , и не содержащее никаких других элементов, т.е. .
Симметрическая разность, обозначаемая как , либо , либо получается объединением элементов множеств за исключением тех, которые встречаются дважды.
Пример: ; ; .
Еще одной часто используемой операцией над множествами является декартово произведение. Обозначение и суть данной операции будут рассмотрены в разделе, связанном с описанием отношений.
Введенные операции называются теоретико-множественными операциями.
Все данные операции на множествах можно проиллюстрировать с помощью диаграмм Эйлера-Венна (рис. 1.5), в которых круги представляют соответствующие множества, участвующие в операциях (например, множество ), а заштрихованная часть плоскости является результатом выполнения операций (например, , , , , ).
а) б)
в) г)
д) е)
Рисунок 1.5 - Применение диаграмм Эйлера-Венна для иллюстрации операций на множествах
Общее определение алгебры
Алгебра в широком понимании может быть определена как наука (учение) о системах объектов той или иной природы, в которых установлены алгебраические операции. Для современной алгебры характерно то, что в центре внимания оказываются свойства операций, а не объектов, над которыми производятся эти операции. Алгебра классифицирует системы с заданными на них алгебраическими операциями по их свойствам и изучает различные задачи, естественно возникающие в этих системах.
Введем формализованное понятие алгебры.
Определение. Множество вместе с заданной на нем совокупностью операций , т.е. система , называется алгеброй. Множество – это основное, или несущее, множество (или просто носитель) алгебры. называется сигнатурой и представляет собой множество операций с элементами множества . Функция типа: называется -арной операцией. Вектор арностей операций алгебры называется её типом.
Определение. Операция, заданная на некотором множестве, называется бинарной, если она действует на два элемента этого множества и её результатом является элемент этого же множества.
Определение. Операция, заданная на некотором множестве, называется унарной, если она действует на один элемент множества и её результатом является элемент этого же множества.
Нульарные операции – это фиксированные элементы множества , называются также выделенными элементами, иногда нулями.
Определение. Множество называется замкнутым относительно -арной операции на , если , т.е. если значения на аргументах из принадлежат . Если замкнуто относительно всех операций алгебры , то система называется подалгеброй (при этом рассматриваются как операции на ).
Примеры алгебр:
1. Алгебра называется полем действительных чисел. Несущее множество – множество действительных чисел. Операции + и – бинарные операции, поэтому тип этой алгебры . Подалгеброй этой алгебры является, например, поле рациональных чисел.
2. Пусть задано множество . Множество всех его подмножеств является булеаном и обозначается . Алгебра называется булевой алгеброй множеств над , её тип . Элементами несущего множества этой алгебры являются множества (подмножества ). Для любого является подалгеброй . Например, если , то основное множество алгебры содержит 16 элементов; алгебра – подалгебра ; её основное множество содержит четыре элемента. Операции являются бинарными, а операция отрицания является унарной.
Понятие алгебры множеств
Алгебра множеств представляет собой теоретико-множественный аналог обычной алгебры действительных чисел и основана на свойствах операций над множествами.
Определение. Алгебра множеств – непустая совокупность подмножеств некоторого множества , замкнутая относительно теоретико-множественных операций (объединения, пересечения, разности, дополнения).
Для того чтобы некоторый класс подмножеств множества был алгеброй множеств, достаточно (и необходимо), чтобы он был замкнут относительно образования объединений и дополнений.
Аксиомы алгебры множеств
Операции над множествами, как и операции над числами, обладают некоторыми свойствами. Эти свойства выражаются совокупностью формул и тождеств, справедливых независимо от конкретного содержания входящих в них множеств. Данные тождества основаны на следующих аксиомах (законах) алгебры множеств, где рассматриваются как произвольные подмножества универсального множества :
1. Коммутативные законы
,
.
2. Ассоциативные законы
,
.
3. Дистрибутивные законы
,
.
4. Свойства пустого и универсального множеств
, ,
, .
, .
5. Законы идемпотентности (самопоглощения)
,
.
6. Закон инволюции
.
7. Закон противоречия
.
8. Закон исключенного третьего
.
9. Законы элиминации (поглощения)
.
.
10.Законы де Моргана
,
.
Свойствами дополнения, разности и равенства также являются:
11. Если .
12. .
13. .
В справедливости перечисленных выше свойств можно убедиться различными способами:
Принцип двойственности
Практически все рассмотренные тождества (законы алгебры множеств) представлены парами двойственных (дуальных) соотношений, одно из которых получается заменой в другом следующих символов: на и на , а также на и на .
Определение. Соответствующие пары символов , и , называются двойственными (дуальными) символами.
При замене в любом законе входящих в него символов дуальными получим новое предложение, которое также является законом. Данное утверждение представляет собой принцип двойственности или дуальности. Законы 11 и 12 не изменяются при замене символов дуальными, поэтому их называют самодвойственными.
Расширяя принцип дуальности на выражения, в которые входит символ включения, необходимо при переходе к дуальному выражению все знаки заменить на и обратно.
Преобразования формул алгебры множеств
Пользуясь основными тождествами (законами) можно упрощать или преобразовывать к удобному виду различные сложные выражения, содержащие множества, аналогично тому, как проводится упрощение выражений в элементарной алгебре. Для выполнения подобных преобразований применяется следующая приоритетность операций относительно друг друга: , , , .
Такие преобразования осуществляются последовательным применением соответствующих свойств операций над множествами.
Пример. Соотношение доказывается следующими преобразованиями с использованием рассмотренных законов
.
Пример. Упростить выражение .
Для упрощения используем законы алгебры множеств.
=.
Важно отметить, что любое тождество алгебры множеств выводимо из первых четырех свойств, которые в свою очередь доказываются только в терминах отношения принадлежности. Это можно рассматривать как иллюстрацию аксиоматического подхода к алгебре множеств.