1. Элементы теории множеств Теоретические сведения

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

Множества будем обозначать заглавными буквами латинского алфавита; объекты, которые образуют множества, будем называть элементами множества и обозначать малыми буквами латинского алфавита. Если элемент x принадлежит множеству X, то этот факт записывается в виде , иначе . Как правило, считается, что все элементы множества различны. Множество с повторяющимися элементами называется мультимножеством.

Множество, содержащее конечное число элементов, называется конечным; в противном случае множество называется бесконечным. Количество элементов конечного множества называется мощностью и обозначается =n, если множество X содержит n элементов. Если множество не содержит ни одного элемента, то оно называется пустым и обозначается

Для произвольных множеств X и Y можно определить два типа отношений – отношение равенства и отношение включения.

Два множества считаются равными, если они состоят из одних и тех же элементов. Принято обозначение X=Y, если X и Y равны, и XY- иначе.

Если каждый элемент множества X является элементом множества Y, то говорят, что X включено в Y и обозначают :

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

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

Невключение подмножества X в множество Y обозначается

Заметим, что если X является подмножеством Y и наоборот, то X и Y состоят из одних и тех же элементов, поэтому

и

Если в рамках некоторого рассуждения рассматриваются подмножества некоторого множества, то оно называется универсальным, или универсумом и обозначается U [7].

Множество может быть задано различными способами [1, 2, 6]: перечислением элементов в скобках (для конечных множеств) или указанием их свойств, однозначно определяющих принадлежность элементов данному множеству, при этом используется запись

X={ обладает свойством P(x)}

(выражение в скобках читается: множество всех элементов x, которые обладают свойством P(x). Так, множество натуральных чисел N={1,2,…} может быть описано следующим образом:

N={ если целое то }.

Для получения новых множеств из уже существующих используют операции над множествами [1, 2, 6]. Рассмотрим основные из них.

Объединением множеств X и Y называется множество , все элементы которого являются элементами множества X или Y:

={x x или }.

Пересечением множеств X и Y называется множество , элементы которого являются элементами обоих множеств X и Y:

={x | x X и x Y}.

Очевидно, что выполняются включения

;

Дополнением множества X называется множество всех тех элементов x, которые не принадлежат множеству X:

={x | x U и xX}.

Разностью множеств X и Y называется множество X\Y всех тех элементов X, которые не принадлежат Y:

X\Y={x x и }=X .

Дополнение множества Х представляется с помощью операции разности следующим образом

=U\X.

Симметричной разностью множеств X и Y называется множество

.

Пример. Пусть на универсуме U={a, b, c, d, e, f, g} определены множества X={a, c, d, f} и Y={b, d, e, f}, тогда

XY={ a, b, c, d, e, f},

XY={d, f},

={b, e, g},

X\Y={a, c},

Y\X={b, e},

XY={a, b, c, e}.

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

Декартовым (прямым) произведением множеств X и Y называется множество упорядоченных пар вида

{(x,y) x и }.

Пример. Пусть X=

Тогда .

Две пары (x, y) и (u, v) считаются равными тогда и только тогда, когда x=u и y =v.

Для любых множеств X, Y, Z справедливы следующие тождества (основные свойства операций над множествами):

1. (коммутативность);

2.

(ассоциативность);

3.

(дистрибутивность);

4.

5.

6. (комплиментарность);

7 . (идемпотентность);

8.

(законы де Моргана);

9. (двойное дополнение);

10.

(законы поглощения).

Примеры решения задач

Задача 1.

Доказать A(BC) = (AB)(AC).

Решение. Чтобы доказать равенство двух множеств X = Y нужно доказать, что XY и XY. Докажем, что A(BC)  (AB)(AC). Для доказательства этого включения выберем произвольный элемент из множества A(BC) и покажем, что он принадлежит множеству (AB)(AC). Итак, пусть x A(BC). Тогда xA и xBC. Если xB, то xAB, а значит, x(AB)(AC). Если xC, то xAC, а значит, x(AB)(AC). Таким образом, A(BC) (AB)(AC). Теперь докажем, что (AB)(AC)A(BC). Пусть x(AB)(AC). Если xAB, то xA и xB, отсюда следует, что xA и xBC, т.е. x A(BC). Если xAC, то xA и xC. Отсюда следует, что xA и xBC, т.е. x A(BC). Итак, (AB)(AC)A(BC). Таким образом, получили, что A(BC)(AB)(AC) и (AB)(AC) A(BC), а это значит, что эти два множества равны.

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

Задача 2. Доказать закон де Моргана.

Доказательство проведем с помощью двух включений.

С одной стороны,

.

С другой стороны,

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

Задача 3.

Доказать тождество .

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

Задача 4. Упростить выражение

.

Решение.

1. Применив дистрибутивный закон, получим

2) Используя коммутативный закон, закон де Моргана и Закон двойного дополнения, получим

.

3) Применив дистрибутивный закон и закон де Моргана, получим

4) Применим закон получим

.