Файл: Дискретная математика_МУ_Реш.Задач.pdf

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

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

высшего образования 

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

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

Ю. П. Шевелев 

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

Методические указания  

по решению задач 

Томск 2017 

 
 
 
 
 
Корректор: А. Н. Миронова  
 
 
 
 
 
 
 

Шевелев Ю. П. 

Дискретная математика : методические указания по решению 

задач / Ю. П. Шевелев. – Томск : ФДО, ТУСУР, 2017. – 36 с.

 Методические указания содержат образцы выполнения заданий, ко-

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

Для  студентов  технических  вузов,  обучающихся  с  использованием 

дистанционных образовательных технологий. 

                                                                                    © Шевелев Ю. П., 2017 
                                                                                    © Оформление. 

ФДО, ТУСУР, 2017 

3 

СОДЕРЖАНИЕ 

Введение ............................................................................................................... 4 

Тема 1. Теория множеств .................................................................................... 5 

Тема 2. Комбинаторика ...................................................................................... 8 

Тема 3. Теория графов ...................................................................................... 15 

Тема 4. Булева алгебра: СДНФ ........................................................................ 18 

Тема 5. Минимизация дизъюнктивных нормальных форм .......................... 20 

Тема 6. Минимизация конъюнктивных нормальных форм .......................... 22 

Тема 7. Контактные структуры ........................................................................ 24 

Тема 8. Комбинационные схемы ..................................................................... 27 

Тема 9. Функционально замкнутые классы .................................................... 29 

Тема 10. Автоматы с памятью ......................................................................... 32 

Литература ......................................................................................................... 35 

4 

ВВЕДЕНИЕ 

В  соответствии  с  учебным  планом  для  студентов,  обучающихся 

с применением дистанционной технологии,  разработана рабочая програм-

ма, предусматривающая изучение таких разделов дискретной математики, 

как теория множеств, комбинаторика, теория графов, алгебра логики, тео-

рия конечных автоматов. Теоретический материал по этим темам изложен 

в учебном пособии «Дискретная математика». 

Для контроля освоения учебного материала из пяти глав пособия вы-

делено десять узких тем, по каждой из них в контрольную работу включе-

но по одной задаче. В данных методических указаниях содержатся приме-

ры решения задач по всем главам пособия. 

В темах, начиная с четвёртой, математическую основу составляет ал-

гебра логики, где наиболее трудоёмкими являются преобразования логиче-

ских формул. В связи с этим при подготовке к контрольной работе особое 

внимание  должно  быть  уделено  освоению  карты  Вейча,  позволяющей 

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

действиями) на такие  преобразования логических  выражений, как  нахож-

дение СДНФ, минимизация, перевод формул в алгебру Жегалкина и др. 

Все подобные задачи могут быть решены и без карты Вейча, только 

аналитическими методами. Однако при этом многократно возрастает вре-

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

зования  в  большинстве  случаев  отличаются  громоздкостью  и  большой 

трудоёмкостью. 

Дополнительную  теоретическую  информацию  можно  получить,  об-

ратившись к источникам, указанным в списке литературы. 

5 

ТЕМА 1. ТЕОРИЯ МНОЖЕСТВ 

Для  успешного  решения  задачи  по  теории  множеств  необходимо 

усвоить  такие  понятия,  как  конечное  множество,  пустое  множество,  уни-
версум; изучить способы задания множеств и ознакомиться с тремя основ-
ными  операциями:  объединение,  пересечение  и  дополнение.  Кроме  того, 
следует уделить внимание законам поглощения и склеивания, а также тео-
ремам де Моргана. 

Согласно условию задачи по теории множеств, требуется найти эле-

менты  множества  P,  заданного  формулой,  построенной  на  основе  мно-
жеств A, B, C, D и теоретико-множественных операций объединения, пере-
сечения и дополнения. Множества A, B, C, D заданы, однако в формуле P 
кроме  этих  множеств  содержатся  их  дополнения.  Следовательно,  прежде 
чем приступать к поиску элементов множества P, необходимо найти мно-

жества 

D

C

B

A

,

,

,

. 

Последовательность  действий,  которые  должны  быть  выполнены 

в процессе решения задачи, иллюстрируется следующими пятью примерами. 

 
Пример 1. Перечислите элементы, из которых состоит множество 

D

C

D

B

A

D

B

A

B

A

P



при условии, что 
  

А = {0, 1, 2, 4, 5, 8};  

В = {1, 2, 3, 4, 7, 9}; 

С = {2, 3, 4, 5, 6, 9}; 

D =  {0, 1, 3, 4, 5, 6, 7}. 

I = {0, 1, 2, …, 9}. 

Решение. Сначала найдём дополнения множеств 

D

C

B

A

,

,

,

: 

A = {3, 6, 7, 9}; 

B = {0, 5, 6, 8}; 

C = {0, 1, 7, 8}; 

D = {2, 8, 9}. 

Находим  элементы  первой  составляющей 

B

A

  заданного  множе-

ства P: 

B

A

= {3, 6, 7, 9} {1, 2, 3, 4, 7, 9} = {3, 7, 9}.