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

Федеральное агентство по образованию 

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

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

Ю.П. Шевелёв 

ÑàëäêÖíçÄü åÄíÖåÄíàäÄ

Учебное

методическое

пособие

2009 

Корректор: Осипова Е.А. 

Шевелёв Ю.П. 
Дискретная  математика:  Учебное  методическое  пособие. — 
Томск:  Томский  межвузовский  центр  дистанционного  образова-
ния, 2009. — 109 с. 

Приведены контрольные задания по теории множеств, математи-

ческой  логике,  теории  конечных  автоматов,  комбинаторике  и  теории 
графов. Контрольные задания представлены в двух видах: компьютер-
ное  тестирование  и 10 задач  для  контрольных  работ  с  письменным 
представлением решений. 

Для формирования контрольных заданий предусмотрено 2000 за-

дач.  Из  них 1000 тестов  и 1000 задач  для  письменных  контрольных 
работ. Приведены образцы их решения. 

Для студентов технических вузов дистанционного, очного и дру-

гих форм обучения. 
 
 
 
 
 
 
 
 

© Шевелёв Ю.П., 2009                                           

© Томский межвузовский центр 

                                                 дистанционного образования, 2009 

3 

éÉãÄÇãÖçàÖ 

ПРЕДИСЛОВИЕ ............................................................................ 5 
ЧАСТЬ 1. ТЕОРИЯ МНОЖЕСТВ .............................................. 7 

1 Вводные замечания................................................................... 7 
2 Тесты по теме № 1: «Операции над множествами» .............. 7 
3 Задачи из письменной контрольной работы.                              

Тема 1: «Теория множеств»..................................................... 9 

ЧАСТЬ 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА........................... 13 

1 Вводные замечания................................................................. 13 
2 Тесты по математической логике.......................................... 13 

2.1 Тесты по теме № 2: «СДНФ булевых функций» ............. 13 
2.2 Тесты по теме № 3: «ДНФ булевых функций»............. 17 
2.3 Тесты по теме № 4: «КНФ булевых функций»............. 19 
2.4 Тесты по теме № 5: «Алгебра Жегалкина» ................... 21 

3 Задачи из письменной контрольной работы ........................ 23 

3.1 Тема 2: «Минимизация нормальных форм» ................. 23 
3.2  Тема 3: «Минимизация ДНФ с учетом             

доопределения» ............................................................... 27 

3.3 Тема 4: «Минимизация КНФ с учетом              

доопределения» ............................................................... 30 

3.4 Тема 5: «Операция импликации»................................... 35 
3.5 Тема 6: «Дифференцирование булевых функций» ...... 37 

ЧАСТЬ 3. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ ................. 42 

1 Тестовое задание..................................................................... 42 

1.1 Асинхронный автомат на T-триггерах........................... 42 
1.2 Тест на тему № 6 «Асинхронный автомат» .................. 44 

2 Задачи из письменной контрольной работы ........................ 45 

2.1 Тема 7: «Синтез преобразователя кодов» ..................... 45 
2.2 Тема 8: «Автомат на JK-триггерах»............................... 53 

ЧАСТЬ 4. КОМБИНАТОРИКА ................................................ 61 

1 Вводные замечания................................................................. 61 
2 Тест на тему № 7: «Задача о шахматном городе»................ 61 
3 Тест на тему № 8: «Теория вероятностей» ........................... 63 
4 Задачи из письменной контрольной работы.                            

Тема 9: «Комбинаторика»...................................................... 67 

4 

ЧАСТЬ 5 . ТЕОРИЯ ГРАФОВ................................................... 77 

1 Вводные замечания................................................................. 77 
2 Тесты по теории графов ......................................................... 77 

2.1 Тесты по теме № 9 «Кодирование деревьев» ............... 77 
2.2 Тест по теме № 10 «Эйлеровы графы».......................... 80 

3 Задачи из письменной контрольной работы.                                 

Тема 10: «Нахождение простых цепей в графе».................. 81 

3.1 Содержание работы......................................................... 81 
3.2 Простые цепи в неориентированном графе .................. 82 
3.3 Простые циклы в неориентированном графе ............... 83 
3.4 Простые цепи в ориентированном графе ...................... 85 
3.5 Оформление решения задачи ......................................... 86 

ЧАСТЬ 6.  ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ ............. 87 

1 Интуитивное понятие алгоритма........................................... 87 

1.1 Определения понятия алгоритма ................................... 87 
1.2 Алгоритм нахождения наибольшего общего                    

делителя............................................................................ 87 

1.3 Пример логической задачи ............................................. 88 
1.4 Общие свойства алгоритмов........................................... 89 

2 Уточнения понятия алгоритма............................................... 91 

2.1 Необходимость уточнения понятия алгоритма ............ 91 
2.2 Машины Тьюринга-Поста .............................................. 92 
2.3 Программирование машины Поста ............................... 93 
2.4 Об алгоритмически неразрешимых проблемах ............ 95 

КОНТРОЛЬНЫЕ ВОПРОСЫ................................................... 97 
ЛИТЕРАТУРА ............................................................................ 105 
ПРИЛОЖЕНИЕ. Рабочая программа по дискретной 
математике.................................................................................... 106 

5 

èêÖÑàëãéÇàÖ 

 
В  пособии  отражены  в  основном  методические  аспекты 

курса  дискретной  математики. Теоретическая  часть  изложена  в 
[3],  где  представлены  разделы:  теория  множеств,  математиче-
ская логика, теория конечных автоматов, комбинаторика и тео-
рия графов. В данном пособии рассматриваются те же пять тем 
и дополнительно приведены элементы теории алгоритмов. 

Пособие  предназначено  в  основном  для  студентов  дистан-

ционной технологии обучения. В нем отражены следующие ви-
ды контроля: 

1) контрольная работа № 1 (в виде компьютерного тестиро-

вания); 

2) контрольная работа № 2 (письменная работа); 
Для контрольной работы № 1 предусмотрены тесты: 
1) операции над множествами;  

6) асинхронный автомат; 

2) СДНФ булевых функций;  

7) кодирование деревьев;  

3) ДНФ булевых функций;  

8) эйлеровы графы; 

4) КНФ булевых функций;  

9) комбинаторика; 

5) алгебра Жегалкина;  

10) теория вероятностей. 

В контрольную работу № 2 включены темы:  
1) теория множеств; 
2) минимизация нормальных форм; 
3) минимизация ДНФ с учетом доопределения; 
4) минимизация КНФ с учетом доопределения; 
5) операция импликации; 
6) дифференцирование булевых функций; 
7) синтез преобразователя кодов; 
8) автомат на JK-триггерах; 
9) комбинаторика; 
10) нахождение простых цепей в графе. 
Контрольные  задания  формируются  случайной  выборкой  не 

менее чем из тысячи задач для письменных контрольных работ и 
не менее чем из тысячи тестов для компьютерного тестирования. 

Главное назначение данного пособия состоит в том, чтобы 

помочь  студенту  в  подготовке  к  тестированию  и  выполнению