- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
Замечание.
Понятие разбиения множества на классы тесно связано с понятием отображения, а именно:
Пусть ƒ – отображение множества А в множество В, то есть ƒ: . Множество элементов А, образы которых в В совпадают, образуют класс элементов, то есть возникает некоторое разбиение множества А.
Пусть В – совокупность тех классов, на которые разбито множество А. Ставя в соответствие каждому элементу а А тот класс ( то есть элемент из В), к которому а принадлежит, то есть g: a Ка, получаем отображение А на множество В.
Примеры.
-
Пусть ƒ – проекция плоскости хy на ось х. Прообразы точек оси х – вертикальные прямые. Следовательно, этому отображению отвечает разбиение плоскости на параллельные прямые.
-
Разобьём все точки трехмерного пространства на классы, объединив в один класс точки, равноудаленные от начала координат. Каждый класс представляет собой сферу некоторого радиуса. Совокупность всех этих классов можно отождествить с множеством всех точек, лежащих на луче [0, ), то есть разбиению трёхмерного пространства на концентрические сферы отвечает отображение этого пространства на полупрямую ƒ: rei r (двумерный случай) или ƒ: r(i cos + j cos + k cos) r(трёхмерный случай).
-
Объединим в один класс все действительные числа с одинаковой дробной частью. Этому разбиению отвечает отображение прямой линии на отрезок [0, 1): ƒ: d.k 0.k.
-
Упорядоченные множества. Изоморфизм теории множеств.
Определение.
Пусть М – произвольное множество, – бинарное отношение, определяемое некоторым множеством . Это отношение называется частичной упорядоченностью, если оно удовлетворяет условиям:
-
рефлексивности: ;
-
транзитивности: из ;
-
антисимметричности: из
Частичную упорядоченность обозначают символом .
Определение.
Множество, в котором задана некоторая частичная упорядоченность, называется частично упорядоченным.
Примеры.
Всякое множество можно тривиальным образом рассматривать как частично упорядоченное, если положить , то есть за частичную упорядоченность всегда можно принять отношение тождества .
Пусть М – множество всех непрерывных функций на отрезке . Положим . Это будет частичная упорядоченность функций из .
Множество всех подмножеств некоторого множества М частично упорядочено по включению, то есть означает .
Множество всех натуральных чисел частично упорядочено, если означает “b делится без остатка на а”.
Определение.
Элемент а называется максимальным, если из следует, что .
Определение.
Элемент а называется минимальным, если из следует, что .
Определение.
Частично упорядоченное множество, для любых двух точек а, b которого найдется следующая за ними точка с , называется направленным.
Определение.
Пусть:
-
М и – частично упорядоченные множества;
-
.
-
Отображение сохраняет порядок, то есть если из , где .
Тогда.
Отображение называется изоморфизмом частично упорядоченных множеств М и , если оно
-
биективно (существует взаимооднозначное соответствие между элементами множеств М и );
-
соотношение .
Пример.
Пусть
М – множество натуральных чисел, частично упорядоченное по “делимости”;
— множество натуральных чисел, упорядоченное естественным образом, то есть , если – неотрицательное число, то есть .
Тогда отображение , то есть ставящее числу n его само:
-
сохраняет порядок;
-
не является изоморфизмом.
Замечание.
Отношение изоморфизма между частично упорядоченными множествами представляет собой отношение эквивалентности (рефлексивность, транзитивность, симметричность). Следовательно, какое-либо множество частично упорядоченных множеств можно разбить на классы изоморфных между собой подмножеств.
Определение.
То общее, что присуще любым двум изоморфным между собой частично упорядоченным множествам, называется порядковым типом.
Определение.
Пусть
М – частично упорядоченное множество;
;
не выполняется ни одно из соотношений и .
Тогда а и b называются несравнимыми элементами.
Определение.
Если в частично упорядоченном множестве М несравнимых элементов нет, то множество М называется упорядоченным (линейно упорядоченным, совершенно упорядоченным), то есть если оно:
частично упорядочено;
для имеет место либо .
Замечания.
Всякое подмножество упорядоченного множества само упорядочено.
Так как упорядоченность есть частный случай частичной упорядоченности, то можно говорить о порядковом типе упорядоченного множества.
Примеры.
Пусть = – множество натуральных чисел с естественным отношением порядка. Его порядковый тип обозначают .
Если два частично упорядоченных множества изоморфны между собой, то они, конечно, имеют одинаковую мощность, так как изоморфизм – это биекция. Следовательно, можно говорить о мощности, отвечающей данному порядковому типу, например, типу отвечает мощность . Однако обратное неверно, так как множество данной мощности может быть упорядочено, вообще говоря, многими разными способами.
Порядковый тип линейно упорядоченного конечного множества однозначно определяется числом n его элементов и обозначается n.
Для счётного множества натуральных чисел возможен такой тип: то есть любое чётное число следует за любым нечётным, при этом чётные и нечётные числа упорядочены по возрастанию.