- •Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «кемеровский государственный университет»
- •Кафедра автоматизации исследований
- •И технической кибернетики
- •Дискретная математика
- •Содержание
- •Глава 1. Теория множеств. Дискретная теория вероятности......5
- •Глава 2. Теория графов.....................................................................53
- •Глава 3. Дискретные структуры: конечные автоматы, коды...76
- •Глава 4. Алгебра логических функций..........................................88
- •Глава 5. Логика высказываний и логика предикатов..............109
- •Глава 6. Схемы переключателей. Комбинационные схемы...................................................................................................123
- •Глава 1. Теория множеств. Дискретная теория вероятности
- •Множества и операции над ними
- •Упражнения
- •1.2. Векторы и прямые произведения множеств. Проекция вектора на ось
- •Упражнения
- •1.3. Комбинаторика Правило суммы
- •Правило произведения
- •Число размещений без повторений
- •Число размещений с повторениями
- •Число перестановок без повторений
- •Число сочетаний без повторений
- •Упражнения
- •1.4. Введение в дискретную теорию вероятностей
- •Свойства элементарных событий:
- •Соотношения между событиями:
- •Свойства операций над событиями:
- •Упражнения
- •1.5. Соответствия и функции
- •Взаимно однозначные соответствия и мощность множеств
- •Упражнения
- •1.6. Отношения
- •Способы задания бинарных отношений
- •Свойства бинарных отношений
- •Отношение эквивалентности
- •Отношение порядка
- •Лексико-графический порядок.
- •Упражнения
- •1.7. Операции и алгебры
- •Свойства бинарных алгебраических операций
- •1.8. Гомоморфизм и изоморфизм алгебр
- •Полугруппы, группы, решетки
- •Упражнения
- •Глава 2. Теория графов
- •2.1. Основные определения, способы задания, основные классы, изоморфизм графов
- •Способы задания графа
- •Степени вершин графа
- •Части, суграфы и подграфы
- •Операции над частями графа
- •Графы и бинарные отношения
- •Упражнения
- •Среди пар графов, изображенных на рисунке, указать пары изоморфных графов и пары неизоморфных графов. Ответ обосновать.
- •Маршруты, цепи и циклы. Расстояния, диаметры, центры. Обходы. Разделяющие множества и разрезы
- •Упражнения
- •Деревья, их свойства. Характеристические числа графов. Сети
- •Упражнения
- •Глава 3. Дискретные структуры: конечные автоматы, коды
- •3.1. Машина Тьюринга
- •Упражнения
- •Основы теории кодирования
- •Упражнения
- •Глава 4. Алгебра логических функций
- •4.1. Основные определения
- •Упражнения
- •4.2. Эквивалентные преобразования
- •Упражнения
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы
- •Упражнения
- •4.4. Дизъюнктивные нормальные формы и импликанты
- •Упражнения
- •4.5. Минимизация днф. Тупикова днф
- •Упражнения
- •4.6. Алгебра Жегалкина
- •Упражнения
- •4.7. Двойственность в алгебре логики. Самодвойственные функции
- •Принцип двойственности
- •Упражнения
- •4.8. Функциональная полнота систем
- •Упражнения
- •Глава 5. Логика высказываний и логика предикатов
- •5.1. Логика высказываний
- •Алгебра логики
- •Исчисление высказываний
- •Упражнения
- •5.2. Логика предикатов
- •Упражнения
- •Глава 6. Схемы переключателей. Комбинационные схемы
- •Схемы переключателей
- •Комбинационные схемы
- •Упражнения
- •Литература
- •650043, Кемерово, ул. Красная, 6.
Способы задания бинарных отношений
Для задания бинарных отношений можно использовать любые способы задания множеств (например, список пар, для которых данное отношение выполняется).
Бинарные отношения, определяемые на конечном множестве обычно задаются списком (пар элементов), бинарной матрицей, или ориентированным графом.
Матрица бинарного отношения, заданного на множестве это квадратная матрица С порядка n, в которой (где i – номер строки, j - номер столбца) определяется так:
Для любого множества М отношение Е, заданное единичной матрицей, в которой по главной диагонали стоят “1”, а остальные “0” – называется отношением равенства.
Поскольку отношения на М задаются подмножествами множества , для них можно определить те же операции, что и над множествами.
Например, отношение “находиться на разном расстоянии от начала координат” является дополнением отношения “находиться на одинаковом расстоянии от начала координат”. Отношение “ ” является объединением отношений “<” и “=”.
Определим еще одну операцию над множествами.
Отношение называется обратным к отношению R, если
.
Например, отношение “ ” обратное к отношению “ ”.
Из определения следует, что .
Свойства бинарных отношений
Отношение R на М называется рефлексивным, если для любого выполняется . Главная диагональ матрицы такого отношения содержит только единицы.
Отношение R на М называется антирефлексивным, если ни для какого не выполняется. Главная диагональ матрицы отношения содержит только нули.
Отношение R на М называется симметричным, если для любой пары из aRb следует bRa (иначе говоря, для любой пары отношение R выполняется в обе стороны или не выполняется вообще). Матрица симметричного отношения – симметрична относительно главной диагонали: для всех i, j, т.е.
Отношение R на М называется антисимметричным, если из того, что (из aRb следует bRa) следует (т. е. ни для каких различных элементов множества М отношение R не выполняется). Матрица антисимметричного отношения не имеет ни одного симметричного относительно главной диагонали единичного элемента.
R симметрично тогда и только тогда, когда .
Отношение R на М называется транзитивным, если для любых a, b, c из множества М из того, что выполняется aRb и bRc следует, что aRc.
Для любого отношения R отношение , называемое транзитивным замыканием R, определяется следующим образом:
, если в М существует цепочка из n элементов , в которой между соседними элементами выполнено отношение R:
Если R – транзитивно, то по определению транзитивного замыкания: .
Отношение эквивалентности
Отношение R на М называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Равенство – это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из Е (т. е. любой единицы на диагонали матрицы Е) оно перестает быть рефлексивным и, следовательно, уже не является эквивалентным.
Пусть на множестве М задано отношение эквивалентности R. Осуществим построение классов эквивалентности, на которые разбивается множество М этим отношением.
Выберем элемент и образуем класс (подмножество М) , состоящий из и всех элементов, эквивалентных ; затем выберем элемент , и образуем класс , состоящий из и всех элементов, эквивалентных и т. д. Получится система классов (возможно бесконечная) такая, что любой элемент из М входит хотя бы в один класс, т. е. .
Эта система обладает свойствами:
1) она образует разбиение, т. е. классы попарно не пересекаются;
2) любые два элемента из одного класса эквивалентны;
3) любые два элемента из разных классов неэквивалентны.
Мощность системы классов эквивалентности называется индексом разбиения.
С другой стороны, любое разбиение М на классы определяет некоторое отношение эквивалентности.