Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200

• Название: Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
• Анкор: Дискретная Математика
• Дата: 15.09.2022
• Размер: 6.37 Mb.
• Имя файла: S_D_Shaporev_-_Diskretnaya_matematika_-_2004.pdf
• Тип: Учебное пособие; #679116
• страница: 1 из 26

Министерство образования Российской Федерации
Балтийский государственный технический университет «Военмех»
С.Д. Шапорев
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Допущено научно-методическим советом по математике вузов Северо-Запада в
качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
«Автоматизированные системы обработки информации и управления», 654600
«Информатика и вычислительная техника», 071900 «Информационные системы и
технологии»
Санкт-Петербург

2 2004

УДК 510.22: 519.1
Ш 24
Шапорев С.Д. Дискретная математика: учебное пособие / Балт. гос. техн. ун-т
«Военмех». СПб., 2004. ??? с.
В книге рассмотрены три раздела курса дискретной математики: теория множеств, комбинаторика и теория графов. Автор уделил особое внимание доступности материала.
Основной текст снабжен большим количеством примеров.
Во второй части книги приведены решения практически всех задач, предложенных на практических занятиях, причем развернутые решения некоторых из них дополняют основной курс, изложенный в первой части данной книги.
Книга полезна для знакомства с основными направлениями и методами дискретной математики и предназначена для студентов технических вузов и читателей, интересующихся данными проблемам.
Р е ц е н з е н т ы: кафедра высшей математики ПГУПС ( проф. каф. доктор техн. наук, проф.
В.Г. Дегтярев ), доктор техн. наук, проф. М.С. Попов.
Утверждено
редакционно-издательским
советом университета
© ШАПОРЕВ С.Д., 2004
© БГТУ, СПб., 2004

2
ЧАСТЬ I. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
1.1. Множества и действия над ними
Первичным понятием теории множеств является понятие самого множества.
Множество - это совокупность некоторых (произвольных) объектов, объединенных по какому-либо признаку. Элементы множества при этом должны быть различными.
Множество обозначается парой скобок
 
... , внутри которых либо просто перечисляются элементы, либо описываются их свойства. Например,


1 2 



x
N
x
A
- множество натуральных чисел, удовлетворяющих условию
1 2 

x
, очевидно, пусто.


B
сложение, умножение

- множество основных арифметических операций. Если необходимо указать, что объект a является элементом множества
A
, то пишут
A
a 
( a принадлежит
A
), наоборот запись
A
a  говорит о том, что
a не принадлежит
A
Если каждый элемент множества
A
является элементом множества B , то пишут
B
A 
или
A
B 
и говорят, что множество
A
является подмножеством множества B .
Множества, состоящие из одних и тех же элементов, называются равными, то есть
B
A 
, в противном случае
B
A 
Очевидно, что

 




 


 
 

A
B
B
A
A
x
B
x
B
x
A
x
x
B
x
A
x
x
B
A



















; итак,

 

A
B
B
A
B
A





Если


M
A
M
и
,
A
M 
, то множество M называется собственным подмножеством множества
A
. Подмножества  - пустое и
A
множества
A
называются несобственными. Если
A
есть подмножество множества B , причем
B
A 
, то пишут
B
A 
или
A
B 
. Совокупность всех подмножеств множества
A
называется его булеаном или множеством - степенью и обозначается через
 
A
P
или
A
2 . С помощью скобок и операций над множествами можно построить новые множества, более сложные чем исходные.
1) Объединение (или сумма). Эта операция над множествами обозначается
B
A 
, определяется как

 



B
x
A
x
C
x
B
A
C







. Все операции над множествами можно иллюстрировать с помощью диаграмм Эйлера

- Венна

. Если за некоторое универсальное множество, содержащее как подмножества все другие множества, обозначить
U
(или

) и
U
U
B B
A
A
Рис 1.1. Объединение множеств
A
и
B
. Рис 1.2. Пересечение множеств
A
и
B
изобразить его в виде всей плоскости, то любое множество
U
A 
можно изобразить в виде части плоскости, то есть в виде некоторой фигуры, лежащей на плоскости. Множество C объединение множеств
A
и B , C на рис. 1.1 заштриховано.
B
A
C


2) Пересечением (или произведением) двух множеств называется такое множество
C , которое состоит из элементов, принадлежащим одновременно обоим множествам, то есть

 



B
x
A
x
C
x
B
A
C







. Пересечение множеств
A
и
B заштриховано и изображено на рис. 1.2.

Леонард Эйлер (1707 - 1783) - швейцарский математик.

Джон Венн (1834 - 1923) - английский математик и логик.

3
3) Разностью двух множеств
A
и B называется множество
B
A \
, состоящее из тех и только тех элементов, которые входят в
A
и одновременно не входят в B , то есть

 



B
A
B
x
A
x
C
x
B
A
C







 \
(см. рис 1.3). Если, в частности,
A
подмножество
U
, то разность
A
U \
обозначается
A
и называется дополнением множества
A
(см. рис 1.4).
U
U
B
A
A
A
Рис 1.3. Разность множеств
A
и
B
. Рис 1.4. Дополнение множества
A
4) Симметрической разностью или кольцевой суммой множеств
A
и B называется множество

 

A
B
B
A
B
A
C
\
\




(см. рис 1.5). Очевидно, что

 


 
 





B
x
A
x
B
x
A
x
C
x
B
A
C











/
. Если
A
a 
и
B
b 
, то пару элемен- тов
 
b
a
,
называют упорядоченной парой, причем пары


1 1
, b
a
и


2 2
, b
a
равны тогда и только тогда, когда и
2 1
2 1
b
b
a
a


5) Множество, элементами которого явля- ются все упорядоченные пары
 
b
a,
,
A
a 
,
B
b 
называется прямым или декарто-
Рис 1.5. Симметрическая разность множеств
A
и
B
вым произведением множеств
A
и B и обозначается
B
A 
Например,
 
 
       


,
3
,
2
,
2
,
2
,
3
,
1
,
2
,
1 3
,
2
,
2
,
1





B
A
B
A
а
       


2
,
3
,
1
,
3
,
2
,
2
,
1
,
2

 A
B
Таким образом, декартово произведение не подчиняется коммутативному закону и
A
B
B
A



справедливо, если
B
A 
Произведение
A
A 
называется декартовым квадратом.
Свойства операций объединения, пересечения и дополнения иногда называются законами алгебры множеств. Эти законы таковы:
1) коммутативный:
A
B
B
A
A
B
B
A






,
;
2) ассоциативный:



 



C
B
A
C
B
A
C
B
A
C
B
A










,
;
3) дистрибутивный:

 
 


 
 
















;
,
C
A
B
A
C
B
A
C
A
B
A
C
B
A
4) законы идемпотентности:
A
A
A
A
A
A




,
, в частности
A
U
A
U
U
A
A
A
A











,
,
,
;
5) законы поглощения:




A
B
A
A
A
B
A
A






,
;
6) законы де Моргана

(двойственности):
,
B
A
B
A
B
A
B
A






7) закон двойного дополнения:
A
A 
;
8). закон включения:
A
B
B
A



;
9). закон равенства:

 
 





B
A
B
A
A
B
B
A
B
A









Конечно, этим кратким перечнем количество законов алгебры множеств не исчерпывается. Другие соотношения между множествами могут быть выведены на основе вышеприведенных законов по правилам алгебры логики.
Пример 1. Доказать включения




\
\
C
B
A
C
B
A




Огастес де Морган (1806 – 1871) – шотландский математик и логик.

4
Легче всего сделать это по диаграмме Эйлера - Венна.
U
U
C C
A
B
A
B


C
B
A
\



C
B
A
\

Пример 2. Пусть




,
4 1
,
6 2








x
N
x
B
x
N
x
A


0 4
2




x
N
x
C
Из каких элементов состоит множество

 

,
C
B
B
A



B
C 
?
Перепишем множества
C
B
A
и
,
, перечислив их элементы.


,
6
,
5
,
4
,
3

A
 
 
2
,
3
,
2


C
B
Тогда
 
  
 
  
3
,
2
,
3
,
2
,
3








C
B
B
A
C
B
B
A
   


   


2
,
3
,
2
,
2
а
,
3
,
2
,
2
,
2




C
B
B
C
1.2. Отношения и функции. Специальные бинарные отношения
Часто элементы разных множеств связаны различными соотношениями, например, соотношениями порядка.
n -местным отношением или
n -местным предикатом P на множествах
n
A
A
A
,...,
,
2 1
называется любое подмножество декартова произведения
n
A
A
A



2 1
. Обозначение n - местного отношения


n
x
x
x
P
,...,
,
2 1
. При
1

n
отношение P называется унарным и является подмножеством множества
1
A . Бинарным (или двуместным при
2

n
) отношением называется множество упорядоченных пар. Элементы
n
x
x
x
,...,
,
2 1
называются координатами или компонентами отношения P .
Для любого множества
A
отношение
 


A
x
x
x
id
A


,
называется тождественным отношением или диагональю, а
 


A
y
A
x
y
x
A
A
A
U
A






,
,
2
полным отношением или полным квадратом.
Пусть P - некоторое бинарное отношение. Тогда областью определения бинарного отношения P называется множество
 


y
P
y
x
x
D
некоторого для
,


, а областью значений множество
 


x
P
y
x
y
R
некоторого для
,


. Аналогично вводится еще несколько определений. Обратным к
P отношением называется множество
 
 


P
y
x
x
y
P



,
,
1
. Композицией бинарных отношений
B
A
P


и
C
B
Q


называется множество
 
 
 


Q
y
z
P
z
x
B
z
C
y
A
x
y
x
Q
P







,
,
,
что т тако
,
,
,

(см. рис 1.6). Для любых бинарных отношений выполняются следующие свойства:
1)
 
P
P



1 1
;
2)


1 1
1




P
Q
Q
P


;
3)




R
Q
P
R
Q
P





- ассоциативность композиции.

5
Пример 1. Пусть


цифра арабская
-
x
x
A 
,
 


5
,
,
,




y
x
A
y
x
y
x
P
. Отношение
P можно записать в виде
         


4
,
9
,
3
,
8
,
2
,
7
,
1
,
6
,
0
,
5

P
. Тогда для этого отношения имеем


9
,
8
,
7
,
6
,
5

D
,


4
,
3
,
2
,
1
,
0

R
,
         


9
,
4
,
8
,
3
,
7
,
2
,
6
,
1
,
5
,
0 1


P
Пример 2. Пусть
 














x
y
y
x
y
x
P
sin
,
2
π
,
2
π
,
,
. Найдем для этого отношения
D , R ,
1

P ,
P
P 
,
P
P

1

,
1

P
P 
отношения.
Очевидно, что

 

2
π
,
1
,
2
π
,
2
π



R
D
. По определению
 
 






P
y
x
x
y
P
,
,
1
 














y
x
x
y
x
y
sin
,
2
π
,
2
π
,
,
. Аналогично для композиции
 

,
,
,
C
y
A
x
y
x
Q
P




B
z 

такой, что
 
  
Q
y
z
P
z
x


,
,
,
, где
B
A
P


, а
C
B
Q


. В нашем случае
B
A
P


,


2
π
,
2
π


A
,
 


y
x
y
x
B


sin
,
,
C
B
P
Q



,


2
π
,
2
π


C
. Тогда
 

 

 


















,
sin
,
2
π
,
2
π
,
,
что т тако
,
2
π
,
2
π
,
2
π
,
2
π
,
x
z
z
x
z
x
z
y
x
y
x
P
P 
A
B C
 









z
y
z
y
y
z
sin
,
2
π
,
2
π
,
,
P
Q
 


y
x
y
x


sin sin
,
. Далее таким же образом
x
z
y
получим
 










,
2
π
,
2
π
,
1
x
y
x
P
P 
Q
P 


z
y



,
2
π
,
2
π
такой, что
 



,
2
π
,
2
π
,
,



z
x
z
x
Рис. 1.6. Графическое представление
 










x
y
y
z
y
z
x
z
sin
,
2
π
,
2
π
,
,
,
sin композиции
Q
P 
 

 
 

2 2
π
,
2
π
2
π
,
2
π
,
2
π
,
2
π
,















y
x
y
x
 




   

















,
2
π
,
2
π
,
/
,
,
что т тако
,
sin
/
,
sin
/
,
1
x
z
x
z
z
x
z
y
x
y
y
y
x
x
x
y
x
P
P 
   





 


















2
π
,
1
,
,
sin
,
2
π
,
2
π
,
/
,
,
,
sin
y
x
y
x
z
y
y
z
y
z
y
z
z
x
Бинарное отношение
B
A
f


называется функцией или отображением из множества
A
в множество
B , если
B
R
A
D
f
f

 ,
и из




f
y
x
f
y
x


2 1
,
,
,
следует, что
2 1
y
y 
. Область определения функции обозначается
f
D
, область значений -
f
R
Определяются они так же, как для бинарных отношений. Если же вместо
A
D
f

выполняется
A
D
f

, то
f
называется частичной функцией.
Говорят, что функция
f
задана на множестве
A
со значениями во множестве B и осуществляет отображение множества
A
во множество
B . Функция
f
из
A
в
B

6 обозначается через
B
A
f

:
или
B
A
f

. Тождественное отношение
   


A
x
x
x
x
id
A

 ,
является функцией
A
A
id
A

:
, для которой
 
x
x
id
A
 для всех
A
x 
Функция
f
называется инъективной (разнозначной), если отношение
1

f
является частичной функцией, т. е. для любых элементов
f
D
x
x

2 1
,
из
2 1
x
x 
следует
 
 
2 1
x
f
x
f

Функция
B
A
f

:
называется функцией
A
на B или сюръективной функцией, если
B
R
f

. Для сюръективной функции для любого
B
y 
существует
A
x 
такой, что
 
y
x
f
 .
Функция
f
называется биективной, если она одновременно сюръективна и инъективна. В этом случае говорят, что
f
осуществляет взаимно однозначное соответствие между множествами
A
и B . Биекция
A
A
f

:
называется подстановкой множества
A
Простейшим примером подстановки является функция
A
id .
На рис. 1.7 показаны функции
B
A
f
j

:
,
4
,
1

i
. Функция
1
f сюръективна, но не инъективна, функция
2
f инъективна, но не сюръективна, функция
3
f биективна и явля- ется подстановкой (если
B
A 
), функция
4
f не
1
f
3
f инъективна и не сюръективна.
Функции обладают несколькими легко
B
2
f доказываемыми свойствами.
1) Композиция двух функций есть функ-
4
f ция, т. е. если
B
A
f

:
,
C
B
g

:
, то
C
A
g
f

:

A
2) Композиция двух биективных функ-
Рис. 1.7. Виды функций.
ций есть биективная функция: если
B
A
f

:
,
C
B
g

:
, то
C
A
g
f

:

3) Отображение
B
A
f

:
имеет обратное отображение
A
B
f


:
1
тогда и только тогда, когда
f
- биекция, т. е. если
B
A
f

:
, то
A
B
f


:
1
,
A
id
f
f

1

,
B
id
f
f



1
В теории множеств важную роль играют два вида специальных бинарных отношений: отношения эквивалентности и отношения порядка. Прообразами этих отношений служат интуитивные понятия равенства, предшествования и предпочтения.
Рассмотрим два конечных множества


n
a
a
a
A
,...,
,
2 1

,


m
b
b
b
B
,...,
,
2 1

и бинарное отношение
B
A
P


. Введем матрицу
 
j
i
p
P
,

бинарного отношения P следующим образом:










,
,
0
,
,
,
1
,
P
b
a
P
b
a
p
j
i
j
i
j
i
Эта матрица содержит полную информацию о связях между элементами множеств
A
и
B и позволяет представить эту информацию в графическом виде.
Матрица любого бинарного отношения обладает следующими свойствами:
1) если
B
A
Q
P


,
и
 
 
j
i
j
i
q
Q
p
P
,
,
,


, то


j
i
j
i
q
p
Q
P
Q
P
,
,





;


j
i
j
i
q
p
Q
P
Q
P
,
,





, причем сложение элементов матрицы осуществляется по правилам 0+0=0, 1+1=1, 1+0=0+1=1, а умножение почленно обычным образом, т. е. по правилам
1 1
1
,
0 1
0 0
1






;
2) если
C
B
Q
B
A
P




,
, то
Q
P
Q
P



и умножение матриц производится по обычному правилу умножения матриц, но произведение и сумма элементов при перемножении матриц находится по правилам пункта 1;

7 3)
T
P
P

1
, где
1

P
- матрица обратного отношения
1

P ;
4) если
Q
P 
, то
 
 
j
i
j
i
q
Q
p
P
,
,
,


и
j
i
j
i
q
p
,
,
