ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

Шандриков А.С.

Витебский государственный политехнический колледж ВГТУ

Термины и определения

Множество – это любая совокупность определённых и различных между собой объектов, мыслимая как единое целое.

Например, резисторы, диоды, конденсаторы образуют совокупность различных между собой объектов, но эта совокупность представляет собой множество РЭК, из которых состоит изделие, и с этой точки зрения такое множество посредством интуиции или интеллекта определяется как единое целое.

Множества обозначаются прописными буквами латинского алфавита – A, B, C и т.д.

Множества состоят из элементов. Элементы множества обозначаются строчными буквами латинского алфавита: a, b, c и т.д.

Множество A, состоящее из элементов a, b и c, записывается в виде

A = {a, b, c}                                                     (1)

Множество A, содержащее один элемент a, обозначается A = {a} и называется одноэлементным.

Множество, которое не содержит элементов, называется пустым и обозначается Ø, например, A = Ø.

В множестве все элементы считаются различными, поэтому запись, например, A = {a, b, b, c, d, c} неверна.

Порядок расположения элементов в множестве не имеет значения.

Принадлежность элемента к множеству обозначается символом Î, а непринадлежность — символом Ï. Запись вида a Î X означает, что элемент a принадлежит множеству X.

Запись вида b Ï D означает, что элемент b не принадлежит множеству D.

Множество с конечным числом элементов называется конечным. Примеры: множество символов алфавита, множество РЭК в телевизоре и т.д.

Множество называется  бесконечным, если число его элементов бесконечно.

Множества A и B называются равными и обозначаются A = B, если они состоят из одних и тех же элементов.

Количество элементов в множестве называется  мощностью множества и обозначается |A|. Например, для множества (1) |A| = 3.

Если любой элемент множества X принадлежит множеству Y, то X – это подмножество (часть) множества Y и записывается в виде X Í Y. Символ Í обозначает отношение нестрогого включения.

Для любого множества A Í A.

Если A Í B и B Í A, то для любых множеств A и B справедливо A = B.

Если A Í B и A ¹ B, то множество A строго включается в множество B.

Строгое включение обозначается A Ì B.

Система множеств – это множество, элементами которого являются множества. Множество подмножеств (частей) множества X обозначается P(X).

Следует различать отношение принадлежности (Î) и отношение включения (Í, Ì). Так, множество A может быть своим подмножеством, т.е. A Ì A, однако множество A не может входить в состав своих элементов, т.е. A Ï A. Отношение включения обладает свойством транзистивности, т.е. если AÎB и BÎC, то AÎC. Отношение принадлежности таким свойством не обладает. Например, множество A = {a₁, {a₂, a₃}, a₄} содержит в числе своих элементов множество A¢ = {a₂, a₃} и поэтому можно записать a₂, a₃ Î A¢ и A¢ Î A. Однако из этого не следует, что элементы a₂, a₃ Î A (среди элементов множества A нет элементов a₂ и a₃), т.е. a₂, a₃ Ï A.

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

Объединение (сумма, соединение) множеств A и B — это множество C, состоящее из элементов, принадлежащих или множеству A, или множеству B, или обоим одновременно.

C = A È B = {x | x Î A или x Î B                                

Пример 1: A = {1, 2, 3, 4}; B = {1, 2, 3}.   C = A È B = {1, 2, 3, 4}.

Пример 2: A = {a, b, c};  B = { a, b, d, e}.  C = A È B = {a, b, c, d, e}.

Наглядное представление об объединении даёт графическая иллюстрация с использованием кругов Эйлера (рис. 1). Множества элементов представлены множествами точек внутри кругов A и B.

Рис. 1 – Объединение множеств

Пересечение (логическое произведение) множеств A и B – это множество C, состоящее из элементов, принадлежащих одновременно как множеству A, так и множеству B.  

C = A Ç B = {x | x Î A и x Î B                                 

Пример 3: A = {1, 3, 5, 6, 7, 9};  B = { 2, 4, 6, 7, 10}. C = A Ç B = {6, 7}.

Пример 4: A = {a, b, c, d, e};  B = {b, e, f, g, m}.  C = A Ç B = {b, e}.

Пример 5: A = {a, b};  B = {c, d}.     C = A Ç B = Ø.

Графическое множество C – это заштрихованная область на рис. 2.

Рис. 2 – Пересечение множеств

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

C = A Ç B = B Ç A                                           

C = A È B = B È A                                         

A È (B È C) = (A È B) È C                                  

A Ç (B Ç C) = (A Ç B) Ç C                                  

A È (B Ç C) = (A È B) Ç (A È C)                            

A Ç (B È C) = (A Ç B) È (A Ç C)                              

Пересечение множества с самим собой равно исходному множеству:  AÇA=A.

Пересечение некоторого непустого множества с пустым множеством даёт пустое множество: A Ç Ø = Ø.

Разность множеств A и B – это множество C, любой элемент которого принадлежит множеству A и не принадлежит множеству B.

C = A\B = {x | x Î A и x Ï B                                   

Пример 6: A = {a, b, c};  B = {b, d}.    C = A\B = {a, c}.

Графическая иллюстрация разности множеств A и B представлена на рис. 3.

Рис. 3 – Разность множеств

Разность в отличие от объединения и пересечения определена только для двух множеств.

Для разности не выполняется переместительный и сочетательный законы, т.е.

A\B ¹ B\A                                                      (2)

и

A\(B\C) ¹ (A\B)\C                                                 (3)

Утверждения (2) и (3) не являются очевидными, поэтому проиллюстрируем их на конкретных примерах. Даны три множества

A = {1, 2, 3, 4, 5};

B = {3, 4, 5};

C = {5}.

A\B = {1, 2, 3, 4, 5}\{3, 4, 5} = {1, 2};

B\A = {3, 4, 5}\{1, 2, 3, 4, 5} = Ø;

Очевидно, что {1, 2} ¹ Ø.

A\(B\C) = {1, 2, 3, 4, 5}\({3, 4, 5}\{5}) = {1, 2, 3, 4, 5}\({3, 4} = {1, 2, 5}

(A\B)\C = ({1, 2, 3, 4, 5}\{3, 4, 5})\{5} = {1, 2}\{5} = {1, 2}.

Очевидно, что {1, 2, 5} ¹ {1, 2}.

Дополнение множества B по отношению к множеству A – это множество `B, элементы которого принадлежат множеству A и одновременно не принадлежат множеству B.

`B = A\B = {x | x Î A и x Ï B

Рис. 3.4. Дополнение`B множества B до множества A

Разбиение множества

Разбиение  некоторого множества A – это такое множество подмножеств R = {A₁, A₂, …, A_m}, полученных из множества A, которое удовлетворяет следующим условиям:

1) любое из подмножеств A_i не является пустым, т.е. не содержит хотя бы один элемент A_i = Ø;

2) любое подмножество A_i является подмножеством множества A, т.е.

A_i  Í A                                                    

3) любые два подмножества являются непересекающимися, т.е. A_iÇA_j = Ø – пересечение любых двух подмножеств является пустым;

4) каждый элемент исходного множества A обязательно принадлежит какому-либо подмножеству A_i, т.е. объединение всех подмножеств A_i, входящих в разбиение R, даёт исходное множество A:

                                        

Элементы произвольного разбиения называются классами разбиения.

Разбиение R множества A называется поэлементным, если каждый класс разбиения R является одноэлементным множеством.

Разбиение R множества A называется целым, если R = {A}.

Целое и поэлементное разбиения множества A называются тривиальными разбиениями, остальные разбиения, если они существуют, — нетривиальными. 

Пример 7: множество {A} = Ø имеет единственное разбиение – пустую  систему R множеств. Это разбиение является поэлементным, целым оно не является;

Пример 8: одноэлементное множество A = {a} имеет единственное разбиение R = {M} = {{a}}. Это разбиение одновременно является и целым, и поэлементным;

Пример 9: двухэлементное множество A = {a, b} имеет два разбиения:

R₁ = {A} – целое разбиение.

R₂ = {{a}, {b}} – поэлементное разбиение (рис. 5).

Рис. 3.5. Разбиения двухэлементного множества

Пример 10: трёхэлементное множество A = {a, b, c} имеет уже пять разбиений (рис. 6):

R₁ = {A};    

R₂ = {{a}, {b}, {c}};

R₃ = {{a}, {b, c}};

R₄ = {{a, b}, {c}};

R₅ = {{a, c}, {b}}.

Рис. 3.6. Разбиения трёхэлементного множества

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

Литература

1. Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский - М. : Энергоатомиздат, 1988. – 480 с. : ил.

2. Методы разбиения схем РЭА на конструктивно законченные части / К.К. Морозов [и др.] ; - М. : Сов. радио, 1978. – 136 с. : ил.