ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.04.2021
Просмотров: 608
Скачиваний: 1
ФЕДЕРАЛЬНОЕ
АГЕНТСТВО
ПО
ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ
ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ
ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО
ОБРАЗОВАНИЯ
«
ВОРОНЕЖСКИЙ
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
»
И
.
Н
.
Булгакова
ДИСКРЕТНАЯ
МАТЕМАТИКА
ЭЛЕМЕНТЫ
ТЕОРИИ
,
ЗАДАЧИ
И
УПРАЖНЕНИЯ
Часть
1
Учебное
пособие
для
вузов
2-
е
издание
,
переработанное
и
дополненное
Издательско
-
полиграфический
центр
Воронежского
государственного
университета
2008
2
Утверждено
научно
-
методическим
советом
факультета
ПММ
ВГУ
19
ок
-
тября
2007
г
.,
протокол
№
2
Рецензент
к
.
т
.
н
.,
доцент
кафедры
ПО
и
АИС
ф
-
та
ПММ
ВГУ
И
.
Е
.
Воронина
Учебное
пособие
подготовлено
на
кафедре
математических
методов
ис
-
следования
операций
факультета
ПММ
Воронежского
государственного
университета
.
Рекомендуется
для
студентов
1
курса
д
/
о
и
в
/
о
,
обучающихся
по
специаль
-
ности
«
Прикладная
математика
и
информатика
»,
а
также
будет
полезна
всем
изучающим
дискретную
математику
.
Для
специальностей
: 010200 –
Прикладная
математика
и
информатика
;
351400 –
Прикладная
информатика
в
юриспруденции
; 351500 –
Математи
-
ческое
обеспечение
и
администрирование
информационных
систем
;
080700 –
Бизнес
-
информатика
; 080800 –
Прикладная
информатика
3
1.
ТЕОРИЯ
МНОЖЕСТВ
И
ОТНОШЕНИЙ
1.1
Элементы
теории
множеств
Под
множеством
понимается
совокупность
некоторых
объектов
(
элементов
),
объединенных
некоторым
признаком
.
Множества
обычно
обозначают
большими
буквами
алфавита
W
Z
U
C
B
A
,
,
,
,
,
.
Элементы
,
входящие
в
множество
,
обозначаются
малыми
буквами
w
,
,
,
,
,
z
y
x
b
a
.
За
-
пись
C
Î
x
означает
,
что
x
является
элементом
множества
C
,
а
запись
C
Ï
x
означает
,
что
x
не
принадлежит
множеству
C
.
Два
множества
счи
-
таются
равными
,
если
они
состоят
из
одних
и
тех
же
элементов
.
Для
описания
множества
пользуются
двумя
способами
.
Первый
спо
-
соб
состоит
в
простом
перечислении
его
элементов
.
Так
,
запись
{
}
5
1
0
,
,
=
A
означает
,
что
множество
A
состоит
из
трех
чисел
0,1
и
5.
Второй
способ
со
-
стоит
в
определении
множества
с
помощью
некоторого
свойства
P,
позво
-
ляющего
определить
,
принадлежит
ли
данный
элемент
данному
множеству
или
нет
.
В
этом
случае
используется
коллективизирующее
обозначение
{
}
)
(
:
x
P
x
=
A
,
которое
читается
следующим
образом
:
множество
A
состоит
из
всех
эле
-
ментов
x
,
для
которых
)
(
x
P
истинно
.
Если
свойство
P
относится
к
эле
-
ментам
некоторого
множества
C
,
то
будем
писать
также
{
}
)
(
:
x
P
x
C
A
Î
=
.
Например
,
множество
{
}
5
4
3
2
1
,
,
,
,
можно
задать
следую
-
щим
образом
:
{
}
[ ]
{
}
5
,
1
:
5
,
4
,
3
,
2
,
1
интервала
из
число
целое
x
x
-
=
.
Множество
,
не
содержащее
элементов
,
называется
пустым
множест
-
вом
и
обозначается
Æ
.
Знаком
Í
обозначим
отношение
включения
между
множествами
,
т
.
е
.
B
A
Í
,
если
каждый
элемент
множества
A
есть
элемент
множества
B
.
Ес
-
ли
B
A
Í
,
то
говорят
,
что
множество
A
есть
подмножество
множества
B
.
Равенство
двух
множеств
A
и
B
означает
выполнение
двух
вклю
-
чений
:
B
A
Í
и
A
B
Í
.
Если
B
A
Í
и
B
A
¹
,
то
говорят
,
что
A
есть
собственное
подмно
-
жество
B
и
пишут
B
A
Ì
.
Множество
всех
подмножеств
множества
A
называется
множест
-
вом
-
степенью
и
обозначается
( )
A
R
.
Заметим
,
что
: a)
C
C
Í
;
б
)
если
Z
U
U
C
Í
Í
,
,
то
Z
C
Í
;
в
)
ес
-
ли
C
U
U
C
Í
Í
,
,
то
U
C
=
.
Не
надо
смешивать
отношения
принадлежности
и
включения
.
Хотя
{ } { } { }
{ }
1
1
,
1
1
Î
Î
,
не
верно
,
что
{ }
{ }
1
1
Î
,
так
как
единственным
элементом
множества
{ }
{ }
1
является
{ }
1 .
Пустое
множество
есть
подмножество
любого
множества
.
4
Число
элементов
в
множестве
C
обозначается
C
.
Рассмотрим
методы
получения
новых
множеств
из
уже
существую
-
щих
.
Объединением
множеств
A
и
B
называется
множество
B
A
È
,
все
элементы
которого
являются
элементами
множества
A
или
B
:
{
}
B
A
B
A
Î
Î
=
È
x
или
x
x
:
.
Пересечением
множеств
A
и
B
называется
множество
B
A
Ç
,
эле
-
менты
которого
являются
элементами
и
множества
A
,
и
множества
B
:
{
}
B
A
B
A
Î
Î
=
Ç
x
и
x
x
:
.
Очевидно
,
что
выполняются
включения
B
A
A
B
A
È
Í
Í
Ç
и
B
A
B
B
A
È
Í
Í
Ç
.
Разностью
множеств
A
и
B
называется
множество
B
A
\
тех
эле
-
ментов
из
A
,
которые
не
принадлежат
B
:
{
}
B
A
B
A
Ï
Î
=
x
и
x
x
:
\
.
Симметричной
разностью
множеств
A
и
B
называется
множество
A
B
B
A
B
A
\
\
È
=
+
.
Если
все
рассматриваемые
в
данный
момент
множества
являются
подмножествами
некоторого
множества
U
,
то
множество
U
называют
универсальным
для
данного
рассмотрения
.
Дополнением
множества
A
называется
множество
A
A
\
U
=
.
Для
наглядного
представления
отношений
между
подмножествами
какого
-
либо
универсального
множества
используются
диаграммы
Эйлера
–
Венна
.
Операции
над
множествами
имеют
следующие
приоритеты
в
поряд
-
ке
убывания
:
операция
взятия
дополнения
,
операция
пересечения
,
опера
-
ция
объединения
.
5
Отметим
следующие
основные
законы
для
операций
над
множествами
:
1.
A
B
B
A
È
=
È
(
коммутативность
объединения
);
2.
A
B
B
A
Ç
=
Ç
(
коммутативность
пересечения
);
3.
(
) (
)
M
B
A
M
B
A
È
È
=
È
È
(
ассоциативность
объединения
);
4.
(
) (
)
M
B
A
M
B
A
Ç
Ç
=
Ç
Ç
(
ассоциативность
пересечения
);
5.
(
) (
) (
)
M
A
B
A
M
B
A
È
Ç
È
=
Ç
È
(1-
й
закон
дистрибутивности
);
6.
(
) (
) (
)
M
A
B
A
M
B
A
Ç
È
Ç
=
È
Ç
(2-
й
закон
дистрибутивности
);
7.
A
A
=
Æ
È
;
8.
U
U
=
È
A
;
9.
Æ
=
Æ
Ç
A
;
10.
A
A
=
Ç
U
;
11.
B
A
B
A
Ç
=
È
(
закон
де
Моргана
);
12.
B
A
B
A
È
=
Ç
(
закон
де
Моргана
);
13.
(
)
A
B
A
A
=
Ç
È
(
закон
поглощения
);
14.
(
)
A
B
A
A
=
È
Ç
(
закон
поглощения
).
Рассмотрим
методику
решения
задач
по
данной
теме
.
Пример
1
.
Равны
ли
следующие
множества
:
1)
{
}
5
,
4
,
2
и
{
}
2
,
5
,
4
,
2
;
2)
{ }
2
,
1
и
1,2 ;
3)
{
}
3
,
2
,
1
и
{ } { } { }
{
}
3
,
2
,
1
;
4)
{ }
{
}
3
,
2
,
1
и
{ } { }
{
}
3
,
2
,
1
.
Решение
.
Для
доказательства
равенства
произвольных
множеств
нужно
проверить
,
что
первое
множество
включено
во
второе
,
а
второе
,
в
свою
очередь
,
включено
в
первое
,
т
.
е
.
любой
элемент
первого
множества
является
элементом
второго
множества
,
а
любой
элемент
второго
множе
-
ства
является
элементом
первого
множества
.
Проверка
дает
положительный
результат
для
множеств
из
пункта
1).
Это
можно
наглядно
показать
на
следующей
схеме
,
где
стрелочка
,
идущая
от
элемента
,
показывает
,
какой
элемент
в
другом
множестве
ему
соответствует
.
{
}
5
,
4
,
2
{
}
2
,
5
,
4
,
2
{
}
2
,
5
,
4
,
2
{
}
5
,
4
,
2
Множества
из
пункта
2)
неравны
,
так
как
,
например
,
элемент
1
из
первого
множества
не
имеет
себе
равного
во
втором
множестве
.
Второе
множество
состоит
из
единственного
элемента
–
множества
{ }
2
,
1 .