Основные понятия алгебры множеств

Рис. 2

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

P ={a, b, c, d, e}; Q ={b, d, a}; R ={a, c, f},

то можно легко установить, что Q

ÌP, но в то же время отношение RÌP для этих множеств неверно, так как элемент f из множества R не является элементом множества P.

Порядок перечисления элементов для множеств несущественен. Например, множества {b,d,a}; {a, b, d}; {d, a, b} – это по сути одно и то же множество. Если же порядок перечисления множеств является существенным, то в этом случае имеем дело не с множествами, а с последовательностями или с упорядоченными множествами (некоторые сведения о них приведены ниже). Математические свойства последовательностей существенно отличаются от математических свойств множеств.

Заметим, что несходство отношений принадлежности и включения можно иллюстрировать следующим примером. Допустим, aÎP, из чего следует, что a является элементом, а P – множеством. Можно ли в этом случае записать aÍP? Оказывается, нельзя, потому что отношение включения применимо только для двух множеств. Правильной в этом случае является запись {a}Í P, в которой слева записан не элемент, а одноэлементное множество.

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

Определение 1. Множества A и B равны, если справедливо как AÍB, так и BÍA.

Если множества связаны отношениями AÌB или AÍB, то в этом случае множество A называют подмножеством множества B. Среди всех возможных подмножеств произвольного множества A обязательно содержится также и само множество A. Другими словами, для любого множества A всегда справедливо AÍA.

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

Пустое множество включено в любое множество.

Для пояснения смысла этого предложения рассмотрим следующий пример. Пусть A – множество крокодилов. Ясно, что это множество может иметь какие-то подмножества. Например, множество C крокодилов, живущих в зоопарках. Тогда отношение между A и C можно записать как CÌA. Рассмотрим еще одно подмножество множества A: подмножество крокодилов, говорящих на русском языке. Ясно, что это пустое множество и, тем не менее, можем его считать подмножеством множества A. В математических рассуждениях, когда нам надо доказать, что данное множество X не существует (или существует), сводим доказательство существования к доказательству отношения X=Æ (или X¹Æ). Часто такой метод позволяет намного упростить доказательство.

Если множество задано перечислением элементов, то часто интерес представляет совокупность всех подмножеств этого множества. Например, для множества A={a, b, c} такая совокупность состоит из восьми подмножеств:

Æ, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.

Само множество А является подмножеством самого себя. Известно также простое соотношение, позволяющее сразу же узнать общее число всех возможных подмножеств множества, содержащего ровно N элементов. Оказывается, что для любого N такое число равно 2N. Например, для нашего множества A={a, b, c} число всех возможных подмножеств равно 23.

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

Для универсума нет общепринятых обозначений. Далее будем обозначать его символом U.

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

Определение 2. Дополнением множества A называется множество , содержащее все элементы универсума, которые не являются элементами множества A.

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

Пример 1. Пусть U={a, b, c, d} и P={a, c}. Тогда ={b, d}.

Определим еще две основные операции – пересечение и объединение множеств.

Определение 3. Пересечением множеств A и B называется множество C, все элементы которого являются одновременно элементами множеств A и B.

Операция пересечения множеств обозначается символом "Ç". Символически определение 3 можно записать как формулу

C = AÇB.

Например, пересечением множества всех студентов данного вуза и множества всех участников КВН, является множество студентов данного вуза, участвующих в КВН. Другой пример: пересечением множества всех чисел, делящихся на 2, и множества всех чисел, делящихся на 3, является множество всех чисел, делящихся на 6.

В логике операции пересечения соответствует логическая связка "И" (обозначается как Ù или &). Если речь идет об объектах со свойствами P или Q, то логическая формула PÙQ означает, что речь идет только об объектах, которым присущи оба этих свойства. Если, допустим, свойствам P и Q соответствуют некоторые множества SP и SQ, то пересечение этих множеств SPÇSQ, будет состоять из элементов, каждому из которых одновременно присущи свойства P и Q

Пример 2. Пусть A={a, b, c, d} и P={a, c, f}. Тогда AÇP = {a, c}.

Определение 4. Объединением множеств A и B называется множество C, все элементы которого являются элементами по крайней мере одного из этих множеств.

Операция объединения множеств обозначается символом "È". Символически определение 4 можно записать как формулу

 Скачать реферат