Кустицкая Т.А. Дискретная математика 1

Содержание

1 Основные определения теории множеств. Способы задания множества. 1

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

2.1 Свойства операций над множествами . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Мощность множества 5

3.1 Разбиения и покрытия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2 Булеан . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3 Множество действительных чисел . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.4 Прямое произведение множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Формула включений и исключений 9

5 Соответствия и функции 10

5.1 Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6 Отношения 13

6.1 Способы задания бинарных отношений . . . . . . . . . . . . . . . . . . . . . . . 13

6.2 Операции над отношениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

6.3 Свойства отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

6.4 Отношение эквивалентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

6.5 Отношение порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

7 Алгебраические системы 16

7.1 Бинарные алгебраические операции . . . . . . . . . . . . . . . . . . . . . . . . 16

1 Основные определения теории множеств. Способы задания

множества.

Дискретная математика изучает в основном конечные множества и операции на них. По-

этому она имеет широкий спектр приложений, прежде всего связанных с компьютерны-

ми технологиями, например с системами автоматизированного проектирования. В самом

первоначальном названии компьютера "электронная цифровая вычислительная машина"

- слово "цифровая" указывает на принципиально дискретный характер работы данного

устройства.

Человеческое мышление утроено так, что оно представляет мир состоящим из отдель-

ных объектов. Хотя с точки зрения философии мир представляет собой единое целое и

выделение в нем объектов -это не более чем произвольный акт нашего мышления.

Основоположник теории множеств Кантор дал следующее определение множества:

Определение 1 Множество – это объединение в одно общее объектов, хорошо разли-

чаемых нашей интуицией или нашей мыслью.

Определение 2 Множество – это определенная совокупность объектов. Эти объекты

называются элементами множества.

Множества будем обозначать, как правило, большими (прописными) буквами латинского

алфавита. Элементы множества - малыми (строчными) буквами латинского алфавита.2 Кустицкая Т.А. Дискретная математика

a ? A - элемент a принадлежит множеству A.

a 6? A - элемент a не принадлежит множеству A.

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

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

1. Перечисление элементов. Элементы заключаются в фигурные скобки.

M = {a1, a2, . . . , ak}

2. Порождающей процедурой. Указывается способ получения новых элементов из уже

имеющихся.

3. С помощью характеристического предиката. Предикат описывает свойство всех эле-

ментов, входящих в множество.M = {x : P (x)} или M = {x|P (x)}

Пример 1

1. N = {0, 1, 2, 3, . . . }

2. 1 ? M; если a ? M, то 2 · a ? M

3. M = {x : x ? N ? x < 10}

Определение 3 Если каждый элемент множества A является элементом множества

B, то говорят, что A содержится в множестве B или A является подмножеством

B (A ? B).

Заметим, что M ? M и по определению ? ? M.

Если A ? B и B ? A, то множества A и B называются равными A = B.

Если A ? B и A =6 ?, A =6 B, то A называется собственным подмножеством B.

Задание 1 Определить как между собой соотносятся множества A = {1, 2, 3, 5, 7}, B =

{1, 3, 5}, C = {a|a ? нечетн ? a < 7}.

Выписать все собственные подмножества множества B

Обычно в конкретных рассуждениях элементы берутся из некоторого одного достаточно

широкого множества U (своего для каждого случая), которое называется универсальным

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

Задание 2 Какое множество из заданных в некоторой задачи можно выбрать в каче-

стве унивесума?

A-множество студентов первого курса СФУ,

B- множество студентов ИКИТ, сдавших на 5 экзамен по физике в зимнюю сессию

2010-2011,

C - множество студентов ИКИТ,

D - множество студентов ИКИТ с фамилией "Иванов".

Диаграмма Эйлера-Венна - это графический способ представления мно-

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

представляющего универсальное множество U, а внутри его – кругов (или каких-нибудь

других замкнутых фигур), представляющих множества. Фигуры должны пересекаться

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

образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут

рассматриваться как элементы соответствующих множеств.Кустицкая Т.А. Дискретная математика 3

Рис. 1: Пример диаграммы Эйлера-Венна

Пример 2 U = {a, b, c, d, f }, A = {a, b, c}

Задание 3 Нарисовать диаграмму Эйлера-Венна для множеств B, C, D из Задания 2,

если известно, что

а) все Ивановы, являющиеся студентами ИКИТ сдали в зимнюю сессию физику на 5

б) среди студентов ИКИТ, сдавших на 5 физику не было ни одного Иванова

в) среди студентов ИКИТ, сдавших на 5 физику был хотя бы один Иванов4 Кустицкая Т.А. Дискретная математика

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

1. Объединение A ? B = {x|x ? A ? x ? B}

2. Пересечение A ? B = {x|x ? A ? x ? B}

3. Разность A \ B = {x|x ? A ? x 6? B}

4. Дополнение A = {x|x ? U ? x 6? A}

5. Симметрическая разность

A 4 B = {x|(x ? A ? x 6? B) ? (x ? B ? x 6? A)}

Пример 3 U = {1, 2, 3, 4, 5, 6}; A = {1, 2, 3}; B = {3, 4, 5}

A ? B = {1, 2, 3, 4, 5}

A ? B = {3}

A \ B = {1, 2}

A 4 B = {1, 2, 4, 5}

A = {4, 5, 6}

2.1 Свойства операций над множествами

Пусть задан универсум U. Тогда ?A, B, C ? U выполняются свойства:Кустицкая Т.А. Дискретная математика 5

1. идемпотентность(повторное действие над объектом не изменяет его)

A ? A = A, A ? A = A;

2. коммутативность

A ? B = B ? A, A ? B = B ? A;

3. ассоциативность

A ? (B ? C) = (A ? B) ? C, A ? (B ? C) = (A ? B) ? C;

4. дистрибутивность

A ? (B ? C) = (A ? B) ? (A ? C), A ? (B ? C) = (A ? B) ? (A ? C)

5. поглощение

(A ? B) ? A = A (A ? B) ? A = A

6. свойство нуля

A ? ? = A, A ? ? = ?;

7. свойство единицы

A ? U = U, A ? U = A

8. инволютивность

A = A

9. законы де Моргана

A ? B = A ? B A ? B = A ? B

10. свойство дополнения

A ? A = U A ? A = ?

11. свойство разности

A \ B = A ? B

Способы доказательства свойств:

1. Провести формальное рассуждение, пользуясь определениями операций.

2. Нарисовать диаграммы Эйлера-Венна для обеих частей равенства и убедиться, что

они совпадают.

Пример 4 Докажем свойство идемпотентности: A ? A = A

Возьмем произвольный x ? A ? A. По определению операции объединения множеств

это означает, что x ? A ? x ? A, т.е. в любом случае x ? A. Это значит, что A ? A ? A.

Пусть теперь x ? A. Это можно записать и так: x ? A ? x ? A. По определению

операции объединения x ? A ? A, т.е. A ? A ? A.

По определению равенства множеств A ? A = A

Пример 5 С помощью диаграмм Эйлера-Венна доказать 1-й закон де Моргана

Пример 6 Упростить выражение A ? B ? B

A ? B ? B = (A ? B) ? B = (A ? B) ? B = A ? (B ? B) = A ? B

3 Мощность множества

Определение 4 Мощность множества - это число его элементов. Обозначение |M|.

Если |A| = |B|, то множества A и B называют равномощными.

Пример 7 |{1, 2, 3, 4}| = 4

|?| = 0, но |{?}| = 1

Мощность множества натуральных чисел |N| = N0 - алеф-нуль.6 Кустицкая Т.А. Дискретная математика

Определение 5 Множество называется счетным, если оно равномощно множеству

натуральных чисел (т.е. его элементы можно перенумеровать натуральными числами).

Пример 8 • Множество простых чисел (простое число - натуральное число,

имеющее ровно два различных натуральных делителя: единицу и самого себя)

{2, 3, 5, 7, 11, 13, 17, . . . };

• Множество целых чисел Z = {. . . , ?2, ?1, 0, 1, 2, . . . }

• Множество рациональных чисел Q(Рациональное число — число, представляемое

несократимой обыкновенной дробью

m

n

, где числитель m — целое число, а знаме-

натель n — натуральное число)

Рис. 2: Нумерация элементов множества Q

Определение 6 Множество называется бесконечным, если его мощность ? N0.

Таким образом, счетное множество - самое "маленькое" из бесконечных

3.1 Разбиения и покрытия

Множества могут сами выступать в качестве элементов множеств. Множество, элементы

которого являются множеством обычно называют классом или семейством и обозначают

прописными "рукописными"буквами латинского алфавита.

Пример 9 На языке множеств опишем жителей квартир, расположенных на одной

лестничной клетке.

A = {Иванов И.И., Иванова А.А, Иванов П.И} - множество жителей 1-й квартиры;

B = {Петров Н.Н., Петрова Г.Г} - множество жителей 2-й квартиры;

C = {Сидорова О.О.} - множество жителей 3-й квартиры.

M = {A, B, C} - семейство жителей квартир на одной лестничной клетке.

Пусть E = {Ei}i?I - некоторое семейство подмножеств множества A, т.е. Ei ? A?i ? I.Кустицкая Т.А. Дискретная математика 7

Определение 7 Семейство E называется покрытием множества A, если каждый эле-

мент A принадлежит хотя бы одному из Ei:

A ?

[

i?I

Ei ?? ?x ? A ?i ? I | x ? Ei

Если при этом множества из E попарно не пересекаются

?i, j | i =6 j Ei ? Ej = ?,

то E называется разбиением множества A.

Пример 10 Пусть M = {a, b, c}.

{{a, b}, {b, c}} - покрытие M,

{{a, b}, {c}} - разбиение M