Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Операции над множествами

Теоретические сведения

Любая операция представляет собой результат отображения множества самого на себя. Все операции определяются на некотором универсуме /. К ним относятся объединение, пересечение, дополнение, разность и симметрическая разность.

Объединением двух множеств Ли В называется новое множество С, элементы которого удовлетворяют следующему условию:

С = 4ий = {х/1?у4 или х е В}. (1.1)

Пересечением двух множеств Л и В называется новое множество С, элементы которого удовлетворяют следующему условию:

С = А п В = {х / л; е А и л; е В). (1.2)

Дополнением множества А называется новое множество С, элементы которого удовлетворяют следующему условию:

С = А={х / х ? А} = 1А. (1.3)

Разностью двух множеств А и В называется новое множество С, элементы которого удовлетворяют следующему условию:

С = А В = {х/хеАих (1.4)

Симметрической разностью двух множеств Л и В называется новое множество С, элементы которого удовлетворяют следующему условию:

С = ААВ = {х/(хє4ихгй) или (х и х є В)}. (1.5)

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

ААВ = (А п В) и (А п В). (1.6)

Результаты применения рассмотренных выше операций удобно отображать графически с помощью диаграмм Эйлера—Венна (рис. 1.1). Квадрате 1 обозначает универсум, круги — множества А и В, результат операции представлен заштрихованными фрагментами.

Диаграммы Эйлера—Венна

Рис. 1.1. Диаграммы Эйлера—Венна

В табл. 1.1 приведены основные свойства операций над множествами.

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

Перечисленные операции получили название теоретико-множественных операций. Результаты всех этих операций над подмножествами универсума / дают также подмножества /.

Таблица 1.1

Идемпотентность

Ап А = А

А и А - А

Коммутативность

А п В - В п А

А и В - В и А

Ассоциативность

АпВпС = (АпВ)пС = - А п(В пС)

ИиЯиС = (ИиЯ)иС = = А и и С)

Дистрибутивность

АклВпС-= (Аи В)п(АиС)

Ип(ЯиС) =

- А п В и А пС

Поглощение

(Ап Я) и А = А

и В) п А = А

Действия с универсумом

Ап I - А

Ии/ = /

Действия с пустым

множеством

А п0 = 0

И и 0 = И

Свойства

дополнения

АпА-0

И и А = I

Двойное

дополнение

А - А

Законы де Моргана

Ии В - АпВ

А п В - А и В

Выражение для разности

АВ=АпВ

Выражение для

симметрической

разности

ААВ = (Аи В)(А п В) = А п В и А п В

Задачи

Задача 1.11. Даны множества / ={1,2, 3, 4, 5, 6, 7, 8, 9}, А = {1, 3, 5, 7, 9}, В= {1, 2, 3, 8, 9}, С= {2, 3, 5, 6, 9}. Найти:

  • 1) 4пйиС;
  • 2) Ап В и С;
  • 3) Ап В и С;
  • 4) 4п5иС.

Решение.

Учитывая старшинство операций, получаем:

1) АпВ = { 1, 3, 9},

АпВиС = { 1, 3, 9} и {2, 3, 5, 6, 9} = {1, 2, 3, 5, 6, 9};

2) 4пй = {2, 4, 5, 6, 7, 8},

Ап В и С = {2, 4, 5, 6, 7, 8} и {2, 3, 5, 6, 9} =

= {2, 3, 4, 5, 6, 7, 8, 9};

3) 5иС = {1, 2, 3, 5, 6, 8, 9} = {4, 7},

А п В и С = {1, 3, 5, 7, 9} п {4, 7} = {7};

4) А п В и С = {1, 2, 3, 5, 6, 9} = {4, 7, 8}.

Алгебра А = <В(1); и, п, > называется алгеброй Кантора, где в качестве множества используется булеан В(1), а в качестве операций выступают объединение, пересечение, дополнение. Алгебру Кантора часто называют алгеброй множеств.

Задача 1.12. С помощью законов алгебры Кантора упростить выражения:

  • 1) А Г) В и А п В
  • 2) Ап Ви А;
  • 3) Ап В и А.

Решение.

Используя закон дистрибутивности, а затем действия с универсумом, получаем АпВиАпВ = Ап(В и В) = А п I = А.

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

АпВиА = (АиВ)иА = АиАиВ = 1иВ = 1.

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

Ап Ви А = А п(В п А) = (А п А) п В = 0 п В = 0.

Задача 1.13. С помощью законов алгебры Кантора показать, что произвольные множества Л и В удовлетворяют следующему свойству:

ААВ = (А и В) п{А п В).

Решение.

Для решения задачи применяем закон де Моргана, два раза подряд закон дистрибутивности, закон дополнения и нормальный порядок скобок:

ААВ = (А и В) п (А п В) = (А и В) п (А и В) =

= Ап(АиВ)иВп(АиВ) = АпАиАпВиВпАиВпВ =

= А п В и А п В = (А п В) и (А п В).

Задача 1.14. Даны множества / = {а, Ь, с, сі, е,/}, А = {а, с, е), В = = {Ь, сі,/}, С = {а, Ь, е,/. Вычислить результат операций:

  • 1) Ап В пС;
  • 2) А и В п С;
  • 3) Л п 5 и С;
  • 4) (АиВ)пС.

Задача 1.15. Даны множества А (треугольник), В (квадрат) и С (круг). Определить через операции объединения, пересечения, дополнения, разности и симметрической разности, чему равна заштрихованная область в указанных четырех случаях а), б), в) и г) (рис. 1.2).

а)

в)

Условия задачи 1.15

Рис. 1.2. Условия задачи 1.15

Задача 1.16. Нарисовать круги Эйлера—Венна для А и (В / С), А / / С), где Л (треугольник), В (квадрат) и С (круг) — из задачи 1.12, а).

Задача 1.17. Для заданных множеств /= {1, 2, 3, 4, 5, 6, 7, 8, 9}, А = {1,3, 5, 7, 9}, В = {1, 2, 3, 8, 9} и С= {2, 3, 5, 6, 9} вычислить результат операций:

  • 1) А п В и С;
  • 2) Ап В и С;
  • 3) Ап В и С;
  • 4) А п В и С.

Задача 1.18. Для заданных множеств /= {1, 2, 3, 4, 5}, А = {1, 3, 5}, В = {1, 2, 4} и С= пустое множество вычислить результат операций:

  • 1) (Д и ~В)пС
  • 3) ЛпСиб;
  • 4) АглС ул В.

Задача 1.19. Задано множество Х= {а, {Ь, с}}. Выделить все элементы и все подмножества для этого множества.

Задача 1.20. Задано множество Х= {а, {а, 6}}. Выделить все элементы и все собственные подмножества для этого множества.

Задача 1.21. Задано множество X = {0,{0}}. Выделить все элементы и все подмножества для этого множества.

 
<<   СОДЕРЖАНИЕ   >>