Множества

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

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

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

для студентов всех форм обучения специальностей

5B0704 – Вычислительная техника и программное обеспечение,

5B0703 – Информационные системы

Алматы 2011

УДК 519.6 (075.8)

ББК 22.176 Я 73

А 91 Дискретная математика:

Учебное пособие /Л.Н. Астраханцева;

АУЭС. Алматы, 2011.- 78 с.

ISBN – 601 – 7098 – 78 - 0

Пособие представляет собой переработанные и дополненные лекции по дискретной математике, читаемые автором в АУЭС, оно включает четыре раздела, традиционно изучаемые в курсе дискретной математики: элементы теории множеств и отношений, элементы математической логики, теории графов и комбинаторики. Содержание разделов взаимно связано друг с другом. В доступной форме изложены основные теоретические сведения, приведены примеры и решённые задачи, помогающие усвоить и закрепить изучаемый материал. Пособие предназначено для студентов всех форм обучения специальностей 5В070400 – Вычислительная техника и программное обеспечение и 5В070300 – Информационные системы.

Ил. 72, табл. 14, библиогр. – 16 назв.

ББК 22.176 Я 73

РЕЦЕНЗЕНТ: КазНУ, канд. физ.-мат. наук, доц. У.К. Койлышов.

АУЭС, канд. физ.-мат. наук, доц. М.Ж. Байсалова.

Печатается по плану издания Министерства образования и науки Республики Казахстан на 2011г.

© НАО «Алматинский университет энергетики и связи», 2011г.

Понятия множества и элемента множества являются первичными (т.е. не определяемыми с помощью других, более простых понятий) такими, как, например, точка и прямая. Под множеством понимается совокупность некоторых объектов (предметов), которые называются элементами множества. Элементы множеств различны. Приняты следующие обозначения: A, B, X,… - множества; a, b, x, x_1, x₂,…- элементы множеств; - элемент принадлежит А, - элемент не принадлежит А; N – множество натуральных чисел; Z – множество целых чисел; Q – множество рациональных чисел; I - множество иррациональных чисел; R – множество действительных чисел; C – множество комплексных чисел; Ø – пустое множество (не содержит ни одного элемента).

Конечные множества состоят из конечного числа элементов.

Бесконечные – из бесконечного числа элементов.

Способы задания множеств:

а) перечислением элементов, например, X={x₁, x₂,…, x_n},

A = {2,4,5,6,8,…};

б) с помощью характеристического свойства: A={x| Р(x)}, гдеP(x) – свойство Р, которым обладает элемент x,например, A={x| x= };

в) порождающей процедурой, которая описывает способ получения элементов из уже имеющихся элементов, например, множество M={1,2,4,8,16,…} можно задать так: 1) 1 M; 2)m M → 2m M.

Определения:

а) множество В называется подмножеством множества А (обозначается ), если каждый элемент множества В является элементом множества А: , - знак включения;

б) множества А и В называют равными,если они состоят из одних и тех же элементов: и ;

в) если и , то В является собственным подмножеством множества А: - строгое включение.

Заметим, что для обозначения отношения включения применяют как знак строгого, так и не строгого включения, как для собственных, так и для несобственных подмножеств. И только если требуется различить эти подмножества, различают и эти знаки. Не следует путать знаки и : - верно, - не верно.

Множества могут быть элементами других множеств. Множество, элементами которого являются множества, иногда называют семейством и обычно обозначают прописными (готическимими) буквами латинского алфавита.Совокупность всех подмножеств множества А называется его булеаном или множеством-степенью. ОбозначаетсяР(А) или 2^А. Таким образом, Р(А) = {B|B A}. Булеан множества из n элементов, содержит 2ⁿ элементов.

Пример 1.1.1 - A={1,2,3},Р(А) ={Ø,{1},{2},{3},{1,2},{1,3},{2,3}, A}.

Р(А) содержит 8 элементов, 8=2³ .

Обычно в конкретных рассуждениях элементы всех множеств берутся из одного достаточно широкого множества U, которое называется универсальным или универсумом. Для наглядного изображения множеств используют диаграммы Эйлера-Венна, на которых множества обозначаются точками кругов внутри прямоугольника, точки которого – множество U- универсум (см, рисунок 1.1.1, где A Р(U)).

Рисунок 1.1.1

Дата добавления: 2014-12-27