Читать онлайн «Дискретная математика: Учебное пособие для вузов»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования САНКТПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ И. Л. Ерош, М. Б. Сергеев, Н. В. Соловьев ДИСКРЕТНАЯ МАТЕМАТИКА Учебное пособие для вузов Допущено УМО вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 230201 (071900) «Информационные системы и технологии» направления подготовки 230200 «Информационные системы» СанктПетербург 2005 1 УДК 519. 2(075) ББК 22. 176я73 Е78 Ерош И. Л. , Сергеев М. Б. , Соловьев Н. В. Е78 Дискретная математика: Учеб. пособие /СПбГУАП. СПб. , 2005. 144 с. : ил. ISBN 5808801699 Учебное пособие содержит как традиционные разделы дискретной математики: теорию множеств, булеву алгебру, комбинаторику, тео рию графов, – так и ряд разделов, которые обычно не входят в учебни ки по дискретной математике, но исключительно важны для специа листов в области вычислительной техники, а именно: теорию диск ретных групп, теорию чисел, теорию разрядных вычислений. Пособие ориентировано на студентов технических университетов, аспирантов и преподавателей дисциплины «Дискретная математика». Рецензенты: кафедра радиосистем СанктПетербургского электротехнического университета; кандидат технических наук В. Н. Сасковец Утверждено редакционноиздательским советом университета в качестве учебного пособия ISBN 5808801699 © ГОУ ВПО «СанктПетербургский государственный университет аэрокосмического приборостроения», 2005 © И. Л. Ерош, М. Б. Сергеев, Н. В. Соловьев, 2005 2  ПРЕДИСЛОВИЕ Дискретная математика (дискретный анализ) занимается изучени ем финитных (конечных) свойств объектов, которые возникают как в различных разделах математики, так и в ее технических приложени ях. Под конечными свойствами понимаются их ограниченность или перечислимость. Важными отличиями разделов дискретной математи ки от классических разделов непрерывной математики являются от сутствие понятия непрерывности и предела последовательности. То, что в разделах дискретной математики рассматриваются конеч ные свойства объектов, совсем не означает, что при исследовании не встречаются бесконечные совокупности объектов или их конфигура ций, однако, как правило, эти бесконечности являются счетными. В то время как в непрерывной математике бесконечности, как прави ло, континуальные. Разделы дискретной математики всегда существовали в математи ке, но стали выделяться в самостоятельную дисциплину в связи с раз витием средств связи и появлением компьютеров.