Декартово произведение множеств




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

1) Дополнение: Дополнение множества A - множество, состоящее из всех элементов универсума, не принадлежащих A.
2) Пересечение: Пересечение множеств A и B - множество, состоящее из всех элементов, принадлежащих одновременно и A, и B.
3) объединение: Объединение множеств A и B - множество, состоящее из элементов, принадлежащих хотя бы одному из указанных множеств.
4) Дизъюнктивная сумма (симметрическая разность): Дизъюнктивная сумма множеств A и B - это множество, состоящее из элементов, принадлежащих либо только A, либо только B.
5) Разность: Разность множеств A и B - это множество, состоящее из элементов, принадлежащих A, но не принадлежащих B.

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

Операции над мно­жествами, сформулированные в (1.4) обладают некоторыми свойствами, приведенными в табл. 1. Эти свойства выражаются совокупностью тождеств, справедливых независимо от конкретного содержания входящих в них множеств, являющихся подмножествами некоторого универсума U.

Таблица 1

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

1а) 1б)
2а) 2б)
3а) 3б)
4а) 4б)
5а) 5б)
6а) 6б)
7а) 7б)
8а) 8б)
9а) 9б)
10а) 10б)
11)
12)
13) - закон двойного отрицания
14)
15)
16)
17) (А + В) + С = А + (В + С)
18) А + Æ = Æ + А
19)
20) Æ

 

Тождества (1а)-(3а) выражают соответственно коммутатив­ный, ассоциативный и дистрибутивный законы для объединения, а тождества (1б)-(3б) - те же законы для пересечения. Соотно­шения (4а)-(7а) определяют свойства пустого множества Æ и универсума U относительно объединения, а соотношения (4б)-(7б) - относительно пересечения.

Выражения (8а) и (8б), называемые законами идемпотент­ности, позволяют записывать формулы с множествами без коэффициентов и показателей степени. Зависимости (9а) и (9б) представ­ляют законы поглощения, а (10а) и (10б) - законы де Моргана.

Соотношения (11)-(20) отражают свойства дополнения, раз­ности, дизъюнктивной суммы, включения и равенства.

Первые десять свойств в табл. 1 представлены парами двойственных (дуальных) соотношений, одно из которых получается заменой в другом символов: È на Ç и Ç на È, а также Æ на U и U на Æ. Соответствующие пары символов È, Ç и Æ, U называются двойственными (дуальными) символами.

При замене в любой теореме входящих в нее символов дуальны­ми получим новое предложение, которое также является теоремой (принцип двойственности или дуальности). Тождество (11) не изменяется при замене символов дуальными, поэтому его называют самодвойственным.

 

Декартово произведение множеств

Декартово произведение множеств A и B – это множество упорядоченных пар, первый элемент которых принадлежит A, а второй – принадлежит B.

Пример.

Свойства декартова произведения:

1) - некоммутативность

2) = - ассоциативность

Свойство ассоциативности позволяет использовать сокращенную запись для декартова произведения нескольких множеств:

3) - дистрибутивность относительно объединения

- дистрибутивность относительно пересечения

- дистрибутивность относительно разности

Доказательство: Докажем, например, дистрибутивность декартова произведения относительно операции пересечения множеств.

1) ;

2) , ,

Особым случаем декартова произведения является произведение множества самого на себя. В этом случае говорят о декартовом квадрате множества или декартовой n-ой степени множества А.

;

Пример. Þ

Теорема. Если множество A содержит n элементов, а B – m элементов, т.е.: , то содержит элементов.

 

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-08 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: