Материал: Prak_alg

ФЕДЕРАЛЬНОЕ

АГЕНТСТВО

ПО

ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ

ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ

ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ

«

ВОРОНЕЖСКИЙ

ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

» 

 
 
 
 
 
 
 

И

.

Н

. 

Булгакова

 
 
 

ДИСКРЕТНАЯ

МАТЕМАТИКА

ЭЛЕМЕНТЫ

ТЕОРИИ

, 

ЗАДАЧИ

И

УПРАЖНЕНИЯ

Часть

 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 .