Реферат декартово произведение

метки: Подмножество, Множество, Декарт, Элемент, Произведение, Принадлежать, Состоять, Универсум

Аксиомы и тождества алгебры Кантора

В общем случае алгебра — это совокупность несущего множества и некоторых операций, заданных на нем. В алгебре Кантора (алгебре множеств) несущим множеством является булеан универсума, на котором заданы три операции: одноместная операция НЕ (  ) , двуместные операции И (  ) и ИЛИ (  ).

Обозначение алгебры Кантора: А к = < P (1),  ,  ,  >.Операции на множествах подчинены простым законам, перекликающимся с аксиомами алгебры чисел, но не совпадающим с ними. Аналогом операции  в алгебре чисел является операция умножения, операции  — сложение. Однако эти аналогии в значительной степени внешние. Законы алгебры множеств более универсальны, чем алгебры чисел.

Аксиомы алгебры Кантора

А1. Тождественность	А  А=А ;	А  А=А ;
А2. Коммута тивность:	А  В=В  А;	А  В= В  А ;
А3.Ассоциативность:	А  (В  С)=(А  В)  С;	А  (В  С)=(А  В)  С ;
А4. Дистри бутивность:	А  (В  С)=(А  В)  (А  С) ;	А  (В  С)= (А  В)  (А  С) ;
А5.Законы дополнения:	А  1=1 ; А  =А ; А  А =1 ;  1 =  ;	А  1=А ; А и  =  ; А   А =  ;  =1 ;
А6.Закон двойного отрицания:	_  А=А ;
Правила де ‘ Моргана:

Законы для разности множеств

1. А\В=А  В
2. 1\А=  А
3. А\1= 
4. А\  =А
5.  \А= 
6. А\А= 
7. (А\В)\С=А\(В  С)
8. А\(В\С)= (А\В)  (А  С)
9. А  (В\С)=(А  В)  (А\С)
10. А  (В\С)=(А  В)\(А  С)

Используя аксиомы и тождества алгебры множеств можно преобразовывать исходные множества, заданные формулами, к формулам определенного вида. Наибольший интерес представляют канонические формы представления. Одной из канонических форм представления множеств является нормальная форма Кантора , т.е. представление множества в виде объединения пересечений множеств или их дополнений. Стратегия преобразований исходной формулы состоит в следующем:

1. Вначале избавляются от всех вхождений знака «вычесть» (\) в исходной формуле.
2. Используя правила де Моргана, заменяют дополнения выражений на объединение и пересечение дополнений.
3. Используя аксиомы дистрибутивности, преобразуют полученное выражение к требуемому виду.

Пример 1.

А\(В\С)=А  (В   С ) = А  (  В  С ) = (А   В)  (А  С).

Полученная формула есть нормальная форма Кантора данной формулы (НФК).

1.2. Понятие множества. Обозначение принадлежности

Математическое понятие множества постепенно выделилось из привычных представлений о совокупности, собрании, классе, семействе и т. д. В 1872 г. Георг Кантор, создатель теории множеств, определил множество как «объединение в одно целое объектов, хорошо различаемых нашей интуицией или нашей мыслью». В первом издании «Теории множеств» Бурбаки, появившемся в 1939 г., в сводке результатов можно найти следующее предложение: «Множество образуется из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств».

Объекты, сущности или элементы, составляющие множество, обозначаются строчными латинскими буквами: х, а,…; множество часто обозначают прописными латинскими буквами Е, N, … . Знак  обозначает вхождение или принадлежность; х  Е читается: «элемент х принадлежит множеству Е», или короче: «х— элемент множества Е». Следует различать «общий элемент» х множества Е, т. е. произвольный элемент, характеризующийся единственным свойством «принадлежать множеству», и конкретные элементы а, b , c ,…, каждый из которых отличен от остальных. Если х не принадлежит Е, будем писать х  Е, что читается « х не является элементом множества Е» или «х не принадлежит множеству Е». Если множество содержит конечное число элементов, говорят, что оно конечно; в противном случае множество называется бесконечным. Множество Е, состоящее из элементов а, b ,…, записывается

Е= [а. b ……..}.

Примеры. 1) Множество четных цифр Р={2, 4,6,8}.

2) Множество трехзначных чисел в двоичной системе:

В 3 = {000, 001, 010, 011, 100, 101, 110, 111}.

1.3. Способы задания множеств

1) Множество может быть задано перечислением всех его элементов.

Пример. Множество цифр: {0,1,…, 9}.

2) Обобщение первого способа состоит в том, что каждый элемент задаваемого множества определяется по некоторому элементу уже известного множества.

Пример. Считая известным множество целых чисел

Z = {….-3.-2,-1, 0. 1, 2, 3,…},

определим множество степеней числа 2

{…, 2 -3 , 2 -2 , 2 -1 , 2 0 , 2 1 , 2 2 , 2 3 , …}

3) Другой способ задания множеств — описание ограничительного свойства, выделяющего элементы множества Е среди элементов более широкого, или основного (универсального, универсума), множества U . Множество Е называется частью, или подмножеством множества U .

Пример. Пусть дано множество N натуральных чисел N = {1, 2, 3,…}. Рассмотрим совокупность всех тех элементов этого множества, которые делятся на 2 (ограничительное и характеризующее свойство); полученное множество есть множество четных чисел Р={2, 4, 6,…}.

4) Аналитически с помощью операций на множествах.

1.4. Множество подмножеств. Включение

Пусть U — основное множество. Основное, или фундаментальное, множество в математике может быть образовано всеми элементами какого-нибудь определенного типа.

Пример. Множество прямых плоскости, множество простых чисел и т. д.

Два свойства, эквивалентные относительно основного множества, определяют одну и ту же часть этого множества, и обратно. Множество элементов U , обладающих свойством х  Е, очевидно, совпадает с Е.

Пример. Пусть I — множество нечетных чисел в десятичной системе

I = {1, 3, 5, 7, 9, 11, 13. 15, 17, 19….};

за основное множество примем множество N натуральных чисел. Можно определить множество нечетных чисел исходя из свойства оканчиваться на нечетную десятичную цифру 1, 3, 5, 7 или 9 ( Р 1 ) ; то же множество соответствует свойству не делиться на 2 ( Р 2 ).

Свойства P 1 и P 2 эквивалентны относительно N и задают множество нечетных чисел, подмножество основного множества N .

Обратимся теперь к свойству не быть целым числом ( Р 3 ), соответствующее этому свойству подмножество основного множества N не содержит ни одного элемента; такое множество будем называть пустым и обозначать  .

Таким образом, свойства, присущие некоторым элементам множества U , могут служить для задания подмножеств этого множества; свойство, отличное от всех свойств элементов U , порождает пустое множество, пустое подмножество множества U . Напротив, наибольшее подмножество, т. е. само множество U , может быть задано любым свойством, присущим всем элементам основного множества.

Пусть А и В — два подмножества основного множества U . Если все элементы из А принадлежат В, то говорят, что А содержится (или включено) в В; употребляются также выражения; В содержит A , или А есть часть множества В. В этом случае будем писать А  В или В  A .

Пример. Множество Р четных чисел содержится в множестве N натуральных чисел: Р  N.

При задании множества путем перечисления элементов или установления соответствия с элементами ранее изученного множества, мы можем сформулировать характеристические свойства общего элемента подмножества Е основного множества U ; эти формулировки будут теоремами, требующими доказательства; способ задания Е — аналитический.

Наоборот, если мы знаем характеристические свойства общего элемента подмножества Е, то мы можем определить, какие элементы основного множества U принадлежат этому подмножеству: речь идет о параметризации подмножества Е: такой способ задания является синтетическим.

Из соотношений А  В и В  С следует соотношение A  С ; следовательно, отношение включения транзитивно. Заметим, что из А  В и B  A следует А = В, и наоборот. Действительно, два множества равны (идентичны), если они состоят из одних и тех же элементов.

Иногда вводят понятия собственного и несобственного подмножества. Множество B называется собственным подмножеством множества A , если оно отлично от A и от .

В этом случае пишут A  B , если возможен случай A = B (в этом случае A называется несобственным подмножеством множества В ), и А  В, если В содержит хотя бы один элемент, не принадлежащий A . При такой системе обозначений невозможен случай, когда А  В и B  A одновременно.

Свойства подмножеств:

1. Пустое множество является подмножеством любого множества: 
2. Всякое множество является своим собственным подмножеством:

Два множества называются равными , если они содержат одни и те же элементы и количество этих элементов одинаково.

или или .

Множеством подмножеств некоторого основного или произвольного множества Е называется множество, элементами которого являются подмножества множества Е. Это множество P (Е) включает в качестве элементов пустое множество 0 и само множество Е; каждый отдельный элемент Е есть также подмножество множества Е.

Пример. Е ={ а, b , с};

P (Е)={{  }, {а}, { b }, {с}, {а, b }, {а, с}, { b , с}, {а, b , с,}}.

Теорема : Конечное множество, содержащее n элементов, имеет 2 n подмножеств.

Доказательство : Пусть и пусть B  A . Поставим ему в соответствие набор длины n из 0 и 1, устроенный так: если элемент a i  B , то на i -ом месте ставим 1, в противном случае — 0.

A:				…
					
В:		1	0	…	0

Каждому подмножеству множества А соответствует свой набор. И наоборот, по всякому набору нулей и единиц можно выписать множество, являющееся подмножеством А. Таким образом, между всеми подмножествами A и п -местными наборами 0 и 1 существует взаимно однозначное соответствие, т.е. подмножеств столько же, сколько таких наборов. Поскольку на каждое из п мест можно поставить либо 0, либо 1, то общее количество п -местных наборов равно , а следовательно, и подмножеств 2 n .

1.5. Основные операции над множествами. Диаграммы Эйлера-Венна.

Для наглядного представления множеств используют диаграммы Эйлера-Венна. В этом случае множества обозначают областями на плоскости и внутри этих областей условно располагают элементы множества. Часто все множества на диаграмме размещают внутри прямоугольника, который представляет собой универсальное множество U . Если элемент принадлежит более чем одному множеству, то области, отвечающие таким множествам, должны перекрываться, чтобы общий элемент мог одновременно находиться в соответствующих областях. Выбор формы областей, изображающих множества на диаграммах, может быть произвольным (круги, внутренности эллипсов, многоугольники и т.п.).

Покажем, например, с помощью диаграммы Эйлера-Венна, что множество А является подмножеством множества В:

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

если АВ, а В С, то АС.

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

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

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

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

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

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) не изменяется при замене символов дуальными, поэтому его называют самодвойственным.

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

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

Пример.

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

1. — некоммутативность
2. = — ассоциативность

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

1. — дистрибутивность относительно объединения

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

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

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

1. ;
2. ,,

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

;

Пример. 

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

PAGE \* MERGEFORMAT 6