1.5. Предметные операции на множествах. Формула множества

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

Определение. Объединением множеств А и В называют множество С, содержащее элементы, входящие хотя бы в одно из них. Обозначают как С = АВ ={x  (xA) или (xB)}.

Пересечением множеств А и В называют множество С, содержащее элементы, входящие одновременно в А и В. Обозначают: С = АВ ={x  (xA) и (xB)}.

Разностью множеств А и В называют множество С, содержащее все элементы из множества А, не входящие в В. Обозначают: С = А\В ={x  (xA), но (xB)}.

Симметрической разностью множеств А и В называют множество С, содержащее элементы из А\В и из В\А. Обозначают: С = АВ =(А\В)  (В\А) .

Рассмотрим множества, состоящие из объектов некоторого вида, содержащихся в заданном универсальном множестве U. Дополнением множества А называют множество С, содержащее элементы из U, не входящие в А. Обозначают дополнение: С=А либо С =  А.

Дополнение любого множества можно представить как результат его вычитания из универсального:  А = U \ А.

Результатом выполнения рассмотренных предметных операций (, , \, , ) всегда является множество.

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

1) любое выражение вида А, В, С,…, где А, В, С,…— обозначения простых множеств, заданных непосредственным определением;

2) любое выражение вида АВ; АВ; А\В; АВ;  А, где А, В — формулы множеств.

Графически множества изображают в виде плоских фигур (кругов, овалов и т.д.). Такие изображения называют диаграммами Венна. На диаграммах а) — д) рис.1.1 показаны результаты выполнения введенных выше операций объединения, пересечения, разности, симметрической разности и дополнения.

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

Рис.1.1

Пример 1.

1. АВС — формула множества, которую с учетом введенного старшинства операций следует понимать как А(ВС).

2. С  А — запись не является формулой множества, так как в ней одноместная операция дополнения соединяет два множества.

Для наиболее полной характеристики содержательного смысла формулы составного множества F, в которую входят простые множества А₁, А₂,…, А_n, рассмотрим множество {R} всех возможных пересечений простых множеств либо их дополнений {А₁ ^1  А₂^2 … А_n ^n}, где _{i =} 0 или 1, А_i¹ = А_i, А_i⁰= А_i. Представляя вектор индексов (₁,₂,…,_n) в виде записи двоичного числа N в промежутке от 0 до 2ⁿ–1, упорядочиваем по возрастанию этих чисел все элементы {R}. Назовем их элементарными пересечениями. Эти пересечения для двух и трех простых круговых множеств даны в виде диаграмм Венна на рис. 1.2.

Рис.1.2

Диаграммы Венна для заданного числа исходных множеств, на которых показаны все их возможные элементарные пересечения, назовем полными диаграммами пересечений. Такие диаграммы с круговыми изображениями исходных множеств могут быть построены только для двух и трех множеств (рис.1.2). При четырех и выше необходимо использовать вместо кругов более сложные фигуры.

Таблицы с упорядоченными по возрастанию чисел N элементарными пересечениями для двух и трех простых множеств имеют вид:

N	А2	А1
0	0	0
1	0	1
2	1	0
3	1	1

N	А3	А2	А1
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

Любой формуле составного множества F(А₁, А₂,…, А_n) можно взаимно однозначно поставить в соответствие вектор, отражающий вхождение в него элементарных пересечений {R}. Назовем его вектором включений. Если формула имеет сложный вид, построение данного вектора можно проводить поэтапно. При объединении двух множеств в итоговом векторе включений учитываются единицы из обоих векторов, при пересечении остаются только единицы, входящие одновременно в оба вектора. При применении отрицания в векторе происходит замена 0 на 1 и 1 на 0. При вычитании А\В в итоговый вектор включают 1 только в том случае, когда в векторе А стоит 1, а векторе В — 0.

Пример 2. Построить векторы включений для составных множеств, заданных на простых множествах А и В следующими формулами: 1) F₁ =  (АВ), 2) F₂ = (АВ), 3) F₃ = АВ  (АВ). Результаты привести в таблице.

Решение. При определении векторов включений используем старшинство операций. Вектор для F₁ строим поэтапно, используя объединение АВ. Вектор включений для F₂ находим с использованием формулы АВ =( А\В)  (В\А) . В случае F₃ рассматриваем предварительно векторы формул АВ, АВ и  (АВ).

N	А	В	А В	F1	А В	F2	А В	 (А В)	F3
0	0	0	0	1	0	1	0	1	1
1	0	1	1	0	1	0	0	0	0
2	1	0	1	0	1	0	0	0	0
3	1	1	1	0	0	1	1	0	1

Данную конструкцию назовем таблицей пересечений.

ЗАДАЧИ

1. Определить, будут ли следующие выражения формулами множеств:

а) АС\; б)  А   В; в)  ( АC); г)  С?

2. Указать очередность выполнения операций в формулах:

а)  А   ВС; б)  А   С; в) АВСD.

3. Построить таблицы пересечений и изобразить все элементарные пересечения на полных диаграммах пересечений для составных множеств, заданных формулами:

а) (АВ)\С; б) (АВС) ; в) А (В  С) ; г) (АВ)  (А\  С) ; д) А В С (В С).

4. Привести примеры непустых исходных множеств А, В, С, при которых будет выполняться равенство составных множеств:

а) АВ и АВ; б) А \ ( ВС) и А\В.