Алгоритмы выполнения теоретико-множественных операций

В этом разделе подробно рассмотрена «технология» (точнее, алгоритмы) выполнения вве-дённых в разделе 2 базовых теоретико-множественных операций для конечных множеств.

Пример 5. Дополнение. Пусть U ={1, 2, 3, 4, 5, 6, 9}, A = {2, 5, 4}. Сделаем следующее.

1. Выпишем подряд все элементы U: 1, 2, 3, 4, 5, 6, 9.

2. Подчеркнём в этом списке все элементы из A; получим 1, 2, 3, 4, 5, 6, 9.

3. Удалим из списка все подчёркнутые элементы; останутся 1, 3, 6, 9.

4. Положим A' = {1, 3, 6, 9} ■

Пример 6. Объединение. Пусть A = { a, f, g, r }, B = { b, d, f, r, t }. Сделаем следующее.

1. Выпишем подряд все элементы B: b, d, f, r, t.

2. Подчеркнём в этом списке все элементы, содержащиеся в A; получим b, d, f, r, t.

3. Удалим из списка все подчёркнутые элементы; останутся b, d, t.

4. Добавим оставшиеся элементы b, d, t к списку A; получим a, f, g, r, b, d, t.

5. Положим A B = { a, f, g, r, b, d, t } ■

Пример 7. Пересечение. Пусть A = { a, f, g, r }, B = { b, d, f, r, t }. Сделаем следующее.

1. Выпишем подряд все элементы A: a, f, g, r.

2. Подчеркнём в этом списке все элементы, не содержащиеся в B; получим a, f, g, r.

3. Удалим из списка все подчёркнутые элементы; останутся f, r.

4. Положим A B = { f, r } ■

Пример 8. Разность. Пусть A = { a, f, g, r }, B = { b, d, f, r, t }. Сделаем следующее.

1. Выпишем подряд все элементы A: a, f, g, r.

2. Подчеркнём в этом списке все элементы, содержащиеся в B; получим a, f, g, r.

3. Удалим из списка все подчёркнутые элементы; останутся a, g.

4. Положим A B = { a, g } ■

Пример 9. Симметрическая разность. Пусть A = { a, f, g, r }, B = { b, d, f, r, t }. Сделаем следующее.

1. Найдём алгоритмом, описанным в примере 8, разность A B. Получим A B = { a, g }.

2. Найдём алгоритмом, описанным в примере 8, разность B A. Получим B A = { b, d, t }.

3. Найдём алгоритмом, описанным в примере 6, объединение (A B) (B A). Получим { a, g b, d, t }

4. Положим A Δ B = { a, g b, d, t } ■

Комбинации нескольких теоретико-множественных операций (например, A (B’ C)) вы-полняются аналогичным образом.

Пример 10. Пусть U = {1, 2, 3, 4, 5, 6, 9}, A = {1, 2, 3, 4}, B = {2, 4, 6}, C = {1, 3, 6, 9}.

Найти следующие множества.

a) A’ B.

1. Алгоритмом из примера 5 находим A’ = {5, 6, 9}.

2. Алгоритмом из примера 7 находим A’ B = {5, 6, 9} {2, 4, 6}= {6}.

b) B’ C’.

1. Алгоритмом из примера 5 находим B’ = {1, 3, 5, 9} и C’ = {2, 4, 5}.

2. Алгоритмом из примера 6 находим B’ C’ = {1, 3, 5, 9} {2, 4, 5}= {1, 3, 5, 9, 2, 4}.

c) A (B C’).

1. C’ = {2, 4, 5} (см. b)).

2. Алгоритмом из примера 6 находим B C’ ={2, 4, 6} {2, 4, 5} = {2, 4, 6, 5}.

3. Алгоритмом из примера 7 находим A (B C’) = {1, 2, 3, 4} {2, 4, 6, 5} = {2, 4}.

d) (A’ C’) B’.

1. A’ = {5, 6, 9} (см. а)).

2. B’ = {1, 3, 5, 9}, C’ = {2, 4, 5} (см. b)).

3. Алгоритмом из примера 6 находим A’ C’ = {5, 6, 9} {2, 4, 5}={5, 6, 9, 2, 4}.

4. Алгоритмом из примера 7 находим (A’ C’) B’ = {5, 6, 9, 2, 4} {1, 3, 5, 9}= {5, 9} ■

Пример 11. Пусть U = { a, b, c, d, e, f, g }, X = { a, c, e }, Y = { a, b, d, e, f }, Z = { a, c, d, g }.

Выполнить операции X (Y Z) '.

1. Алгоритмом из примера 8 находим Y Z = { a, b, d, e, f } { a, c, d, g } = { b, e, f }

2. Алгоритмом из примера 5 находим (Y Z) ' = { b, e, f } ' = { a, c, d, g}.

3. Алгоритмом из примера 7 находим X (Y Z)’ = {a, c, e} {a, c, d, g }={ a, c } ■

Задание 5. Найти пересечение множеств (см. пример 7):

1. {3, 4, 5, 6, 7} {4, 6, 8, 10}

2. {9, 14, 25, 30} {10, 17, 19, 38, 52}

3. {5, 9, 11} Æ

4. { a, m, n, s, w } { c, d, m, o, s }

5. { P, Q, R } { F, H, Q, X, R } ■

Задание 6. Найти объединение множеств (см. пример 6):

1. {1, 5, 7} {3, 7, 10}

2. { a, m, n, s, w } { c, d, m, o, s }

3. { P, Q, R } { F, H, Q, X, R } ■

Задание 7. Найти разность множеств (см. пример 8):

1. {1, 5, 7} {3, 7, 10}

2. { a, m, n, s, w } { c, d, m, o, s }

3. { P, Q, R } { F, H, Q, X, R }

4. {3, 5, 7} {1, 2, 3, 4, 5, 7}

5. { f, g, h, i, j, k } { g, i, k } ■

Задание 8. Пусть U = { a, b, c, d, e, f, g }, X = { a, c, e, g }, Y = { a, b, c }, Z = { b, c, d, e, f }. Вы-полнить указанные операции:

1. X (Y Z)	2. Y (X Z)	3. (Y Z’) X
4. (X’ Y’) Z	5. (Z X’) ’ Y	6. (Y X’) ’ Z’
7. X Y	8. Y X	9. X’ Y
10. Y’ X	11. X (X Y)	12. Y (Y X) ■

Задание 9. Пусть U = { a, b, c, d, e, f, g }, A = { a, c, e }, B = { a, b, d, e, f }, C = { a, c, d, g }.

Выполнить указанные операции:

Дата добавления: 2015-10-16