Теормин - шпоры
Описание файла
PDF-файл из архива "Теормин - шпоры", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru)Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru)Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru)1. Ʉɥɚɫɫɢɱɟɫɤɚɹ ɥɨɝɢɤɚ ɩɪɟɞɢɤɚɬɨɜ ɩɟɪɜɨɝɨ ɩɨɪɹɞɤɚ1) ɟɫɥɢ P – m-ɦɟɫɬɧɵɣ ɩɪɟɞɢɤɚɬ, ɚ t1 , t2 ,..., tm - ɬɟɪɦɵ, ɬɨ ɡɚɩɢɫɶ ɜɢɞɚ P (t1 , t2 ,..., tm ) ɛɭɞɟɬɹɜɥɹɬɶɫɹ ɮɨɪɦɭɥɨɣ (ɚɬɨɦɚɪɧɨɣ ɮɨɪɦɭɥɨɣ);2) ɟɫɥɢ \ ɢ M - ɮɨɪɦɭɥɵ, ɬɨ ɮɨɪɦɭɥɨɣ ɬɚɤɠɟ ɛɭɞɟɬ ɹɜɥɹɬɶɫɹ ɥɸɛɨɟ ɜɵɪɚɠɟɧɢɟ ɜɢɞɚ M , \ , M \ , M &\ , M o \ ;3) ɟɫɥɢ M - ɮɨɪɦɭɥɚ, ɚ ɯ – ɩɪɟɞɦɟɬɧɚɹ ɩɟɪɟɦɟɧɧɚɹ, ɬɨ ɮɨɪɦɭɥɨɣ ɬɚɤɠɟ ɛɭɞɟɬ ɹɜɥɹɬɶɫɹ ɥɸɛɨɟɜɵɪɚɠɟɧɢɟ ɜɢɞɚ xM , xM ;4) ɧɢɤɚɤɢɯ ɞɪɭɝɢɯ ɮɨɪɦɭɥ ɧɟɬ.ȿɫɥɢ t – ɬɟɪɦ, d1, d2, …, dm – ɩɪɟɞɦɟɬɵ, ɬɨ t ( x1 , x2 ,..., xm )[d1 , d 2 ,..., d m ] - ɷɬɨ ɩɪɟɞɦɟɬ ɢɡ ɨɛɥɚɫɬɢɢɧɬɟɪɩɪɟɬɚɰɢɢ, ɤɨɬɨɪɵɣ ɹɜɥɹɟɬɫɹ ɡɧɚɱɟɧɢɟɦ ɬɟɪɦɚ:- ɟɫɥɢ t = xi, ɬɨ t ( x1 , x2 ,..., xm )[d1 , d 2 ,..., d m ] ɛɭɞɟɬ ɪɚɜɟɧ di;Ɉɩɪɟɞɟɥɟɧɢɟ.
ɉɪɟɞɢɤɚɬ – ɮɨɪɦɚ, ɩɪɢ ɩɨɦɨɳɢ ɤɨɬɨɪɨɣ ɡɚɞɚɸɬɫɹ ɨɬɧɨɲɟɧɢɹ ɦɟɠɞɭɨɛɴɟɤɬɚɦɢ ɢ ɫɭɛɴɟɤɬɚɦɢɋɥɨɜɨ «ɩɪɟɞɢɤɚɬ» ɩɪɨɢɫɯɨɞɢɬ ɨɬ ɥɚɬɢɧɫɤɨɝɨ «ɩɪɟɞɫɤɚɡɵɜɚɬɶ».ɉɪɟɞɢɤɚɬɵ ɧɭɥɟɜɨɝɨ ɩɨɪɹɞɤɚ – ɛɟɡ ɢɫɩɨɥɶɡɨɜɚɧɢɹ ɤɜɚɧɬɨɪɨɜ.ɉɪɟɞɢɤɚɬɵ ɩɟɪɜɨɝɨ ɩɨɪɹɞɤɚ – ɤɜɚɧɬɨɪɵ ɢɫɩɨɥɶɡɭɸɬɫɹ ɬɨɥɶɤɨ ɩɨ ɨɬɧɨɲɟɧɢɸ ɤ ɩɪɟɞɦɟɬɚɦɉɪɟɞɢɤɚɬɵ ɜɵɫɲɟɝɨ ɩɨɪɹɞɤɚ – ɤɜɚɧɬɨɪɵ ɢɫɩɨɥɶɡɭɸɬɫɹ ɩɨ ɨɬɧɨɲɟɧɢɸ ɤ ɮɭɧɤɰɢɹɦ.Ɉɩɪɟɞɟɥɟɧɢɟ.
Ⱥɥɮɚɜɢɬ (ɫɢɝɧɚɬɭɪɚ) ɄɅɉ – ɷɬɨ ɧɚɛɨɪ ɫɱɟɬɧɵɯ ɦɧɨɠɟɫɬɜ:1. ɩɪɟɞɦɟɬɧɵɯ ɩɟɪɟɦɟɧɧɵɯ, ɤɨɬɨɪɨɟ ɨɛɨɡɧɚɱɚɟɬɫɹ ɤɚɤ Var {x1 , x2 ,..., xn ,...} ;2. ɩɪɟɞɦɟɬɧɵɯ ɤɨɧɫɬɚɧɬ, ɤɨɬɨɪɵɟ ɫɨɨɬɜɟɬɫɬɜɭɸɬ ɢɦɟɧɚɦ ɩɪɟɞɦɟɬɨɜ ɢ ɨɛɨɡɧɚɱɚɸɬɫɹ ɤɚɤConst {c1 , c2 ,..., cn ,...} ;3.4.ɮɭɧɤɰɢɨɧɚɥɶɧɵɯ ɫɢɦɜɨɥɨɜ Func { f1k1 , f 2k2 ,..., f mkm ,...} , ɝɞɟ ki – ɦɟɫɬɧɨɫɬɶɮɭɧɤɰɢɨɧɚɥɶɧɨɝɨ ɫɢɦɜɨɥɚ, ɩɪɢɱɟɦ ki t 1 (ɜ ɩɪɨɬɢɜɧɨɦ ɫɥɭɱɚɟ ɮɭɧɤɰɢɨɧɚɥɶɧɵɣ ɫɢɦɜɨɥɹɜɥɹɟɬɫɹ ɤɨɧɫɬɚɧɬɨɣ);ɩɪɟɞɢɤɚɬɧɵɯ ɫɢɦɜɨɥɨɜ, ɤɨɬɨɪɵɟ ɢɫɩɨɥɶɡɭɸɬɫɹ ɞɥɹ ɨɛɨɡɧɚɱɟɧɢɹ ɨɬɧɨɲɟɧɢɣ ɦɟɠɞɭɩɪɟɞɦɟɬɚɦɢ ɢ ɨɛɨɡɧɚɱɚɸɬɫɹ Pred {P1l1 , P2l2 ,..., Prlr ,...} , ɝɞɟ li – ɦɟɫɬɧɨɫɬɶ ɩɪɟɞɢɤɚɬɧɨɝɨɫɢɦɜɨɥɚ (ɟɫɥɢ li 0 , ɬɨ ɞɚɧɧɵɣ ɩɪɟɞɢɤɚɬɧɵɣ ɫɢɦɜɨɥ ɨɛɨɡɧɚɱɚɟɬ ɭɬɜɟɪɠɞɟɧɢɟ, ɧɟɡɚɜɢɫɹɳɟɟ ɨɬ ɤɚɤɢɯ-ɥɢɛɨ ɩɪɟɞɦɟɬɨɜ).ȼ ɮɨɪɦɭɥɚɯ ɧɚɢɛɨɥɶɲɢɣ ɩɪɢɨɪɢɬɟɬ ɢɦɟɸɬ ɤɜɚɧɬɨɪɵ ɢ ɨɬɪɢɰɚɧɢɟ, ɡɚɬɟɦ ɤɨɧɴɸɧɤɰɢɹ,ɞɢɡɴɸɧɤɰɢɹ ɢ ɢɦɩɥɢɤɚɰɢɹ.Ɇɧɨɠɟɫɬɜɨ ɜɫɟɯ ɮɨɪɦɭɥ ɨɛɨɡɧɚɱɚɟɬɫɹ ɤɚɤ Form.Ɉɩɪɟɞɟɥɟɧɢɟ.
Ɉɛɥɚɫɬɶɸ ɞɟɣɫɬɜɢɹ ɤɜɚɧɬɨɪɨɜ ɧɚɡɵɜɚɟɬɫɹ ɮɨɪɦɭɥɚ M ɢɡ ɜɵɪɚɠɟɧɢɹ xMɢɥɢ xM . ɉɪɢ ɷɬɨɦ ɜɯɨɠɞɟɧɢɟ ɩɟɪɟɦɟɧɧɨɣ ɯ ɜ ɷɬɢɯ ɜɵɪɚɠɟɧɢɹɯ ɧɚɡɵɜɚɟɬɫɹ ɫɜɹɡɚɧɧɵɦ.ȿɫɥɢ ɜɯɨɠɞɟɧɢɟ ɩɟɪɟɦɟɧɧɨɣ ɧɟ ɫɜɹɡɚɧɧɨɟ, ɬɨ ɨɧɨ ɧɚɡɵɜɚɟɬɫɹ ɫɜɨɛɨɞɧɵɦ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɋɜɹɡɚɧɧɨɣ (ɫɜɨɛɨɞɧɨɣ) ɩɟɪɟɦɟɧɧɨɣ ɧɚɡɵɜɚɟɬɫɹ ɩɟɪɟɦɟɧɧɚɹ ɯ, ɟɫɥɢ ɨɧɚ ɢɦɟɟɬɫɜɹɡɚɧɧɨɟ (ɫɜɨɛɨɞɧɨɟ) ɜɯɨɠɞɟɧɢɟ ɜ ɧɟɤɨɬɨɪɭɸ ɮɨɪɦɭɥɭ.Ɂɚɩɢɫɶ VarM ɨɛɨɡɧɚɱɚɟɬ ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɫɜɨɛɨɞɧɵɯ ɩɟɪɟɦɟɧɧɵɯ, ɜɯɨɞɹɳɢɯ ɜ ɮɨɪɦɭɥɭ M.ɋɥɭɠɟɛɧɵɟ ɫɢɦɜɨɥɵ – ɷɬɨ:- ɥɨɝɢɱɟɫɤɢɟ ɫɜɹɡɤɢ: , , o, ;- ɤɜɚɧɬɨɪɵ: (ɜɫɟɨɛɳɧɨɫɬɢ) ɢ (ɫɭɳɟɫɬɜɨɜɚɧɢɹ);- ɡɧɚɤɢ ɩɪɟɩɢɧɚɧɢɹ: ( ) ,Ɉɩɪɟɞɟɥɟɧɢɟ. ȿɫɥɢ ɦɧɨɠɟɫɬɜɨ VarM ɩɭɫɬɨ, ɬɨ ɮɨɪɦɭɥɚ M ɧɚɡɵɜɚɟɬɫɹ ɡɚɦɤɧɭɬɨɣ ɮɨɪɦɭɥɨɣ(ɩɪɟɞɥɨɠɟɧɢɟɦ).ɋɥɨɜɚ ɜ ɚɥɮɚɜɢɬɟ – ɷɬɨ ɰɟɩɨɱɤɢ ɫɢɦɜɨɥɨɜ.Ɉɩɪɟɞɟɥɟɧɢɟ. Ɍɟɪɦɨɦ ɧɚɡɵɜɚɟɬɫɹ ɜɫɹɤɨɟ ɫɥɨɜɨ, ɤɨɬɨɪɨɟ ɦɨɠɟɬ ɛɵɬɶ ɩɨɫɬɪɨɟɧɨ ɩɨɫɥɟɞɭɸɳɢɦ ɩɪɚɜɢɥɚɦ:1) ɥɸɛɚɹ ɩɟɪɟɦɟɧɧɚɹ ɹɜɥɹɟɬɫɹ ɬɟɪɦɨɦ;2) ɥɸɛɚɹ ɤɨɧɫɬɚɧɬɚ ɹɜɥɹɟɬɫɹ ɬɟɪɦɨɦ;3) ɟɫɥɢ f – k-ɦɟɫɬɧɵɣ ɮɭɧɤɰɢɨɧɚɥɶɧɵɣ ɫɢɦɜɨɥ, ɚ t1 , t2 ,..., tk - ɬɟɪɦɵ, ɬɨ f (t1 , t2 ,..., tk ) ɬɚɤɠɟɛɭɞɟɬ ɹɜɥɹɬɶɫɹ ɬɟɪɦɨɦ;4) ɞɪɭɝɢɯ ɬɟɪɦɨɜ ɧɟɬ.Ɇɧɨɠɟɫɬɜɨ ɜɫɟɯ ɬɟɪɦɨɜ ɨɛɨɡɧɚɱɚɟɬɫɹ ɤɚɤ Term.ɋɦɵɫɥɨɜɨɟ ɫɨɞɟɪɠɚɧɢɟ ɹɡɵɤɚ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ ɨɩɪɟɞɟɥɹɟɬɫɹ ɟɝɨ ɫɟɦɚɧɬɢɤɨɣ.
ɉɪɢ ɷɬɨɦɨɩɢɫɚɧɢɟ ɜɵɪɚɠɟɧɢɣ ɟɫɬɟɫɬɜɟɧɧɨɝɨ ɹɡɵɤɚ ɹɜɥɹɟɬɫɹ ɝɨɪɚɡɞɨ ɛɨɥɟɟ ɫɥɨɠɧɨɣ ɡɚɞɚɱɟɣ, ɧɟɠɟɥɢɨɩɢɫɚɧɢɟ ɧɟɤɨɬɨɪɵɯ ɦɚɬɟɦɚɬɢɱɟɫɤɢɯ ɭɬɜɟɪɠɞɟɧɢɣ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɂɧɬɟɪɩɪɟɬɚɰɢɹ – ɦɚɬɟɦɚɬɢɱɟɫɤɚɹ ɤɨɧɫɬɪɭɤɰɢɹ, ɤɨɬɨɪɚɹ ɩɨɡɜɨɥɹɟɬ ɨɩɢɫɵɜɚɬɶɜɫɟ ɦɧɨɝɨɨɛɪɚɡɢɟ ɜɨɨɛɪɚɠɚɟɦɵɯ ɦɢɪɨɜ. ɂɧɬɟɪɩɪɟɬɚɰɢɟɣ ɛɭɞɟɦ ɧɚɡɵɜɚɬɶ ɚɥɝɟɛɪɚɢɱɟɫɤɭɸɫɢɫɬɟɦɭ I D, Const, Func, Pred ! , ɤɨɬɨɪɚɹ ɫɨɫɬɨɢɬ ɢɡ ɫɥɟɞɭɸɳɢɯ ɤɨɦɩɨɧɟɧɬ:- DI z - ɨɛɥɚɫɬɶ ɢɧɬɟɪɩɪɟɬɚɰɢɢ (ɩɪɟɞɦɟɬɧɨɟ ɦɧɨɠɟɫɬɜɨ, ɭɧɢɜɟɪɫɭɦ), ɤɨɬɨɪɨɟɩɪɟɞɫɬɚɜɥɹɟɬɫɹ ɜɫɟɦɢ ɜɨɡɦɨɠɧɵɦɢ ɩɪɟɞɦɟɬɚɦɢ ɜɨɨɛɪɚɠɚɟɦɨɝɨ ɦɢɪɚ;- Const - ɨɬɨɛɪɚɠɟɧɢɟ c Const o c DI (ɩɪɟɞɦɟɬ ɜ ɦɢɪɟ I, ɧɨɫɹɳɢɣ ɢɦɹ ɤɨɧɫɬɚɧɬɵ ɫ)- Func - ɨɬɨɛɪɚɠɟɧɢɟ Func : f ( n ) Func o ( f ( n ) : DI o DI ) ;Ɂɚɩɢɫɶ t ( x1 , x2 ,..., xn ) ɢɫɩɨɥɶɡɭɟɬɫɹ ɞɥɹ ɨɛɨɡɧɚɱɟɧɢɹ ɬɟɪɦɚ, ɜ ɤɨɬɨɪɨɦ ɫɨɞɟɪɠɚɬɫɹ ɬɨɥɶɤɨɩɟɪɟɦɟɧɧɵɟ ɢɡ ɦɧɨɠɟɫɬɜɚ { x1 , x2 ,..., xn }.- Pred - ɨɬɨɛɪɚɠɟɧɢɟ Pred : P ( m ) Pred o ( P ( m ) : DI o {T , F }) .Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɜɫɟ ɷɥɟɦɟɧɬɵ ɧɚɲɟɝɨ ɹɡɵɤɚ ɩɪɢɨɛɪɟɬɚɸɬ ɱɟɬɤɢɣ ɦɚɬɟɦɚɬɢɱɟɫɤɢɣ ɫɦɵɫɥ.ȿɫɥɢ t – ɬɟɪɦ, ɬɨ ɜɵɪɚɠɟɧɢɟɦ Vart ɛɭɞɟɦ ɨɛɨɡɧɚɱɚɬɶ ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɩɟɪɟɦɟɧɧɵɯ, ɤɨɬɨɪɵɟɫɨɞɟɪɠɚɬɫɹ ɜ ɬɟɪɦɟ t.ɇɚ ɨɫɧɨɜɚɧɢɢ ɩɨɧɹɬɢɹ ɢɧɬɟɪɩɪɟɬɚɰɢɢ ɦɨɠɧɨ ɨɰɟɧɢɜɚɬɶ ɜɫɟ ɮɨɪɦɭɥɵ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ.ȿɫɥɢ Vart ɹɜɥɹɟɬɫɹ ɩɭɫɬɵɦ ɦɧɨɠɟɫɬɜɨɦ, ɬɨ ɬɟɪɦ t ɧɚɡɵɜɚɟɬɫɹ ɨɫɬɨɜɧɵɦ ɬɟɪɦɨɦ.Ɉɩɪɟɞɟɥɟɧɢɟ.
Ɏɨɪɦɭɥɨɣ ɧɚɡɵɜɚɟɬɫɹ ɫɥɨɜɨ ɜ ɹɡɵɤɟ ɄɅɉ, ɤɨɬɨɪɨɟ ɦɨɠɟɬ ɛɵɬɶ ɩɨɫɬɪɨɟɧɨ ɩɨɫɥɟɞɭɸɳɢɦ ɩɪɚɜɢɥɚɦ:Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ I – ɢɧɬɟɪɩɪɟɬɚɰɢɹ, M - ɮɨɪɦɭɥɚ ɨɬ n ɩɟɪɟɦɟɧɧɵɯ, d1, d2, …, dn – ɧɚɛɨɪɩɪɟɞɦɟɬɨɜ. Ɍɨɝɞɚ ɨɬɧɨɲɟɧɢɟɦ ɜɵɩɨɥɧɢɦɨɫɬɢ ɧɚɡɵɜɚɟɬɫɹ ɫɥɟɞɭɸɳɟɟ ɨɬɧɨɲɟɧɢɟ:I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] , ɤɨɬɨɪɨɟ ɨɛɨɡɧɚɱɚɟɬ «ɮɨɪɦɭɥɚ M ɜ ɢɧɬɟɪɩɪɟɬɚɰɢɢ Iɜɵɩɨɥɧɹɟɬɫɹ ɧɚ ɡɧɚɱɟɧɢɹɯ d1, d2, …, dn ɟɟ ɫɜɨɛɨɞɧɵɯ ɩɟɪɟɦɟɧɧɵɯ» ɢ ɨɩɪɟɞɟɥɹɟɬɫɹɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:1.
Ɂɧɚɱɟɧɢɟ ɬɟɪɦɚ ɧɚ ɞɚɧɧɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɢ:3ɋɜɟɞɟɦ ɡɚɞɚɱɭ ɧɚɯɨɠɞɟɧɢɹ ɥɨɝɢɱɟɫɤɨɝɨ ɫɥɟɞɫɬɜɢɹ ɤ ɩɪɨɛɥɟɦɟ ɨɛɳɟɡɧɚɱɢɦɨɫɬɢ.Ɍɟɨɪɟɦɚ (ɨ ɥɨɝɢɱɟɫɤɨɦ ɫɥɟɞɫɬɜɢɢ). ȿɫɥɢ M0 , M1 ,..., M n - ɡɚɦɤɧɭɬɵɟ ɮɨɪɦɭɥɵ, ɬɨ {M1 ,..., Mn }| M0ɷɤɜɢɜɚɥɟɧɬɧɨ | (M1 &...& Mn ) o M0 (ɬ.ɟ. ɞɥɹ ɥɸɛɨɝɨ ɥɨɝɢɱɟɫɤɨɝɨ ɫɥɟɞɫɬɜɢɹ ɞɚɧɧɨɝɨɦɧɨɠɟɫɬɜɚ ɮɨɪɦɭɥ ɬɚɤɚɹ ɢɦɩɥɢɤɚɰɢɹ ɨɛɳɟɡɧɚɱɢɦɚ).Ɇɧɨɠɟɫɬɜɨ ɜɫɟɯ ɥɨɝɢɱɟɫɤɢɯ ɫɥɟɞɫɬɜɢɣ – ɷɬɨ ɢ ɟɫɬɶ ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɥɨɝɢɱɟɫɤɢɯ ɡɚɤɨɧɨɜ.Ɂɚɦɟɱɚɧɢɟ.
ɋɭɳɟɫɬɜɭɸɬ ɮɨɪɦɭɥɵ, ɜɵɩɨɥɧɢɦɵɟ ɧɚ ɤɨɧɟɱɧɵɯ ɢɧɬɟɪɩɪɟɬɚɰɢɹɯ ɢɧɟɜɵɩɨɥɧɢɦɵɟ ɧɚ ɛɟɫɤɨɧɟɱɧɵɯ.Ɋɚɫɫɦɨɬɪɢɦ ɮɨɪɦɭɥɭ M0 M1 & M 2 o M3 , ɝɞɟ M1 xR( x, x) ,xyR( x, y ) . * | M , ' !. M, * | ' ! M1 & M 2 , * | ' !3. L & :. M1 , M 2 , * | ' ! * | M1 & M 2 , ' !4. R & :. ȼ ɞɚɧɧɨɦ ɫɥɭɱɚɟ ɩɪɨɢɫɯɨɞɢɬ ɜɟɬɜɥɟɧɢɟ ɩɪɨɰɟɫɫɚ ɬɚɛɥɢɱɧɨɝɨ * | M1 , ' ! * | M 2 , ' !ɜɵɜɨɞɚ, ɢ ɜɵɩɨɥɧɢɦɨɫɬɶ Ɍ0 ɷɤɜɢɜɚɥɟɧɬɧɚ ɜɵɩɨɥɧɢɦɨɫɬɢ ɢɥɢ Ɍ1, ɢɥɢ Ɍ2. M1 M 2 , * | ' !.5. L : , * | ' ! , * | ' !2.
R :M1M2 * | M1 M 2 , ' !. * | M1 , M 2 , ' ! M1 o M 2 , * | ' !7. L o :. M 2 , * | M1 , ' ! * | M1 o M 2 , ' !8. R o :. ,* | ,' !6. R :M1Ɍɟɨɪɟɦɚ: ɇɚ ɥɸɛɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɢ I, ɬɚɤɨɣ, ɱɬɨ DI - ɤɨɧɟɱɧɨɟ ɦɧɨɠɟɫɬɜɨ, M 0 ɜɵɩɨɥɧɢɦɚ,ɨɞɧɚɤɨ M 0 ɧɟ ɨɛɳɟɡɧɚɱɢɦɚ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɍɩɨɪɹɞɨɱɟɧɧɚɹ ɩɚɪɚ ɦɧɨɠɟɫɬɜ ɮɨɪɦɭɥ *, ' ! ɧɚɡɵɜɚɟɬɫɹ ɫɟɦɚɧɬɢɱɟɫɤɨɣɬɚɛɥɢɰɟɣ.ȿɫɥɢ ɩɟɪɟɫɟɱɟɧɢɟ Ƚ ɢ ' ɧɟ ɩɭɫɬɨ, ɬɨ ɬɚɤɚɹ ɫɟɦɚɧɬɢɱɟɫɤɚɹ ɬɚɛɥɢɰɚ ɧɚɡɵɜɚɟɬɫɹ ɡɚɤɪɵɬɨɣ.ȿɫɥɢ M - ɮɨɪɦɭɥɚ, ɬɨ ɬɚɛɥɢɰɟɣ ɞɥɹ ɮɨɪɦɭɥɵ M ɧɚɡɨɜɟɦ ɫɟɦɚɧɬɢɱɟɫɤɭɸ ɬɚɛɥɢɰɭTM ,{M} !ɋɨɞɟɪɠɚɬɟɥɶɧɵɣ ɫɦɵɫɥ ɫɟɦɚɧɬɢɱɟɫɤɨɣ ɬɚɛɥɢɰɵ ɬɚɤɨɜ: Ƚ – ɦɧɨɠɟɫɬɜɨ ɮɨɪɦɭɥ, ɤɨɬɨɪɵɟ ɦɵɯɨɬɢɦ ɫɱɢɬɚɬɶ ɢɫɬɢɧɧɵɦɢ, ' - ɦɧɨɠɟɫɬɜɨ ɮɨɪɦɭɥ, ɤɨɬɨɪɵɟ ɦɵ ɯɨɬɢɦ ɫɱɢɬɚɬɶ ɥɨɠɧɵɦɢ.Ɍɨɝɞɚ ɡɚɤɪɵɬɚɹ ɬɚɛɥɢɰɚ ɩɪɨɬɢɜɨɪɟɱɢɜɚ, ɚ ɬɚɛɥɢɰɚ ɞɥɹ ɮɨɪɦɭɥɵ M ɛɭɞɟɬ ɹɜɥɹɬɶɫɹ ɢɫɯɨɞɧɵɦɫɨɫɬɨɹɧɢɟɦ ɞɥɹ ɞɨɤɚɡɚɬɟɥɶɫɬɜɚ ɨɛɳɟɡɧɚɱɢɦɨɫɬɢ ɮɨɪɦɭɥɵ M ɨɬ ɩɪɨɬɢɜɧɨɝɨ.Ɉɩɪɟɞɟɥɟɧɢɟ.
Ɍɚɛɥɢɰɚ T * | ' ! ɧɚɡɵɜɚɟɬɫɹ ɜɵɩɨɥɧɢɦɨɣ, ɟɫɥɢ ɫɭɳɟɫɬɜɭɟɬ ɢɧɬɟɪɩɪɟɬɚɰɢɹI, ɬɚɤɚɹ, ɱɬɨ ɥɸɛɚɹ ɮɨɪɦɭɥɚ M ɢɡ ɦɧɨɠɟɫɬɜɚ Ƚ ɛɭɞɟɬ ɜɵɩɨɥɧɢɦɚ ɜ ɞɚɧɧɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɢ, ɚɥɸɛɚɹ ɮɨɪɦɭɥɚ \ ɢɡ ɦɧɨɠɟɫɬɜɚ ' ɜɵɩɨɥɧɢɦɨɣ ɜ ɞɚɧɧɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɢ ɧɟ ɛɭɞɟɬ.ɍɬɜɟɪɠɞɟɧɢɟ. Ɂɚɤɪɵɬɚɹ ɬɚɛɥɢɰɚ ɧɟ ɹɜɥɹɟɬɫɹ ɜɵɩɨɥɧɢɦɨɣ.Ⱦɥɹ ɞɨɤɚɡɚɬɟɥɶɫɬɜɚ ɨɛɳɟɡɧɚɱɢɦɨɫɬɢ ɮɨɪɦɭɥɵ, ɫɥɟɞɭɟɬ ɩɪɟɨɛɪɚɡɨɜɚɬɶ ɟɟ ɬɚɛɥɢɰɭ. ɗɬɚɨɩɟɪɚɰɢɹ ɧɚɡɵɜɚɟɬɫɹ ɬɚɛɥɢɱɧɵɦ ɜɵɜɨɞɨɦ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɪɚɜɢɥɨɦ ɬɚɛɥɢɱɧɨɝɨ ɜɵɜɨɞɚ ɧɚɡɵɜɚɟɬɫɹ ɮɢɝɭɪɚ ɜɢɞɚT0.T1 (T2 )ȼɜɟɞɟɦ ɫɥɟɞɭɸɳɭɸ ɫɢɫɬɟɦɭ ɩɪɚɜɢɥ: M , * | ' !1.
L :. L ɨɡɧɚɱɚɟɬ, ɱɬɨ ɦɵ ɩɪɟɨɛɪɚɡɨɜɵɜɚɟɦ ɥɟɜɭɸ ɱɚɫɬɶ ɬɚɛɥɢɰɵ, ɩɪɢɱɟɦ * | M, ' !ɨɬɪɢɰɚɧɢɟ – ɝɥɚɜɧɚɹ ɥɨɝɢɱɟɫɤɚɹ ɫɜɹɡɤɚ ɜ ɮɨɪɦɭɥɟ M.M2ɋ ɩɨɦɨɳɶɸ ɞɚɧɧɵɯ ɩɪɚɜɢɥ ɦɨɠɧɨ ɫɭɳɟɫɬɜɟɧɧɨ ɭɩɪɨɫɬɢɬɶ ɬɚɛɥɢɰɭ. Ⱦɥɹ ɭɩɪɨɳɟɧɢɹ ɮɨɪɦɭɥɫ ɤɜɚɧɬɨɪɚɦɢ ɬɪɟɛɭɟɬɫɹ ɜɜɟɫɬɢ ɞɨɩɨɥɧɢɬɟɥɶɧɵɟ ɩɨɧɹɬɢɹ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɨɞɫɬɚɧɨɜɤɨɣ ɧɚɡɵɜɚɟɬɫɹ ɥɸɛɨɟ ɨɬɨɛɪɚɠɟɧɢɟ T : Var o Term . Ɉɛɥɚɫɬɶɸɩɨɞɫɬɚɧɨɜɤɢ ɧɚɡɵɜɚɟɬɫɹ ɦɧɨɠɟɫɬɜɨ DomT {x : T ( x) z x} . ȿɫɥɢ ɨɛɥɚɫɬɶ ɩɨɞɫɬɚɧɨɜɤɢɤɨɧɟɱɧɚ, ɬɨ ɬɚɤɚɹ ɩɨɞɫɬɚɧɨɜɤɚ ɧɚɡɵɜɚɟɬɫɹ ɤɨɧɟɱɧɨɣ. Ɇɧɨɠɟɫɬɜɨ ɜɫɟɯ ɤɨɧɟɱɧɵɯ ɩɨɞɫɬɚɧɨɜɨɤɛɭɞɟɦ ɨɛɨɡɧɚɱɚɬɶ ɤɚɤ Subst. ȿɫɥɢ T - ɤɨɧɟɱɧɚɹ ɩɨɞɫɬɚɧɨɜɤɚ, ɬɨ ɨɧɚ ɩɪɟɞɫɬɚɜɢɦɚ ɜ ɜɢɞɟxnxx2ɦɧɨɠɟɫɬɜɚ ɫɜɹɡɨɤ: T { 1T ( x1 ) , T ( x2 ) ,..., T ( xn )} .{ x } .
Ɍɨɝɞɚ ɡɚɩɢɫɶ ɜɢɞɚtȿT ɛɭɞɟɬ ɧɚɡɵɜɚɬɶɫɹ ɪɟɡɭɥɶɬɚɬɨɦ ɩɪɢɦɟɧɟɧɢɹ ɩɨɞɫɬɚɧɨɜɤɢ T ɤ ȿ. Ɉɧ ɨɩɪɟɞɟɥɹɟɬɫɹɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:t,y{x1) ȿ – ɩɟɪɟɦɟɧɧɚɹ ( E y Var ). Ɍɨɝɞɚ ET ®T ( y) .¯ y, y z x2) ȿ – ɤɨɧɫɬɚɧɬɚ (ȿ = ɫ). Ɍɨɝɞɚ ET E .3) ȿ – ɫɨɫɬɚɜɧɨɣ ɬɟɪɦ ( E f (t1 , t2 ,..., tk ) ). Ɍɨɝɞɚ ET f (t1T , t2T ,..., tkT ) .4) ȿ – ɚɬɨɦɚɪɧɚɹ ɮɨɪɦɭɥɚ ( E P(t1 , t2 ,..., tk ) ). Ɍɨɝɞɚ ET P (t1T , t2T ,..., tkT ) .Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ ȿ – ɥɨɝɢɱɟɫɤɨɟ ɜɵɪɚɠɟɧɢɟ T - ɩɨɫɬɚɧɨɜɤɚ T5) ȿ – ɮɨɪɦɭɥɚ ɜɢɞɚ M1 x M 2 , ɝɞɟ x ɨɡɧɚɱɚɟɬ ɤɨɧɴɸɧɤɰɢɸ, ɞɢɡɴɸɧɤɰɢɸ ɢɥɢ ɢɦɩɥɢɤɚɰɢɸ.Ɍɨɝɞɚ ȿT M1T x M2T , ɚ ɟɫɥɢ ȿ – ɮɨɪɦɭɥɚ ɜɢɞɚ M , ɬɨ ET MT .6) ȿ – ɮɨɪɦɭɥɚ ɫ ɤɜɚɧɬɨɪɨɦ yM ɢɥɢ yM . Ɍɨɝɞɚ ET E, y { x°.®yMT , y z x°¯Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɟɪɟɦɟɧɧɚɹ ɯ ɹɜɥɹɟɬɫɹ ɫɜɨɛɨɞɧɨɣ ɞɥɹ ɬɟɪɦɚ t ɜ ɮɨɪɦɭɥɟ M, ɟɫɥɢ ɜ M ɧɟɬɫɜɨɛɨɞɧɵɯ ɜɯɨɠɞɟɧɢɣ ɩɟɪɟɦɟɧɧɨɣ ɯ ɜ ɨɛɥɚɫɬɢ ɞɟɣɫɬɜɢɹ ɤɜɚɧɬɨɪɨɜ, ɫɜɹɡɵɜɚɸɳɢɯɩɟɪɟɦɟɧɧɵɟ ɢɡ ɦɧɨɠɟɫɬɜɚ Vart (ɦɧɨɠɟɫɬɜɚ ɩɟɪɟɦɟɧɧɵɯ ɬɟɪɦɚ t).ɇɚ ɨɫɧɨɜɟ ɩɨɧɹɬɢɹ ɩɨɞɫɬɚɧɨɜɤɢ ɜɜɟɞɟɦ 4 ɧɨɜɵɯ ɩɪɚɜɢɥɚ ɬɚɛɥɢɱɧɨɝɨ ɜɵɜɨɞɚ:6Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ.
(ɫ) 2006 GrGr (grgr@later.ru)Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru)^ y`); ɭ ɧɟ ɫɨɞɟɪɠɢɬɫɹ ɜ M ( ɯ)Ɇɟɬɨɞ ɪɟɡɨɥɸɰɢɣ – ɨɞɢɧ ɢɡ ɧɚɢɛɨɥɟɟ ɷɮɮɟɤɬɢɜɧɵɯ ɫɩɨɫɨɛɨɜ ɚɜɬɨɦɚɬɢɱɟɫɤɨɝɨɞɨɤɚɡɚɬɟɥɶɫɬɜɚ ɬɟɨɪɟɦ. Ɉɛɳɢɟ ɩɪɢɧɰɢɩɵ ɞɨɤɚɡɚɬɟɥɶɫɬɜɚ ɭɬɜɟɪɠɞɟɧɢɣ ɫ ɩɨɦɨɳɶɸ ɦɟɬɨɞɚɪɟɡɨɥɸɰɢɣ ɬɚɤɨɜɵ:1. ȿɫɥɢ ɦɵ ɯɨɬɢɦ ɞɨɤɚɡɚɬɶ ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ ɮɨɪɦɭɥɵ M, ɬɨ ɞɥɹ ɷɬɨɝɨ ɞɨɫɬɚɬɨɱɧɨ ɩɨɤɚɡɚɬɶ,ɱɬɨ ɮɨɪɦɭɥɚ M1 M ɩɪɨɬɢɜɨɪɟɱɢɜɚ (ɬ.ɟ. ɩɪɨɜɟɫɬɢ ɞɨɤɚɡɚɬɟɥɶɫɬɜɨ ɨɬ ɩɪɨɬɢɜɧɨɝɨ).2.
Ɏɨɪɦɭɥɚ M1 ɩɪɢɜɨɞɢɬɫɹ ɤ ɩɪɟɞɜɚɪɟɧɧɨɣ ɧɨɪɦɚɥɶɧɨɣ ɮɨɪɦɟ M2, ɜ ɤɨɬɨɪɨɣ ɜɫɟ ɤɜɚɧɬɨɪɵɫɬɨɹɬ ɜ ɧɚɱɚɥɟ ɮɨɪɦɭɥɵ.3. Ɏɨɪɦɭɥɚ M2 ɩɪɢɜɨɞɢɬɫɹ ɤ ɫɤɨɥɟɦɨɜɫɤɨɣ ɫɬɚɧɞɚɪɬɧɨɣ ɮɨɪɦɟ, ɜ ɤɨɬɨɪɨɣ ɨɬɫɭɬɫɬɜɭɸɬɤɜɚɧɬɨɪɵ ɫɭɳɟɫɬɜɨɜɚɧɢɹ: M3 x1x2 ...xn ( D1 & D2 &...& Dn ) , ɝɞɟ Di L1 L2 ... Lm , ɚ A½L j ® ¾ .
ɋɥɟɞɭɟɬ ɭɛɟɞɢɬɶɫɹ, ɱɬɨ ɫɨɞɟɪɠɢɦɨɟ M ɧɟ ɛɵɥɨ ɩɨɬɟɪɹɧɨ.¯ A ¿4. Ⱦɨɤɚɡɚɬɟɥɶɫɬɜɨ ɨɛɳɟɡɧɚɱɢɦɨɫɬɢ M ɫɜɨɞɢɬɫɹ ɤ ɞɨɤɚɡɚɬɟɥɶɫɬɜɭ ɩɪɨɬɢɜɨɪɟɱɢɜɨɫɬɢ ɫɢɫɬɟɦɵɞɢɡɴɸɧɤɬɨɜ S {D1 , D2 ,..., Dn } . Ⱦɥɹ ɷɬɨɝɨ ɩɪɢɦɟɧɹɟɬɫɹ ɩɪɚɜɢɥɨ ɪɟɡɨɥɸɰɢɣ Ɋɨɛɟɧɫɨɧɚ:{D ' L, D '' L} {D ' D '' } . ɑɬɨɛɵ ɩɪɢɦɟɧɟɧɢɟ ɷɬɨɝɨ ɩɪɚɜɢɥɚ ɫɬɚɥɨ ɜɨɡɦɨɠɧɵɦ,Ɋɨɛɟɧɫɨɧ ɜɜɟɥ ɚɥɝɨɪɢɬɦ ɭɧɢɮɢɤɚɰɢɢ ɞɥɹ ɫɢɫɬɟɦɵ {D ' L ', D '' L ''} . ȿɫɥɢ L’ ɢ L’’ɭɧɢɮɢɰɢɪɨɜɚɧɵ, ɬɨ ɬɚɤɨɣ ɦɟɬɨɞ ɩɨɫɬɪɨɟɧɢɹ ɜɵɜɨɞɚ ɞɥɹ ɨɛɳɟɡɧɚɱɢɦɨɣ ɮɨɪɦɭɥɵ ɫɬɚɧɟɬɩɨɥɧɵɦ.9) | ( xM ) { x(M )&&10) | ( xM ) \ { x(M \ )x Var\&&11) | x(M \ ) { (xM ) (x\ )Ɉɩɪɟɞɟɥɟɧɢɟ.
