Файл: Дискретная математика.pdf

6

Введение

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

Цель изучения данных дисциплин — дать математическое обеспечение для со-

временных компьютерных и информационных технологий.

Материал этих дисциплин составляет базу для таких важнейших на сегодняш-

ний день узкоспециализированных дисциплин, как «Теоретическая информатика»,
«Методы и алгоритмы принятия решений», «Функциональное и логическое про-
граммирование», «Структуры и организация данных для компьютера», «Констру-
ирование программ», «Системный анализ и моделирование», «Теория искусствен-
ного интеллекта» и др. Все эти дисциплины «держатся на трёх китах»: логике,
алгебре и графах. Систематическое изучение данного материала позволит узнать
базовые математические модели и алгоритмы, которые в дальнейшем позволят
профессионально решать множество задач в конкретных областях информатики
и вычислительной техники. Полученные знания дадут возможность грамотно при-
менять их для абстрактного проектирования логических структур и вычислитель-
ных процессов на графах.

Соглашения, принятые в книге

Для улучшения восприятия материала в данной книге используются пикто-

граммы и специальное выделение важной информации.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Этот блок означает определение или новое понятие.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Этот блок означает внимание. Здесь выделена важная информа-
ция, требующая акцента на ней. Автор здесь может поделиться
с читателем опытом, чтобы помочь избежать некоторых ошибок.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает теорему.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Введение

7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает лемму.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

Пример

. . . . . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает пример. В данном блоке автор может привести прак-

тический пример для пояснения и разбора основных моментов, отраженных в тео-
ретическом материале.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

Выводы

. . . . . . . . . . . . . . . . . . . . . . . . .

Эта пиктограмма означает выводы. Здесь автор подводит итоги, обобщает из-

ложенный материал или проводит анализ.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Контрольные вопросы по главе

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Глава 1

ОСНОВЫ ТЕОРИИ МНОЖЕСТВ

И ОТНОШЕНИЙ

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

Понятие множества является основным, но трудно определяемым понятием,

поэтому его можно только пояснить.

Интуитивное определение множества, принадлежит немецкому математику Ге-

оргу Кантору (1845–1918 гг.): «Под множеством M будем понимать любое собра-
ние определенных и различимых между собою объектов, мыслимое как единое
целое. Эти объекты называются элементами множества M».

Принято элементы множества обозначать строчными буквами латинского ал-

фавита, а само множество — прописной буквой.

В интуитивном определении множества, существенным является то обстоя-

тельство, что собрание предметов само рассматривается как один предмет, мыс-
лится как единое целое. Что касается самих предметов, которые входят во мно-
жество, то их природа может быть различной. Это множество целых чисел, мно-
жество точек плоскости, множество студентов в аудитории и т. д. Таким образом,
канторовская формулировка позволяет рассматривать множества, элементы кото-
рых по той или иной причине нельзя точно указать (например, множество простых
чисел, множество белых тигров и т. п.). Из этого следует, что множество может со-
держать неоднородные объекты. Можно объединить в одно множество и людей,
и животных, и овощи.

Если элемент m принадлежит множеству M, то используется запись m

∈ M,

в противном случае используется запись m

∉ M.

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

ли множество не содержит ни одного элемента, то оно называется пустым и обо-
значается

∅.

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

9

Множество может быть задано различными способами: перечислением эле-

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

Например, множество M цифр десятичного алфавита можно задать в виде M

=

= {0, 1, 2, . . ., 9} или M = {i / i — целое, 0 ⩽ i ⩽ 9}, где справа от наклонной черты
указано свойство элементов этого множества.

Множество M нечётных чисел можно записать в виде M

= {m / m — чётное число}.

Множество M

a

называется подмножеством множества M (M

a

включено в M)

тогда и только тогда, когда любой элемент множества M

a

принадлежит M:

M

a

⊂ M ↔ (m ∈ M

a

→ m ∈ M),

где

⊂ — знак включения подмножества; a

→ b означает: если a, то b; a ↔ b означает:

b, если и только если a. В частном случае множества M и M

a

могут совпадать.

Невключаемое подмножество M

a

в множество M обозначается:

M

a

/⊂ M.

Множества M

a

и M

b

называются равными: M

a

= M

b

, если множество M

a

яв-

ляется подмножеством множества M

b

и множество M

b

является подмножеством

множества M

a

.

Если множество M

a

является подмножеством множества M, а множество M не

является подмножеством множества M

a

, то множество M

a

называется собственным

подмножеством множества M. Это можно обозначать:

M

a

⊂⊂ M.

Множества можно задавать графически с помощью диаграмм Эйлера—Венна.

Например, множества M

1

= {a, b, c, d} и M

2

= {e, f , c, g} на рисунке 1.1, заданы

диаграммами Эйлера—Венна.

Рис. 1.1 – Пример представления множеств диаграммами Эйлера—Венна

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

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

из уже существующих. Над множествами можно выполнять следующие основные
операции:

• объединение

A

∪ B ∶= {x ∣ x ∈ A ∨ x ∈ B};

• пересечение

A

∩ B ∶= {x ∣ x ∈ A ∧ x ∈ B};

10

Глава 1. Основы теории множеств и отношений

• разность

A

/B ∶= {x ∣ x ∈ A ∧ x /∈ B};

• симметрическая разность

A

∆B

≡ A÷ ∶= (A ∪ B)/(A ∩ B) = {x ∣ (x ∈ A & x /∈ B) ∨ (x /∈ A & x ∈ B)};

• дополнение

A

∶= {x ∣ x /∈ A}.

Операция дополнения подразумевает некоторый универсум (множество U , ко-

торое содержит A):

A

∶= {x ∣ x /∈ A}.

Указанные операции можно пояснить следующим образом:

• Объединением множеств A и B называется множество A

∪ B, все элементы

которого являются элементами множества A или B:

A

∪ B = {x ∣ x ∈ A ∨ x ∈ B}.

• Пересечением множеств A и B называется множество A

∩ B, элементы ко-

торого являются элементами обоих множеств A и B:

A

∩ B = {x ∣ x ∈ A & x ∈ B},

т.е выполняются включения A

∩ B ⊆ A ⊆ A ∪ B и A ∩ B ⊆ B ⊆ A ∪ B.

Говорят, что два множества не пересекаются, если их пересечение — пустое

множество.

• Относительным дополнением множества A до множества X называется

множество X

/A всех тех элементов множества X , которые не принадлежат

множеству A:

X

/A = {x ∣ x ∈ X & x ∉ A} (также называют разностью множеств X и A).

Когда фиксирован универсум U , абсолютным дополнением множества A
называется множество всех тех элементов x, которые не принадлежат мно-
жеству A:

A

= {x ∣ x ∈ U & x ∉ A}.

• Симметрической разностью множеств A и B называется множество:

A

÷ B = (A/B) ∪ (B/A).

Заметим, что дополнение множества A

= U/A. Часто вместо A будем писать ¬A

или A

′

.

Первым стал использовать теперь общепринятые обозначения операций над

множествами Джузеппе Пеано (1888 г.).

Для наглядного представления отношений между подмножествами какого-либо

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