Файл: Учебное пособие по изучению курса Дискретная математика для студентов направления 230100 Информатика и вычислительная техника.pdf

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ
ПЕРМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ
Кафедра Информационных технологий и автоматизированных систем
Викентьева О.Л., Соловьев А. Е., Файзрахманов Р. А.
ДИСКРЕТНАЯ МАТЕМАТИКА
Пермь 2007

2
Составители: Викентьева О.Л., Соловьев А. Е., Файзрахманов Р. А.
УДК 681.3
Учебное пособие по изучению курса «Дискретная математика» для студентов направления
230100 «Информатика и вычислительная техника» специальностей 230101
«Вычислительные машины, комплексы, системы и сети», 230101 «Автоматизированные системы обработки информации и управления», 075400 «Комплексная защита объектов информатизации» для дневной и заочной форм обучения.
Сост. Викентьева О.Л., Соловьев А. Е., Файзрахманов Р. А.
Рецензенты:
д.п.н., профессор кафедры Высшей математики ГУ ВШЭ ПФ Плотникова Е.Г.
(с) Пермскй государственный
Технический университет, 2007

3
Введение .................................................................................................................. 6 1. Теория множеств ................................................................................................ 7 1.1. Основные понятия теории множеств ......................................................... 7 1.1.1.Понятие множества ................................................................................ 7 1.1.2. Задание множеств .................................................................................. 7 1.1.4. Отношения принадлежности и включения ......................................... 7 1.1.5. Парадоксы теории множеств ................................................................ 8 1.1.6. Диаграммы Эйлера-Венна .................................................................... 9 1.2. Операции над множествами........................................................................ 9 1.3. Алгебра множеств ...................................................................................... 11 1.4. Графики....................................................................................................... 13 1.4.1. Понятие графика .................................................................................. 13 1.4.2. Свойства графиков .............................................................................. 14 1.5. Соответствия............................................................................................... 16 1.5.1. Понятие соответствия.......................................................................... 16 1.5.2. Свойства соответствий........................................................................ 16 1.6. Функции и отображения............................................................................ 18 1.7. Отношения .................................................................................................. 19 1.7.1. Понятие отношения ............................................................................. 19 1.7.2. Свойства отношений ........................................................................... 19 1.8. Отношения эквивалентности. Классы эквивалентности........................ 20 1.8.1. Понятие отношения эквивалентности ............................................... 20 1.8.2. Понятие класса эквивалентности ....................................................... 20 1.8.3. Свойства отношения эквивалентности.............................................. 21 1.8.4. Покрытия и разбиения множеств ....................................................... 21 1.9. Отношения порядка ................................................................................... 22 1.10. Решетки ..................................................................................................... 23 1.10.1. Основные определения...................................................................... 23 1.10.2. Понятие решетки. .............................................................................. 25 1.11. Мощность множеств ................................................................................ 29 1.11.1. Понятие мощности ............................................................................ 29 1.11.2. Сравнение мощностей....................................................................... 29 1.11.3. Мощность множества действительных чисел................................. 30
Контрольные вопросы ...................................................................................... 32 2. Алгебраические структуры.............................................................................. 34 2.1. Алгебраические структуры ....................................................................... 34 2.2. Свойства операций..................................................................................... 34 2.3. Алгебры с одной операцией...................................................................... 35 2.4. Алгебры с двумя операциями ................................................................... 36 2.5. Морфизмы................................................................................................... 38
Контрольные вопросы ...................................................................................... 40 3. Математическая логика.................................................................................... 41 3.1. Основные определения.............................................................................. 41

4 3.1.1. Понятие высказывания........................................................................ 41 3.1.2. Логические операции .......................................................................... 41 3.1.3. Булевы функции................................................................................... 44 3.1.4. Формулы ............................................................................................... 45 3.1.5. Равносильные формулы ...................................................................... 46 3.1.6. Подстановка и замена.......................................................................... 47 3.2. Формы представления высказываний ...................................................... 48 3.2.1. Дизъюнктивная и конъюнктивная нормальные формы................... 48 3.2.2. Совершенные нормальные формы..................................................... 49 3.2.3. Переход от ДНФ к КНФ и наоборот.................................................. 50 3.3. Минимизация сложных высказываний методом Квайна ....................... 50 3.4. Полные системы функций......................................................................... 51 3.4.1. Система функций {
} .................................................................. 51 3.4.2. Замкнутые классы................................................................................ 52 3.4.3. Функциональная полнота.................................................................... 53
Контрольные вопросы ...................................................................................... 55 4. Теория графов ..........................................................................Цель не найдена!
4.1. Основные определения.....................................................Цель не найдена!
4.2. Операции над графами .....................................................Цель не найдена!
4.3. Маршруты, цепи, циклы. Основные определения .........Цель не найдена!
4.4. Связность. ..........................................................................Цель не найдена!
4.5. Способы задания графов ..................................................Цель не найдена!
4.6. Приведение графа к ярусно-параллельной форме .........Цель не найдена!
4.7. Определение маршрутов с заданным количеством реберЦель не найдена!
4.8. Определение кратчайших путей ......................................Цель не найдена!
4.8.1. Алгоритм Шимбелла ..................................................Цель не найдена!
4.8.2. Алгоритм Дейкстры для определения кратчайшего путиЦель не найдена!
4.9. Деревья ...............................................................................Цель не найдена!
4.9.1. Основные понятия ......................................................Цель не найдена!
4.9.2. Задача об остове наименьшего веса..........................Цель не найдена!
4.10. Эйлеровы циклы..............................................................Цель не найдена!
4.11. Гамильтоновы циклы......................................................Цель не найдена!
4.12. Ядро графа .......................................................................Цель не найдена!
4.12.1 Внутренняя устойчивость графа ..............................Цель не найдена!
4.12.2 Внешняя устойчивость графа ...................................Цель не найдена!
4.13. Клики графа .....................................................................Цель не найдена!
4.14. Планарность графов........................................................Цель не найдена!
4. 15. Формула Эйлера .............................................................Цель не найдена!
4.16. Раскраска графа...............................................................Цель не найдена!
4. 17. Теорема Менгера............................................................Цель не найдена!
4.18. Теорема Холла.................................................................Цель не найдена!
Контрольные вопросы .............................................................Цель не найдена!
5 Теория автоматов......................................................................Цель не найдена!

5 5.1. Понятие автомата ..............................................................Цель не найдена!
5.2. Законы функционирования автоматов............................Цель не найдена!
5.3. Способы задания автоматов.............................................Цель не найдена!
5.3.1.
Таблицы переходов и выходов ..............................Цель не найдена!
5.3.2. Графы переходов и выходов......................................Цель не найдена!
5.4. Минимизация автоматов ..................................................Цель не найдена!
5.4.1. Классы эквивалентности состояний автомата .........Цель не найдена!
5.4.2. Процедура минимизации: ..........................................Цель не найдена!
5.4.3. Особенности минимизации автомата Мура .............Цель не найдена!
5.5. Переход от автомата Мили к автомату Мура.................Цель не найдена!
5.6. Переход от автомата Мили к автомату Мура.................Цель не найдена!
Контрольные вопросы .............................................................Цель не найдена!
6. Формальные языки и грамматики..........................................Цель не найдена!
6.1. Понятие формальной грамматики ...................................Цель не найдена!
6.2. Деревья вывода..................................................................Цель не найдена!
6.3. Классификация грамматик и языков по Хомскому .......Цель не найдена!
6.4. Примеры классификации языков и грамматик ..............Цель не найдена!
6.5. Распознаватели ..................................................................Цель не найдена!
6.6. Классификация распознавателей по типам языков .......Цель не найдена!
Контрольные вопросы .............................................................Цель не найдена!
Список литературы............................................................................................... 56

6
Введение
Данное пособие представляет собой конспективный учебник по дискретной математике и включает в себя следующие разделы: теория множеств, алгебраические структуры, математическая логика, теория графов,
теория автоматов, формальные грамматики. Пособие предназначено для студентов младших курсов направления «Информатика и вычислительная техника».
Дискретная математика является инструментарием для представления и обработки информации в компьютерах, а также алгебраических методов решения задач.
Дискретная математика предоставляет математический аппарат,
который помогает расширить возможности математического описания сложных систем. Далеко не все задачи, которые возникают в сложных системах, включающих человека, можно свести к задачам механики или математического анализа, традиционно называемого в технических вузах
«высшей математикой».
Самостоятельное значение имеют математические проблемы теоретического и практического программирования.
Задача данного пособия состоит в выработке навыков формализации физических сущностей с помощью различных «диалектов» современного математического языка, и, наоборот, интерпретации полученных математических результатов.
Содержательный аспект обычно предшествует формализации и имеет для нас значение при осмыслении результатов математических манипуляций.
Так что акцент в большей степени сделан на понятийной, а не вычислительной стороне ряда разделов математики.
Дисциплина «Дискретная математика» относится к естественно-научным дисциплинам федерального компонента. Она базируется на знаниях,
полученных слушателями при изучении дисциплины «Алгебра», «Методы программирования и
прикладные алгоритмы».
Знания и
навыки,
приобретенные на основе дисциплины
«Дискретная математика»,
используются студентами при изучении дисциплины «Математическая логика и теория алгоритмов», а также в дисциплинах, связанных с изучением программирования и алгоритмизации, моделированием и проектированием сложных систем.

7
1. Теория множеств
1.1. Основные понятия теории множеств
1.1.1.Понятие множества
Множество - фундаментальное неопределяемое понятие.
Примеры.
1) Множество деревьев в лесу.
2) Множество страниц в книге.
3) Множество студентов в группе.
4) Множество натуральных чисел.
Для интуитивного понятия множества существенны два момента:
1) различимость элементов множеств;
2) возможность осмыслить их как единое целое.
Таким образом, можно дать следующее интуитивное определение множества. Множество это объединение в одно целое объектов, хорошо различимых нашей интуицией или мыслью.
Множество, не содержащее элементов, называется пустым множеством и обозначается
∅
или
{}
. Обычно именно фигурные скобки используются для выделения множества (отсутствие элементов в скобках и говорит о том,
что это пустое множество).
Множество, заведомо содержащее все рассматриваемые элементы,
называется универсальным или универсумом - U.
1.1.2. Задание множеств
Существуют следующие способы для задания множеств.
1) Перечислением элементов.
Например:
А={‘a’,’b’,’c’,’d’}.
Группа_студентов={Иванов, Петров, Сидоров}.
2) Характеристическим свойством (предикатом)
А={a|C{a}}, т. е. множество А содержит такие элементы а, которые обладают свойством С(а).
Например:
А={а| а – символ от ‘a’ до ‘d’}.
Группа_студентов={a| a – студент}.
1.1.4. Отношения принадлежности и включения
Запись означает, что элемент х принадлежит множеству А . Если х не принадлежит множеству А, то это записывается как
Запись означает, что каждый элемент множества А является элементом множества В, т. е. из того, что следует, что
. Такая запись читается как «множество А включено в множество В» или «А
является подмножеством В».

8
Если и
, то А В - отношение строгого включения.
Рис. 1. Пример отношения включения
Множество деревьев
Множество елок
Множество сосен
Свойства отношения включения
1. Рефлексивность: A
⊆
A.
2. Принцип объемности: Если A
⊆
B и B
⊆
A, то B = A (на основе этого принципа и доказывается равенство двух множеств).
3. Транзитивность: Если A
⊆
B и B
⊆
C, то A
⊆
C.
Проиллюстрируем принцип объемности.
Примеры.
1. Пусть множество А – это множество всех положительных четных чисел, множество В – множество положительных целых чисел, представимых в виде суммы двух положительных нечетных чисел.
Если
, то для некоторого целого положительного числа m x=2m.
Тогда x=(2m-1)+1, следовательно,
, т. е. из того, что следует, что и можно сказать, что
Если
, то для некоторых целых положительных p и q x=(2p-1)+(2q-
1)=2p+2q-2=2(p+q-1), т .е
, следовательно,
Таким образом, множества А и В состоят из одних элементов,
следовательно, они равны.
2. В силу принципа объемности {2,4,6}={4,2,6}={2,4,4,6}
{{1,2}}≠{1,2}, т. к. множество {{1,2}} состоит из одного элемента
{1,2}, а множество {1,2} из двух элементов: чисел 1 и 2.
Различие между отношением принадлежности и включения
1 {1}, {1} {{1}}, но не верно, что 1 {{1}}, т. к. единственным элементом множества{{1}}является элемент {1}.
Пустое множество есть подмножество любого множества.
1.1.5. Парадоксы теории множеств
Описанные выше понятия теории множеств могут быть использованы в началах алгебры, анализа, математической логике и т. д. Но надо иметь в виду, что при более строгих рассмотрениях такое интуитивное восприятие может оказаться неудовлетворительным. Несовершенство интуитивных

9
представлений о множествах иллюстрируется известным парадоксом Б.
Рассела.
Парадокс Рассела. Можно указать такие множества, которые принадлежат самим себе как элементы, например, множество всех множеств.
Можно указать множества, которые не являются элементами самих себя,
например, множество {1,2} содержит числа 1 и 2. Рассмотрим теперь множество А всех множеств Х, таких, что Х не содержит себя в качестве элемента А={X| X X}. Тогда, если А не является элементом А, то, по определению, А также есть элемент А, т. е. A A. С другой стороны, если А
является элементом А, то А – одно из множеств Х, которые являются элементами самих себя, т.е. А А. Получается логическое противоречие,
когда А есть элемент А и А не является элементом А.
Более прост в понимании парадокс брадобрея: брадобрей бреет тех и
только тех, кто не бреется сам. Перед брадобреем неразрешимый вопрос:
Включать ли самого себя в множество тех, кого он обязан брить?!
Чтобы избежать этого парадокса,
можно ограничить характеристические предикаты с
помощью известного,
заведомо существующего множества – универсума U: А={x| x U и S(x)}.