Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств

Организационные вопросы Лектор – Романовский Иосиф Владимирович, профессор кафедр исследования операций и информатики. Курс читается весь год по 1 разу в неделю. Во втором семестре упражнения – 1 раз в две недели. В первом семестре зачет, во втором экзамен.

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

Дополнительный материал Комплекс DA_Demo демонстрационных программ по отдельным темам курса. Можно написать такую программу и получить отлично на экзамене. Но это дело не простое.

Программа 1-го семестра Немного теории множеств Комбинаторика Элементы теории вероятностей Строки и работа с ними Сжатие и защита информации Поиск и организация информации

Некоторые понятия теории множеств Вам должны быть знакомы понятия Множество Элемент множества Пересечение множеств Объединение множеств Разность множеств Симметрическая разность множеств Пустое множество Мощность множества – число элементов в нем (для конечных множеств)

Запись введенных обозначений aA A B A\B A B A= |A| $a\in A$ $a\notin A$ $A\subset B$ $A\cap B$ $A\cup B$ $A\setminus B$ $A\Delta B$ $A=\nothing$ $|A|$

Объяснение правого столбца Тексты, записанные в правом столбце таблицы, - это условная запись соответствующих формул, применяемая в специальном языке для набора научных текстов. Этот язык и его программная поддержка были разработаны знаменитым американским математиком и программистом Дональдом Эрвином Кнутом (Donald E. Knuth). Язык называется TeX. Вы обязательно должны будете им овладеть.

Прочтите и поймите тексты Говорят, что множества $A$ и $B$ дизъюнктны, если $A\cap B=\nothing$. Для любых $A$ и $B$ справедлива следующая формула $|A\cap B|+|A\cup B|=|A|+|B|$. Для любых $A$, $B$ и $C$ справедлива формула $(A\cap C)\cup(B\cap C)=(A\cup B)\cap C$. Множество целых чисел от $k$ до $l$, где $k\leq l$, мы будем обозначать через $k:l$. (Здесь введено новое обозначение: $\leq$ используется для символа (less or equal).) Таким образом, $1:37 \cup 30:60 = 1:60$. Напишите, чему равны $1:37\cap 30:60$ и $1:37\Delta 30:60$.

Новые понятия Декартово или прямое произведение множеств ( это портрет Рене Декарта – Rene Descartes ) Разбиение множества

Прямое произведение множеств Пусть заданы два (конечных) множества A и B. Прямым произведением этих множеств называется множество всевозможных пар {(a,b)}, где a пробегает все множество A, а b пробегает все множество B. Можно это записать так AB= {(a,b) | aA, bB} Или в ТеХе $A\times B=\{(a,b)\,|\,a\in A,b\in B\}$ Очевидно, что равенство AB= BA верно не всегда.

Пример 1. Шахматная доска Множество клеток шахматной доски можно рассматривать как прямое произведение множества столбцов {a,b,c,d,e,f,g,h} и множества строк 1:8

Пример 2. Колода игральных карт в 52 листа Колода игральных карт является произведением множества мастей {} на множество значений {A,K,D,J,T,9,8,7,6,5,4,3,2}. При добавлении джокеров это свойство теряется – расширенная колода в произведение двух множеств не раскладывается.

Пример 3. Множество секунд в минуте Множество 60 секунд одной минуты можно представить как произведение множества 0:5, задающего десятки секунд, и множества 0:9, задающего единицы внутри десятки. Таким образом пара (3,7) определяет 37-ю секунду минуты, если считать от нулевой секунды. Аналогично можно описывать множество минут в часе, а множество часов в сутках так не описать. Можно только разбить сутки на две половины.

Еще о примере 3 Отметим еще, что если на множествах A и B заданы упорядочения, то на их произведении C=AB естественно возникает еще и упорядочение: предшествование пары (a,b) паре (a,b) означает, что либо a предшествует a в упорядочении множества A, либо a = a, но b предшествует b в упорядочении множества B. Такое упорядочение называется лексикографическим. Дальше мы будем рассматривать более общее определение лексикографического упорядочения.

Продолжение примера 3 Если на множествах A = 0:9 и B = 0:5 заданы нумерации, то на их произведении C=AB естественно возникает нумерация #C(a,b)=#B(b)|A|+#A(a). Можно считать, что у нас получилась позиционная система счисления с двухзначными числами: A – множество цифр младшего разряда, а B – старшего разряда.

Мощность произведения множеств Теорема. Мощность произведения двух множеств равна произведению их мощностей. Доказательство прямо следует из определения произведения чисел.

Произведение нескольких множеств Аналогично предыдущему можно определить произведение любого нумерованного набора конечных множеств A 1, A 2, …, A k. A 1A 2… A k = {(a 1, a 2, …, a k )| a i A i, i1:k} Сомножители в произведении могут быть одинаковыми. Как и раньше, | A 1A 2… A k |= i1:k |A i |. Как и раньше, если все множества упорядочены, на их произведении можно определить лексикографический порядок. Попробуйте его определить сами.

Особый случай произведения Пусть B=0:1. Множество B k – это множество последовательностей из нулей и единиц длины k. Очевидно, что |B k |=2 k. Вы, конечно, уже знаете, что с помощью нулей и единиц представляются целые числа и что память компьютера состоит из элементов, каждый из которых хранит нуль или единицу. На следующей лекции мы будем заниматься всевозможными трактовками этого объекта.

Цилиндрические множества Пусть заданы два непустых множества A и B, и C=AB. Пусть PA. Множество R=PB называется цилиндрическим.

Разбиения Пусть задано множество A. Совокупность непустых множеств A ={A i } i1:k, которые попарно дизъюнктны и объединение которых равно A, называется разбиением A. Пример. Множество A={ a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,s,t,u,v,w,x,y,z } разбито на три подмножества – красных, синих и черных букв. Эта система множеств составляет разбиение A.

Сравнение разбиений Пусть задано множество S и два его разбиения A ={A i } i1:k и B ={B j } j1:m. Будем говорить, что разбиение B мельче разбиения A, и писать B A, если для любого B j, j1:m, найдется такое A i, которое содержит B j полностью. (Мы можем сказать также, что A крупнее B ). Некоторые разбиения могут быть несравнимы, ни одно из двух не будет мельче другого. Каждое разбиение мельче и одновременно крупнее самого себя.

Произведение разбиений Пусть снова задано множество S и два его разбиения A ={A i } i1:k и B ={B j } j1:m. Разбиение C ={C r } r1:n называется произведением разбиений A и B, если оно является самым крупным из разбиений, которые мельче и A и B. Такого разбиения может и не существовать. Разбиения, о которых идет речь, не все сравнимы между собой. Но оказывается, что самое крупное из них, существует.

Теорема о произведении разбиений Произведение C разбиений A и B существует. Доказательство. Мы просто предъявим разбиение C, а затем докажем, что это оно и есть. Образуем набор множеств C ={C ij =A iB j } i1:k, j1:m Покажем, что множества C ij попарно дизъюнктны и их объединение равно S. Так что, если бы все эти множества были непусты, то C было бы разбиением. Дизъюнктность. Возьмем два различных множества C ij =A iB j и C ij =A iB j, так что либо i i, либо j j. Рассмотрим первый случай, второй аналогичен. Так как A i A i, то они не пересекаются ( A - разбиение), значит не пересекаются и их подмножества C ij и C ij.

Продолжение доказательства Объединение равно S. Вычислим это объединение. i1:k, j1:m C ij = i1:k ( j1:m A iB j ) = i1:k (A i j1:m B j ) = i1:k (A i S) = S Покажем теперь, что для любого разбиения D, D A, D B, выполняется D C. Возьмем какой-либо элемент D s разбиения D. Из того, что D A, следует, что найдется A i, D s A i. Аналогично, найдется B i, D s B j. Значит, нашлось C ij, D s C ij, и все доказано. Осталось выкинуть из построенного набора пустые множества, и он станет искомым разбиением.

Экзаменационные вопросы 1. Прямое произведение множеств. 2. Разбиения множеств. Произведение разбиений.

Упражнения 1. Пусть A={a,c,e,h,k}, B={b,c,d,e,h}. Найдите A B, A B, A\B, A B. 2. Найдите A B. 3. Сколько элементов содержит множество A B B A B B ? 4. Пусть разбиения A и B заданы раскраской множества S: {a,b,c,d,e,f,g,h} и {a,b,c,d,e,f,g,h}. Постройте произведение этих разбиений.