Дискретная математика. Кулабухов С.Ю. - 12 стр.

gLAWA wWEDENIE W TEORI@ MNOVESTW
      I.




dOKAZATELXSTWO. pRAWAQ ^ASTX RAWENSTWA (2) QWLQETSQ SUMMOJ n SLAGAEMYH, k-E PO PORQDKU
SLAGAEMOE IMEET WID
                                        (;1)k;1Sk (A1 
 A2
 : : :
 An)

GDE Sk (A1 
 A2
 : : :
 An) ESTX SUMMA ^ISEL jAi1 \ Ai2 \ : : : \ Aik j PO WSEM WOZMOVNYM PERESE^ENIQM
ROWNO k RAZNYH MNOVESTW IZ MNOVESTW A1 
 A2
 : : :
 An.
   iZ FORMULY (1) SLEDUET, ^TO FORMULA (2) SPRAWEDLIWA DLQ DWUH MNOVESTW. pREDPOLOVIM, ^TO
ONA SPRAWEDLIWA DLQ n ; 1 MNOVESTWA, I POKAVEM, ^TO ONA WYPOLNQETSQ I DLQ n MNOVESTW, TO
ESTX PROWEDEM DOKAZATELXSTWO METODOM MATEMATI^ESKOJ INDUKCII.
   pO PREDPOLOVENI@
                       jA1 A2 : : : Anj = jA1j + jA2 A3 : : : Anj;
                       ;j(A1 \ A;2) (A1 \ A3) : : : (A1 \ An)j =
                       = jA1 j + S1 (A2 
 A3
 : : :
 An) ; S2 (A 2 
 A3
 : : :
 An) + : : :
                       : :;: + (;1) Sn;1 (A2
 A3 
 : : :
 An ) ;
                                   n ; 2
                                                               


                       ; S1(A1 \ A2
 A1 \ A3
 : : :
 A1 An);
                       ;S2 (A1 \ A2
 A1 \ A3
 : : :
 A1 \ An) + : : :
                       : : : + (;1)n;2Sn;1 (A1 \ A2
 A1 \ A3
 : : :
 A1 \ An)
                                                                                    



   dLQ TOGO, ^TOBY OTS@DA POLU^ITX FORMULU (2), OSTAETSQ PRINQTX WO WNIMANIE, ^TO
                    jA1j + S1(A2
 A3
 : : :
 An) = S1(A1
 A2
 : : :
 An)

                    S2 (A2
 A3 
 : : :
 An ) + S1 (A1 \ A2
 A1 \ A3
 : : :
 A1 \ An) =
                                                                 = S2 (A1
 A2 
 : : :
 An )

                    Sk (A2 
 A3
 : : :
 An) + Sk;1 (A1 \ A2
 A1 \ A3
 : : :
 A1 \ An) =
                                                                 = Sk (A1
 A2 
 : : :
 An )

                    Sn;1 (A1 \ A2 
 A1 \ A3 
 : : :
 A1 \ An ) = Sn (A1 
 A2
 : : :
 An):
tEOREMA DOKAZANA.
zADA^A 1. kAVDYJ U^ENIK KLASSA | LIBO DEWO^KA, LIBO BLONDIN, LIBO L@BIT MATEMATIKU. w
KLASSE 20 DEWO^EK, IZ NIH 12 BLONDINOK, I ODNA BLONDINKA L@BIT MATEMATIKU. wSEGO W KLASSE
24 U^ENIKA-BLONDINA, MATEMATIKU IZ NIH L@BQT 12, A WSEGO U^ENIKOW (MALX^IKOW I DEWO^EK),
KOTORYE L@BQT MATEMATIKU, 17, IZ NIH 6 DEWO^EK. sKOLXKO U^ENIKOW W DANNOM KLASSE?
rEENIE. eSLI A | MNOVESTWO DEWO^EK, B | BLONDINOW, C | U^ENIKOW, KOTORYE L@BQT MATEMA-
TIKU, TO jA B C j | ISKOMOE ^ISLO. A \ B | MNOVESTWO BLONDINOK, A \ C | MNOVESTWO DEWO^EK,
KOTORYE L@BQT MATEMATIKU, A \ B \ C | MNOVESTWO BLONDINOK, KOTORYE L@BQT MATEMATIKU.
tOGDA
                  jA    B C j = jAj + jB j + jC j; (jA \ B j + jA \ C j + jB \ C j)+
                          +jA \ B \ C j = 20 + 24 + 17 ; (12 + 6 + 12) + 1 = 32:
tAKIM OBRAZOM, W KLASSE 32 U^ENIKA.

   1.9. aLGEBRY MNOVESTW. pUSTX U | NEKOTOROE FIKSIROWANNOE MNOVESTWO. oBOZNA^IM
^EREZ B(U) MNOVESTWO WSEH PODMNOVESTW MNOVESTWA U. oTMETIM, ^TO REZULXTAT PRIMENENIQ
OPERACIJ NAD MNOVESTWAMI K MNOVESTWAM IZ B(U) DAET MNOVESTWA, PRINADLEVA]IE TAKVE B(U).
w \TOM SLU^AE GOWORQT, ^TO B(U) ZAMKNUTO OTNOSITELXNO UKAZANNYH WYE OPERACIJ, TO ESTX B(U)
OBRAZUET ALGEBRU OTNOSITELXNO OPREDELENNYH RANEE OPERACIJ. |TA ALGEBRA NAZYWAETSQ BULEWOJ
ALGEBROJ PODMNOVESTW MNOVESTWA U. |TO NAZWANIE W ^ESTX ANGLIJSKOGO MATEMATIKA I LOGIKA
dVORDVA bULQ (1815{1864).
                                                       12