Дискретная математика. Углубленный курс

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

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

4

цикла систем особо выделяется одна сервисная задача, имеющая первостепенное значение для обеспечения информационно-системной безопасности систем. Это задача создания программно-технических средств 
(ПТС) решения всех других задач жизненного цикла системы. Создание 
любых ПТС в рамках СОКР – это основа новой технологии программирования, названной радикальным программированием. 
Главный принцип радикального программирования – создание всякого ПТС должно быть организовано в режиме разработки, модификации 
и верификации этого ПТС под обязательным интеллектуальным контролем со стороны СОКР соответствующей системы. 
Таким образом, обсуждение проблем нового этапа прикладной математики, например, в рамках углубленного курса дискретной математики 
является делом назревшим и, надеемся, востребованным. 
Кроме традиционных вопросов дискретной математики, в предлагаемом учебнике излагаются вопросы алгебры и топологии, что связано с 
рассмотрением синтаксиса и семантики языка. Расматриваются четкие и 
нечеткие сведения о точке, энтропия и количество информации в таких 
сведениях, вопросы математического моделирования баз данных и баз 
знаний, проблемы интеллектуализации систем и связанные с этим вопросы информационно-системной безопасности систен, радикального моделирования и радикального программирования. 
      Учебник создан в соответствии с Федеральным государственным образовательным стандартом по направлениям подготовки "Информатика и вычислительная техника", "Информационная безопасность", 
"Прикладная информатика", "Прикладная математика", "Инфокоммуникационные технологии".  
 
Авторы выражают благодарность специалистам, коллегам по научным семинарам «Проблемы современных информационно-вычислительных систем» на мех.-мат. факультете МГУ им. М.В. Ломоносова и «Интеллектуализация военно-технических систем» в военной академии РВСН 
им. Петра Великого.  
 
 

ВВЕДЕНИЕ 
 
ДИСКРЕТНАЯ МАТЕМАТИКА – СОВРЕМЕННАЯ 
МАТЕМАТИКА 
 
 
 Математика – царица наук 
         К.Ф. Гаусс (1777 - 1855) 
 
0.1.  Математика – универсальный язык познания. Наука – это 
сфера человеческой деятельности, назначением которой является выработка и систематизация знаний об объектах выделенного класса. В зависимости от вида объектов вся наука условно подразделяется на частные 
науки, которые сегодня составляют четыре большие группы: естественные, общественные, технические и информационные. Точной границы 
между этими группами наук нет. Тем не менее их определяют свои специфические объекты исследования. 
Естественные науки изучают объекты природы, понимаемой как нечто отличное от общества. Например, физика, химия, биология, геология, 
география, астрономия и т.д. 
Общественные (гуманитарные) науки изучают различные стороны 
существования общества, т.е. обособившейся от природы части материального мира, представляющей собой развивающуюся форму жизнедеятельности людей. Например, социология, психология, история, археология, политическая экономия, филология, юриспруденция, образовательные науки, торгово-финансовые науки и т.д. 
Технические (инженерные) науки изучают искусственные объекты. 
Это объекты так называемой природы номер два, по меткому выражению 
академика В.И. Вернадского. Эти объекты в большей или меньшей степени созданы руками людей и используются для обслуживания различных 
потребностей общества, главным образом для технологических процессов 
производства. Главное отличие искусственных систем – это наличие у них 
предназначения. Они всегда – целенаправленные системы. Примерами 
технических наук являются теория машин и механизмов, сопротивление 
материалов, теория гироскопов, теория технического регулирования, техническая кибернетика, разнообразные (включая биологические) технологии, транспортные, энергетические и др. методики и т.д. 
Информационные науки возникли в последнее время. Сначала они 
появились как технические, но сейчас бурно развиваются в рамках всех 
наук для описания и исследования таких специфических систем, как ин
6

формационные. Информационные системы – это вспомогательные системы различного назначения, базы данных и базы знаний, экспертные системы, управляющие, диагностирующие, прогнозирующие, контролирующие, коммуникационные, обучающие и многие др. Надо отметить, что 
роль информационных систем, с учетом бурного развития компьютерных 
технологий, постоянно возрастает. Информационные системы все больше 
проникают во все целенаправленные системы, сращиваются с ними. Причем 
это происходит во всех сферах деятельности людей и для всех систем, идеальных и реальных, в том числе, и технических, и общественных, и природных. В 
частности, для таких жизненно важных систем, как военные, экономические, 
финансовые, банковские, торговые, логистические и др. Сейчас во всех искусственных системах различного назначения выделяется общая информационная сущность их функционирования. Происходит образование единой информационной отрасли деятельности людей – информатики. Одновременно с тенденцией к объединению всего разнообразия форм деятельности людей происходит понимание общности и единства всех информационных процессов. Происходит сращивание и взаимопроникновение естественных, общественных и 
технических наук в единую обобщающую науку – информатику. 
Среди всех наук особое место занимает МАТЕМАТИКА, которую считают 
царицей всех наук. Математика – это наука о наиболее абстрактных, наиболее 
общих, наиболее универсальных, наиболее отвлеченных от конкретности, 
символьных, знаковых объектах. Математические объекты не имеют конкретного осязаемого образа. Они без цвета и запаха, без вкуса и звуков и т.д. 
Абстрактность математики удобно подчеркивать уточняющим термином  
чистая математика. В чистой математике требуется строгая формализация 
как самих абстрактных объектов, так и методов исследования таких объектов. 
В первую очередь это логические (дедуктивные), алгебраические и топологические методы исследования этих объектов. 
Когда абстрактные математические объекты соотносят, ставят в соответствие с объектами некоторой предметной области, реальной или идеальной, 
то говорят о математических моделях этих предметов с обязательным свойством всяких моделей, с их адекватностью, т.е. со степенью их соответствия 
предметной области. Абстрактность математических понятий (объектов) 
обеспечивает прикладную универсальность математических моделей и методов их исследований. Одни и те же математические модели и методы исследования обычно, в силу их абстрактности, ориентированы сразу на разные 
предметы моделирования без ограничений, без оговорок, без запретов. 
Именно поэтому одни и те же математические методы исследования успешно 
применяются в самых разнообразных прикладных областях. Универсальность математического моделирования удобно подчеркивать уточняющим 
термином  прикладная математика. 

7

В любой частной науке, где применяются знаковые (символьные) модели объектов, происходит математизация этой науки, использование математических моделей и методов исследования. Современная математика 
обогатилась новыми разделами, позволяющими вести математические исследования там, где раньше использовался при описании только образный, художественный язык. В любой частной науке, в любой области знаний закономерен процесс математизации. По мнению знаменитого немецкого философа И. Канта (1724 – 1804) «в каждой науке столько истины, 
сколько в ней заключено математики». Жизнь постоянно подтверждает 
эту мысль. 
Все науки, и математика тоже, являются частью естественного языка, 
понимаемого в широком смысле в единстве с синтаксисом, семантикой и 
прагматикой языка. Естественный язык возник и всегда ориентирован на 
обслуживание всех жизненных задач всего общества, всех экономических 
отношений, всех производственных технологий и т.д. Естественный язык 
является средоточием разнообразных фактов и знаний о всем окружающем мире. 
Приведем четыре высказывания великих математиков на эту тему. 
«Математика –- это язык, на котором написана книга природы» – Г. 
Галилей (1564 – 1642). 
«Математика –- это язык, на котором говорят все точные науки» – 
Н.И. Лобачевский (1792 – 1856). 
«Математика –– это искусство называть разные вещи одним и тем же 
именем» — А. Пуанкаре (1854 – 1912). 
«Бог является математиком весьма высокого класса и в своем построении 
Вселенной он пользовался весьма сложной математикой» – П.А.М. Дирак 
(1902 – 1984). 
Выделим следующие пять методологических, основополагающих, 
системообразующих, концептуальных признаков математики: 
Первый признак математики –  абстрактность и универсальность. 
Математика является той частью естественного языка, которая максимально абстрактна и универсальна, но всегда ориентирована на обслуживание жизнедеятельности людей, всего разнообразия практики людей, в 
первую очередь на обслуживание наиболее типовых экономических отношений и массовых производственных технологий данного периода развития общества. 
Второй признак математики –-  логический вывод. Это строго формализованный способ введения математических понятий и проверки истинности высказываний об абстрактных понятиях математики. Этот способ 
проверки истинности еще носит название дедуктивный метод, доказательство или умозаключение. 

8

Третий признак математики –-  математическая постановка задач. 
Это строго формализованный способ формулировки задания цели исследования абстрактных математических объектов и формулировки правил 
разрешенных и строго формализованных их преобразований. 
Четвертый признак математики –  алгоритмизация решения математических задач. Это строго формализованный способ эффективного решения задач, которому предшествует формализованное обоснование алгоритма в форме математического метода решения задач. Сразу отметим, 
что не все математические задачи имеют алгоритм их решения. Есть алгоритмически неразрешимые задачи. 
Пятый признак математики –  компьютеризация решения задач. Это 
современный этап технического решения математических задач. Компьютерная программа ориентирована на оперативное исполнение техническим устройством, компьютером, алгоритмов решения задач. Для создания программ требуется реализовать новый технологический процесс, 
называемый программированием. Программирование означает переложение алгоритма решения задач на компьютерный язык кодов машин, отладка программ, ее верификация, защита ее от искажений и многое другое. Этот пятый признак математики совпадает с базовым признаком современной новой частной науки, информатики. Можно сказать, что информатика представляет собой, по своей сути,  современный этап прикладной математики. 
 
0.2.  Три периода развития математики. В истории цивилизации 
можно выделить три крупных периода развития: аграрный (сельскохозяйственный) – до XVII в., индустриальный – с XVII до XX вв. и информационный с XX в. Эти периоды определялись научно-техническими революциями, следовательно, определялись характером тех новых систем и явлений, которые были вовлечены в сферу главных интересов и потребностей 
людей. В каждый из периодов строилась новая научная картина реального 
мира, развивались новые технологии производства, создавались новые системы знаний (науки) и, в частности, новая математика. Тем самым крупные периоды развития общества, цивилизации должны ярко соответствовать периодам развития математики. Так оно и происходило на самом деле 
(рис. 0.1). 
До XVII в. люди активно использовали материальные, вещественные 
системы, которые определяются главным своим качеством — возможностью непосредственно влиять на наши органы чувств. Характерной особенностью таких систем является то, что в них возможно выделять части, 
соединять части в единое целое, причем связи между такими частями 
могли и не рассматриваться. Например, куча камней, камень, полкамня, 

9

сельскохозяйственное поле, целиком или разбитое на части под отдельные 
виды посевов и т.д. 
Основная деятельность людей в это время была связана с простейшими материальными системами, основные технологии основывались на 
преобразовании вещества. Например, обработка земли, урожая, глины, 
камня, дерева и т.п. 
В это время господствовала метафизическая (наглядная) картина реального мира. Все непознанное, неосознанное в мире объяснялось действием божественных сил. Вершиной научных знаний к концу XVI в., самой абстрактной частью всех знаний явилась элементарная математика. 
Она включала в себя в первую очередь арифметику, а также элементарную 
алгебру, планиметрию, стереометрию, тригонометрию, сферическую геометрию и др. Большинство математических моделей, используемых в технологических процессах того времени, основывались на понятии числа 
(рис.0.1). 
 

Аграрный период 

…   - XVII в.

Индустриальный 

XVII в. - XX в.

Информационный

XX в. - …

Метафизика   
(наглядность)

Элементарная
математика

Арифметика 

Непрерывная 
математика

Анализ       

Информатика  

Дискретная  
математика

Алгебра     

Физика  

Число
Функция
Радикал

 
 
Рис. 0.1. Три периода развития математики 
 
0.3.  Период непрерывной математики. К XVII в. основная деятельность людей во многом была связана с динамическими системами, с 
использованием рычагов, блоков, кораблей, парусов, ременных передач. 
Интенсивно изучалось движение тел на Земле и движение небесных тел. 
Развитие мореплавания и дальних путешествий вызвало необходимость 

10

высокоточного описания движения планет. Уже Галилео Галилей использовал понятие скорости, ускорения. Были изобретены механические часы 
и вскоре паровая машина. Произошла научно-техническая революция. Основные технологии стали базироваться на моторах, т.е. на устройствах 
преобразования энергии из одного вида в другой. Например, из энергии 
маятника, пружины, пара, ветра в механическую энергию движения. 
Наступил индустриальный период. Сформировалась физическая (энергетическая) научная картина реального мира. Были научно объяснены причины движения материи в пространстве и во времени. На смену метафизики пришло время нового мировоззрения, физики. 
Уже к середине XVII в. оформилась новая непрерывная (высшая) математика, в первую очередь трудами математиков француза Р. Декарта, 
англичанина И. Ньютона, немца Г.В. Лейбница. В основе непрерывной 
математики лежит идея инфинитезимальных свойств пространства и времени, выражаемых числовой осью, т.е. континуальными свойствами действительных чисел. Потребовался и появился новый тип моделей, функция. И сразу были разработаны методы их исследования в виде дифференциального (локальное поведение функций) и интегрального (глобальное 
поведение функций) исчислений. Далее, в XVIII - XX веках продолжалось 
глубокое, интенсивное изучение динамических систем, распределенных 
сред, аэромеханики, гидромеханики, электродинамики, микро- и макромира. 
К середине XX в. человек посредством машин и механизмов во много 
раз увеличил свои энергетические (мышечные) возможности. В математике этот период связан с господством непрерывной (высшей) математики, которая опирается на элементарную математику и включает в себя 
разные дисциплины. В первую очередь это анализ (бесконечно малых, 
функций действительных переменных, функций комплексных переменных, функциональный анализ), а также аналитическая и дифференциальная геометрия, высшая алгебра, теория вероятностей и др. В основе большинства математических моделей, используемых в технологиях индустриального периода, лежит понятие функции (рис. 0.1). Термин «непрерывная математика» отражает доминирующее положение действительных чисел (числовой оси) во всех математических построениях этого периода, особенно в теории пределов, математическом анализе, аналитической геометрии, дифференциальных уравнениях, теории вероятностей и 
других разделах. 
0.4.  Период дискретной математики. Начиная с середины XX в. 
происходит новая научно-техническая революция. В нашу жизнь бурно 
вошли и вскоре заняли доминирующее место информационные системы 

11

различного назначения, основанные на использовании электронно-вычислительных машин (ЭВМ), компьютеров. Появилась новая отрасль экономики, новая частная наука, новый раздел математики и даже новое мировоззрение, которые объединяются под термином информатика. Изменилась научная картина мира. Теперь наряду с физическими, энергетическими, объяснениями причин движения материи в пространстве и во времени на передний план вышли информационные процессы, которые не являются физическими. Именно они осуществляют регулирование и управление изменениями энергии из одного ее вида в другой. Информатика, как 
мировоззрение, уверено вышла на передний план в современной научной 
картине мира, заметно потеснив физику. Информационные системы сначала были кибернетическими системами, а затем все увереннее становятся 
системами с интеллектуальными свойствами. 
Кибернетические системы — это разнообразные автоматы. Автоматы 
обрабатывают входные сигналы (входное слово) и вырабатывают выходные сигналы (выходное слово). Те входные слова, которые автомат не обрабатывает, называются нештатными ситуациями. Таким образом, кибернетические системы всегда решают только штатные для них задачи. 
Интеллектуальные системы нацелены на решение не только своих штатных задач, но и некоторых нештатных для них задач. Примерами интеллектуальных систем являются: человек, сообщество людей, высшее животное, популяция высших животных и т.п.; организационная система с преобладанием 
человеческого фактора (государство, фирма, армия, школа и т.п.); автоматизированные системы с преобладанием технического фактора (пилотируемый 
космический корабль, самолет, автомобиль, подводная лодка, надводный корабль, поезд, гидроэлектростанция, система управления производством, операционная система компьютера вместе с пользователем и т.п.); наконец, автоматизированные системы с интеллектуальными свойствами, в которых предполагается отсутствие человека (беспилотный летательный аппарат, робот, 
межпланетный космический аппарат, навигационная спутниковая группировка и т.п.) 

Определяющие процессы в кибернетических и интеллектуальных систе-мах -- это информационно–логические, принципиально дискретные 
процессы решения разнообразных задач. Такие системы несут на себе 
функции управления, регулирования, контроля, прогноза, диагноза, анализа и синтеза динамических систем различного назначения. В середине 
XX в. появились и быстро распространились на практике разнообразные 
автоматизированные системы. В настоящее время идет процесс информатизации общества, интеллектуализации организационных систем, внедрения компьютеров в производство, транспорт, коммунальные, торговые, 

12