Обзор содержания курса

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

Классическая математика – это математика непрерывных величин. Основное понятие классической математики, понятие предела, связано с представлением о непрерывной действительной прямой – континууме. Основная модель классической математики – система дифференциальных уравнений, описывающая движение по непрерывной траектории в фазовом пространстве.

Элементы дискретной математики зародились в рамках классической, но до середины XX века не занимали в ней заметного места.

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

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

Основные понятия теории множеств

Понятие множества является первичным и поэтому формально не может быть определено. Обычно множество объясняют, следуя основателю теории множеств Г. Кантору, как совокупность объектов произвольной природы, рассматриваемую, как единое целое.

Объекты, составляющие множество, называют его элементами. Множества обозначают прописными буквами латинского алфавита (), элементы множеств – строчными буквами ().Утверждение «элемент принадлежит множеству » записывается следующим образом: ( – символ принадлежности). В противном случае – (или ).

Если каждый элемент множества входит в множество , то называется подмножеством . При этом пишут: или . Если и , то пишут или . Здесь , , , – символы включения. Множества и равны, если они состоят из одних и тех же элементов, иначе говоря, если и .

Множество, не содержащее ни одного элемента, называется пустым (обозначается ). Множество называется истинным, если оно не пустое.

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

Различают два вида подмножеств множества : само и называют несобственными подмножествами; все остальные подмножества, если они существуют, – собственными.

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

– квантор общности (означающий «любой», «для всех», «каков бы ни был»);

– квантор существования (означающий «существует», «найдется», «можно найти»);

– импликация (символ следствия, означающий «влечет за собой).

С помощью этих символов условие запишется так:

.

Множество называется эквивалентным множеству (обозначается ), если между элементами и можно установить взаимно однозначное соответствие. Различают конечные и бесконечные множества. Число элементов множества называется его мощностью или кардинальным числом и обозначается или card (англ. cardinality – мощность). Таким образом, конечное множество, содержащее элементов, имеет мощность . Если эквивалентно множеству натуральных чисел , то его называют счетным и его мощность обозначается через . Множество , эквивалентное множеству действительных чисел , называется континуальным, а его кардинальное число c – мощностью континуума.