Материал: Дискретная математика. учебное пособие. Собенина О.В

О.В. Собенина

Дискретная математика

Учебное пособие

Воронеж 2012

ФГБОУ ВПО «Воронежский государственный технический университет»

О.В. Собенина

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

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

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

Воронеж 2012

УДК 519.1

Собенина О.В. Дискретная математика: учеб. пособие / О.В. Собенина. Воронеж: ФГБОУ ВПО «Воронежский государственный технический университет», 2012. 196 с.

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

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

Учебное пособие подготовлено в электронном виде в текстовом редакторе Word и содержится в файле «diskret.doc».

Библиогр.: 10 назв.

Рецензенты:

кафедра вычислительной математики и прикладных информационных технологий Воронежского государственного университета (зав. кафедрой д-р техн. наук, проф. Т.М. Леденева); канд. физ.-мат. наук, доц. В.Н. Дурова

 Собенина О.В., 2012

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

«Воронежский государственный

технический университет», 2012

Введение

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

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

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

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

Стремление к строгости математических рассуждений и анализ рабочего инструмента математики – логики – привели к выделению еще одного важного раздела математики – математической логики (19-20 вв.).

Однако наибольшего развития дискретная математика достигла в связи с запросами практики, приведшими к появлению новой науки – кибернетики и ее теоретической части – математической кибернетики (20 в.)

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

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

1.1. Основные понятия и определения теории множеств

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

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

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

Отдельные объекты, из которых состоит множество, называют элементами множества. Так, число 3 – элемент множества натуральных чисел, а буква б – элемент мно­жества букв русского алфавита.

Общим обозначением множества служит пара фигур­ных скобок { }, внутри которых перечисляются элементы множества. Для обозначения конкретных множеств исполь­зуют различные прописные буквы A, S, X... или пропис­ные буквы с индексами А₁, А₂. Для обозначения элементов множества в общем виде используют различные строчные буквы а, s, x... или строчные буквы с индексами а₁, а₂...

Для указания того, что некоторый элемент а является элементом множества S, используется символ  принад­лежности множеству. Запись aS означает, что элемент a принадлежит множеству S, а запись xS означает, что элемент х не принадлежит множеству S. Записью х₁, x₂,... ...,x_nS пользуются в качестве сокращения для записи x₁S, x₂S,..., x_nS.

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

Будем использовать следующие обозначения для числовых множеств:

– множество натуральных чисел, т.е.

– множество целых чисел, т.е. = {0, 1, 2, …};

– множество рациональных чисел, ={ / \ ,  ;  0};

– множество вещественных чисел;

– множество комплексных чисел.

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

Важным понятием теории множеств является понятие пустого множества. Пустым множеством называют мно­жество, не содержащее ни одного элемента. Пустое множество обозначают символом Например:

{xR | x²-x+1=0}=

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

Множество, содержащие все элементы, находящиеся в рассмотрении, называется универсальным или универсумом и обозначается U.

Для того чтобы оперировать с конкретными множест­вами, нужно уметь их задавать. Существуют два способа задания множеств: перечисление и описание. Задание мно­жества способом перечисления соответствует перечислению всех элементов, составляющих множество. Так, множество отличников группы можно задать, перечислив студентов, которые учатся на отлично, например {Иванов, Петров, Сидоров}. Для сокращения записи Х={х₁, х₂, ...,х_n} иногда вводят множество индексов I={1, 2,..., n} и пишут X={x_i}, iI. Такой способ удобен при рассмотрении конечных множеств, содержащих не­большое число элементов, но иногда он может применяться и для задания бесконечных множеств, например {2, 4, 6, 8...}. Естественно, что такая запись применима, если вполне ясно, что понимается под многоточием.

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

X={x | x обладает свойством Q(x)}.

Выражение в скобках читается: множество всех элементов х, которые обладают свойством Q(x). Так, если М — множество сту­дентов группы, то множество A отличников этой группы запишется в виде А={хМ | х – отличник группы},

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

В тех случаях, когда не вызывает сомнений, из какого множества берутся элементы х, указание о принадлежно­сти х множеству М можно не делать. При этом множест­во А запишется в виде

А={х | х – отличник группы}.

Приведем несколько примеров задания множеств мето­дом описания: {x | x – четное} – множество четных чисел;

{х | х²–1=0} – множество {+1, –1}.

Пусть Z – множество целых чисел. Тогда {xZ | 0<x7} есть множество {1, 2, 3, 4, 5, 6, 7}.

Множество нечетных чисел можно определить как {x | x=2k+1 для некоторого kZ}.

Способ задания множества с помощью свойств таит некоторые опасности, поскольку «неправильно» заданные свойства могут привести к противоречию. Приведем один из наиболее типичных парадоксов – парадокс Рассела. Рассмотрим множество всех множеств, которые не являются своими собственными элементами: . Спросим теперь, является ли множества К своим элементом? Если КК, то должно выполняться свойство, задающее множество К, т.е. КК, что приводит к противоречию. Если КК, то, поскольку выполняется свойство, задающее К, приходим к тому, что КК, а это противоречит предположению. Таким образом, не всякое свойство приводит к осмысленному заданию множества.

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

Заметим, что для любых элементов = 0; = 1.

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

Для произвольных множеств X и Y можно определить два типа отношений – отношение равенства и отношение включения.

Два множества считаются равными, если они состоят из одних и тех же элементов. Принято обозначение X=Y, если X и Y равны, и X Y – иначе.

Легко видеть, что для любых множеств X, Y, Z справедливы соотношения

,

,

( и ) .