Читать онлайн «Курс дискретной математики.»

В. Н. НЕФЕ * ■ : B. A. OC ПОВ ' А А В. Н. НЕФЕДОВ В. А. ОСИПОВА КУРС ДИСКРЕТНОЙ МАТЕМАТИКИ Допущено Государственным комитетом СССР по народному образованию в качестве учебного пособия для студентов вузов, обучающихся по специальности «Прикладная математика» МОСКВА ИЗДАТЕЛЬСТВО МАИ 1992 ББК 16. 2. 12 Н58 УДК 519. 1(075. 8) Рецензенты: доктор технических наук Л. Т. КУЗИН, кандидат физико-математических наук В. В. МОРОЗОВ Нефедов В. Н. , Осипова В. А. Н58 Курс дискретной математики: Учеб. пособие. — М. : Изд-во МАИ, 1992. —264 с: ил. ISBN 5-7035-0157-Х Излагаются основы современной дискретной математики. Рассматриваются вопросы, связанные с математической логикой, теорией алгебраических систем, комбинаторикой, теорией графов. Приводится ряд практических задач и даются алгоритмы их решения. Учебное пособие предназначено для студентов, обучающихся по епециальности «Прикладная математика», но может оказаться полезным также и студентам экономических и технических факультетов, изучающих курс «Дискретная математика» 1602120000-10 Р1М, 4ontt% Н 6-90 ББК 16. 2. 12 094(02)-92 ISBN 5-7035-0157-Х © В. Н. Нефедов, В. А. Осипова, 1992 ПРЕДИСЛОВИЕ В последние годы инженеры-математики, занимающиеся прикладными исследованиями, все больше используют аппарат дискретной математики. Это объясняется необходимостью создания и эксплуатации современных электронных вычислительных машин, средств передачи и обработки информации, автоматизированных систем управления и проектирования. Наконец, в современной математической науке исследования в областях, традиционно относящихся к дискретной математике (математической логике, теории алгебраических систем, теории графов и сетей и т. д. ), занимают все более заметное место. Цель создания учебного пособия — научить студентов основам дискретной математики, где дискретность понимается как антипод непрерывности. В настоящее время наряду с такими классическими разделами математики, как математический анализ, дифференциальные уравнения, в учебных планах специальности «Прикладная математика» и многих других технических и экономических специальностей появились разделы по математической логике, алгебре, комбинаторике и теории графов. В связи с этим представляется целесообразным создание учебного пособия для студентов младших курсов, в котором основы перечисленных разделов математики излагались бы в доступной форме, но достаточно полно и строго. Данное издание включает в себя не только основные понятия и теоретические результаты, но также методы и алгоритмы решения ряда прикладных задач. Во введении рассматриваются начальные понятия математики: множества, отношения и функции. В первой главе излагаются основы логики выска^ зываний и логики предикатов. Аппарат логики вы- S оказываний используется при изучении булевых функций. На примере логики высказываний осуществляется знакомство со строгой формализацией математической теории — строится исчисление высказываний. Затрагиваются вопросы, связанные с эффективной вычислимостью.