Математическая логика и теория алгоритмов. Самохин А.В. - 10 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Составители: 

Рубрика: 

10 çÌÁ×Á I. íÎÏÖÅÓÔ×Á É ÍÏÝÎÏÓÔÉ
ÓÔÑÈ É ÄÌÑ ÂÅÓËÏÎÅÞÎÙÈ ÍÎÏÖÅÓÔ×.) óÌÅÄÕÀÝÁÑ ÆÏÒÍÕÌÁ ÐÏÚ×ÏÌÑÅÔ ÎÁÊÔÉ
ÍÏÝÎÏÓÔØ ÏÂßÅÄÉÎÅÎÉÑ ÎÅÓËÏÌØËÉÈ ÍÎÏÖÅÓÔ×, ÅÓÌÉ ÉÚ×ÅÓÔÎÙ ÍÏÝÎÏÓÔÉ ËÁ-
ÖÄÏÇÏ ÉÚ ÎÉÈ, Á ÔÁËÖÅ ÍÏÝÎÏÓÔÉ ×ÓÅÈ ÐÅÒÅÓÅÞÅÎÉÊ.
ôÅÏÒÅÍÁ 1 (æÏÒÍÕÌÁ ×ËÌÀÞÅÎÉÊ É ÉÓËÌÀÞÅÎÉÊ).
|A ∪ B| = |A| + |B| − |A ∩ B|;
|A ∪ B ∪ C| = |A| + |B| + |C| −
− |A ∩ B| − |A ∩ C| − |B ∩ C| +
+ |A ∩ B ∩ C|;
×ÏÏÂÝÅ |A
1
∪ . . . ∪ A
n
| ÒÁ×ÎÏ
X
i
|A
i
| −
X
i<j
|A
i
∩ A
j
| +
X
i<j<k
|A
i
∩ A
j
∩ A
k
| − . . .
äÏËÁÚÁÔÅÌØÓÔ×Ï. üÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ ÎÅÓÌÏÖÎÏ ÄÏËÁÚÁÔØ ÉÎÄÕËÃÉÅÊ ÐÏ n,
ÎÏ ÍÙ ÐÒÉ×ÅÄ¾Í ÄÒÕÇÏÅ ÄÏËÁÚÁÔÅÌØÓÔ×Ï. æÉËÓÉÒÕÅÍ ÐÒÏÉÚ×ÏÌØÎÏÅ ÍÎÏÖÅÓÔ-
×Ï U, ÐÏÄÍÎÏÖÅÓÔ×ÁÍÉ ËÏÔÏÒÏÇÏ Ñ×ÌÑÀÔÓÑ ÍÎÏÖÅÓÔ×Á A
1
, . . . , A
n
.
èÁÒÁËÔÅÒÉÓÔÉÞÅÓËÏÊ ÆÕÎËÃÉÅÊ ÍÎÏÖÅÓÔ×Á X ⊂ U ÎÁÚÙ×ÁÀÔ ÆÕÎË-
ÃÉÀ χ
X
, ËÏÔÏÒÁÑ ÒÁ×ÎÁ 1 ÎÁ ÜÌÅÍÅÎÔÁÈ X É 0 ÎÁ ÏÓÔÁÌØÎÙÈ ÜÌÅÍÅÎÔÁÈ U.
ïÐÅÒÁÃÉÉ ÎÁÄ ÐÏÄÍÎÏÖÅÓÔ×ÁÍÉ ÍÎÏÖÅÓÔ×Á U ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ÏÐÅÒÁÃÉÑÍ Ó
ÉÈ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÉÍÉ ÆÕÎËÃÉÑÍÉ. ÷ ÞÁÓÔÎÏÓÔÉ, ÐÅÒÅÓÅÞÅÎÉÀ ÍÎÏÖÅÓÔ×
ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÐÒÏÉÚ×ÅÄÅÎÉÅ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÉÈ ÆÕÎËÃÉÊ:
χ
A∩B
(u) = χ
A
(u)χ
B
(u)
äÏÐÏÌÎÅÎÉÀ (ÄÏ U) ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÆÕÎËÃÉÑ 1 − χ, ÅÓÌÉ χ ¡ ÈÁÒÁËÔÅÒÉÓÔÉ-
ÞÅÓËÁÑ ÆÕÎËÃÉÑ ÉÓÈÏÄÎÏÇÏ ÍÎÏÖÅÓÔ×Á.
þÉÓÌÏ ÜÌÅÍÅÎÔÏ× ÍÎÏÖÅÓÔ×Á ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÁË ÓÕÍÍÕ ÚÎÁÞÅÎÉÊ ÅÇÏ ÈÁ-
ÒÁËÔÅÒÉÓÔÉÞÅÓËÏÊ ÆÕÎËÃÉÉ:
|X| =
X
u
χ
X
(u).
ïÂßÅÄÉÎÅÎÉÅ A
1
∪ . . . ∪ A
N
ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÁË ÄÏÐÏÌÎÅÎÉÅ Ë ÐÅÒÅÓÅÞÅÎÉÀ
ÄÏÐÏÌÎÅÎÉÊ ÍÎÏÖÅÓÔ× A
i
; × ÔÅÒÍÉÎÁÈ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÉÈ ÆÕÎËÃÉÊ ÉÍÅÅÍ
χ
A
1
∪...∪A
n
= 1 − (1 − χ
A
1
) . . . (1 − χ
A
n
).
òÁÓËÒÙ× ÓËÏÂËÉ × ÐÒÁ×ÏÊ ÞÁÓÔÉ, ÍÙ ÐÏÌÕÞÉÍ
X
i
χ
A
i
−
X
i<j
χ
A
i
χ
A
j
+
X
i<j<k
χ
A
i
χ
A
j
χ
A
k
− . . .
É ÐÒÏÓÕÍÍÉÒÏ×Á× ÌÅ×ÕÀ É ÐÒÁ×ÕÀ ÞÁÓÔØ ÐÏ ×ÓÅÍ ÜÌÅÍÅÎÔÁÍ U (ÏÂÅ ÏÎÉ ÅÓÔØ
ÆÕÎËÃÉÉ ÎÁ U), ÐÏÌÕÞÉÍ ÆÏÒÍÕÌÕ ×ËÌÀÞÅÎÉÊ É ÉÓËÌÀÞÅÎÉÊ.
10                                                    çÌÁ×Á I. íÎÏÖÅÓÔ×Á É ÍÏÝÎÏÓÔÉ

ÓÔÑÈ É ÄÌÑ ÂÅÓËÏÎÅÞÎÙÈ ÍÎÏÖÅÓÔ×.) óÌÅÄÕÀÝÁÑ ÆÏÒÍÕÌÁ ÐÏÚ×ÏÌÑÅÔ ÎÁÊÔÉ
ÍÏÝÎÏÓÔØ ÏÂßÅÄÉÎÅÎÉÑ ÎÅÓËÏÌØËÉÈ ÍÎÏÖÅÓÔ×, ÅÓÌÉ ÉÚ×ÅÓÔÎÙ ÍÏÝÎÏÓÔÉ ËÁ-
ÖÄÏÇÏ ÉÚ ÎÉÈ, Á ÔÁËÖÅ ÍÏÝÎÏÓÔÉ ×ÓÅÈ ÐÅÒÅÓÅÞÅÎÉÊ.
     ôÅÏÒÅÍÁ 1 (æÏÒÍÕÌÁ ×ËÌÀÞÅÎÉÊ É ÉÓËÌÀÞÅÎÉÊ).
                        |A ∪ B| = |A| + |B| − |A ∩ B|;
                    |A ∪ B ∪ C| = |A| + |B| + |C| −
                                     − |A ∩ B| − |A ∩ C| − |B ∩ C| +
                                     + |A ∩ B ∩ C|;
×ÏÏÂÝÅ |A1 ∪ . . . ∪ An | ÒÁ×ÎÏ
             X             X               X
                   |Ai | −    |Ai ∩ Aj | +   |Ai ∩ Aj ∩ Ak | − . . .
                i             i

Страницы