Число элементов в конечном множестве


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Число элементов в конечном множестве

УТВЕРЖДЕНИЯ
, принимаемые без доказательств.

1.

Множество
{1,,3,…,
n
}

содержит
n

элементов.

.

A
,
B



множества, и существует
правило, сопоставляющее каждому элементу из A вполне определе
нный элемент из
B
, причем
взаимно

однозначно
.

Т
о
гда

|
A
|

|
B
|
, где
|
A
|


число элементов во множестве мощность множества.

Замечание
: В теории отношений правило
, сопоставляющее каждому элементу
x
X


вполне определенный элемент
f
x
Y



,

называют

отображением

f

или
соответствием
, действующем из
X

в
Y
.

3.

0
|
|


но
1
}
{


.

Опр.

Если существует между
{1,,3,…,
n
}

и
A

взаимно

одно
значное соответствие
, то

говорят, что множество
{1,,3,…,
n
}

нумерует

множество A:
A
a
a
a
n

{
,
,
,
}
1


.

Утверждение
.

Если множество
{1,,3,…,
n
}

нумерует A, то
|
A
|

n
.

Опр.

Говорят, что множество
A

конечно
, если существует такое число
n
A
, что множество
{1,
,3,…,
n
А
}

нумерует A, при
этом
|
A
|

n
А
.

Утверждение
. Число элементов в конечном множестве определено однозначно.

ПРАВИЛА
.
Пусть
A
,
B
, С


конечные множества.

1.

Пусть
A
,
B



непересека
ющиеся множества, тогда
|
|
A
B


|
|
A

|
|
B
.

.

|
|
A
B


|
|
A

|
|
B

|
|
A
B

.


Очевидно,
B
A



\

A
B
A

, и множества A и
A
B
\

не пересекаются. Тогда из правила 1 получим:


|
|
A
B


A
B
A
\

.

*

Очевидно,

\



A
B
B
A
B



, и множества
B
A


и
A
B
\

не пересекаются.
Тогда из правила 1 получим:



\



A
B
B
A
B



.

**

Подставляя выражение для
A
B
\

из ** в *, получаем:
|
|
A
B


|
|
A

|
|
B

|
|
A
B

.



3.

правило включения

исключения

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A
B
C
A
B
C
A
B
A
C
B
C
A
B
C
















знаки чередуются


4.


пра
вило суммы

A
A
A
A
i
j
A
A
A
n
i
j
n
i
i
n
1
1
1
,
,
:
,
|
|
|
|












.

5.

|
|
|
|
|
|
A
B
A
B


. Следствие:
|
|
|
|
A
A
A
n
n









.


В случае, когда одно из множеств
A
,
B

пусто, то и
B
A


пусто. Рассмотрим случай, когда

A
,
B



непустые
множества. Пронумеруем

A
:
}
,
,
,
{

1
A
a
a
a
A


.

Тогда


A
i
i
B
a
B
A
1
}
{





и множества
B
a
i

}
{

попарно не пересекаются.
По правилу суммы:






A
i
i
B
a
B
A
1
}
{
|
|
.

Пронумеруем
B
:
}
,
,
,
{

1
B
b
b
b
B


.

Имеем:
B
a
i

}
{



}
,

,...,
,
{
1
B
i
i
b
a
b
a

и
B
a
i

}
{

B
. Следовательно,
B
A
B
B
A
A
i





1
|
|
.



ПРИМЕР
.

Из города
A

в город
B

ведет три дороги, а из города
B

в город
C



4 дорог
и. Сколькими способами можно добрат
ь
ся из
A

в
C

через
B
?



AB



множество дорог из
A

в
B
.
BC



дороги из
B

в
C
.

Дорог из
A

в
C



упорядоченная пара дорог из
AB

и
BC
, т.е.
AC


AB

BC
.

|
|
AB
BC




3
4
1


6.

A
,

A



множест
во всех подмножеств.
Тогда

|
|
|
|


A
A

.

ПРИМЕР
.

A

{
,
,
}
1

3
,

1

3
1

1
3

3
1

3
A


{
,
{
},
{
},
{
},
{
,
},
{
,
},
{
,
},
{
,
,
}}
.

7.

X
Y
,


,
Y
X


множество отображений, действующих из
X

в
Y
т.е.
f
Y
f
X
Y
X



:
, м
н
о
жество

степень.
Тогда
|
|
|
|
|
|
Y
Y
X
X

.

ПРИМЕР
.

В НИИ работает 4 курьера


A
,
B
,
C
,
D
. Сколько существует способов разослать 7 писем в 7 различных организ
а
ций, если
доставка осуществляется только курьерами, работающими в НИИ?

Способ доставки определя
ется указанием для каждого
письма, какой из курьеров его доставляет. Т.е способ
доставки


отображение из множества писем во множество
курьеров. Тогда число способов доставки писем


|
|
|
|
|
|
K
K
П
П



4
1634
7

способа.































П











К







Приложенные файлы

  • pdf 15869469
    Размер файла: 176 kB Загрузок: 0

Добавить комментарий