ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5512
Скачиваний: 27
Министерство образования Российской Федерации
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ
УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
Е.Н. Сафьянова
ДИСКРЕТНАЯ МАТЕМАТИКА
Часть 2
Учебное пособие
2000
Сафьянова Е.Н.
Дискретная математика. Часть 2: Учебное пособие.
− Томск:
Томский межвузовский центр дистанционного образования,
2000.
− 98 с.
Учебное пособие рассмотрено и рекомендовано к изданию
методическим семинаром кафедры автоматизированных систем
управления ТУСУР 17 мая 1999 г.
© Сафьянова Е.Н., 2000
© Томский межвузовский центр
дистанционного образования, 2000
3
СОДЕРЖАНИЕ
1 ФОРМАЛЬНЫЕ ТЕОРИИ ........................................................ 5
1.1 Основные положения ........................................................... 5
1.2 Исчисление высказываний .................................................. 7
1.3 Исчисление предикатов ..................................................... 10
2 ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ ..................................... 13
2.1 Интуитивное понятие алгоритма и проблема его
уточнения ............................................................................. 13
2.2 Элементы теории рекурсивных функций......................... 16
2.2.1 Основные понятия .................................................................... 17
2.2.2 Преобразования функций......................................................... 19
2.2.3 Примитивно-рекурсивные функции........................................ 23
2.2.4 Частично рекурсивные функции ............................................. 24
2.3 Машины Тьюринга............................................................. 26
2.4 Нормальные алгорифмы Маркова .................................... 35
2.5 Задачи и упражнения.......................................................... 38
3 ЭЛЕМЕНТЫ КОМБИНАТОРНОГО АНАЛИЗА ................. 40
3.1 Постановка задач комбинаторного
программирования .............................................................. 41
3.1.1 Задачи определения очередности выполнения заданий ........ 42
3.1.2 Задачи определения порядка обработки деталей ................... 43
3.1.3 Задачи распределения заданий ................................................ 45
3.1.4 Задача о назначениях................................................................ 48
3.2 Основные понятия и операции комбинаторики .............. 48
3.3 Выборки и упорядочения................................................... 50
3.4. Разложение на циклы ........................................................ 53
3.5.Размещения и заполнения.................................................. 55
3.6. Производящие функции.................................................... 57
3.7 Комбинаторно-логический аппарат.................................. 61
3.7.1 Метод включений и исключений ............................................ 62
4
3.7.2 Системы представителей множеств ........................................ 66
3.8 Общая модель и основные способы описания задач
комбинаторного программирования ................................. 72
3.9 Методы решения экстремальных задач комбинаторного
программирования .............................................................. 81
3.10 Задачи и упражнения........................................................ 87
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО КУРСУ
«ДИСКРЕТНАЯ МАТЕМАТИКА»........................................... 90
СПИСОК ЛИТЕРАТУРЫ .......................................................... 98
5
1
ФОРМАЛЬНЫЕ
ТЕОРИИ
1.1
Основные
положения
Мы рассмотрели две логических системы: алгебру высказыва-
ний и логику предикатов. Это было содержательное рассмотрение.
Попытаемся теперь описать их с формальной точки зрения, дав по-
нятие формальной теории.
Построение формальной теории начинают с построения фор-
мального языка теории. А для построения формального языка нужно
выделить множество знаков, составляющих его алфавит, а затем
указать правила, по которым будем строить формулы нашей тео-
рии.
Формальная теория - это множество все формул формального
языка с выделенным в нем подмножеством формул, называемых
«истинными». Теория, в которой не все формулы истинны, называ-
ется непротиворечивой.
Среди формальных теорий наиболее важным является класс
формальных теорий, называемых аксиоматическими. Их рассмот-
рением мы и ограничимся.
Для аксиоматических теорий характерен следующий порядок
выделения «истинных» формул:
1)
выделяется некоторое подмножество формул, называемых
аксиомами теории;
2)
указывается конечное множество отношений между фор-
мулами. Эти отношения называются правилами вывода.
Правила вывода ставят в соответствие некоторым конечным
последовательностям формул – новые формулы. С помощью этих
правил из аксиом получаются новые истинные формулы – теоремы.
Чтобы определить, что такое теорема, определим вначале, что
такое доказательство.
Доказательством называется конечная последовательность
формул
A
1
,
A
2
, ... ,
A
n
такая, что каждая
A
i
есть либо аксиома тео-
рии, либо получена из предыдущих формул по одному из правил
вывода.