Элементы тории множеств, отношений, графов, алгоритмов и булевых функций

Г.И. КОРОТЕЕВ

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

ЭЛЕМЕНТЫ ТОРИИ МНОЖЕСТВ, ОТНОШЕНИЙ, ГРАФОВ, АЛГОРИТМОВ И БУЛЕВЫХ ФУНКЦИЙ

Комсомольск-на-Амуре

ВВЕДЕНИЕ

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

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

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

В разделах 2, 3 рассмотрены основные понятия теории неориентированных и ориентированных графов, их способы задания, числовые характеристики, типы графов (деревья, двудольные графы, планарные графы), а также задачи с ними связанные, потоки в транспортных сетях, введение в теорию алгоритмов.

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

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

По программе курса выполняется контрольная работа и типовой расчет (РГЗ).

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

Номер варианта контрольной работы определяется по последней цифре номера зачетной книжки.

Номер варианта типового расчета определяется по двум последним цифрам номера зачетной книжки. Для вычисления варианта используется формула: n = p (mod 25). Здесь n – номер варианта; p – число, соответствующее двум последним цифрам номера зачетной книжки. Смысл приведенной формулы будет ясен после изучения раздела 1. Например, если p = 51, то номер варианта типового расчета равен: n = 1.

При составлении пособия использовались литературные источники, приведенные в библиографическом списке, в том числе и электронные.

1. МНОЖЕСТВА, ОТНОШЕНИЯ И ФУНКЦИИ

1.1. Элементы теории множеств

Ø Множества

Ø Интуитивные принципы

Ø Подмножество. Множество-степень (булеан)

Ø Определение множеств через заданные множества (операции над множествами)

Ø Диаграммы Эйлера-Венна

Ø Семейство множеств

Ø Мощность множеств

Ø Основные теоретико-множественные тождества

Ø Метод характеристических функций

Множество, понятие множества

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

Объекты, составляющие множество S,называются элементами этого множества.

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

Дата добавления: 2015-07-20