Министерство транспорта Российской Федерации

Федеральное агентство железнодорожного транспорта

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Дальневосточный государственный университет путей сообщения»

Кафедра «Высшая математика»

В.С. Васильева, с.В. Коровина, л.В. Марченко дискретная математика

Рекомендовано Методическим советом ДВГУПС в качестве учебного пособия

Хабаровск

Издательство ДВГУПС

2013

УДК [510.2 + 510.6 + 519.1] (075.8)

ББК B 176я73

В 191

Рецензенты:

Кафедра математики ДВГГУ

(заведующий кафедрой кандидат педагогических наук, доцент И.В. Карпова)

Кандидат физико-математических наук,

доцент кафедры «Высшая математика» ТОГУ Н.В. Маркова

Васильева, в.С.

В 191 Дискретная математика : учеб. пособие / В.С. Васильева, С.В. Коровина, Л.В. Марченко. – Хабаровск : Изд-во ДВГУПС, 2013. – 119 с. : ил.

Учебное пособие соответствует ФГОС ВПО направлений подготовки 270800.62 «Строительство», 271501.65 «Строительство железных дорог, мостов и транспортных тоннелей».

Рассмотрены базовые разделы математики, необходимые для изучения дисциплин естественно-научного цикла. Помимо теоретической части включены варианты индивидуальных заданий.

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

Предназначено для студентов 1-го, 2-го курсов дневной формы обучения, изучающих дисциплину «Математика».

УДК [510.2 + 510.6 + 519.1] (075.8)

ББК B 176я73

ã ДВГУПС, 2013

Введение

В математике значительно сильнее, чем в других дисциплинах, обнаруживается черта организованности, стремление находить скрытый порядок во всем, что нас окружает…

А. Сухотин

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

Основной особенностью дискретной математики (ДМ) является отсутствие предельного перехода и непрерывности, характерных для классической (непрерывной) математики.

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

Теоретическое и методическое значение ДМ обусловлено возрастающими требованиями к профессиональным знаниям специалиста и формированию научного понимания структуры основных законов и принципов построения современных сложных технических систем. Преподавание ДМ имеет целью повысить общую культуру мышления студентов и тем самым подготовить их к сознательному и глубокому усвоению математических дисциплин общего и специального циклов.

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

Дискретная математика представляет собой фундамент для изучения других математических и специальных дисциплин (физика, теория вероятностей и математическая статистика, информатика, теория информации, моделирование систем, цифровые устройства и микропроцессоры, аппаратные средства вычислительной техники и др.).

Раздел «Дискретная математика» позволяет освоить базовые математические понятия, способствующие успешному овладению последующими курсами естественных наук и получению специализированных компетенций: способности корреспондировать с профессиональной деятельностью базовые знания естественных наук; владения методами поиска необходимой информации, алгоритмами последовательного, доказательного мышления; приемами работы с источниками знания.

Учебное пособие состоит из четырех тематических разделов, сопровождающихся иллюстрациями и поясняющими примерами. Для изучения основных тем достаточно знаний по математике в объеме средней школы.

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

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

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

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

В пятом разделе учебного пособия приведены 30 вариантов индивидуальных заданий, в каждом из которых по 15 заданий по темам изложенного материала.

Пособие предназначено для студентов технического вуза, но может быть полезно всем желающим углубить свои знания в области ДМ.

Для более глубокого изучения разделов дискретной математики можно обратиться к дополнительному теоретическому материалу [1–30] из библиографического списка, приведенного в конце учебного пособия.