Файл: Дискретная мат-ка_Ч.2_УП.pdf

Министерство образования Российской Федерации 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ 

УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) 

Кафедра автоматизированных систем управления (АСУ) 

Е.Н. Сафьянова 

ДИСКРЕТНАЯ МАТЕМАТИКА 

Часть 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

 есть либо аксиома тео-

рии,  либо  получена  из  предыдущих  формул  по  одному  из  правил 
вывода.