Теормин - шпоры, страница 2
Описание файла
PDF-файл из архива "Теормин - шпоры", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
Ɏɨɪɦɭɥɚ M ɧɚɡɵɜɚɟɬɫɹ ɢɫɬɢɧɧɨɣ ɜ ɢɧɬɟɪɩɪɟɬɚɰɢɢ I, ɟɫɥɢ ɞɥɹ ɥɸɛɨɝɨ ɧɚɛɨɪɚɩɪɟɞɦɟɬɨɜ d1, d2, …, dn I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] .Ɉɩɪɟɞɟɥɟɧɢɟ. Ɏɨɪɦɭɥɚ M ɧɚɡɵɜɚɟɬɫɹ ɧɟɜɵɩɨɥɧɢɦɨɣ (ɢɥɢ ɩɪɨɬɢɜɨɪɟɱɢɜɨɣ) ɜ ɢɧɬɟɪɩɪɟɬɚɰɢɢI, ɟɫɥɢ ɨɧɚ ɧɟ ɹɜɥɹɟɬɫɹ ɜɵɩɨɥɧɢɦɨɣ (ɬ.ɟ. ɟɫɥɢ ɷɬɚ ɮɨɪɦɭɥɚ ɫɨɨɬɜɟɬɫɬɜɭɟɬ ɬɨɠɞɟɫɬɜɟɧɧɨɥɨɠɧɨɦɭ ɭɬɜɟɪɠɞɟɧɢɸ).Ɉɩɪɟɞɟɥɟɧɢɟ.
Ɏɨɪɦɭɥɚ M ɧɚɡɵɜɚɟɬɫɹ ɨɛɳɟɡɧɚɱɢɦɨɣ, ɟɫɥɢ ɨɧɚ ɹɜɥɹɟɬɫɹ ɢɫɬɢɧɧɨɣ ɜ ɥɸɛɨɣɢɧɬɟɪɩɪɟɬɚɰɢɢ. Ɉɛɳɟɡɧɚɱɢɦɨɫɬɶ ɮɨɪɦɭɥɵ ɨɛɨɡɧɚɱɚɟɬɫɹ |=M.ȼɵɩɨɥɧɢɦɵɟ, ɧɨ ɧɟ ɨɛɳɟɡɧɚɱɢɦɵɟ ɮɨɪɦɭɥɵ ɧɚɢɛɨɥɟɟ ɢɧɬɟɪɟɫɧɵ ɞɥɹ ɪɚɫɫɦɨɬɪɟɧɢɹ, ɬɨɝɞɚɤɚɤ ɨɛɳɟɡɧɚɱɢɦɵɟ ɮɨɪɦɭɥɵ ɨɛɵɱɧɨ ɦɚɥɨ ɢɧɮɨɪɦɚɬɢɜɧɵ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ * Form - ɦɧɨɠɟɫɬɜɨ ɡɚɦɤɧɭɬɵɯ ɮɨɪɦɭɥ. Ɍɨɝɞɚ ɢɧɬɟɪɩɪɟɬɚɰɢɹ Iɧɚɡɵɜɚɟɬɫɹ ɦɨɞɟɥɶɸ ɞɥɹ ɦɧɨɠɟɫɬɜɚ Ƚ, ɟɫɥɢ ɥɸɛɚɹ ɮɨɪɦɭɥɚ ɢɡ Ƚ ɜɵɩɨɥɧɢɦɚ ɜ ɞɚɧɧɨɣɢɧɬɟɪɩɪɟɬɚɰɢɢ.Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru) xM ( x), * | ' !ɩɪɢ ɭɫɥɨɜɢɢ, ɱɬɨ ɩɟɪɟɦɟɧɧɚɹ ɯ ɜ ɮɨɪɦɭɥɟ M(ɯ) ɫɜɨɛɨɞɧɚ xM ( x), M ( x){ x }, * | ' !tɞɥɹ ɬɟɪɦɚ t. * | xM ( x), ' !10. R :, ɝɞɟ ɫ – ɷɬɨ ɤɨɧɫɬɚɧɬɚ, ɤɨɬɨɪɚɹ ɧɟ ɫɨɞɟɪɠɢɬɫɹ ɜ Ƚ, ' ɢɥɢ M(ɯ). * | M ( x){ x }, ' !c xM ( x), * | ' !11.
L :.x M ( x){ }, * | ' !c9. L : * | xM ( x), ' ! * | xM ( x), M ( x){ x }, ' !tɌɚɤɢɦ ɨɛɪɚɡɨɦ, ɢɦɟɟɦ 12 ɩɪɚɜɢɥ, ɪɚɫɩɨɥɚɝɚɹ ɤɨɬɨɪɵɦɢ, ɦɨɠɧɨ ɩɨɫɬɪɨɢɬɶ ɬɚɛɥɢɱɧɵɣ ɜɵɜɨɞ.12. R :Ɉɩɪɟɞɟɥɟɧɢɟ. Ɍɚɛɥɢɱɧɵɦ ɜɵɜɨɞɨɦ ɫɟɦɚɧɬɢɱɟɫɤɨɣ ɬɚɛɥɢɰɵ Ɍ0 ɧɚɡɵɜɚɟɬɫɹ ɤɨɪɧɟɜɨɟ ɞɟɪɟɜɨ,ɜɟɪɲɢɧɵ ɤɨɬɨɪɨɝɨ ɩɨɦɟɱɟɧɵ ɬɚɛɥɢɰɚɦɢ, ɩɪɢɱɟɦ ɷɬɨ ɞɟɪɟɜɨ ɭɞɨɜɥɟɬɜɨɪɹɟɬ ɫɥɟɞɭɸɳɢɦɬɪɟɛɨɜɚɧɢɹɦ:1. Ʉɨɪɧɟɜɚɹ ɜɟɪɲɢɧɚ ɩɨɦɟɱɟɧɚ ɬɚɛɥɢɰɟɣ Ɍ0.2. Ʉɚɠɞɚɹ ɜɢɫɹɱɚɹ ɜɟɪɲɢɧɚ ɞɨɥɠɧɚ ɛɵɬɶ ɩɨɦɟɱɟɧɚ ɥɢɛɨ ɡɚɤɪɵɬɨɣ ɬɚɛɥɢɰɟɣ, ɥɢɛɨ ɬɚɤɨɣɬɚɛɥɢɰɟɣ, ɱɬɨ ɜ ɧɟɣ ɫɨɞɟɪɠɚɬɫɹ ɬɨɥɶɤɨ ɚɬɨɦɚɪɧɵɟ ɮɨɪɦɭɥɵ (ɬ.ɟ. ɛɟɡ ɫɜɹɡɨɤ ɢ ɤɜɚɧɬɨɪɨɜ).3. ɇɟ ɜɢɫɹɱɚɹ ɜɟɪɲɢɧɚ, ɩɨɦɟɱɟɧɧɚɹ ɬɚɛɥɢɰɟɣ Ɍi, ɨɛɹɡɚɬɟɥɶɧɨ ɢɦɟɟɬ ɨɞɧɨɝɨ ɢɥɢ ɞɜɭɯɧɚɫɥɟɞɧɢɤɨɜ, ɤɨɬɨɪɵɟ ɩɨɥɭɱɚɸɬɫɹ ɢɡ Ɍi ɩɨ ɨɞɧɨɦɭ ɢɡ 12 ɩɪɚɜɢɥ ɬɚɛɥɢɱɧɨɝɨ ɜɵɜɨɞɚ.Ⱦɟɪɟɜɨ (ɢɥɢ ɜɵɜɨɞ) ɫɱɢɬɚɟɬɫɹ ɭɫɩɟɲɧɵɦ (ɭɫɩɟɲɧɵɣ ɜɵɜɨɞ ɧɚɡɵɜɚɟɬɫɹ ɞɨɤɚɡɚɬɟɥɶɫɬɜɨɦ),ɟɫɥɢ ɤɚɠɞɚɹ ɜɟɬɜɶ ɞɟɪɟɜɚ ɡɚɜɟɪɲɚɟɬɫɹ ɡɚɤɪɵɬɨɣ ɬɚɛɥɢɰɟɣ.Ⱦɥɹ ɬɚɛɥɢɱɧɨɝɨ ɜɵɜɨɞɚ ɤɚɤ ɞɥɹ ɞɨɤɚɡɚɬɟɥɶɫɬɜɚ ɨɛɳɟɡɧɚɱɢɦɨɫɬɢ ɫɪɚɡɭ ɜɨɡɧɢɤɚɸɬ ɫɥɟɞɭɸɳɢɟɜɨɩɪɨɫɵ:- ɤɨɪɪɟɤɬɧɨɫɬɢ;- ɩɨɥɧɨɬɵ (ɹɜɥɹɟɬɫɹ ɥɢ ɬɚɛɥɢɱɧɵɣ ɜɵɜɨɞ ɭɧɢɜɟɪɫɚɥɶɧɵɦ ɫɩɨɫɨɛɨɦ ɞɨɤɚɡɚɬɟɥɶɫɬɜɚ);- ɷɮɮɟɤɬɢɜɧɨɫɬɢ (ɤɚɤɢɦ ɨɛɪɚɡɨɦ ɢ ɜ ɤɚɤɨɦ ɩɨɪɹɞɤɟ ɫɥɟɞɭɟɬ ɩɪɢɦɟɧɹɬɶ ɩɪɚɜɢɥɚ ɬɚɛɥɢɱɧɨɝɨɜɵɜɨɞɚ).Ɍɟɨɪɟɦɚ (ɤɨɪɪɟɤɬɧɨɫɬɢ): ȿɫɥɢ ɬɚɛɥɢɰɚ Ɍ0 ɢɦɟɟɬ ɭɫɩɟɲɧɵɣ ɬɚɛɥɢɱɧɵɣ ɜɵɜɨɞ, ɬɨ Ɍ0ɧɟɜɵɩɨɥɧɢɦɚ.ɋɥɟɞɫɬɜɢɟ 1.
ȿɫɥɢ ɬɚɛɥɢɰɚ TM ,{M} ! ɢɦɟɟɬ ɭɫɩɟɲɧɵɣ ɬɚɛɥɢɱɧɵɣ ɜɵɜɨɞ, ɬɨ ɮɨɪɦɭɥɚ Mɨɛɳɟɡɧɚɱɢɦɚ.ɋɥɟɞɫɬɜɢɟ 2. ȿɫɥɢ ɬɚɛɥɢɰɚ TM' {M}, ! ɢɦɟɟɬ ɭɫɩɟɲɧɵɣ ɬɚɛɥɢɱɧɵɣ ɜɵɜɨɞ, ɬɨ ɮɨɪɦɭɥɚ Mɹɜɥɹɟɬɫɹ ɩɪɨɬɢɜɨɪɟɱɢɜɨɣ.Ɍɟɨɪɟɦɚ (ɩɨɥɧɨɬɵ ɬɚɛɥɢɱɧɨɝɨ ɜɵɜɨɞɚ): ȿɫɥɢ ɬɚɛɥɢɰɚ Ɍ0 ɧɟɜɵɩɨɥɧɢɦɚ, ɬɨ Ɍ0 ɢɦɟɟɬɭɫɩɟɲɧɵɣ ɬɚɛɥɢɱɧɵɣ ɜɵɜɨɞ.ɋɥɟɞɫɬɜɢɟ 1 (ɬɟɨɪɟɦɚ Ƚɺɞɟɥɹ ɨ ɩɨɥɧɨɬɟ): ȿɫɥɢ ɮɨɪɦɭɥɚ M ɨɛɳɟɡɧɚɱɢɦɚ, ɬɨ ɬɚɛɥɢɰɚTM ,{M} ! ɢɦɟɟɬ ɭɫɩɟɲɧɵɣ ɬɚɛɥɢɱɧɵɣ ɜɵɜɨɞ.ɋɥɟɞɫɬɜɢɟ 2 (ɬɟɨɪɟɦɚ Ʌɢɜɟɧɝɟɣɦɚ-ɋɤɨɥɟɦɚ ɨ ɫɱɟɬɧɨɣ ɦɨɞɟɥɢ): ȿɫɥɢ ɮɨɪɦɭɥɚ Mɜɵɩɨɥɧɢɦɚ, ɬɨ M ɢɦɟɟɬ ɦɨɞɟɥɶ ɫ ɧɟ ɛɨɥɟɟ, ɱɟɦ ɫɱɟɬɧɨɣ ɛɟɫɤɨɧɟɱɧɨɣ ɨɛɥɚɫɬɶɸɢɧɬɟɪɩɪɟɬɚɰɢɢ.ɋɥɟɞɫɬɜɢɟ 3 (ɬɟɨɪɟɦɚ Ɇɚɥɶɰɟɜɚ ɨ ɤɨɦɩɚɤɬɧɨɫɬɢ): ɉɭɫɬɶ * Form - ɩɪɨɢɡɜɨɥɶɧɨɟɦɧɨɠɟɫɬɜɨ ɮɨɪɦɭɥ.
Ɍɨɝɞɚ Ƚ ɢɦɟɟɬ ɦɨɞɟɥɶ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɤɚɠɞɨɟ ɟɟɩɨɞɦɧɨɠɟɫɬɜɨ ɢɦɟɟɬ ɦɨɞɟɥɶ.Ⱦɨɤɚɡɚɬɟɥɶɫɬɜɨ ɭɬɜɟɪɠɞɟɧɢɹ ɩɪɟɞɥɚɝɚɟɬɫɹ ɩɪɨɜɟɫɬɢ ɫɚɦɨɫɬɨɹɬɟɥɶɧɨ.8M ª\ F º ɨɡɧɚɱɚɟɬ ɡɚɦɟɧɭ ɜ ɮɨɪɦɭɥɟ M ɩɨɞɮɨɪɦɭɥɵ \ ɧɚ F.«¬»¼Ɍɟɨɪɟɦɚ: ɉɭɫɬɶ M, \, F - ɩɪɨɢɡɜɨɥɶɧɵɟ ɮɨɪɦɭɥɵ. Ɍɨɝɞɚ ɢɡ ɪɚɜɧɨɫɢɥɶɧɨɫɬɢ \ ɢ F ɫɥɟɞɭɟɬ,ɱɬɨ | M { M ª\ º .«¬ F »¼Ɉɩɪɟɞɟɥɟɧɢɟ. Ʌɢɬɟɪɚ – ɷɬɨ ɥɢɛɨ ɚɬɨɦ AɆɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru)Ɉɩɪɟɞɟɥɟɧɢɟ. Ɉɫɧɨɜɧɵɦ ɬɟɪɦɨɦ ɧɚɡɵɜɚɟɬɫɹ ɥɸɛɨɣ ɬɟɪɦ, ɧɟ ɢɦɟɸɳɢɣ ɫɜɨɛɨɞɧɵɯɩɟɪɟɦɟɧɧɵɯ.H i { f ( k ) (t1 , t2 ,..., tk )} ɞɥɹ ɜɫɟɯ f ( k ) FuncM ɢ t1 , t2 ,..., tk H ifP(t1 , t2 ,..., tn ) , ɥɢɛɨ A .Ɉɩɪɟɞɟɥɟɧɢɟ.
Ⱦɢɡɴɸɧɤɬ – ɷɬɨ ɥɢɛɨ ɞɢɡɴɸɧɤɰɢɹ ɚɬɨɦɨɜ L1 L2 ... Ln , ɥɢɛɨ ɩɭɫɬɨɣɞɢɡɴɸɧɤɬ - ɬɨɠɞɟɫɬɜɟɧɧɚɹ ɥɨɠɶ.ɍɬɜɟɪɠɞɟɧɢɟ. Ɉɬɧɨɲɟɧɢɟ ɪɚɜɧɨɫɢɥɶɧɨɫɬɢ ɹɜɥɹɟɬɫɹ ɨɬɧɨɲɟɧɢɟɦ ɷɤɜɢɜɚɥɟɧɬɧɨɫɬɢ.Ɍɟɨɪɟɦɚ (ɨ ɩɪɟɞɜɚɪɟɧɧɨɣ ɧɨɪɦɚɥɶɧɨɣ ɮɨɪɦɟ): Ⱦɥɹ ɥɸɛɨɣ ɡɚɦɤɧɭɬɨɣ ɮɨɪɦɭɥɵ Mɫɭɳɟɫɬɜɭɟɬ ɪɚɜɧɨɫɢɥɶɧɚɹ ɟɣ ɩɪɟɞɜɚɪɟɧɧɚɹ ɧɨɪɦɚɥɶɧɚɹ ɮɨɪɦɚ \.ɍɬɜɟɪɠɞɟɧɢɟ. ȿɫɥɢ ɮɨɪɦɭɥɵ M ɢ \ ɪɚɜɧɨɫɢɥɶɧɵ, ɬɨ:1.
ɂɡ ɨɛɳɟɡɧɚɱɢɦɨɫɬɢ M ɫɥɟɞɭɟɬ ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ \;2. ɂɡ ɜɵɩɨɥɧɢɦɨɫɬɢ M ɫɥɟɞɭɟɬ ɜɵɩɨɥɧɢɦɨɫɬɶ \;3. ȿɫɥɢ I ɹɜɥɹɟɬɫɹ ɦɨɞɟɥɶɸ ɞɥɹ M, ɬɨ ɨɧɚ ɹɜɥɹɟɬɫɹ ɬɚɤɠɟ ɦɨɞɟɥɶɸ ɞɥɹ \.Ɉɩɪɟɞɟɥɟɧɢɟ. ɋɤɨɥɟɦɨɜɫɤɚɹ ɫɬɚɧɞɚɪɬɧɚɹ ɮɨɪɦɚ – ɷɬɨ ɩɪɟɞɜɚɪɟɧɧɚɹ ɧɨɪɦɚɥɶɧɚɹ ɮɨɪɦɚɜɢɞɚ x1x2 ...xn M ( x1 , x2 ,..., xn ) .Ɍɟɨɪɟɦɚ (ɨ ɫɤɨɥɟɦɨɜɫɤɨɣ ɫɬɚɧɞɚɪɬɧɨɣ ɮɨɪɦɟ): Ⱦɥɹ ɥɸɛɨɣ ɡɚɦɤɧɭɬɨɣ ɮɨɪɦɭɥɵ Mɫɭɳɟɫɬɜɭɟɬ ɫɤɨɥɟɦɨɜɫɤɚɹ ɧɨɪɦɚɥɶɧɚɹ ɮɨɪɦɚ \, ɩɪɢɱɟɦ M ɜɵɩɨɥɧɢɦɚ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ,ɤɨɝɞɚ ɜɵɩɨɥɧɢɦɚ \.3. H*Hii 0Ɉɩɪɟɞɟɥɟɧɢɟ. ɗɪɛɪɚɧɨɜɫɤɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɟɣ ɞɥɹ ɫɢɫɬɟɦɵ ɞɢɡɴɸɧɤɬɨɜ SM ɧɚɡɵɜɚɟɬɫɹɢɧɬɟɪɩɪɟɬɚɰɢɹ I H , Const, Func, Pred ! , ɝɞɟ H – ɷɪɛɪɚɧɨɜɫɤɢɣ ɭɧɢɜɟɪɫɭɦ, ɚ ɨɫɬɚɥɶɧɵɟɦɧɨɠɟɫɬɜɚ ɨɩɪɟɞɟɥɹɸɬɫɹ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:Const : c Const; c cFunc : f ( m ) Func; f10: t1 , t2 ,..., tm Hf(m): (t1 , t2 ,..., tm ) o f ( m ) (t1 , t2 ,..., tm )Ɍɟɨɪɟɦɚ (ɨɛ ɷɪɛɪɚɧɨɜɫɤɢɯ ɢɧɬɟɪɩɪɟɬɚɰɢɹɯ): ɋɢɫɬɟɦɚ ɞɢɡɴɸɧɤɬɨɜ ɧɟɜɵɩɨɥɧɢɦɚ ɬɨɝɞɚ ɢɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɨɧɚ ɧɟɜɵɩɨɥɧɢɦɚ ɧɚ ɷɪɛɪɚɧɨɜɫɤɢɯ ɢɧɬɟɪɩɪɟɬɚɰɢɹɯ.ɋɭɳɟɫɬɜɭɟɬ ɧɟɫɤɨɥɶɤɨ ɫɩɨɫɨɛɨɜ ɩɪɟɞɫɬɚɜɥɟɧɢɹ ɷɪɛɪɚɧɨɜɫɤɢɯ ɢɧɬɟɪɩɪɟɬɚɰɢɣ:1.
Ɍɟɨɪɟɬɢɤɨ-ɦɧɨɠɟɫɬɜɟɧɧɵɣ.ɇɚɡɨɜɟɦ ɨɫɧɨɜɧɵɦ ɚɬɨɦɨɦ ɚɬɨɦɚɪɧɭɸ ɮɨɪɦɭɥɭ (ɛɟɡ ɫɜɨɛɨɞɧɵɯ ɩɟɪɟɦɟɧɧɵɯ), ɩɨɥɭɱɟɧɧɭɸ ɜɪɟɡɭɥɶɬɚɬɟ ɩɨɞɫɬɚɧɨɜɤɢ ɜ ɧɟɤɨɬɨɪɵɣ ɩɪɟɞɢɤɚɬ Ɋ ɨɫɧɨɜɧɵɯ ɬɟɪɦɨɜ:P(t1 , t2 ,..., tm ) Atom;(t1 , t2 ,..., tm ) HɌɨɝɞɚ I ɛɭɞɟɬ ɹɜɥɹɬɶɫɹ ɷɪɛɪɚɧɨɜɫɤɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɟɣ ɞɥɹ ɦɧɨɠɟɫɬɜɚ ɨɫɧɨɜɧɵɯ ɚɬɨɦɨɜ, ɟɫɥɢɧɚ ɧɟɣ ɛɭɞɟɬ ɜɵɩɨɥɧɢɦ ɥɸɛɨɣ ɨɫɧɨɜɧɨɣ ɚɬɨɦ ɢɡ ɷɬɨɝɨ ɦɧɨɠɟɫɬɜɚ.2. ɉɨɫɥɟɞɨɜɚɬɟɥɶɧɵɣɈɫɧɨɜɧɨɣ ɥɢɬɟɪɨɣ ɧɚɡɵɜɚɟɬɫɹ ɥɢɛɨ ɨɫɧɨɜɧɨɣ ɚɬɨɦ, ɢɥɢ ɟɝɨ ɨɬɪɢɰɚɧɢɟ. ɍɩɨɪɹɞɨɱɟɧɧɨɟɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɨɫɧɨɜɧɵɯ ɚɬɨɦɨɜ ɛɭɞɟɬ ɧɚɡɵɜɚɬɶɫɹ ɷɪɛɪɚɧɨɜɫɤɢɦ ɛɚɡɢɫɨɦ ȼ.
Ɍɨɝɞɚ ɫɷɪɛɪɚɧɨɜɫɤɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɟɣ ɦɨɠɧɨ ɫɜɹɡɚɬɶ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɫɬɶ ɥɢɬɟɪ A1V1 , A2V 2 ,..., AlV l ,... ,ɩɪɢɱɟɦ AiV i ɛɭɞɟɬ ɪɚɜɧɨ Ai , ɟɫɥɢ Ai ɜɵɩɨɥɧɢɦɚ ɜ I, ɢ Ai ɜ ɩɪɨɬɢɜɧɨɦ ɫɥɭɱɚɟ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ BHA1ɮɨɪɦɭɥɚ M ɜɵɩɨɥɧɢɦɚ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɜɵɩɨɥɧɢɦɚ ɮɨɪɦɭɥɚx1x2 ...xk F ( x1 , x2 ,..., xk , f ( k ) ( x1 , x2 ,..., xk )) . ɉɪɢ ɷɬɨɦ f ( k ) ɧɚɡɵɜɚɟɬɫɹ ɫɤɨɥɟɦɨɜɫɤɨɣ ɮɭɧɤɰɢɟɣ.Ɍɟɨɪɟɦɚ. Ɏɨɪɦɭɥɚ M ɨɛɳɟɡɧɚɱɢɦɚ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɧɟɜɵɩɨɥɧɢɦɚ ɫɢɫɬɟɦɚɞɢɡɴɸɧɤɬɨɜ S M .(m)Pred : P ( n ) PredɅɟɦɦɚ (ɨ ɫɤɨɥɟɦɢɡɚɰɢɢ): ɉɭɫɬɶ ɡɚɦɤɧɭɬɚɹ ɮɨɪɦɭɥɚ M ɢɦɟɟɬ ɜɢɞx1x2 ...xk y F ( x1 , x2 ,..., xk , y ) ɢ ɩɭɫɬɶ ɬɚɤɠɟ ɢɦɟɟɬɫɹ ɮɭɧɤɰɢɨɧɚɥɶɧɵɣ ɫɢɦɜɨɥ f ( k ) .
ɌɨɝɞɚɈɩɪɟɞɟɥɟɧɢɟ. ɋɢɫɬɟɦɚ ɞɢɡɴɸɧɤɬɨɜ S ɧɚɡɵɜɚɟɬɫɹ ɧɟɜɵɩɨɥɧɢɦɨɣ, ɟɫɥɢ ɧɟ ɫɭɳɟɫɬɜɭɟɬ ɬɚɤɨɣɢɧɬɟɪɩɪɟɬɚɰɢɢ, ɜ ɤɨɬɨɪɨɣ ɛɭɞɭɬ ɜɵɩɨɥɧɢɦɵ ɨɞɧɨɜɪɟɦɟɧɧɨ ɜɫɟ ɞɢɡɴɸɧɤɬɵ, ɜɯɨɞɹɳɢɟ ɜ S.9Ɉɩɪɟɞɟɥɟɧɢɟ. Ɏɨɪɦɭɥɚ M ɧɚɡɵɜɚɟɬɫɹ ɜɵɩɨɥɧɢɦɨɣ ɜ ɢɧɬɟɪɩɪɟɬɚɰɢɢ I, ɟɫɥɢ ɞɥɹ ɧɟɤɨɬɨɪɨɝɨɧɚɛɨɪɚ ɩɪɟɞɦɟɬɨɜ d1, d2, …, dn I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] .2. H i 1Ɉɩɪɟɞɟɥɟɧɢɟ. Ɂɚɩɢɫɶ M [\ ] ɨɡɧɚɱɚɟɬ, ɱɬɨ ɜ ɮɨɪɦɭɥɟ M ɫɨɞɟɪɠɢɬɫɹ ɩɨɞɮɨɪɦɭɥɚ \; ɡɚɩɢɫɶɈɩɪɟɞɟɥɟɧɢɟ. ɉɪɟɞɜɚɪɟɧɧɚɹ ɧɨɪɦɚɥɶɧɚɹ ɮɨɪɦɚ – ɷɬɨ ɮɨɪɦɭɥɚ ɜɢɞɚQ1 x1Q2 x2 ...Qn xn M ( x1 , x2 ,..., xn ) , ɝɞɟ Qi {, } - ɤɜɚɧɬɨɪɧɚɹ ɩɪɢɫɬɚɜɤɚ, ɚ Ɇ – ɛɟɫɤɜɚɧɬɨɪɧɚɹɮɨɪɦɭɥɚ (ɦɚɬɪɢɰɚ), ɹɜɥɹɸɳɚɹɫɹ ɄɇɎ ɜɢɞɚ D1 & D2 &...Dn , ɝɞɟ Di – ɧɟɩɭɫɬɨɣ ɞɢɡɴɸɧɤɬ. & & (\ F )) { (M \ ) (M F )& & &6) | M { M&7) | (M \ ) { (M \ )&I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] d 0 DI I | \ ( x0 , x1 ,..., xn )[ d 0 , d1 , d 2 ,..., d n ] ,2) ɜ ɫɥɭɱɚɟ x0\ ( x0 , x1 ,..., xn ) :I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] d 0 DI I | \ ( x0 , x1 ,..., xn )[d 0 , d1 , d 2 ,..., d n ] .Ɉɩɪɟɞɟɥɟɧɢɟ.
ɗɪɛɪɚɧɨɜɫɤɢɦ ɭɧɢɜɟɪɫɭɦɨɦ (ɇ) ɧɚɡɵɜɚɟɬɫɹ ɦɧɨɠɟɫɬɜɨ ɨɫɧɨɜɧɵɯ ɬɟɪɦɨɜ,ɤɨɬɨɪɨɟ ɫɬɪɨɢɬɫɹ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:ConstM1. H 0 ®¯ {a}ȼɜɟɞɟɦ ɧɨɜɭɸ ɫɜɹɡɤɭ M { \ , ɤɨɬɨɪɚɹ ɷɤɜɢɜɚɥɟɧɬɧɚ ɮɨɪɦɭɥɟ (M o \ ) & (\ o M ) .Ɉɩɪɟɞɟɥɟɧɢɟ. Ɏɨɪɦɭɥɵ M ɢ \ ɧɚɡɵɜɚɸɬɫɹ ɪɚɜɧɨɫɢɥɶɧɵɦɢ, ɟɫɥɢ ɨɛɳɟɡɧɚɱɢɦɚ ɮɨɪɦɭɥɚM {\ .5) | (Mȿɫɥɢ M - ɮɨɪɦɭɥɚ ɜɢɞɚ x0\ ( x0 , x1 ,..., xn ) , x0\ ( x0 , x1 ,..., xn ) , ɬɨ ɟɟ ɜɵɩɨɥɧɢɦɨɫɬɶɷɤɜɢɜɚɥɟɧɬɧɚ1) ɜ ɫɥɭɱɚɟ x0\ ( x0 , x1 ,..., xn ) :78) | xM ( x) { y (M ( x) x2.
Ɇɟɬɨɞ ɪɟɡɨɥɸɰɢɣɌɟɨɪɟɦɚ: ɋɥɟɞɭɸɳɢɟ ɩɚɪɵ ɮɨɪɦɭɥ ɹɜɥɹɸɬɫɹ ɪɚɜɧɨɫɢɥɶɧɵɦɢ:1) | (M o \ ) { (M \ )&&2) | (M \ ) { (\ M )& && &3) | (M (\ F )) { ((M \ ) F ) &4) | (M M ) { M I | \ 1 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]1) ɜ ɫɥɭɱɚɟ \ 1 &\ 2 : I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] ®¯ I | \ 2 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]ª I | \ 1 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]2) ɜ ɫɥɭɱɚɟ \ 1 \ 2 : I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] «¬ I | \ 2 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]ª I |z \ 1 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]3) ɜ ɫɥɭɱɚɟ\ 1 o \ 2 : I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] «¬ I | \ 2 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]4) ɜ ɫɥɭɱɚɟ \ : I | M ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] I |z \ ( x1 , x2 ,..., xn )[ d1 , d 2 ,..., d n ] .5Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ.
