Файл: Diskretnaya_matematika.doc

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

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

Цель дисциплины «Дискретная математика» – знакомство с основными разделами этой науки: теорией множеств, математической логикой и теорией графов.

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

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

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

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

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

Для обозначения конкретных множеств принято использовать прописные буквы A,S,X, ... Для обозначения элементов множества используют строчные буквыa,s, х,…

Множество X, элементами которого являются х₁, х₂, х₃, обозначают:X= {x₁,x₂, х₃}. Это первый способ задания множества– перечисление всех его элементов. Он удобен при рассмотрении конечных множеств, содержащих небольшое число элементов.

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

Для указания того, что элемент х принадлежит множеству X, используется запись хX. Запись хXозначает, что элемент х не принадлежит множествуX.

Так, если М – множество студентов группы, то множество Xотличников этой группы записывается в виде

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

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

Известные числовые множества обозначим следующим образом:

N= {1, 2, 3, …} – множество натуральных чисел;

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

Q– множество рациональных чисел;

R– множество действительных чисел.

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

Пример.X= {хZ| х²- х + 1 = 0} =.

Множество Xявляетсяподмножеством множестваY, если любой элемент множестваXпринадлежит множествуY. Этот факт записывается какXY.

Два множества XиYравны в том случае, когда они состоят из одних и тех же элементов. РавенствоX=Yозначает: если хX, то хYи если уY, то уX.

Для сокращения записи в теории множеств используются некоторые логические символы. Это символы общности и существования, а также символы следствияи эквивалентности.

Смысл этих обозначений следующий:

 – «любой», «каждый», «для всех»;

 – «существует», «найдется», «хотя бы один»;

 – «следует», «влечет»;

 – «эквивалентно», «необходимо и достаточно».

Рассмотрим примеры использования этих символов.

1. Определение подмножества X  Y приводит к записи:

 х [х  X  х  Y].

2. Определение равных множеств X=Y приводит к записи: X = Y  X  Y и Y  X.

Множество называется конечным, если оно содержит конечное число элементов, ибесконечным, если число его элементов бесконечно.

1.2. Операции над множествами

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

Объединением(суммой) множествXиYназывают множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множествX,Y(рис. 1.1).

Рис. 1.1. Объединение множеств

Объединение двух множеств символически записывают как X  Y. Объединение множеств X_i (i = 1, 2, ..., n) есть множество элементов, каждый из которых принадлежит хотя бы одному из множеств X_i. Соответствующее обозначение:

Пересечением множествXиYназывают множество, состоящее из всех тех элементов, которые принадлежат какмножеству X, так и множеству Y (рис. 1.2).

Рис. 1.2. Пересечение множеств

Пересечение множеств обозначается через X Y. Множества X и Y называют непересекающимися, если они не имеют общих элементов, т.е. если X  Y = .

Пересечением множеств Х_i (i = 1, 2, ..., n) называется множество элементов, принадлежащих каждому X_i. Оно обозначается как

Разностью множеств X и Y называют множество, состоящееиз всех тех элементов, которые принадлежат X и не принадлежат Y (рис. 1.3). Разность множеств обозначается через X \ Y. Очевидно, что X \ Y  Y \ X.

Рис. 1.3. Разность множеств

Симметрической разностью X⊕Y множеств X и Y называется объединение разностей X\Y иY\X. Эта разность множеств является составной операцией:

X ⊕ Y = (X \ Y)  (Y \ X).

Пример 1. Пусть: X – множество отличников в группе, Y – множество студентов, живущих в общежитии. Тогда: X  Y – множество студентов, которые или учатся на «отлично», или проживают в общежитии; X  Y – множество отличников, живущих в общежитии; X \ Y – множество отличников, живущих вне общежития.

Дополнительным кмножеству X по отношению к множествуW, еслиX  W, называется множество, состоящее из элементов W, не принадлежащих множествуX. Дополнительное множество обозначается:Z_w(X) (рис. 1.4).

Рис. 1.4. Дополнительное множество

Универсальным множеством называется множество I, для которого справедливо соотношение:XI=X. Оно означает, что множество I содержит все элементы множества X. Следовательно, любое множество X полностью содержится во множестве I, т.е. является его подмножеством: Х  I. Так, для примера 1 универсальным множеством можно считать множество студентов в группе.

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

Дополнением множества X (до универсального множества I) называют множество Х, определяемое из соотношения: Х = I \ X.

На рис 1.5 множествоХ представляет собой не заштрихованную область.