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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)«МАИ»Кафедра «Математическая кибернетика»В.Н. НЕФЕДОВАЛГЕБРА МНОЖЕСТВ, БИНАРНЫЕОТНОШЕНИЯ В ПРИМЕРАХ И ЗАДАЧАХУчебное пособиеУтвержденона заседании редсовета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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги