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

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

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


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

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

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

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

С = АулВ = {х/хеА или х е В). (1.1)

Новое множество С состоит из тех и только тех элементов, которые или принадлежат Л, или принадлежат В, или обоим множествам одновременно.

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

С = Л п В = {х / х е Л и х е В). (1.2)

Новое множество С состоит из тех и только тех элементов, которые принадлежат обоим множествам Ли В одновременно.

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

С = А = {х / х ? А) = I А. (1.3)

Таким образом, в новом множестве С содержатся те и только те элементы из универсума, которые не принадлежат Л.

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

С = А В = {х / х е А х ? В). (1.4)

Таким образом, в новом множестве С содержатся только те элементы из Л, которые не принадлежат В.

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

С = ЛАВ = {х / (х е А и х или (1.5)

Новое множество С состоит из тех и только тех элементов, которые принадлежат А и не принадлежат В или принадлежат В, но не принадлежат А

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

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

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

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

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

Т

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

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

Рассмотрим решение несколько задач.

Задача 1.1

Даны множества /= {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) /1п5иС;
  • 2) А п В и С;
  • 3) А п В и С;
  • 4) А п В и С.

Решение.

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

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

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

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

Некоторые рассмотренные выше двухместные операции обладают свойствами идемпотентности, коммутативности и ассоциативности.

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

Таблица 1.1

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

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

Ап А = А

А и А - А

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

А п В - В п А

Ии В - В и А

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

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

ИиДиС = (ИиД)иС = = И и (5 и С)

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

А и ВпС =

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

Ип(ДиС) =

- А п В ^ А пС

Поглощение

(АпВ)иА = А

(Ии В)пА = А

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

А п I = А

Ии/ = 1

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

А п0 - 0

И и 0 = И

Свойства

дополнения

А п А = 0

И и И = /

Двойное

дополнение

^11

II

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

А и В = А п В

И п В - А и В

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

А В = А п В

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

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

разности

ААВ - (А и В)(А п В) - А п В и А п В

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

Под алгеброй А = <М, *5Ъ> понимается совокупность множества М с заданными на нем операциями 5 = {0, 02,..., О,,}.

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

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

Задача 1.2

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

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

Решение.

  • 1) АпВ'иАпВ = Ап(ВиВ) = Ап1 = А;
  • 2) А п В и А = Акл В и А = I и В = /;
  • 3) АпВ'иА = АпВпА = 0пВ = 0.

Задача 1.3

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

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

Решение.

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

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

= Агл(А^) В)ул Вгл (А ул В) = АпАулАпВулВпАулВпВ =

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

Полученная форма совпадает с выражением симметрической разности через операции объединение, пересечение и отрицание (см. 1.6).

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