Введение в дискретную математику

Московский государственный технический университет 
имени Н.Э. Баумана 
В.А. Кутыркин, А.Ю. Бушуев 
Введение в дискретную математику 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

УДК 512.5+519.1 
ББК 22.174 
        К95 
 
 
Издание доступно в электронном виде на портале ebooks.bmstu.ru 
по адресу: http://ebooks.bmstu.ru/catalog/96/book1355.html 
Факультет «Фундаментальные науки» 
Кафедра «Вычислительная математика и математическая физика» 
К95 
Рекомендовано Редакционно-издательским советом  
МГТУ им. Н.Э. Баумана в качестве учебного пособия 
 
Рецензенты: 
д-р физ.-мат. наук, профессор В.А. Горелик 
канд. техн. наук, доцент Т.Н. Ничушкина 
 
Кутыркин, В. А. 
Введение в дискретную математику: учебное пособие /  
В. А. Кутыркин, А. Ю. Бушуев. — Москва : Издательство 
МГТУ им. Н. Э. Баумана, 2015. — 119, [3] с.: ил. 
ISBN 978-5-7038-4301-7 
В пособии приведены основные понятия и математические 
структуры дискретной математики, в частности рассмотрены методы и способы построения, анализа и синтеза конечных автоматов и регулярных языков, порожденных формальными грамматиками. Для усвоения материала разобраны демонстрационные 
примеры. 
Для студентов МГТУ имени Н.Э. Баумана, обучающихся по 
направлениям «Математика и компьютерные науки» и «Информатика и вычислительная техника». 
 
УДК 512.5+519.1 
ББК 22.174 
 
 
 
 
 
  
 МГТУ им. Н.Э. Баумана, 2015 
 
 
 Оформление. Издательство  
ISBN 978-5-7038-4301-7 
 
МГТУ им. Н.Э. Баумана, 2015  
2 

ПРЕДИСЛОВИЕ 
Цель учебного пособия — изучение основ дискретной 
математики, ориентированной на компьютерную практику, 
методов анализа и синтеза конечных автоматов, а также элементарных способов синтаксического анализа алгоритмических языков. 
Пособие предназначено для студентов, изучающих дисциплины «Дискретная математика» и «Теория автоматов и алгоритмические языки», которые предусмотрены учебным планом МГТУ им. Н.Э. Баумана по направлению «Математика и 
компьютерные науки». 
В главе 1 для понимания главных принципов дискретной 
математики изложены начала арифметики. Приведены понятия теории автоматов и формальных языков. Описаны методы конструктивного построения и использования формальных языков, которые могут быть полезны при работе с 
искусственными языками. В главе 2 рассмотрены методы 
анализа и синтеза конечных автоматов, основы теории графов, понятия которой необходимы для компьютерных способов задания и наглядного представления конечных автоматов. Даны определения основных понятий теории автоматов 
с описанием алгоритмов оптимального построения конечных 
автоматов. Особое внимание уделено задачам анализа и синтеза для автоматов, являющихся дискретными преобразователями конечных автоматов. Приведены классификация формальных грамматик алгоритмических языков по Хомскому и 
методы построения автоматов-анализаторов, используемых 
при синтаксическом анализе регулярных языков. 
3 

Изложение материала пособия сопровождается многочисленными примерами решения типовых задач. 
Для проверки усвоения представленного в пособии материала в конце каждой главы даны вопросы и задания для самоконтроля. 
При изучении методов анализа регулярных языков полезно будет ознакомиться с учебным пособием [1], для более 
глубокого понимания изложенного теоретического материала — с изданиями [2, 3]; большое количество задач по дискретной математике и методы их решения можно найти в задачнике [4]. 
В приложении 1 приведены индивидуальные задания  
с вариантами условий задач для самостоятельного решения, 
тематика которых отражает основные аспекты теоретического материала. В приложении 2 представлен словарь математических символов и фраз. 
4 

ВВЕДЕНИЕ 
Термин «дискретный» произошел от латинского слова discre- 
tus — прерывистый, состоящий из отдельных частей. Антонимами  
этого термина являются термины «непрерывный», «континуальный». 
В учебном пособии представлена точка зрения на дискретную 
математику, согласно которой при описании ее дискретной структуры предполагается, что все составляющие могут быть взаимно 
однозначно представлены совокупностью слов некоторого формального языка. Такие математические структуры используют, 
например, в языках программирования. В частности, совокупность 
натуральных чисел является такой дискретной структурой вследствие возможности ее представления формальным языком, традиционный алфавит которого состоит из десяти цифр. В этом языке 
любое натуральное число задают соответствующим словом, при 
этом каждое слово языка представляет собой некоторое единственное натуральное число. Но класс всех действительных чисел 
не допускает возможности представления его в каком-либо формальном языке и, следовательно, с классической точки зрения не 
рассматривается в качестве дискретной структуры. Такое понимание дискретности отражает классические представления, отличающиеся от современных неклассических. 
Согласно рассмотренной в пособии классической точке зрения, изложение начал учебного предмета «Дискретная математика» включает только тот круг вопросов, который можно озаглавить «Теоретические основы компьютерной математики». 
В компьютерной практике используют конструктивно (алгоритмически) заданные формальные языки, определяемые формальными грамматиками. В отличие от формальных языков их 
можно называть искусственными. Поэтому в настоящем пособии 
фраза задан формальный язык указывает на то, что этот язык может быть определен каким-либо конструктивным образом, т. е.  
5 

в виде некоторого искусственного языка, заданного в виде его словаря. Элементами этого языка являются все входящие в него слова. В пособии приведены некоторые конструктивные способы построения искусственных языков и их словарей. 
В компьютерной практике можно не применять научно неоднозначное понятие множества, вызвавшее в свое время кризис математики, в связи с чем в настоящем пособии аппелируют понятиями  
совокупности и класса. Поясним смысл этих понятий, полезных для 
их использования в компьютерной математике. Предполагается, что 
каждая непустая совокупность допускает взаимно-однозначное 
представление в каком-либо заданном формальном языке, т. е. элементам совокупности конструктивным образом можно взаимно однозначно поставить в соответствие слова этого искусственного языка. Для класса такое условие может оказаться несправедливым, но 
предполагается, что в нем можно выделить некоторую доступную 
для использования совокупность элементов. Таким образом, совокупность является классом, но класс может не являться совокупностью. Например, согласно такой точке зрения, действительные числа в отличие от натуральных образуют класс, но не совокупность. 
Заданный бесконечный формальный язык, т. е. искусственный язык, 
образует совокупность. Любой непустой конечный набор элементов 
также образует совокупность. По определению пустой набор является совокупностью. 
Введенные в пособии понятия позволяют описать основные 
математические объекты и структуры дискретной математики, 
применяемые в компьютерной практике, без использования теоретико-множественного подхода. 
6 

ГЛАВА 1. ОСНОВЫ АРИФМЕТИКИ 
1.1. НАЧАЛА АРИФМЕТИКИ 
Математические знаки 
Описание исходных объектов дискретной математики во многом напоминает литературные приемы письменности естественных языков. При этом исходными элементами служат особым образом зафиксированные идеальные объекты, представляющие 
собой простые и неделимые математические знаки (далее — знаки), т. е. своеобразные атомы — неделимые элементы. Во многих 
случаях изображение (запись) знаков заимствовано из начертания 
букв алфавитов естественных языков. Кроме того, в силу идеального характера математики неизбежны погрешности при фиксировании знаков и, в частности, расчленении их изображения (материальной фиксации) на части. Однако от последнего свойства 
изображения следует абстрагироваться и воспринимать знак неделимым. Следует добавить, что принципы использования грамматико-графических элементов естественных языков в качестве 
изображений математических знаков и в письменной литературе 
естественных языков различаются. В дискретной математике, кроме особо оговариваемых случаев, знаки рассматривают только  
с формальной точки зрения. Строчную и прописную буквы какоголибо алфавита естественного языка используют как изображение 
различных знаков. От обычных знаков отличаются также знаки, 
записанные полужирным шрифтом, и знаки индексов, которые  
в верхнем и нижнем индексах различаются. 
Согласно закону тождества, знак можно воспроизвести без потери идентичности. Следовательно, теоретически становится возможным неограниченное копирование знака, при котором копии 
не отличаются от оригинала. Таким образом, закон тождества от7 

ражает идеальную природу (сущность) знаков в дискретной математике. Для материальных объектов, природа которых всегда неидеальна, этот закон применить нельзя. 
Ряд натуральных чисел и принцип 
математической индукции 
На практике натуральные числа используют для определения 
(подсчета) количества каких-либо однотипных предметов (объектов), находящихся в некоторой области. В математике ряд натуральных чисел занимает исключительное и фундаментальное положение, являясь ее основой. В настоящее время в математике не 
существует единого подхода к введению в арифметику натуральных чисел. В пособии описан один из возможных подходов, согласно которому натуральные числа можно рассматривать как 
естественные дискретные элементы рационального мышления человека, организованные в виде динамического процесса — последовательного (пошагового) развертывания ряда натуральных чисел 
(обыкновенного счета). Отметим, что слова природа, естество синонимы слова натура, поэтому натуральные числа можно было бы 
также называть природными или естественными числами. 
Классический подход к введению в арифметику ряда натуральных чисел опирается на положение, называемое принципом 
математической индукции. Согласно этому принципу, ряд натуральных чисел начинается с числа, называемого в русском языке 
один. При пошаговом развертывании этого ряда за текущим числом непосредственно следует единственное натуральное число, 
отличное от всех предыдущих. При полном развертывании ряда 
обязательно должно встретиться каждое число и только один раз. 
Этот процесс удовлетворяет идеальному закону тождества — все 
повторные развертывания ряда натуральных чисел идентичны. 
Кроме того, при таком процессе развертывания среди натуральных 
чисел устанавливается порядок «старшинства». Натуральное 
число больше (меньше) другого натурального числа, если в этом 
процессе оно появляется после другого числа или перед ним. 
Принцип математической индукции обеспечивает единственность ряда натуральных чисел и соблюдение всех правил арифметики натуральных чисел. Этот фундаментальный принцип являет8 

ся содержательным и не может быть обоснован математическими 
средствами. Следовательно, с классической точки зрения математику нельзя считать самодостаточной (свободной — с либеральной 
точки зрения) наукой и признавать за ней абсолютную строгость 
(точность). 
Замечание 1.1. Натуральные числа не следует отождествлять с их 
названиями (именами) и обозначениями (изображениями), которые зависят от использования тех или иных естественных языков и традиций. Допуская определенную нестрогость, вместо натуральных чисел можно использовать их традиционные названия и обозначения. Часто при 
изложении арифметики натуральных чисел предполагают, что ряд натуральных чисел начинается с числа нуль, выражающего отсутствие предметов в выделенной области. Такой ряд натуральных чисел называют  
0-рядом натуральных чисел.  ► 
Математические строки 
Математические строки (или строки) конструируют (записывают) из знаков последовательно (пошагово), слева направо и подряд. Для фиксации отсутствия текста на каком-либо носителе вводят особую пустую строку, в записи которой нет ни одного знака. 
Конечность математических строк позволяет хранить и реализовывать их в техническом устройстве, например в памяти компьютера. 
Каждый знак в непустой строке имеет свое место, точнее, номер места, являющийся натуральным числом. Номер места началь- 
ного знака строки — число один, следующего, если такой имеется, — 
число два и так далее в соответствии с расположением элементов  
в ряду натуральных чисел согласно принципу математической индукции, каждый записываемый знак непустой строки получает 
единственный номер места в этой строке. Длиной непустой строки 
называют номер места последнего знака. По определению пустая 
строка имеет нулевую длину. Для краткости номер места знака  
в непустой строке называют номером знака. Так, начальный знак 
непустой строки будет ее первым знаком, следующий, если такой 
имеется, вторым и т. д. В силу своего построения строки удовлетворяют закону тождества, но в отличие от знаков делимы. 
9 

Математический язык и основы его грамматики 
Главной составляющей математического языка является понятие символа. Знак (или строку) называют символом, если он обозначает некоторый математический объект, отличный от него,  
в частности, математическую операцию, какое-либо отношение 
между математическими объектами и т. п. Например, символ + 
может обозначать операцию сложения натуральных чисел. Поскольку знак пробела не имеет изображения, для его обозначения 
применяют символ . Аналогично для обозначения пустой строки используют символ . Следовательно, символ, имеющий вид 
знака или строки, несет дополнительную смысловую нагрузку, которая предварительно должна быть оговорена (декларирована), 
можно сказать, отождествляет формальные математические знаки 
и строки с обычными словами естественного языка. Из строк или 
символов составляют строки, являющиеся соответствующими математическими предложениями (фразами) или математическим 
текстом. Математические фразы можно использовать в контексте 
естественного языка, что существенно сокращает описание математических структур. 
Далее приведены примеры символов, традиционно применяемых в математике. 
Символ  обозначает совокупность всех натуральных чисел. 
Для элементов какой-либо совокупности символ  заменяет слово 
естественного языка принадлежит. Следовательно, если n — 
символ некоторого натурального числа, строка n соответствует фразе естественного языка натуральное число n является элементом (принадлежит) совокупности натуральных чисел. Пусть 
m и m  — символ, обозначающий то же натуральное число, 
что и число n. Тогда строка m
n

 представляет собой математическую фразу число m  равно натуральному числу n, в которой 
слово естественного языка равно заменено на символ =. Для обозначения несовпадения математических объектов используется 
символ . Например, если m  и n — различные натуральные числа, создают символ 
.
m
n

 Строка 
,
m n указывает на то, что m  
и n — натуральные числа. В ней встречается символ , запятой, 
который аналогичен запятой в естественном языке. 
Символы A и B  обозначают некоторые совокупности натуральных чисел. Для них используют строки A  и B , в ко10