- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
Определение.
Каждый раз, когда некоторое множество М представлено тем или иным способом как сумма попарно непересекающихся подмножеств, говорят о разбиении множества М на классы.
Обычно разбиения связаны с признаком, по которому элементы множества объединяются в классы.
Ещё примеры:
множество всех треугольников можно разбить на
а) классы равных между собой треугольников;
б) классы равновеликих треугольников и т.д.
все функции от х можно разбить на классы, собирая в один класс функции, принимающие в данной точке одинаковые значения.
Признаки могут быть самыми разнообразными, но их выбор не произволен.
Определение.
Бинарное отношение над множеством М – это подмножество множества М М всех упорядоченных пар из М.
Определение.
Бинарным отношением между двумя множествами называется соответствие элементов одного из них элементам другого.
Замечание.
Вместо принадлежности пары (х, y) бинарному отношению , то есть вместо (х, y) часто используют инфиксную запись, то есть х y.
Определение.
Бинарное отношение над М называется рефлексивным, если для всех х М имеем: (х, х) или, другими словами,
хх для х М.
Определение.
Бинарное отношение над М называется транзитивным, если из (х, y) и (y, z) (x, z) или, в инфексной записи:
если хy и yz, то хz.
Определение.
Для каждого бинарного отношения над М определено обращение Т (обратное отношение), а именно:
(х, y) Т (y, x) .
Определение.
Бинарное отношение над М называется симметричным, если Т = , или, в инфиксной записи: если хy, то yx.
Определение.
Бинарное отношение называется отношением эквивалентности, если оно:
-
рефлексивно;
-
транзитивно;
-
симметрично.
Теорема.
Для того, чтобы бинарное отношение позволяло разбить множество М на классы необходимо и достаточно, чтобы было эквивалентным.
Доказательство:
Докажем необходимость утверждения.
Пусть имеется множество М и его разбиение на классы, то есть пусть а и b находятся в одном классе и связаны отношением . Легко видеть, что в классе Ка выполняется:
аа;
если аb и bc, то ас;
если аb (а это так), то ba,
то есть отношение является эквивалентным.
Докажем достаточность.
Пусть
1. — отношение эквивалентности между элементами множества М;
2. Ка — класс элементов х М, эквивалентных элементу а, то есть xa, где – отношение эквивалентности.
Так как — отношение эквивалентности, то в силу рефлексивности а Ка. Докажем, что два класса Ка и Кb либо совпадают, либо не пересекаются. Пусть с Ка и с Кb, то есть
са (3)
и
сb. (4)
В силу симметричности из (3)
ас (5)
и, учитывая (5) и транзитивность , имеем:
аb . (6)
Для х Ка по определению имеем
ха . (7)
Учитывая (6): аb и свойство транзитивности из (6) и (7) имеем хb, то есть х Кb. Аналогично доказывается, что y Кb одновременно принадлежит и Ка. Таким образом, два класса Ка и Кb, имеющих хотя бы один общий элемент, совпадают между собой. Итак, получено разбиение множества М на классы по заданному отношению эквивалентности, что и требовалось доказать.