nasyrov_a_z_nasyrov_z_h_diskretnaya_matematika
.pdf20. iZ KONTAKTOW x; y; z SOSTAWXTE SHEMU TAK, ^TOBY ONA IMELA SOSTOQNIE 1, ESLI NE MENEE DWUH KONTAKTOW IME@T SOSTOQNIE 1.
o nAJDITE MINIMALXNU@ dnf, POSTROJTE KONTAKTNU@ SHEMU PO
21.
MINIMALXNOJ dnf DLQ SLEDU@]IH BULEWYH FUNKCIJ:
A) f(x; y; z) = (1011 0011)T ;
B) g(a; b; c; d) = (0 ; 5; 8; 9; 12 ;
22. nAJDITE MINIMALXNU@ dnf I POSTROJTE KONTAKTNU@ SHEMU DLQ SLEDU@]IH FUNKCIJ, ZADANNYH FORMULAMI:
A) (x yz)(x ! y) _ (xyz x) ;
B)o ((x y) z) _ (x y)z .
23. dLQ SHEM, IZOBRAVENNYH NA RIS. 6 I 7, NAJDITE FUNKCI@ PROWODIMOSTI, PREOBRAZUJTE EE K MINIMALXNOJ dnf I POSTROJTE UPRO- ]ENNU@ SHEMU PO MINIMALXNOJ dnf.
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
z |
|
|
r |
y |
|
|
|||
|
|
|
|
|
z |
|
|
|
|
|
|
|
|
|
|
||||
+ |
|
|
|
|
|
; |
+ |
x |
xr |
|
|
; |
|
||||||
|
|
|
|
|
|
|
z |
|
|
|
|||||||||
|
|
|
|
x |
r |
|
|
|
|
r |
|||||||||
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
y |
|
|||
|
|
|
|
|
z |
|
|
|
|
x |
|
|
zr |
|
r |
|
|
||
|
|
|
|
rIS. 6 |
|
|
|
|
|
|
rIS. 7 |
|
|
|
|
o dLQ SHEM, IZOBRAVENNYH NA RIS. 8 I 9, NAJDITE FUNKCI@ PRO-
24.
WODIMOSTI, PREOBRAZUJTE EE K MINIMALXNOJ dnf I POSTROJTE UPRO- ]ENNU@ SHEMU PO MINIMALXNOJ dnf.
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y |
|
|
z |
|
|
|
|
|
|
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
z |
|
x |
|
|
|
|
|
|
|
y |
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
y |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
|
|
; |
||||||
|
|
|
z |
|
|
|
|
x |
|
|
|
r |
|
|
x |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
z |
z |
||||||||||||
|
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r |
|
|
|
y |
|
|
|
|
|
|
|
z |
|
|
; |
|
|
y |
|
|
x |
|
|
|
y |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
z |
|
x |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
rIS. 8 |
|
|
|
|
|
|
|
|
rIS. 9 |
|
||||||
25. wY^ISLITE ZNA^ENIQ PREDIKATOW |
|
|
|
|
|
|
|
|
||||||||||||||||
A = |
|
9x(x > 2 |
^ x < 5) I B = |
8x(x > 2 |
^ x < 5) , ESLI |
|
||||||||||||||||||
A) x 2 [3; 4] , |
B) x 2 [0; 2] , |
|
|
W) |
x 2 N . |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
21 |
|
|
|
|
|
|
|
|
|
o |
|
|
|
|
|
26. sRAWNITE ZNA^ENIQ WYSKAZYWANIJ A I B , ESLI |
|
|||||
A) A = 9x(x > 2 x < 3) , B = 9x(x > 2) 9x(x < 3) , x 2 |
R ; |
|||||
B) A = 8x(x > 2 ! x < 5) , B = 8x(x > 2) ! 8x(x < 5) , x 2 [3; 6] . |
||||||
27. nAJDITE OBLASTI ISTINNOSTI SLEDU@]IH PREDIKATOW: |
|
|||||
A) |
9x(x2 + y2 |
6 1), |
B) |
9x(x2 + y2 |
> 1), |
|
W) |
8x(x2 + y2 |
> 1), |
G) |
8x(x2 + y2 |
6 1), |
|
D) y > 0 9x(x2 + y2 6 2 ^ y > x) . |
|
|
|
o nAJDITE OBLASTI ISTINNOSTI SLEDU@]IH PREDIKATOW:
28.
A) 8x(xy < 1 ! x > ;1) , ESLI x; y 2 R ;
B) 9x(y > x2) (y 6 1) , ESLI x 2 R , y 2 [;2; 2] ;
W) (y > 5) 8x(y > x2) , ESLI x 2 [;2; 2] , y 2 R .
29. dOKAVITE, ^TO 9x P (x) _ 9x Q(x) = 9x(P (x) _ Q(x)) ;
SRAWNITE ZNA^ENIQ WYSKAZYWANIJ A = 9x(x < 2 ^ x > 3) I
3) , ESLI x 2 R .
o
30. dOKAVITE, ^TO 8x P (x) ^ 8x Q(x) = 8x(P (x) ^ Q(x)) ;
SRAWNITE ZNA^ENIQ WYSKAZYWANIJ A = 8x(x > 2 _ x < 3) I
B = 8x(x > 2) _ 8x(x < 3) , ESLI x 2 R .
22
g l a w a 2 mnovestwa i otno{eniq
x1. pONQTIE MNOVESTWA. pODMNOVESTWO
pOD MNOVESTWOM A PONIMAETSQ SOWOKUPNOSTX OB_EKTOW PROIZWOLXNOJ PRIRODY, ONI NAZYWA@TSQ \LEMENTAMI MNOVESTWA A . s^I- TAETSQ, ^TO \LEMENTY MNOVESTWA POPARNO RAZLI^NY. eSLI x QWLQETSQ \LEMENTOM MNOVESTWA A , TO PI[UT: x 2 A , W PROTIWNOM SLU- ^AE PI[UT: x 2= A . mNOVESTWO, NE IME@]EE \LEMENTOW, NAZYWAETSQ PUSTYM I OBOZNA^AETSQ SIMWOLOM ? . dRUGAQ KRAJNOSTX: MNOVESTWO WSEH \LEMENTOW, RASSMATRIWAEMYH W DANNYJ MOMENT, NAZYWAETSQ UNIWERSUMOM I OBOZNA^AETSQ BUKWOJ U . mNOVESTWO MOVNO ZADAWATX LIBO PERE^ISLENIEM EGO \LEMENTOW, NAPRIMER, TAK: fa; b; cg , LIBO WYDELITX EGO IZ DRUGOGO MNOVESTWA S POMO]X@ NEKOTOROGO SWOJSTWA, NAPRIMER, fx 2 A j P(x)g OZNA^AET MNOVESTWO \LEMENTOW x 2 A , UDOWLETWORQ@]IH SWOJSTWU (PREDIKATU) P (x) .
oPREDELENIE 1. mNOVESTWA A I B RAWNY, OBOZNA^AETSQ A = B , ESLI ONI SOSTOQT IZ ODNIH I TEH VE \LEMENTOW, T.E. x 2 A = x 2 B .
sWOJSTWO 1. pUSTOE MNOVESTWO EDINSTWENNO.
dOKAZATELXSTWO. pUSTX ?1 I ?2 { PUSTYE MNOVESTWA, TOGDA UTWERVDENIQ x 2 ?1 I x 2 ?2 RAWNOSILXNY, T.K. ONI OBA QWLQ@TSQ LOVNYMI. sLEDOWATELXNO, ?1 = ?2 PO OPREDELENI@ 1.
dLQ OBOZNA^ENIQ STANDARTNYH ^ISLOWYH MNOVESTW BUDEM PRIMENQTX SLEDU@]IE OBOZNA^ENIQ:
N = f1; 2;3; : : : ; n; : : : g | MNOVESTWO NATURALXNYH ^ISEL, Z = f0; 1; 2; : : : ; n; : : : g | MNOVESTWO CELYH ^ISEL,
Q = fmn j m 2 Z; n 2 Ng | MNOVESTWO RACIONALXNYH ^ISEL, R = (;1; +1) | MNOVESTWO DEJSTWITELXNYH ^ISEL,
C = fa + bi j a 2 R; b 2 Rg | MNOVESTWO KOMPLEKSNYH ^ISEL.
23
oPREDELENIE 2. mNOVESTWO A QWLQETSQ PODMNOVESTWOM MNOVES-
TWA B , OBOZNA^AETSQ A B ILI A |
|
B , ESLI WSE \LEMENTY A |
|||||||||||
PRINADLEVAT TAKVE I MNOVESTWU B , T.E. x 2 A ! x 2 B . |
|||||||||||||
sWOJSTWO 2. |
? |
A , A A . |
|
A , TO A = B . |
|
||||||||
sWOJSTWO 3. eSLI A B |
I B |
|
|||||||||||
sWOJSTWO 4. eSLI A B I B |
C , TO A C . |
A B , TO IZ |
|||||||||||
pRIWEDEM DOKAZATELXSTWO SWOJSTWA 4. pOSKOLXKU |
|||||||||||||
x 2 A SLEDUET, ^TO x |
2 B . t.K. |
B C , TO IZ x 2 B SLEDUET, |
|||||||||||
^TO x 2 C . tAKIM OBRAZOM, IZ x |
2 A |
WYTEKAET, |
^TO x 2 C , A \TO |
||||||||||
OZNA^AET, ^TO A C . |
|
|
|
|
|
|
|
|
|
|
|||
dLQ KAVDOGO MNOVESTWA A SU]ESTWUET MNOVESTWO WSEH EGO POD- |
|||||||||||||
MNOVESTW, OBOZNA^AEMOE P (A) ; TAKIM OBRAZOM P (A) = fx j x Ag |
|||||||||||||
I x 2 P (A) , x A . |
|
|
|
|
|
|
|
|
|
|
|||
pRIMER 1. P (?) = f?g , P (fxg) = f?; fxgg . |
|
|
|||||||||||
x2. oPERACII OB_EDINENIQ I PERESE^ENIQ MNOVESTW |
|||||||||||||
oPREDELENIE 1. oB_EDINENIEM MNOVESTW A I B NAZYWAETSQ |
|||||||||||||
MNOVESTWO A [ B , |
SOSTOQ]EE IZ \LEMENTOW, PRINADLEVA]IH HOTQ |
||||||||||||
BY ODNOMU IZ \TIH MNOVESTW, T.E. A [ B = fx j x |
2 A _ x 2 Bg , SM. |
||||||||||||
RIS. 10. |
|
|
|
|
|
|
|
|
|
|
|
|
|
sWOJSTWO 1. A |
[ |
? = A , A |
[ |
A = A . |
|
A |
B |
||||||
sWOJSTWO 2. |
A |
|
|
|
|
|
|
|
|
|
## |
||
[ B = B [ A . |
|
|
|
[ C . |
|
|
|||||||
sWOJSTWO 3. |
A |
[ |
(B |
[ C) = (A [ B) |
|
|
|||||||
sWOJSTWO 4. |
A |
[ B = A , B |
A . |
|
|
|
|
||||||
dOKAZATELXSTWO SWOJSTW 1 { 4 NEPOSREDSTWENNO |
|
rIS. 10 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
""!! |
SLEDUET IZ OPREDELENIQ OPERACII OB_EDINENIQ MNOVESTW. |
|||||||||||||
oB_EDINENIEM MNOVESTW A , GDE 2 I , NAZYWAETSQ MNOVESTWO |
|||||||||||||
|
|
|
[2I |
A = x (x A ) : |
|
|
|||||||
|
|
|
|
f |
|
|
I |
2 |
g |
|
|
||
|
|
|
|
|
j 92 |
|
|
|
|||||
oPREDELENIE 2. pERESE^ENIEM MNOVESTW A I B NAZYWAETSQ MNO- |
|||||||||||||
VESTWO A \ B , SOSTOQ]EE IZ \LEMENTOW, |
PRINADLEVA]IH KAVDOMU |
IZ DANNYH MNOVESTW A I B , T.E. A \ B = fx j x 2 A ^ x 2 Bg , SM.
RIS. 11.
24
|
A \ ? = ? , A \ A = A . |
|
|
A |
|
|
B |
||||||||||
sWOJSTWO 5. |
|
|
|
## |
|||||||||||||
sWOJSTWO 6. |
A \ B = B \ A . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
sWOJSTWO 7. |
A \ (B \ C) = (A \ B) \ C . |
|
|
|
|
|
|||||||||||
sWOJSTWO 8. |
A \ B = A |
, A |
B . |
|
2 I , |
|
|
|
|
|
|||||||
pERESE^ENIEM MNOVESTW |
A |
, |
GDE |
|
|
|
rIS |
|
|
||||||||
NAZYWAETSQ MNOVESTWO |
|
|
|
|
|
|
""!!. 11 |
||||||||||
A = |
|
x |
|
|
|
(x |
|
A ) . |
|
|
|
||||||
|
|
|
|
|
f |
|
|
|
I |
|
2 |
g |
|
|
|
|
|
|
I |
|
|
|
j 8 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
||
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
) SWOJSTWA SWQZYWA@T OPERACII |
||||||||||||
sLEDU@]IE (DISTRIBUTIWNYET |
|||||||||||||||||
PERESE^ENIQ I OB_EDINENIQ: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
sWOJSTWO 9. |
A [ (B \ C) = (A [ B) \ (A [ C) , |
|
|
|
|
||||||||||||
sWOJSTWO 10. |
A \ (B [ C) = (A \ B) |
[ (A \ C) . |
|
|
|
||||||||||||
pRIWEDEM DOKAZATELXSTWO SWOJSTWA 10 PO OPREDELENI@ RAWENSTWA |
|||||||||||||||||
MNOVESTW. rAWNOSILXNOSTX PREDIKATOW x |
2 LP I x 2 RP DOKAZY- |
||||||||||||||||
WAEM, ISPOLXZUQ OPREDELENIQ PERESE^ENIQ I OB_EDINENIQ MNOVESTW: |
|||||||||||||||||
x 2 LP = x 2 |
A ^ x 2 (B [ C) = x |
|
2 |
A |
^ (x |
2 |
B _ x |
2 |
C) = |
||||||||
= (x 2 A ^ x 2 |
B) _ (x 2 |
A ^ x |
2 |
C) = x 2 A \ B _ x 2 |
A |
\ C = |
|||||||||||
= x 2 (A \ B) [ (A \ C) = x 2 RP . |
~TO I TREBOWALOSX DOKAZATX. |
x3. oPERACII RAZNOSTI I SIMMETRI^ESKOJ RAZNOSTI
MNOVESTW
oPREDELENIE 1. rAZNOSTX@ A n B MNOVESTW A I B NAZYWAETSQ |
|||||||||||||||||
MNOVESTWO TEH \LEMENTOW IZ A , |
KOTORYE NE PRINADLEVAT MNOVES- |
||||||||||||||||
sWOJSTWO 1. |
A n ? |
= A , A n A = |
? . |
|
## |
||||||||||||
TWU B , T.E. A |
n |
B = |
f |
|
j |
|
2 |
|
^ |
2 |
|
|
g |
|
|
||
|
|
x |
|
x |
|
A |
|
x = B |
|
|
|
||||||
(SM. RIS. 12). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
B |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
""!!. 12 |
|
|
4. |
A n B = A |
, A \ B = . |
|
|||||||||||||
sWOJSTWO |
2. |
A n B |
= |
A n (A \ B) . |
|
|
|
|
|||||||||
sWOJSTWO 3. |
A n B = ? , A B . |
|
|
|
rIS |
||||||||||||
sWOJSTWO |
|
|
|
|
|
|
|
|
|
|
|
|
|
? |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
oPREDELENIE 2. dOPOLNENIEM MNOVESTWA A NAZYWAETSQ MNOVES- |
|||||||||||||||||
TWO A , RAWNOE U n A , GDE |
U | UNIWERSUM (SM. RIS. 13). |
||||||||||||||||
sWOJSTWO 5. |
A |
[ B = A \ B . |
|
|
|
|
|
A |
|||||||||
sWOJSTWO 6. |
A |
\ B = A [ B . |
|
|
|
|
|
A# |
|||||||||
sWOJSTWA 5 I 6 NAZYWA@TSQ ZAKONAMI |
|
"! |
|||||||||||||||
DE mORGANA I LEGKO DOKAZYWA@TSQ METODOM |
|
||||||||||||||||
KRUGOW |JLERA, SM. NIVE. |
|
|
|
|
|
|
|
|
rIS. 13 |
25
oPREDELENIE 3. sIMMETRI^ESKOJ RAZNOSTX@ MNOVESTW A I B |
||||||||||||||||||||
sWOJSTWO |
7. |
A4B = (A |
[ B) n (A \ B) . |
|
|
## |
||||||||||||||
NAZYWAETSQ MNOVESTWO |
A4B , |
RAWNOE |
|
|
A |
|
|
B |
||||||||||||
(A n B) [ (B n A) (SM. RIS. 14). |
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
""!!. 14 |
|||||||||||||||
|
|
|
|
|
10. A4(B4C) = (A4B)4C . |
|
|
|||||||||||||
sWOJSTWO |
8. |
A4B = B4A . |
|
|
|
|
|
|
|
|||||||||||
sWOJSTWO 9. A4? = A , |
|
A4A = ? . |
|
|
|
|
|
|||||||||||||
sWOJSTWO |
|
|
|
|
|
|
|
|
|
|
|
|
|
rIS |
||||||
pRIWEDEM DOKAZATELXSTWO SWOJSTWA 10. rAWNOSILXNOSTX PREDI- |
||||||||||||||||||||
KATOW |
x 2 |
LP |
I x 2 |
RP |
|
DOKAVEM , ISPOLXZUQ METOD ISTINNOST- |
||||||||||||||
NYH TABLIC, SDELAW RAZBOR PO WSEWOZMOVNYM ZNA^ENIQM PREDIKATOW |
||||||||||||||||||||
x 2 A , x 2 B , |
x 2 C . uDOBNO, ODNAKO, WMESTO ISTINNOSTNOJ TAB- |
|||||||||||||||||||
LICY ISPOLXZOWATX METOD KRUGOW |JLERA |
|
|
## |
|||||||||||||||||
(SM. RIS. 15), IZOBRAZIW DANNYE MNOVESTWA |
A |
|
|
B |
||||||||||||||||
KRUGAMI TAK, ^TOBY ONI RAZBIWALI PLOS- |
|
|
||||||||||||||||||
|
|
|
M6 |
|||||||||||||||||
KOSTX NA 8 |
^ASTEJ, OTWE^A@]IH STRO^KAM |
M4 |
|
M2 |
||||||||||||||||
|
|
|
M7 |
|||||||||||||||||
ISTINNOSTNOJ TABLICY. nAPRIMER, ^ASTX |
|
|
|
|||||||||||||||||
|
|
|
# |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
4 4 |
|
|
|
M5 |
M3 |
||
|
f |
|
j |
|
2 |
|
^ |
|
2 |
|
|
^ |
|
|
|
|
|
"! |
||
M6 = |
|
x |
|
x |
|
A |
|
x |
|
B |
|
x = C |
|
|
SO- |
|
|
|
M1 |
|
OTWETSTWUET STROKE (110) . wYRAZIM ^EREZ |
C |
|
""!! |
|||||||||||||||||
M0 | M7 |
MNOVESTWA LP = A (B |
|
C) I |
|
|
rIS. 15 |
RP = (A4B)4C . LP = (M4; M5 ; M6; M7)4(M1; M2; M5; M6) =
= (M1 ; M2; M4; M7) , RP = (M2; M3; M4; M5)4(M1; M3; M5; M7) =
= (M1; M2; M4 ; M7) , ZDESX ZAPQTYE MEVDU MNOVESTWAMI OZNA^A@T OB_EDINENIE. iTAK, OBA MNOVESTWA SOSTOQT IZ ODNIH I TEH ^ASTEJ M1; M2; M4 I M7 , ^TO I DOKAZYWAET IH RAWENSTWO.
x4. dEKARTOWO PROIZWEDENIE MNOVESTW, BINARNYE
OTNO[ENIQ
oPREDELENIE 1. dEKARTOWYM (PRQMYM) PROIZWEDENIEM MNOVESTW
NAZYWAETSQ MNOVESTWO WSEH UPORQDO^ENNYH NABOROW
(x1; x2; : : : ; xn) |
TAKIH |
, |
^TO |
xi 2 Ai |
PRI |
i = 1; 2; : : : n |
, |
OBOZNA^AETSQ |
||||
|
|
|
|
n |
|
|
|
|||||
DEKARTOWO PROIZWEDENIE TAK: A1 A2 : : : An ILI |
i=1 |
Ai . |
|
|
||||||||
w ^ASTNOSTI |
, A |
B = f(x; y) |
j x 2 A; y 2 Bg ; |
|
ZAMETIM |
, |
^TO |
|||||
|
|
|
Q |
|
|
|||||||
z 2 A B = 9x 2 A 9y 2 B (z = (x; y)) . |
|
|
|
|
|
|
||||||
|
|
|
|
|
26 |
|
|
|
|
|
|
|
|
pRIMER 1. eSLI DANY MNOVESTWA A = f1; 2g |
I B = f1; 2; 3g , TO |
|||||||||||||||||||||||||||||||||||
A B = f(1; 1); (1; 2); (1; 3); (2; 1); (2; 2); (2; 3)g . |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
oPREDELENIE 2. bINARNYM OTNO[ENIEM MEVDU MNOVESTWAMI A |
||||||||||||||||||||||||||||||||||||
I B NAZYWAETSQ PODMNOVESTWO R |
A |
B . w ^ASTNOM SLU^AE, PRI |
|||||||||||||||||||||||||||||||||||
A = B , GOWORQT O BINARNOM OTNO[ENII R NA MNOVESTWE A . |
|
|
|||||||||||||||||||||||||||||||||||
|
oPREDELENIE 3. oBLASTX@ OPREDELENIQ OTNO[ENIQ |
R A |
B |
||||||||||||||||||||||||||||||||||
NAZYWAETSQ MNOVESTWO D(R) = fx |
2 |
|
A |
j 9y 2 |
B ((x; y) |
2 |
R)g , |
||||||||||||||||||||||||||||||
QWLQ@]EESQ PROEKCIEJ R NA A . oBLASTX@ ZNA^ENIJ R NAZYWAETSQ |
|||||||||||||||||||||||||||||||||||||
MNOVESTWO |
V (R) = fy 2 B j 9x 2 A ((x; y) 2 R)g | PROEKCIQ R |
||||||||||||||||||||||||||||||||||||
NA B . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
oPREDELENIE 4. |
pUSTX |
R1 A |
B . oBRATNYM K R NAZYWAET- |
|||||||||||||||||||||||||||||||||
SQ BINARNOE OTNO[ENIE |
R; = f(y; x) |
|
j |
(x; y) |
2 |
Rg , |
|
ZAMETIM |
, |
^TO |
|||||||||||||||||||||||||||
R; |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
B |
A |
. |
dOPOLNENIEM BINARNOGO OTNO[ENIQ |
|
R |
NAZYWAETSQ |
||||||||||||||||||||||||||||||
OTNO[ENIE R = (A |
B) n R . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
sWOJSTWO 1. |
D(R;1) = V (R) , V (R;1) = D(R) . |
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
|
dOKAVEM, ^TO D(R;1) = V (R) . |TI MNOVESTWA RAWNY, POSKOLX- |
||||||||||||||||||||||||||||||||||||
KU |
y 2 |
|
|
|
|
1 |
|
() 9x ((y; x) 2 |
|
|
1 |
|
() 9x ((x; y) 2 |
|
|
() |
|||||||||||||||||||||
D(R; ) |
|
R; ) |
R) |
|
|||||||||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||||||||||
() y |
2 V (R) . wTOROE RAWENSTWO DOKAZYWAETSQ ANALOGI^NO. |
|
|
||||||||||||||||||||||||||||||||||
|
oPREDELENIE 5. kOMPOZICIEJ R1 |
A B I R2 |
B |
C NAZYWA- |
|||||||||||||||||||||||||||||||||
ETSQ OTNO[ENIE R1 R2 = f(x; z) j 9y 2 B |
((x; y) 2 |
R1^(y; z) 2 R2)g , |
|||||||||||||||||||||||||||||||||||
PRI \TOM R1 |
R2 A C . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
sWOJSTWO |
2. R1 |
(R2 |
R3) = (R1 R2) R3 . |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
dOKAZATELXSTWO |
. |
zAMETIM |
, |
^TO |
|
(x; y) |
2 R1 (R2 R3) () |
|
|
|||||||||||||||||||||||||||
() 9p ((x; p) |
2 R1 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
^ (p; y) |
2 R2 R3) () |
2 R3) . |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
() 9p |
9q ((x; p) |
2 R1 |
^ (p; q) |
2 R2 |
^ (q; y) |
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
aNALOGI^NO |
, |
UBEVDAEMSQ |
, |
^TO |
(x; y) 2 |
(R1 R2) R3 () |
|
|
||||||||||||||||||||||||||||
() 9p |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 R2 |
|
|
|||||||||||||||||||||
9q ((x; p) |
2 R1 ^ (p; q) |
^ |
(q; y) |
2 R3) . |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
sWOJSTWO 3. (R1 |
|
R2);1 = |
R;1 |
|
|
R;1 . |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|||
|
dOKAZATELXSTWO |
. |
zAMETIM |
, |
^TO |
|
(x; y) 2 (R1 |
R2); |
() |
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
|
|
(y; x) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
() |
2 |
R1 |
|
R2 |
() 9 |
p ((y; p) |
|
|
R1 |
|
^ |
(p; x) |
2 |
R2) |
() 1 |
|
|
|
|||||||||||||||||||
|
p |
|
|
|
|
|
1 |
|
|
|
|
1 2 |
|
|
(x; y) |
R; |
1 |
. |
|
|
|||||||||||||||||
() 9 |
((p; y) |
2 |
R; |
|
^ |
(x; p) |
2 |
R; ) |
() |
2 |
|
|
R; |
|
|
||||||||||||||||||||||
|
|
|
|
|
|
1 |
|
|
|
|
2 |
|
|
|
|
2 |
|
1 |
|
|
|
x5. oTNO[ENIQ \KWIWALENTNOSTI I PORQDKA oPREDELENIE 1. bINARNOE OTNO[ENIE R NA A NAZYWAETSQ
27
A) REFLEKSIWNYM, ESLI 8a 2 A ((a; a) 2 R) ,
B) SIMMETRI^NYM, ESLI IZ (x; y) 2 R SLEDUET, ^TO (y; x) 2 R , W) TRANZITIWNYM, ESLI (x; y) 2 R , (y; z) 2 R =) (x; z) 2 R , G) ANTISIMMETRI^NYM, ESLI (x; y) 2 R , (y; x) 2 R =) x = y .
eSLI BINARNOE OTNO[ENIE R NA A QWLQETSQ REFLEKSIWNYM, SIMMETRI^NYM I TRANZITIWNYM, TO EGO NAZYWA@T OTNO[ENIEM \K- WIWALENTNOSTI NA A I PI[UT x y WMESTO (x; y) 2 R . uSLOWIQ REFLEKSIWNOSTI, SIMMETRI^NOSTI I TRANZITIWNOSTI MOVNO PEREPISATX TAK:
A) 8a 2 A (a a) ,
B) x y =) y x ,
W) x y , y z =) x z .
eSLI DANO OTNO[ENIE \KWIWALENTNOSTI NA MNOVESTWE SOM \KWIWALENTNOSTI, POROVDAEMYM \LEMENTOM MNOVESTWO Kx = fy 2 A j y xg .
tEOREMA 1. kAVDOE OTNO[ENIE \KWIWALENTNOSTI NA A POROVDAET RAZBIENIE A NA NEPERESEKA@]IESQ KLASSY \KWIWALENTNOSTI.
dOKAZATELXSTWO. pUSTX Kx I Kz { KLASSY \KWIWALENTNOSTI. rAZBEREM DWA WOZMOVNYH SLU^AQ.
1. |
pUSTX |
x z . |
w \TOM SLU^AE |
y 2 Kx |
() y |
x ; |
POSKOLXKU |
|||
|
|
|
|
|||||||
x z , TO y x () y z () y 2 Kz , T.E. |
y |
2 Kx () y 2 Kz I, |
||||||||
ZNA^IT, |
Kx = Kz . |
|
|
|
|
|
|
|
||
2. |
pUSTX |
x 6 z . w \TOM SLU^AE Kx \ Kz |
= |
? , T.K. ESLI BY |
||||||
SU]ESTWOWAL \LEMENT y TAKOJ, ^TO y 2 Kx |
I y 2 Kz , TO BYLO BY |
|||||||||
y x I y z =) x |
z , ^TO PROTIWORE^IT USLOWI@. |
|
|
|||||||
tEOREMA DOKAZANA. |
|
|
|
|
|
|
||||
pRIMER 1. nA MNOVESTWE CELYH ^ISEL Z RASSMOTRIM BINARNOE |
||||||||||
OTNO[ENIE R = f(x; y) j (x;y) . 3g . dOKAZATX, ^TO R | OTNO[ENIE |
||||||||||
\KWIWALENTNOSTI, NAJTI WSE KLASSY \KWIWALENTNOSTI. |
; x = 0 . 3 , |
|||||||||
rE[ENIE. |
(x; x) |
2 R PRI L@BOM x 2 Z , |
T.K. |
x |
||||||
PO\TOMU R | REFLEKSIWNO. eSLI (x; y) 2 |
R , TO |
(x |
; y) . 3 , T.E. |
|||||||
x;y = 3k , GDE k 2 Z . oTS@DA SLEDUET, ^TO y;x = ;3k |
I, ZNA^IT, |
|||||||||
(y; x) |
2 |
R , PO\TOMU R | SIMMETRI^NO. nAKONEC, PUSTX (x; y) 2 R |
||||||||
I (y; z) |
2 R , TOGDA x ; y = 3k I y ; z = 3l . oTS@DA SLEDUET, ^TO |
x ; z = 3(k + l) I, ZNA^IT, (x; z) 2 R , PO\TOMU R | TRANZITIWNO.
28
mY DOKAZALI, ^TO R | OTNO[ENIE \KWIWALENTNOSTI.
nAJDEM KLASSY \KWIWALENTNOSTI. Kx = fy j y xg , T.E. y 2 Kx
OZNA^AET, ^TO (y;x). 3 () y = 3k+x , GDE k 2 Z . oTS@DA SLEDUET, ^TO Kx = f3k + x j k 2 Zg . oSTALOSX ZAMETITX, ^TO
RAZBIWA@T Z NA NEPERESEKA@]IESQ KLASSY \KWIWALENTNOSTI. oPREDELENIE 2. bINARNOE OTNO[ENIE R NA MNOVESTWE M NAZY-
WAETSQ ^ASTI^NYM PORQDKOM, ESLI ONO REFLEKSIWNO, ANTISIMMETRI^NO I TRANZITIWNO, PI[UT x 6 y WMESTO (x; y) 2 R . tAKIM OBRAZOM, OTNO[ENIE 6 UDOWLETWORQET USLOWIQM
1) 8x 2 M (x 6 x) | REFLEKSIWNOSTX,
2) (x 6 y ^ y 6 x) =) (x = y) | ANTISIMMETRI^NOSTX, 3) (x 6 y ^ y 6 z) =) (x 6 z) | TRANZITIWNOSTX.
pREDIKAT x < y OPREDELQETSQ KAK x 6 y ^ x 6= y .
mNOVESTWO, NA KOTOROM ZADAN ^ASTI^NYJ PORQDOK, NAZYWAETSQ ^ASTI^NO UPORQDO^ENNYM ILI UPORQDO^ENNYM.
pRIMER 2. mNOVESTWO P (M) ^ASTI^NO UPORQDO^ENO OTNO[ENIEM PODMNOVESTWA.
w ^ASTI^NO UPORQDO^ENNOM MNOVESTWE MOGUT BYTX NESRAWNIMYE \LEMENTY, TAK W PRIMERE 2, ESLI M = f1; 2; 3; 4g , TO PODMNOVESTWA f1; 2; 3g I f2; 3; 4g NESRAWNIMY.
oPREDELENIE 3. ~ASTI^NO UPORQDO^ENNOE MNOVESTWO M NAZYWAETSQ LINEJNO UPORQDO^ENNYM, ESLI W NEM NET NESRAWNIMYH \LEMENTOW, T.E. DLQ L@BYH x; y 2 M WYPOLNQETSQ ODNO IZ USLOWIJ: x < y ,
x = y ILI y < x .
pRIMER 3. mNOVESTWA N; Z; Q; R S ESTESTWENNYM PORQDKOM NA NIH QWLQ@TSQ LINEJNO UPORQDO^ENNYMI.
x6. fUNKCII
oPREDELENIE 1. fUNKCIEJ f , OTOBRAVA@]EJ MNOVESTWO A WO MNOVESTWO B , OBOZNA^AETSQ f : A ! B , NAZYWAETSQ PRAWILO, PO KOTOROMU KAVDOMU x 2 A STAWITSQ W SOOTWETSTWIE \LEMENT y 2 B , KOTORYJ S^ITAETSQ ZNA^ENIEM FUNKCII f I OBOZNA^AETSQ f(x) .
mNOVESTWO ;f |
= f(x; y) j x |
2 A; y = f(x)g |
NAZYWAETSQ GRAFI- |
KOM FUNKCII f : |
A ! B . zAMETIM, ^TO ;f |
QWLQETSQ BINARNYM |
|
|
|
29 |
|
OTNO[ENIEM MEVDU A I B . mNOVESTWO A NAZYWAETSQ OBLASTX@
OPREDELENIQ, A V (f) = ff(x) j x |
2 Ag QWLQETSQ OBLASTX@ ZNA^ENIJ |
|||||||||||||
FUNKCII f . |
|
|
|
|
|
|
|
|
|
|
|
|
||
oPREDELENIE 2. fUNKCIQ f : X |
! Y |
NAZYWAETSQ |
|
|||||||||||
A) S@R_EKTIWNOJ, ESLI 8y 2 Y 9x 2 |
X (y = f(x)) , |
|
||||||||||||
B) IN_EKTIWNOJ, ESLI 8x1; x2 2 X (x1 6= x2 |
! f(x1) 6= f(x2)) , |
|
||||||||||||
W) BIEKTIWNOJ, ESLI ONA S@R_EKTIWNA I IN_EKTIWNA, ^TO MOVNO ZA- |
||||||||||||||
PISATX TAK: |
8y 2 Y |
9! x |
2 X (y = f(x)) . |
|
|
|
|
|
||||||
pRIMER |
1. fUNKCIQ |
E : X ! X , WY^ISLQEMAQ PO PRAWILU |
||||||||||||
E(x) = x DLQ L@BOGO x 2 X , NAZYWAETSQ TOVDESTWENNOJ. o^E- |
||||||||||||||
WIDNO, E | BIEKCIQ. |
|
|
|
|
|
|
|
|
|
|||||
oPREDELENIE 3. eSLI f : A |
! B , g : B |
! C | FUNKCII, TO |
||||||||||||
IH KOMPOZICIEJ NAZYWAETSQ FUNKCIQ |
(f g) |
: |
A ! C , KOTORAQ |
|||||||||||
WY^ISLQETSQ PO PRAWILU (f g)(x) = g(f(x)) |
DLQ L@BOGO x 2 A . |
|||||||||||||
sWOJSTWO 1. pUSTX f : X ! Y , g : Y |
! Z , TOGDA |
|
||||||||||||
A) ESLI f |
I g c@R_EKTIWNY, TO f g |
S@R_EKTIWNA, |
|
|||||||||||
B) ESLI f |
I g IN_EKTIWNY, TO f g IN_EKTIWNA, |
|
||||||||||||
W) ESLI f I g BIEKTIWNY, TO f |
g |
BIEKTIWNA. |
|
|
||||||||||
dOKAZATELXSTWO. pUSTX f I |
g |
{ c@R_EKTIWNYE FUNKCII. dLQ |
||||||||||||
DOKAZATELXSTWA S@R_EKTIWNOSTI f |
g |
RASSMOTRIM PROIZWOLXNYJ |
||||||||||||
\LEMENT c |
2 Z . wWIDU S@R_EKTIWNOSTI FUNKCII g : Y ! Z SU- |
|||||||||||||
]ESTWUET \LEMENT b 2 Y TAKOJ, ^TO c = g(b) . pOSKOLXKU FUNKCIQ |
||||||||||||||
f : X ! Y |
TAKVE S@R_EKTIWNA, TO MOVNO NAJTI \LEMENT a 2 X |
|||||||||||||
TAKOJ, ^TO b = f(a) . iZ RAWENSTW c = g(b) |
I b = f(a) SLEDUET, |
^TO |
||||||||||||
c = g(f(a)) , T.E. |
c = (f g)(a) , A \TO I OZNA^AET S@R_EKTIWNOSTX |
|||||||||||||
FUNKCII f g . |
|
|
|
|
|
|
|
|
|
|
|
|||
pUSTX f |
I g { IN_EKTIWNYE FUNKCII. dLQ DOKAZATELXSTWA IN_- |
|||||||||||||
EKTIWNOSTI f g RASSMOTRIM PROIZWOLXNYE \LEMENTY x1; x2 2 |
X , |
|||||||||||||
x1 6= x2 . wWIDU IN_EKTIWNOSTI f |
IMEEM, ^TO f(x1) 6= f(x2) . |
pO- |
||||||||||||
SKOLXKU FUNKCIQ |
|
TAKVE IN_EKTIWNA |
|
TO |
|
|
6 |
^TO |
||||||
g |
, |
g(f(x1)) = g(f(x2)) , |
||||||||||||
|
|
|
|
|
|
|
|
|
I OZNA^AET IN_EKTIWNOSTX KOMPOZICII f g .
w ZAWER[ENIE DOKAZATELXSTWA ZAMETIM, ^TO UTWERVDENIE W) QWLQETSQ O^EWIDNYM SLEDSTWIEM UTWERVDENIJ A) I B).
30