В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)«МАИ»Кафедра «Математическая кибернетика»В.Н. НЕФЕДОВАЛГЕБРА МНОЖЕСТВ, БИНАРНЫЕОТНОШЕНИЯ В ПРИМЕРАХ И ЗАДАЧАХУчебное пособиеУтвержденона заседании редсовета15 мая 2011 г.МоскваИздательство «Доброе слово»2014ББК 517УДК 512Н 58Рецензенты: профессор, к.т.н. Спиридонова Т.А., доцент, к.ф.-м.н.,Прозоров К.В.Нефедов Виктор Николаевич. Алгебра множеств, бинарные отношения в примерах и задачах: Учебное пособие. – М.: Издательство«Доброе слово», 2014.

– 88 с.: ил.ISBN 978-5-89796-489-0Пособие включает в себя основные теоретические сведения по следующим темам: алгебра множеств; бинарные отношения, функции; отношениеэквивалентности; отношение частичного порядка; равномощность множеств, счетные, континуальные множества. В каждой из тем приведеныкраткие теоретические сведения (сопровождаемые примерами и упражнениями), необходимые для решения задач, а также множество задач и их решений. Пособие предназначено для студентов, обучающихся по специальности«Прикладная математика», а также для студентов других специальностей,изучающих курс «Дискретная математика».Корректура: Яковлева С.Ю.Издательство «Доброе слово»www.dobroeslovo.infoПодписано в печать: 21.01.2014П.л. 6,25.

Формат 60х90/16© Нефедов В.Н., 2014© Издательство «Доброе слово», 20142ПРЕДИСЛОВИЕПособие предназначено для студентов, обучающихся по специальности «Прикладная математика», а также для студентов других специальностей, изучающих курс «Дискретная математика». Пособие включает в себя основные теоретические сведения по следующим темам: алгебра множеств; бинарные отношения, функции; отношение эквивалентности; отношение частичного порядка; равномощность множеств,счетные, континуальные множества. Вводимые понятия часто поясняются примерами.

Некоторые из утверждений предлагаются в качествеупражнений. Большинство задач и упражнений сопровождаются решениями (иногда указаниями). По указанным разделам дискретной математики существует немало задач, решение которых не является вполнеочевидным, а требует привлечения необычных (особенно для студентовмладших курсов) методов и идей. Большинство из этих задач давно стали классическими и, например, в большей полноте представлены в [1].Долговременный методический опыт показывает, что студентам младших курсов полезным является задачник с подробным решением «трудных» задач, с наиболее доступным изложением этих решений, в частности, сопровождаемым пояснениями в виде рисунков, таблиц, позволяющих на образном уровне понять идеи вводимых понятий и решений.Автор стремился передать свой многолетний опыт преподавания этихразделов дискретной математики. Пособие является методическим дополнением к учебнику [2].

В пособии использовались некоторые задачииз [1], а также решения или указания к ним. Автор выражает благодарность Бодрихину Е.В. за помощь в графическом изображении рисунков.3Тема №1. Алгебра множествПонятие множества будем считать первоначальным, неопределяемым, мыслимым интуитивно (аналогично понятиям точки, прямой,плоскости в школьной геометрии). Под множеством M интуитивнопонимаем совокупность определенных, различимых между собой объектов, мыслимых как единое целое. Эти объекты называются элементами множества M .Пример 1.1.

Множество студентов, учащихся в МАИ, множествонатуральных чисел, множество целых чисел и т.д.Мы пишем x  M , если x – элемент множества M , и x  M – впротивном случае.Принцип объемности. Два множества считаются равными, еслиони состоят из одних и тех же элементов. Мы пишем A  B , если множества A и B равны, и A  B – в противном случае. Из определенияравенства множеств следует, что A  B  (а) для любого x  A справедливо x  B ; (б) для любого x  B справедливо x  A .Если элементами множества A являются объекты a1 , a2 ,..., an итолько они, то обозначаем A  {a1 , a2 ,..., an }.

Множество, не содержащее элементов, называется пустым и обозначается  . В случае, есликаждый элемент множества A является элементом множества B , множество A называется подмножеством множества B (или A включенов B ; или B включает в себя A ). Для любых множеств A, B, C выполняется:   A; A  A; A  B, B  A  A  B; A  B, B  C  A  C. Количество элементов в конечном множестве A будем обозначать A .Пример 1.2.   0, {}  1, {,{}}  2 и т.д.Пример 1.3. (а) {1,2,3,4}  {3,4,2,1}, (б) {1,2,3,4}  4,{{1,2,3,4}}  1, {{1,2},{3,4}}  2.Принцип абстракции. Многие конечные множества трудно (илидаже невозможно) описать перечислением объектов, принадлежащих4этим множествам (тем более это относится к бесконечным множествам).В таких случаях часто применяется так называемый принцип абстракции. Приведем несколько определений.

Языковое предложение, о котором имеет смысл говорить, что оно истинно или ложно называется высказыванием.Пример 1.4. «Москва – столица РФ», « 2  3 », « 2  2  3 » – высказывания. Предложения: «который час?», « x  2 » – не являются высказываниями.Под «формой от x » интуитивно понимается языковое предложение с вхождением в него x такое, что, если каждое вхождение в него xзаменить именем некоторого объекта из рассматриваемой совокупностиобъектов, то в результате получится высказывание.Пример 1.5. Пусть рассматриваемая совокупность объектов является множеством действительных чисел.

Тогда предложения : « x  2 »,« x  3 », « 1  x  4 » являются формами от x . Напротив, предложения:« x  2 », «для любого x выполняется x  2 », «существует такое x , что1  x  4 » не являются формами от x , так как после подстановки вместо x конкретного числа первое предложение не будет являться высказыванием, а подстановка вместо x конкретного числа в другие двапредложения нарушает их смысл, т.е. такая подстановка неправомерна.Обозначим форму от x через P(x) .

Сформулируем теперь интуитивный принцип абстракции. Любая форма P(x) определяет некотороемножество A , состоящее из тех и только тех предметов a , для которыхP(a) – истинное предложение. При этом обозначаем A  {x | P( x)}.Пример 1.6. {x | « x – натуральное нечетное число, меньшее9»}={1,3,5,7}.Следующий пример иллюстрирует несовершенство интуитивныхпредставлений о множествах. Заметим, что для множества   {x | x  x} выполняется    , а для множества  выполняется   , т.е для любого множества возможны обе ситуации.Пример 1.7 (Парадокс Рассела). Пусть N  {x | x  x} .

Возможныдва случая: 1) N  N , и тогда по определению N выполняется N  N ;52) N  N , и тогда по определению N выполняется N  N , т.е. в любомслучае приходим к противоречию.Таким образом, теория множеств в интуитивном изложении является противоречивой. Между тем, если в ходе данного рассуждения невыходить за пределы некоторого конкретного множества U (например,являющегося предметной областью какого-нибудь классического раздела математики, исследование которого никогда не приводило к противоречиям, или даже доказана непротиворечивость системы аксиом, накоторой базируется указанный раздел), т.е. предполагать, что{x | P( x)}  {x | x U , P( x)}, то при удачном выборе U мы можем избежать противоречий. При этом множество U называется универсальным для данного рассуждения. Всюду далее будем предполагать, чтоуниверсальное множество U выбрано, при этом U   .Для любого множества A  U обозначим 2 A  {B | B  A}.Пример 1.8.

Пусть A  {1,2,3}. Тогда 2 A  {, A,{1},{2},{3},{1,2},{1,3},{2,3}}.Утверждение 1.1. Если | A | n, то | 2 A | 2| A|  2 n.Доказательство. Пусть A  {a1 ,..., an }. Произвольное подмножество B  A есть результат заполнения n ячеек: первая ячейка соответствует элементу a1 , вторая – элементу a 2 и т.д., n -я ячейка – элементу a n . Каждая ячейка может быть заполнена соответствующим элементом или нет (т.е. имеются две возможности для каждой ячейки) независимо от других ячеек. Тогда общее число возможностей для заполнения совокупности из n ячеек выражается формулой 2 n (перемножаем число вариантов для каждой из ячеек n раз).Операции над множествами.

Введем следующие двухместныеоперации: A  B  {x | x  A или x  B} – объединение множеств A иB ; A  B  {x | x  A, x  B} – пересечение множеств A и B ; A \ B  {x | x  A, x  B} – относительное дополнение множества B до множества A ; A  B  ( A \ B)  ( B \ A) – симметрическая разность мно6жеств A и B , а также одноместную операцию A  U \ A – абсолютноедополнение множества A . Для упрощения записи различных выражений в алгебре множеств последняя операция считается самой «сильной», т.е. выполняемой в первую очередь.Основные тождества алгебры множеств. Для любых множествA , B , C справедливы равенства:1.

A  B  B  A (коммута1 . A  B  B  A (коммутативность объединения);тивность пересечения);2. A  ( B  C )  ( A  B)  C2 . A  ( B  C )  ( A  B)  C(ассоциативность объединения);3. A  ( B  C )  ( A  B)  ( A  C )(ассоциативность пересечения);(дистрибутивность объединенияотносительно пересечения);4. A  A  A (идемпотентностьобъединения);(дистрибутивность пересеченияотносительно объединения);4 . A  A  A (идемпотентность пересечения);3. A  ( B  C )  ( A  B)  ( A  C )5. A  A  U ;5. A  A  ;6.

A    A;6 . A    ;7. A  U  U ;7 . A  U  A;8. A  B  A  B (закон де8. A  B  A  B (закон деМоргана);9. A  ( A  B)  A (закон по-Моргана);глощения);поглощения);9 . A  ( A  B)  A (закон10. ( A  B)  ( A  B )  A10. ( A  B)  ( A  B )  A(закон расщепления);(закон расщепления);11. A  A;12.

A \ B  A  B ;13. A  B  ( A  B) \ ( A  B)  ( A  B)  ( A  B).Тождества 1, 1, 2, 2 , 4–7, 4  7 , 9, 9 , 11 следует признать очевидными. Докажем тождество 3. Для любого x  U имеем:7x Ax  A  (B  C)   x  A  x  B  C  x  B, x  C  x  A  B, x  A  C  x  ( A  B)  ( A  C).С другой стороны, для любого x  U имеем:x  ( A  B)  ( A  C)  x  A  B, x  A  C x A  x  A  ( B  C ). x  A  x  B, x  C  x  B  C Докажем тождество 3. Для любого x  U имеем:x  A  ( B  C)  x  A, x  B  C  x  A,xB  x A B x  B  x  C  x  A  C   x  ( A  B)  ( A  C).С другой стороны, для любого x  U имеем:x  A  B  x  A, x  Bx  ( A  B)  ( A  C )   x  A  B  x  A  C  x  A, x  C  x  A, x  B  C  x  A  ( B  C ).Докажем тождество 8.