О.В. Собенина

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

Учебное пособие

Воронеж 2012

ФГБОУ ВПО «Воронежский государственный технический университет»

О.В. Собенина

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

Утверждено Редакционно-издательским советом университета

в качестве учебного пособия

Воронеж 2012

УДК 519.1

Собенина О.В. Дискретная математика: учеб. пособие / О.В. Собенина. Воронеж: ФГБОУ ВПО «Воронежский государственный технический университет», 2012. 196 с.

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

Издание соответствует требованиям Федерального государственного образовательного стандарта высшего профессионального образования по направлению 230100.62 «Информатика и вычислительная техника» (профиль «Системы автоматизированного проектирования в машиностроении»), дисциплине «Дискретная математика».

Учебное пособие подготовлено в электронном виде в текстовом редакторе Word и содержится в файле «diskret.doc».

Библиогр.: 10 назв.

Рецензенты:

кафедра вычислительной математики и прикладных информационных технологий Воронежского государственного университета (зав. кафедрой д-р техн. наук, проф. Т.М. Леденева); канд. физ.-мат. наук, доц. В.Н. Дурова

 Собенина О.В., 2012

 Оформление. ФГБОУ ВПО

«Воронежский государственный

технический университет», 2012

Введение

Дискретная математика – область математики, занимающаяся изучением свойств дискретных структур, которые возникают как внутри математики, так и в ее приложениях. Дискретность (от лат discretus – разделенный, прерывистый) – прерывность; противопоставляется непрерывности. Например, система целых чисел (в противоположность системе действительных чисел) является дискретной; дискретное изучение какой-либо величины во времени – это изменение, происходящее через определенные промежутки времени (скачками).

В отличие от дискретной математики классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической математики или дискретной математики как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь, и в связи с этим, какую модель изучаемого явления он рассматривает: дискретную или непрерывную.

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

Элементы дискретной математики возникли в глубокой древности. Развиваясь с другими разделами математики, они явились их составной частью. Типичными для того времени были задачи, связанные со свойствами целых чисел и приведшие затем к созданию теории чисел. К их числу могут быть отнесены отыскания алгоритмов сложения и умножения натуральных чисел (2-е тыс. до н. э.), задачи о суммировании и вопросы делимости натуральных чисел в пифагорейской школе (6 в. до н. э.) и т.д.

Стремление к строгости математических рассуждений и анализ рабочего инструмента математики – логики – привели к выделению еще одного важного раздела математики – математической логики (19-20 вв.).

Однако наибольшего развития дискретная математика достигла в связи с запросами практики, приведшими к появлению новой науки – кибернетики и ее теоретической части – математической кибернетики (20 в.)

Дискретная математика включает в себя такие математические разделы, как теория множеств и отношений, теория графов, теория алгоритмов, комбинаторный анализ, математическую логику и другие, которые наиболее интенсивно стали развиваться в связи с внедрением вычислительной техники. Теория графов является эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством и дискретной оптимизации. Широкое применение дискретная математика нашла в современной вычислительной технике: в теоретическом программировании, при проектировании ЭВМ и сетей ЭВМ, баз данных, систем логического управления. Элементы математической логики применяются при решении проблем функционально-логического проектирования.