Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Понятие множества и способы его задания | Понятие сортиравки | Пузырьковая сортировка | Сортировка выбором | Cортировка вставками | Квадратичная выборка | Быстрая сортировка | Основные определения | Способы задания бинарных отношений | Операции над бинарными отношениями |


Читайте также:
  1. Анализ депозитных операций.
  2. Антибактериальные свойства кордицепса
  3. Арифметические преобразования при выполнении арифметических операций вида X op Y
  4. Аудит учета кассовых операций.
  5. Вид маркетинга, который характеризуется производством и маркетингом нескольких продуктов с различными свойствами для всех покупателей, однако рассчитанные на разные их вкусы
  6. Виды ошибок измерений, свойства случайных ошибок. Принцип арифметической средины.
  7. Виды смешанных гипсовых вяжущих. Свойства и применение.

 

Чтобы записывать и преобразовывать теоретико-множественные

 

выражения, необходимо знать свойства операций над множествами.

 

Основные из этих свойств следующие.

 

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

 

A È B = B È A; A Ç B = B Ç A.

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

 

A È(B È C)=(A È BA; A Ç(B Ç C)=(A Ç BA.

 

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


А È (В Ç С)

 

А Ç (В È С)


= (А È В) Ç (A È C);

 

= (А Ç В) È (A Ç C).


 

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

 

A È B = A Ç B; A Ç B = A È B.

 

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

 

A È A = A

 

6. Законы поглощения

 

A È(A Ç B)= A; A Ç(A È B)= A.

 

7. Закон двойного дополнения:

 

A = A.

 

8. Операции с универсальным и пустым множествами: A È U = U; A ÇÆ =Æ; A ÈÆ = A;

A Ç U = A; A È A = U; A Ç A =Æ.

 

Если внимательно рассмотреть свойства теоретико-множествен-ных операций, то можно сформулировать правило, известное как принцип двойственности.


 

Теоретико-множественное выражение, содержащее операции объ-

 

единения, пересечения, дополнения, а также универсальное множество U и пустое множество Æ, останется справедливым, если в нем произвести следующие замены

 

 

È® Ç; Ç®È; Æ ® U; U ®Æ; Ì®É.

 

Все перечисленные выше свойства могут быть доказаны по одной

 

схеме. Суть ее в следующем.

 

Пусть требуется доказать теоретико-множественное равенство M = N, где M и N есть некоторые множества.

Первая часть доказательства будет состоять в том, чтобы показать, что если некоторый элемент принадлежит множеству M, то он также

принадлежит множеству N. Этим будет доказана справедливость со-отношения M Ì N.

Вторая часть доказательства состоит в необходимости показать, что если некоторый элемент принадлежит множеству N, то он также принадлежит множеству M. Этим будет доказана справедливость со-отношения N Ì M.

Из соотношений M Ì N и N Ì M следует, что M = N.

 

Пример. Пусть требуется доказать, что

 

А È (В Ç С) = (А È В) Ç (A È C).

 

Очевидно, что здесь M = A È(B Ç C)и N = (А È В)Ç (A È C).

 

1. Проводим доказательство «слева направо» (=>).

 

Пусть имеется элемент х такой, что x Î M. Тогда из определения

 

операции объединения следует, что этот элемент принадлежит мно-жеству A (x Î A) или(здесьимеемнеисключающее«или»)множеству

B Ç C (x Î B Ç C).


 

Рассмотрим каждый из этих случаев.

 

а)Если(x Î A),то,поопределениюоперацииобъединения,имеем x Î A È B и x Î A È C.

 

Следовательно, этот элемент будет общим для этих множеств, то есть x Î(А È В)Ç (A È C).

 

Иначе говоря, для данного случая доказано, что M Ì N.

 

б) Если x Î B Ç C, то элемент x является общим для каждого из множеств В и С, то есть x Î B и x Î C. Но тогда будем иметь, что

x Î A и A È C. Следовательно, x Î(А È В)Ç (A È C). Другими сло-вами, и для данного случая M Ì N.

 

2. Проведем теперь доказательство «справа налево» (<=). Пусть x Î N. Тогда, по определению операции пересечения, можно записать, что x Î A È B и x Î A È C.

Рассмотрим два случая.

 

а)Предположим,что x Î A. Тогдаочевидно,что x Î A È(B Ç C).Следовательно, x Î M и мы имеем в этом случае N Ì M.

б) Предположим, что x Î A. В этом случае из выражения для N за-

 

ключаем, что элемент х является общим для множеств В и С, то есть x Î B Ç C. Нотогда x Î A È(B Ç C),такимобразомивэтомслучае N Ì M.

 

Так как мы доказали, что M Ì N и N Ì M N, то это может быть только тогда, когда M = N.


 

Лекция 3

 

 


Дата добавления: 2015-11-16; просмотров: 131 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Операции над множествами| Упорядоченные множества. Прямое произведение множеств

mybiblioteka.su - 2015-2024 год. (0.01 сек.)