Читать онлайн «Дискретная математика: теория, задачи, приложения»

. . какая бы я был теперь несчастным человеком, если бы смолоду не приобрел известный запас знаний и вкус к ним. Чооторфилд «Пи. сыну» ЕТНАЯ АТИКА Я. М. ЕРУС Я. М. ЕРУСАЛИМСКИИ ДИСКРЕТНАЯ МАТЕМАТИКА: теория, задачи, приложения Москва «Вузовская книга» Z000 Ерусалнмскин Я. М. Дискретная математика: теория, задачи, приложения. 3-е изда- издание. — М. : Вузовская книга, 2000. — 280 с ISBN 5-89522-034-7 Учебное пособие но дискретной j pa высказываний, алгебра предикат*» комбинаторики, отношения, булевы Отдельный раздел состааляют задачи I! Фу i У НКШ! праж ;ест [И, пен в, отобра элсмснть им ISBN 5-S9522-034-7 © Ерусллимскии Я Ч , ,jh книи», оформление. Введение Памяти моего брата посвящаю Дискретная математика — бурно развивающаяся в XX веке ветвь ма- математики. Ее роль и место определяются в основном тремя факторами' — дискретную математику можно рассматривать как теоретические основы компьютерной математики; — модели и методы дискретной математики являются хорошим сред- средством и языком для построения н анализа моделей в различных науках, . мню, биологию, генетику, физику, психологию, экологию и — язык дискретной математики чрезвычайно удобен и стал фактиче- фактически метаязыком всей современной математики. Математика как наука, естественно, от рождения делится на дискрет- дискретную и континуальную математику. Что мы относим к континуальной ма- математике? Все, что явно иди неявно содержит идеи теории пределов н не- непрерывности. Все остальное — дискретная математика (т. е. арифметика, алгебра, теория множеств и общая теория отображений, математическая логика, комбинаторный анализ, теория алгоритмов и многое другое). В учебный предмет «Дискретная математика» включают только тот круг вопросов, который можно озаглавить «Теоретические основы ком- компьютерной математики». Прообраз этого пособия — курс дискретной математики, читаемый в течение ряда лет автором студентам первого курса специальности 01. 02 1 — «Прикладная математика» и направления подготовки 51. 02 — «При- ^чладная математика и информатика». Это и определило его содержание ht* характер изложения. Введаш Учебный курс дискретной математики на механико-математическом факультете Ростовского государственного университета читается в первых двух семестрах и включает в себя 70 часов лекционных я 35 часов лабо- лабораторных занятий. Главных задач у этого учебного предмета две: первая — дать элементарное введение в теорию множеств, отображений, ком- комбинаторику, язык предикатов и кванторов; вторая — стать теоретической основой для дисциплин компьютерного цикла. Существенным отличием этого пособия от других является система- систематическое использование языка множеств и отображений (в том числе при изложении элементов комбинаторики). Это позволило сделать курс дис- дискретной математики достаточно цельным, несмотря на разнообразие и внешнюю неоднородность изначального материала. Такой подход к из- изложению материала сложился на кафедре алгебры и дискретной матема- математики РГУ со дня ее основания в 1972 г.