ФГБОУ ВПО «Воронежский

государственный технический университет»

В.В. Горбунов М.Л. Лапшина

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

Утверждено Редакционно-издательским советом

университета в качестве учебного пособия

Воронеж 2014

УДК 519.617 (075.8)

Горбунов В.В., Лапшина М.Л. Дискретная математика: учеб. пособие [Электронный ресурс]. – Электрон. текстовые, граф. данные (2,9 Мб) / В.В. Горбунов, М.Л. Лапшина – Воронеж: ФГБОУ ВПО «Воронежский государственный технический университет», 2014. – 1 электрон.опт. диск (СD-ROM). – Систем.требования: ПК 500 и выше; 256 Мб ОЗУ; WindowsXP; MS Word 2007 или более поздняя версия; 1024х768; CD-ROM; мышь. – Загл. с экрана. – Диск и сопровод. материал помещены в контейнер 12х14 см.

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

Издание соответствует требованиям Федерального государственного образовательного стандарта высшего профессионального образования по направлению 09.03.02 «Информационные системы и технологии», профилю «Информационные системы и технологии» и дисциплине «Дискретная математика».

Табл. 32. Ил. 59. Библиогр.: 6 назв.

Рецензенты: кафедра вычислительной техники и информационных систем ВГЛТА

(зав. кафедрой д-р техн. наук, проф. В.К. Зольников);

канд. физ.-мат. наук, доц. В.И. Кузнецова

• Горбунов В.В., Лапшина М.Л., 2014

• Оформление. ФГБОУ ВПО

«Воронежский государственный технический университет», 2014

Введение

_{Данное пособие посвящено изучению следующих разделов высшей математики: матрицы, определители и системы линейных алгебраических уравнений, векторная алгебра, аналитическая геометрия на плоскости и в пространстве, кривые второго порядка.}

_{Пособие имеет следующую структуру. В начале каждого параграфа приводятся соответствующие теоретические сведения (определения основных понятий, уравнения, формулы, правила, признаки, методы). Затем следуют вопросы для самопроверки и примеры решения типовых задач различной степени трудности.}

_{Пособие рекомендовано студентам бакалаврам, обучающимся по} направлению 09.03.02 «Информационные системы и технологии» в помощь к изучению курса «Дискретная математика».

Предисловие

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

В данном пособии излагаются теория множеств, комбинаторное исчисление, математическая логика, теория графов.

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

1. Теория множеств

1.1. Понятие множества

Понятие множества является первичным и не сводится к другим понятиям и определениям, а основано на интуитивном представлении о совокупности объектов. Основатель теории множеств Георг Кантор под множеством понимал «объединение в одно общее объектов, хорошо различаемых нашей интуицией или нашей мыслью». В настоящее время под множеством принято понимать совокупность объектов произвольной природы, обладающих общим, «одинаковым» признаком. Множество считается определенным, если о каждом объекте можно сказать, принадлежит он к множеству или нет, т.е. обладает объект характерным признаком или нет.

Объекты, составляющие множество, называются элементами множества. Множества элементов обозначаются прописными буквами латинского алфавита: А,В,С,..., а элементы множеств — строчными буквами а,b,с,… Если элемент а является элементом множества А, то пишут (а принадлежит А). Если же элемент а не принадлежит множеству А, то пишут (а не принадлежит А).

Некоторые множества имеют устоявшиеся обозначения: N — множество натуральных чисел; Z — множество целых чисел; – множество рациональных чисел; R — множество действительных чисел; – множество комплексных чисел и т.д.

Выделяются четыре различных способа задания множеств. Первый способ (перечислительный) заключается в перечислении элементов множества. Элементы перечисляемого множества принято заключать в фигурные скобки. Например, множество А={1,2,3,4,5} описывает множество натуральных чисел, не превышающих пяти, множество В={Белгород, Воронеж, Липецк, Орел, Курск, Тамбов} — множество областных центров центрально-черноземного региона.

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

Третий способ задания множества связан с порождающей процедурой, которая позволяет получать новые элементы множества из уже полученных с помощью правил, называемых рекурсивными. Например, множество В натуральных чисел, делящихся на 3 без остатка, может быть описано с помощью порождающей процедуры, включающей два правила: а) б) если то .

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

Данный способ описания оказался перспективным в связи с интенсивным развитием теории нечетких множеств, где характеристическая функция не обязательно принимает только значения 0 и 1. Заметим, что для любых элементов = 0; = 1.

Пример 1.1. Пусть на универсуме U={a,b,c} определено множество X={a,c}, тогда

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

Если все элементы множества можно пронумеровать, то множество называется счетным. В противном случае имеем дело с несчетным множеством.

Множество, не содержащее ни одного элемента, называется пустым и обозначается Ø. Количество элементов конечного множества А называются мощностью множества и обозначается . Например, = n, если множество А содержит n элементов.

Множество А называется подмножеством множества В, если всякий элемент из множества А является элементом множества В. Символ включения в записи указывает на подмножество А множества В (множество А включено в множество В). Это означает справедливость следующего утверждения: для любого элемента а, если а А, то а В при условии . Исходное множество, имеющее подмножества, обычно называется универсальным множеством U (от английского слова universe – вселенная.). Совокупность всех подмножеств исходного множества называется булеаном и обозначается .

Рассмотрим универсальное множество X, состоящее из трех элементов . Собственными подмножествами (подмножествами, не совпадающими с исходным множеством) множества X являются три множества из двух элементов , , , три единичных множества , , и пустое множество Ø. Таким образом,

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