- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
Замечания.
Иногда бесконечное множество оказывается эквивалентным своей истинной части, например:
-
Натуральные числа эквивалентны множеству всех целых чисел.
-
Натуральные числа эквивалентны множеству рациональных чисел.
-
На интервале столько же точек, сколько и на всей прямой.
Теорема.
Всякое бесконечное множество эквивалентно некоторому своему собственному подмножеству.
Доказательство:
Согласно известной теореме: из всякого бесконечного множества М можно выбрать счётное подмножество. Пусть – такое подмножество. Разобьём множество А на два счётных подмножества: и .
Между А и можно установить биекцию:
, где .
Рассмотрим множества:
1. ; 2. .
Установив взаимно однозначное соответствие между А и , легко продолжить это соответствие на рассматриваемые множества, отнеся каждому элементу множества сам этот элемент. Таким образом, установлено взаимнооднозначное соответствие между множествами М и . Теорема доказана.
Теорема Кантора.
Для любой последовательности {} действительных чисел из любого интервала I существует точка p из I такая, что при всех n.
Доказательство:
много способов доказательства этой теоремы. Рассмотрим один из них.
Возьмем отрезок такой, что . Затем берём отрезок такой, что . Продолжая процесс по индукции, выберем в отрезок такой, что . Полученная последовательность вложенных отрезков имеет непустое пересечение. Если , то и при всех n, что и требовалось доказать.
Следствие из теоремы Кантора.
Ни один интервал не является счётным множеством.
Впервые доказательство нёсчетности этого множества Кантор привёл в 1873 г.
Примеры несчётных множеств.
-
Множество всех точек любого отрезка или интервала .
-
Множество всех точек на прямой.
-
Множество всех точек плоскости, пространства, поверхности сферы, точек, лежащих внутри сферы и т.д.
-
Множество всех прямых на плоскости.
-
Множество всех непрерывных функций одного или нескольких переменных.
-
Аксиома выбора. Теорема Цермело.
Аксиома выбора, называемая также аксиомой Цермело, возникшая в рамках наивной теории множеств, восходящей к Кантору и Цермело, вместе с другими вопросами, такими как континуум-гипотеза, то есть вопрос о совпадении мощности континуума с первой несчётной мощностью , привела к многочисленным работам по математической логике и основаниям математики. Были построены аксиоматические теории множеств Гёделя-Бернайса и Цермело-Френкеля, в которых были установлены непротиворечивость и независимость аксиомы выбора.
При сравнении вполне упорядоченных множеств по мощности возникает вопрос: можно ли всякое множество вполне упорядочить каким-либо образом. Положительный ответ означал бы, в частности, что несравнимых мощностей нет.
Теорема Цермело.
Каждое множество может быть вполне упорядочено.
Аксиома выбора.
Пусть А – некоторое множество индексов и пусть для каждого задано некоторое произвольное множество . Тогда можно построить функцию на А, относящую каждому некоторый элемент из соответствующего , то есть можно составить некоторое множество, выбрав из каждого по одному и только одному элементу (см. рис. 1.13).
Рис. 1.13. Иллюстрация аксиомы выбора.
Замечание.
Теорема Цермело эквивалентна аксиоме выбора. Так, если предположить, что каждое из множеств вполне упорядочено, то для построения функции , существование которой утверждается аксиомой выбора, достаточно в каждом взять первый элемент.
Сформулируем еще некоторые предложения, эквивалентные аксиоме выбора.
Определение.
Пусть М – частично упорядоченное множество. Всякое его подмножество А, в котором любые два элемента сравнимы между собой в смысле введенной в М частичной упорядоченности, называется цепью.
Определение.
Цепь называется максимальной, если она не содержится в качестве собственного подмножества ни в какой другой цепи, принадлежащей М, где М – частично упорядоченное множество.
Определение.
Пусть М – частично упорядоченное множество. Элемент называется верхней гранью подмножества , если любой элемент подчинен , то есть .
Определение.
Пусть М – частично упорядоченное множество. Если множество верхних граней А подмножества имеет наименьший элемент , то называется точной верхней гранью множества .
Определение.
Пусть М – частично упорядоченное множество. Элемент называется нижней гранью подмножества , если любой элемент следует за , то есть .
Определение.
Пусть М – частично упорядоченное множество. Если множество нижних граней А множества имеет наибольший элемент , то называется точной нижней гранью множества .
Определение.
Частично упорядоченное множество, всякое непустое конечное подмножество которого обладает точной верхней гранью и точной нижней гранью, называется решеткой, или структурой.
Теорема Хаусдорфа.
В частично упорядоченном множестве всякая цепь содержится в некоторой его максимальной цепи.
Лемма Цорна.
Если всякая цепь в частично упорядоченном множестве М имеет верхнюю грань, то всякий элемент из М подчинен некоторому максимальному.
-
Примеры задач и упражнений.
Пример 1. Задать различными способами множество А всех четных чисел 2, 4, 6, …., не превышающих 1000.
Решение. 1. Перечислением: А={2, 4, 6, 8, 10, …, 998, 1000};
Описанием: А={x|xN и х/2N, N1000}; (N – множество натуральных чисел 1, 2, 3, ….)
Порождающей процедурой: а) 2А; б) если хА, то (х+2)А;
в) х1000.
Пример 2. Верно ли, что: 1). {{1,2}, {2,3}}={1,2,3}? 2).{{1,2}}={1,2}?
Решение. 1). Нет, так как элементами первого множества являются подмножества {1,2} и {2,3}, а второго – элементы 1,2,3.
2). Нет, так как первое множество одноэлементное, состоящее из одного элемента - подмножества, а второе имеет два элемента 1 и 2.
Пример 3. Перечислить элементы следующих множеств:
1). А={a|aB, B={1,2,3}};
2). A={a|aB, B={1,2,3}}.
Решение. 1). Так как аВ, а В – трехэлементное множество, то имеется 23=8 подмножеств: А={{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, }.
2). Так как аВ, то А=В={1,2,3}.
Пример 4. Доказать, используя тождества алгебры множеств, что
Решение. Используя тождества алгебры множеств, получаем
Пример 5. Упростить выражение
Решение. Используя законы и тождества алгебры множеств, получаем:
Пример 6. Построить диаграммы Венна для множеств А, В, С, DI, если АВСD, , .
Решение. Одно из возможных решение может быть представлено следующей диаграммой:
Пример 7. Опрос 100 студентов, изучающих иностранные языки, показал: английский язык изучают 29 студентов, немецкий –30, французский –9, только французский - 1, английский и немецкий – 10, немецкий и французский – 4, все три языка – 3 студента. Сколько студентов не изучают ни одного языка? Сколько студентов изучают только немецкий язык? При решении использовать диаграммы Венна.
Решение. Введем обозначения: I – множество всех опрошенных студентов; А – множество студентов, изучающих английский язык; Н – множество студентов, изучающих немецкий язык; Ф – множество студентов, изучающих французский язык (См. диаграмму Эйлера-Венна на рис. 1.1)
По условию задачи очевидно, что =3, тогда =4-3=1; 10-3=7. В таком случае только немецкий язык изучают 30-7-3-1=19 студентов.
Из условия задачи также следует, что 9-1-1-3=4, а поэтому только английский язык изучают 29-4-3-7=15 студентов. Тогда число студентов, не изучающих ни одного языка, будет равно
Рис. 100-(1+1+3+4+7+15+19)=50 студентов.
Пример 8. Доказать аналитически: .
Решение. Введем обозначения: ; .
а). Пусть , тогда имеет место либо , либо . Если , тогда и и в таком случае и или, что тоже самое, , т.е. . Если , тогда можно записать и одновременно. Откуда, очевидно, и в этом случае , т.е. .
Итак, если , то . Следовательно,
б). Пусть . Тогда и . Если , то либо либо Но если , то (см. п.а) . Если же , тогда Из последнего следует, что и т.е. , или, что тоже самое, , т.е. .
Итак, если то . Следовательно, .
Из пп. а и б следует, что и . Следовательно, D=E, т.е. . Тождество доказано.
Пример 9. Доказать, что для произвольных множеств А и В имеет место соотношение .
Решение. Для доказательства используем метод от противного, т.е. предположим, что . Тогда
Из АВ если аА, то аВ. (1)
С другой стороны, из существует такой элемент а, что и . (2)
Но с учетом (1) и (2)
=, т.е. получили противоречие.
Следовательно, предположение ложно и поэтому , т.е. .
Аналогично можно показать, что и, значит, , что и требовалось доказать.
Пример 10. {(1,2), (2,2), (Иванов, Петров)} есть функция с областью определения {1, 2, Иванов} и областью значений {2, Петров}.
Пример 11. {(1,2), (1,3), (2,5)} не является функцией, т.к. различные элементы (1,2) и (1,3) имеют одинаковую первую координату.
Пример 12. Множество {(a,b), (c,b), (e,d), (k,m)} есть функция, а подмножество этого множества {(a,b), (e,d)} является сужением этой функции на множество {a,e}.
Отображение представляет собой отображение множества Х в самого себя и определяется парой (Х, R), где . В этом случае для обозначения данного отображения используется термин отношение и вводят специальную символику: yRx – у находится в отношении R к х.
Подмножество называется n-местным отношением между А1, А2, …..An. Если n=2, то R называется бинарным отношением.
Пример 13. Множество {(3,4), (4,6), (7,9), (4,12)} будучи множеством упорядоченных пар натуральных чисел, есть бинарное отношение на N, где N – множество натуральных чисел.
Отношение R называется ():
рефлексивным, если для любого имеет место ;
антирефлексивным, если ни для какого не выполняется ;
симметричным, если для пары из aRb следует bRa;
антисимметричным, если из aiRaj и ajRai следует, что ai=aj;
транзитивным, если для любых a, b, c из aRb и bRc следует aRс.
Отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Обозначается символом .
Пример 14. Докажите, что отношение равенства «=» на любом множестве является отношением эквивалентности.
Решение. Действительно, для данного отношения выполняются свойства: рефлексивности (а=а); симметричности (а=в в=а); транзитивности [(а=в и в=с)а=с].
Отношением предпорядка на множестве А называется отношение , если оно рефлексивно и транзитивно.
Отношением порядка называется отношение, если оно рефлексивно, антисимметрично и транзитивно.
Отношением строгого порядка называется отношение, если оно антирефлексивно, антисимметрично и транзитивно.
Пример 15. Задано бинарное отношение R на множестве М={1, 2, 3, 4}. Является ли оно рефлексивным, симметричным, антисимметричным, транзитивным? Найти область определения R, область значений R, обратное отношение R-1, пересечение и объединение отношений R и R-1
R={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2), (4,3), (4,4).
Решение.
Отношение R, заданное на множестве М, называется рефлексивным, если для всякого х из этого множества хRх истинно. Заданное отношение не является рефлексивным, так как нет пар (2,2) и (3,3).
Отношение R, заданное на множестве M называется симметричным, если на этом множестве из xRy следует yRx. Заданное отношение не является симметричным, т.к., например, пара (1,2)R, а (2,1)R.
Отношение R, заданное на множестве M называется антисим-метричным, если на этом множестве из xRy и yRx следует x=y. Заданное отношение не является антисимметричным, так как ему принадлежат пары (1,4) и (4,1), но 14.
Отношение R, заданное на множестве M называется антирефлексивным, если для любого xRx ложно. Заданное отношение антирефлек-сивно, так как (уже было показано) нет пар (2,2) и (3,3).
Отношение R, заданное на множестве M называется транзитивным, если на этом множестве из xRy и yRz следует xRz. Заданное отношение является транзитивным, так как для любых двух пар (a,b) и (b,c) следует, что (a,c)R, где а, в, с М.
Областью определения отношения R называется множество R ={x| (у) xRy}. Следовательно, областью определения R является двухэлементное множество {1, 4}.
Областью значений отношения R называется множество R={y|(x) xRy}. Следовательно, областью значений является все множество М={1, 2, 3, 4}.
Обратным отношением для R называется отношение R-1={(y,x)|(x,y)R}.
Обратное отношение R-1={(1,1), (2,1), (3,1), (4,1), (1,4), (2,4), (3,4), (4,4)}.
Пересечение R и R-1 равно RR-1={(1,1), (4,1), (1,4), (4,4)}.
Объединение R и R-1 равно RR-1={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2), (4,3), (4,4), (2,1), (3,1)}.