Теормин - шпоры, страница 5
Описание файла
PDF-файл из архива "Теормин - шпоры", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
Ɍɨɝɞɚ ɞɥɹɥɸɛɨɣ ɧɚɱɚɥɶɧɨɣ ɤɨɧɮɢɝɭɪɚɰɢɢ D 0 ai1 ,..., aik ; q1 ; b j1 ,..., b jn ! ɫɭɳɟɫɬɜɭɟɬ ɡɚɤɥɸɱɢɬɟɥɶɧɚɹ*ɤɨɧɮɢɝɭɪɚɰɢɹ E 0 a 'l1 ,..., a 'lm ; q0 ; b 'r1 ,..., b 'rt ! , ɬɚɤɚɹ, ɱɬɨ a o E , ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ,Tɤɨɝɞɚ ɡɚɩɪɨɫ GD 0 : ? R (x( aik , x( aik 1 ,..., ( ai1 , nil )...), q1 , x(b j1 ,..., (b jn , nil )...)) ɢɦɟɟɬ ɭɫɩɟɲɧɨɟ SLDɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ ɫ ɨɬɜɟɬɨɦK^ u x(a ' , x(...(a ' , nil)...) ; v q ; w x(b ' , x(...(b ' , nil)...))` .lml10r1rtɌɟɨɪɟɦɚ (ɑɺɪɱɚ; ɨ ɧɟɪɚɡɪɟɲɢɦɨɫɬɢ ɩɪɨɛɥɟɦɵ ɨɛɳɟɡɧɚɱɢɦɨɫɬɢ ɞɥɹ ɤɥɚɫɫɢɱɟɫɤɨɣɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ): ɇɟ ɫɭɳɟɫɬɜɭɟɬ ɚɥɝɨɪɢɬɦɚ, ɤɨɬɨɪɵɣ ɞɥɹ ɥɸɛɨɣ ɮɨɪɦɭɥɵ M ɩɨɡɜɨɥɹɥɛɵ ɩɪɨɜɟɪɢɬɶ ɟɟ ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ, ɬ.ɟ.
ɧɟ ɫɭɳɟɫɬɜɭɟɬ ɚɥɝɨɪɢɬɦɚ, ɤɨɬɨɪɵɣ ɜɵɞɚɜɚɥ ɛɵ ɧɚɜɵɯɨɞɟ 1, ɟɫɥɢ ɮɨɪɦɭɥɚ M ɨɛɳɟɡɧɚɱɢɦɚ, ɢ 0 ɜ ɩɪɨɬɢɜɧɨɦ ɫɥɭɱɚɟ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɪɚɜɢɥɨɦ ɜɵɛɨɪɚ ɩɨɞɰɟɥɟɣ ɧɚɡɵɜɚɟɬɫɹ ɨɬɨɛɪɚɠɟɧɢɟ R : ? C1 ,..., Cn o Ci (ɬ.ɟ.ɨɬɨɛɪɚɠɟɧɢɟ, ɩɨɤɚɡɵɜɚɸɳɟɟ, ɤɚɤɨɣ ɚɬɨɦ ɞɨɥɠɟɧ ɛɵɬɶ ɜɵɛɪɚɧ ɧɚ ɬɟɤɭɳɟɦ ɷɬɚɩɟɜɵɱɢɫɥɟɧɢɹ).Ɉɩɪɟɞɟɥɟɧɢɟ. SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ ɧɚɡɵɜɚɟɬɫɹ R-ɜɵɱɢɫɥɟɧɢɟɦ, ɟɫɥɢ ɧɚ ɤɚɠɞɨɦɲɚɝɟ ɜɵɱɢɫɥɟɧɢɹ ɨɱɟɪɟɞɧɚɹ ɩɨɞɰɟɥɶ ɜɵɛɢɪɚɟɬɫɹ ɩɨ ɩɪɚɜɢɥɭ R.18ɧɟɣ, ɩɭɫɬɶ ɬɚɤɠɟ ɢɦɟɟɬɫɹ SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ G0 , (G1 ,T1 ),..., ( , T n ) , ɩɪɢɱɟɦ G1 ɢG2 - ɷɬɚɩɵ SLD-ɪɟɡɨɥɸɬɢɜɧɨɝɨ ɜɵɱɢɫɥɟɧɢɹ, ɧɚ ɤɨɬɨɪɵɯ i-ɚɹ ɩɨɞɰɟɥɶ ɛɵɥɚ ɪɚɫɤɪɵɬɚ ɩɨɩɪɚɜɢɥɭ D1 ɢ D2 ɫɨɨɬɜɟɬɫɬɜɟɧɧɨ. Ɍɨɝɞɚ ɫɭɳɟɫɬɜɭɟɬ SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟG0 , (G '1 ,T '1 ), (G '2 , T '2 ),..., ( ,T 'n ) , ɬɚɤɨɟ, ɱɬɨ ɧɚ ɷɬɚɩɟ G '1 ɪɚɫɤɪɵɬɢɟ ɩɪɨɢɫɯɨɞɢɥɨ ɩɨ ɩɪɚɜɢɥɭD2 , ɚ ɧɚ ɷɬɚɩɟ G '2 - ɩɨ ɩɪɚɜɢɥɭ D1 , ɩɪɢ ɷɬɨɦ ɞɥɹ ɜɵɱɢɫɥɟɧɧɵɯ ɨɬɜɟɬɨɜ K ɢ K ' ɫɭɳɟɫɬɜɭɸɬɤɨɧɟɱɧɵɟ ɩɨɞɫɬɚɧɨɜɤɢ U ɢ U ' , ɬɚɤɢɟ, ɱɬɨ K K ' U ' , K ' KU .Ɍɟɨɪɟɦɚ: ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, G – ɡɚɩɪɨɫ ɤ ɧɟɣ, R ɢ R' – ɪɚɡɥɢɱɧɵɟɩɪɚɜɢɥɚ ɜɵɛɨɪɚ.
Ɍɨɝɞɚ ɟɫɥɢ K - R-ɜɵɱɢɫɥɢɦɵɣ ɨɬɜɟɬ ɧɚ G ɤ Ɋ, ɬɨ ɫɭɳɟɫɬɜɭɟɬ ɬɚɤɨɣ R'ɜɵɱɢɫɥɢɦɵɣ ɨɬɜɟɬ K ' , ɬɚɤɨɣ, ɱɬɨ K K ' U ' ɢ K ' KU ɞɥɹ ɧɟɤɨɬɨɪɵɯ ɤɨɧɟɱɧɵɯ ɩɟɪɟɫɬɚɧɨɜɨɤ(ɩɟɪɟɢɦɟɧɨɜɚɧɢɣ) U ɢ U ' .Ɍɟɨɪɟɦɚ (ɫɢɥɶɧɨɣ ɩɨɥɧɨɬɵ): ɉɭɫɬɶ G – ɡɚɩɪɨɫ ɤ ɯɨɪɧɨɜɫɤɨɣ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ, R –ɩɪɚɜɢɥɨ ɜɵɛɨɪɚ, T - ɩɪɚɜɢɥɶɧɵɣ ɨɬɜɟɬ ɧɚ G ɤ Ɋ. Ɍɨɝɞɚ ɫɭɳɟɫɬɜɭɟɬ R-ɜɵɱɢɫɥɢɦɵɣ ɨɬɜɟɬ K ,ɬɚɤɨɣ, ɱɬɨ T KU , ɝɞɟ U - ɤɨɧɟɱɧɚɹ ɩɨɞɫɬɚɧɨɜɤɚ (ɩɟɪɟɢɦɟɧɨɜɚɧɢɟ).Ɉɩɪɟɞɟɥɟɧɢɟ.
ɉɭɫɬɶ G – ɡɚɩɪɨɫ ɤ ɯɨɪɧɨɜɫɤɨɣ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ, ɜ ɤɨɬɨɪɨɣ ɜɫɟɩɪɨɝɪɚɦɦɧɵɟ ɭɬɜɟɪɠɞɟɧɢɹ ɭɩɨɪɹɞɨɱɟɧɵ. Ɍɨɝɞɚ ɞɟɪɟɜɨɦ SLD-ɪɟɡɨɥɸɬɢɜɧɵɯ ɜɵɱɢɫɥɟɧɢɣɡɚɩɪɨɫɚ G ɤ Ɋ ɧɚɡɵɜɚɟɬɫɹ ɤɨɪɧɟɜɨɟ ɭɩɨɪɹɞɨɱɟɧɧɨɟ (ɬ.ɟ. ɜɵɯɨɞɹɳɢɟ ɢɡ ɥɸɛɨɝɨ ɭɡɥɚ ɞɭɝɢɩɪɨɧɭɦɟɪɨɜɚɧɵ) ɞɟɪɟɜɨ, ɨɛɥɚɞɚɸɳɟɟ ɫɥɟɞɭɸɳɢɦɢ ɫɜɨɣɫɬɜɚɦɢ:1) ɤɚɠɞɨɣ ɜɟɪɲɢɧɟ ɩɪɢɩɢɫɚɧ ɡɚɩɪɨɫ;2) ɤɨɪɧɸ ɞɟɪɟɜɚ ɩɪɢɩɢɫɚɧ ɡɚɩɪɨɫ G;3) ɢɡ ɤɚɠɞɨɣ ɜɟɪɲɢɧɵ, ɩɨɦɟɱɟɧɧɨɣ ɡɚɩɪɨɫɨɦ G0 , ɢɫɯɨɞɹɬ ɞɭɝɢ, ɩɨɦɟɱɟɧɧɵɟɧɚɬɭɪɚɥɶɧɵɦɢ ɱɢɫɥɚɦɢ 1 d i1 d ...
d ik d N , ɝɞɟ N – ɤɨɥɢɱɟɫɬɜɨ ɩɪɨɝɪɚɦɦɧɵɯɭɬɜɟɪɠɞɟɧɢɣ ɜ Ɋ, ɢ ɢɞɭɳɢɟ ɜ ɜɟɪɲɢɧɵ, ɩɨɦɟɱɟɧɧɵɟ G1 , G2 ,..., Gk ɜ ɬɨɦ ɢ ɬɨɥɶɤɨ ɜ ɬɨɦɫɥɭɱɚɟ, ɤɨɝɞɚ l [1, k ] ɡɚɩɪɨɫ Gl ɩɨɥɭɱɟɧ ɢɡ ɡɚɩɪɨɫɚ G ɩɭɬɟɦ ɩɪɢɦɟɧɟɧɢɹɩɪɨɝɪɚɦɦɧɨɝɨ ɭɬɜɟɪɠɞɟɧɢɹ Drl ɢ ɩɪɢ ɷɬɨɦ ɞɪɭɝɢɯ SLD-ɪɟɡɨɥɶɜɟɧɬ, ɢɧɰɢɞɟɧɬɧɵɯ G0 ,ɧɟɬ.Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɤɚɠɞɚɹ ɜɟɬɜɶ ɬɚɤɨɝɨ ɞɟɪɟɜɚ ɛɭɞɟɬ ɫɨɨɬɜɟɬɫɬɜɨɜɚɬɶ ɜɵɱɢɫɥɟɧɢɸ ɨɬɜɟɬɚ ɧɚɡɚɩɪɨɫ G ɤ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɋɬɪɚɬɟɝɢɟɣ ɜɵɱɢɫɥɟɧɢɹ ɧɚɡɵɜɚɟɬɫɹ ɫɬɪɚɬɟɝɢɹ ɨɛɯɨɞɚ ɞɟɪɟɜɚ SLDɪɟɡɨɥɸɬɢɜɧɵɯ ɜɵɱɢɫɥɟɧɢɣ:x ɫɬɪɚɬɟɝɢɹ ɨɛɯɨɞɚ ɜ ɲɢɪɢɧɭ: ɩɨɹɪɭɫɧɨɟ ɩɨɫɬɪɨɟɧɢɟ ɞɟɪɟɜɚ. Ʉɚɤ ɬɨɥɶɤɨ ɜ ɨɞɧɨɣɢɡ ɜɟɬɜɟɣ ɨɛɧɚɪɭɠɢɜɚɟɬɫɹ , ɬɨ ɨɬɜɟɬ ɜɵɱɢɫɥɹɟɬɫɹ ɩɭɬɟɦ «ɫɛɨɪɚ» ɜɫɟɯɩɨɞɫɬɚɧɨɜɨɤ ɧɚ ɞɚɧɧɨɣ ɜɟɬɜɢ;x ɫɬɪɚɬɟɝɢɹ ɨɛɯɨɞɚ ɜ ɝɥɭɛɢɧɭ ɫ ɜɨɡɜɪɚɬɨɦ – ɩɨɫɬɪɨɟɧɢɟ ɞɟɪɟɜɚ ɩɨ ɜɟɬɜɹɦ (ɧɚɤɚɠɞɨɦ ɷɬɚɩɟ ɜɵɛɢɪɚɟɬɫɹ ɫɚɦɚɹ ɥɟɜɚɹ ɢɡ ɧɟɩɪɨɣɞɟɧɧɵɯ ɜɟɬɜɟɣ)Ɉɩɪɟɞɟɥɟɧɢɟ.
ɋɬɪɚɬɟɝɢɹ ɜɵɱɢɫɥɟɧɢɹ (ɨɛɯɨɞɚ ɞɟɪɟɜɚ SLD-ɪɟɡɨɥɸɬɢɜɧɵɯ ɜɵɱɢɫɥɟɧɢɣ)ɧɚɡɵɜɚɟɬɫɹ ɩɨɥɧɨɣ, ɟɫɥɢ ɞɥɹ ɥɸɛɨɝɨ ɡɚɩɪɨɫɚ G ɤ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ ɜɫɟ ɜɵɱɢɫɥɟɧɧɵɟɨɬɜɟɬɵ ɛɭɞɭɬ ɩɨɫɬɪɨɟɧɵ.19Ɉɩɪɟɞɟɥɟɧɢɟ. Ɉɩɟɪɚɬɨɪ ɨɬɪɢɰɚɧɢɹ (not) – ɷɬɨ ɨɩɟɪɚɬɨɪ ɥɨɝɢɱɟɫɤɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɫɨɫɥɟɞɭɸɳɟɣ ɨɩɟɪɚɰɢɨɧɧɨɣ ɫɟɦɚɧɬɢɤɨɣ:ɉɭɫɬɶ Ɋ – ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, ɚ G – ɡɚɩɪɨɫ ɜɢɞɚ not(A). Ɍɨɝɞɚ ɪɟɚɤɰɢɹ ɢɧɬɟɪɩɪɟɬɚɬɨɪɚ ɧɚɞɚɧɧɵɣ ɡɚɩɪɨɫ ɛɭɞɟɬ ɫɥɟɞɭɸɳɟɣ:1) ɟɫɥɢ ɫɭɳɟɫɬɜɭɟɬ ɭɫɩɟɲɧɨɟ SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ ɧɚ ɡɚɩɪɨɫ G ' : ? A , ɬɨɪɟɡɭɥɶɬɚɬɨɦ ɜɵɱɢɫɥɟɧɢɹ ɛɭɞɟɬ fail;2) ɟɫɥɢ SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɞɟɪɟɜɨ ɜɵɱɢɫɥɟɧɢɣ ɞɥɹ ɡɚɩɪɨɫɚ G ' : ? A ɩɪɟɞɫɬɚɜɥɹɟɬ ɫɨɛɨɣɤɨɧɟɱɧɨɟ ɱɢɫɥɨ ɧɟɭɞɚɱɧɵɯ ɜɟɬɜɟɣ, ɬɨ ɡɚɩɪɨɫ G ɢɦɟɟɬ ɭɫɩɟɲɧɨɟ ɜɵɱɢɫɥɟɧɢɟ;3) ɟɫɥɢ ɢɧɬɟɪɩɪɟɬɚɬɨɪɭ ɧɟ ɭɞɚɥɨɫɶ ɨɛɨɣɬɢ ɜɫɟ ɜɟɬɜɢ ɞɟɪɟɜɚ ɡɚ ɤɨɧɟɱɧɨɟ ɱɢɫɥɨ ɲɚɝɨɜ (ɬ.ɟ.ɟɫɥɢ ɜ SLD-ɪɟɡɨɥɸɬɢɜɧɨɦ ɞɟɪɟɜɟ ɜɵɱɢɫɥɟɧɢɣ ɞɥɹ ɡɚɩɪɨɫɚ G ' : ? A ɩɪɢɫɭɬɫɬɜɭɟɬ ɯɨɬɹɛɵ ɨɞɧɚ ɛɟɫɤɨɧɟɱɧɚɹ ɜɟɬɜɶ, ɚ ɨɫɬɚɥɶɧɵɟ ɧɟɭɞɚɱɧɵ), ɬɨ ɨɬɜɟɬɨɦ ɧɚ ɡɚɩɪɨɫ G ɛɭɞɟɬ f .Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɨɩɟɪɚɬɨɪ not ɪɚɛɨɬɚɟɬ ɧɚ ɨɫɧɨɜɟ «ɩɨɱɬɢ ɬɪɟɯɡɧɚɱɧɨɣ» ɥɨɝɢɤɢ, ɱɬɨ ɞɚɟɬɷɮɮɟɤɬ ɧɟɦɨɧɨɬɨɧɧɨɫɬɢ ɜɵɜɨɞɚ.4.
Ɉɛɡɨɪ ɪɚɡɞɟɥɨɜ ɦɚɬɟɦɚɬɢɱɟɫɤɨɣ ɥɨɝɢɤɢ4.1. ɂɫɱɢɫɥɟɧɢɟ ɩɪɟɞɢɤɚɬɨɜ ɢ ɷɥɟɦɟɧɬɚɪɧɚɹ ɬɟɨɪɢɹɂɫɱɢɫɥɟɧɢɟ ɩɪɟɞɢɤɚɬɨɜ ɫɨɫɬɨɢɬ ɢɡ ɫɢɫɬɟɦɵ ɚɤɫɢɨɦ ɢ ɩɪɚɜɢɥ ɜɵɜɨɞɚ. ɋɭɳɟɫɬɜɭɟɬ ɦɧɨɝɨɪɚɡɧɵɯ ɫɢɫɬɟɦ ɚɤɫɢɨɦ.ɋɢɫɬɟɦɚ ɚɤɫɢɨɦ:Ax1: M o \ o M Ax 2 : M o \ o F o M o \ o M o F - ɡɚɤɨɧ ɫɥɨɠɧɨɝɨ ɫɢɥɥɨɝɢɡɦɚ20Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ.
(ɫ) 2006 GrGr (grgr@later.ru)Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru)Ax3 : M &\ o MAx 4 : M &\ o \4.2. ɂɧɬɭɢɰɢɨɧɢɫɬɫɤɚɹ ɥɨɝɢɤɚ- ɫɜɨɣɫɬɜɚ ɤɨɧɴɸɧɤɰɢɢAx5 : M o \ o M &\ - ɫɜɨɣɫɬɜɚ ɞɢɡɴɸɧɤɰɢɢAx8 : M o F o \ o F o M \ o F Ax9 : M o M o \ Ax10 : M o \ o M o \ o M - ɡɚɤɨɧɵ ɩɪɨɬɢɜɨɪɟɱɢɹAx11: M M - ɡɚɤɨɧ ɢɫɤɥɸɱɟɧɧɨɝɨ ɬɪɟɬɶɟɝɨ^ t ` , ɝɞɟ ɯ ɫɜɨɛɨɞɧɚ ɞɥɹ t ɜ M .Ax13 : M ( x) ^ x ` o xM ( x)tAx12 : xM ( x) xɉɪɚɜɢɥɚ ɜɵɜɨɞɚ:M M o\1.- ɩɪɚɜɢɥɨ ɨɬɞɟɥɟɧɢɹ (modus ponens); ɫɥɟɞɫɬɜɢɟ ɢɦɩɥɢɤɚɰɢɢ ɨɬɞɟɥɹɟɬɫɹ ɨɬ\MI , S |I int , S | p & q ® int¯ I int , S |ª I int , S |I int , S | p q «¬ I int , S |pqpqI int , S | p S ' S : R ( S , S ') I int , S ' |z p- ɩɪɚɜɢɥɨ ɨɛɨɛɳɟɧɢɹ.- ɥɢɛɨ Mi ɩɨɥɭɱɚɟɬɫɹ ɢɡ ɩɪɟɞɲɟɫɬɜɭɸɳɢɯ ɮɨɪɦɭɥ ɩɨ ɩɪɚɜɢɥɭ ɨɬɞɟɥɟɧɢɹ ɢɥɢ ɨɛɨɛɳɟɧɢɹ.Ʌɨɝɢɱɟɫɤɢɣ ɜɵɜɨɞ – ɮɨɪɦɚɥɢɡɚɰɢɹ ɩɨɧɹɬɢɹ ɦɚɬɟɦɚɬɢɱɟɫɤɨɝɨ ɞɨɤɚɡɚɬɟɥɶɫɬɜɚ.ɉɨɫɥɟɞɧɹɹ ɮɨɪɦɭɥɚ M n ɢɡ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɫɬɢ ɥɨɝɢɱɟɫɤɨɝɨ ɜɵɜɨɞɚ ɧɚɡɵɜɚɟɬɫɹ ɜɵɜɨɞɢɦɨɣ ɢɡȽ ɢ ɨɛɨɡɧɚɱɚɟɬɫɹ ɤɚɤ * | M n .
ȿɫɥɢ Ƚ – ɩɭɫɬɨɟ ɦɧɨɠɟɫɬɜɨ, ɬɨ M n ɧɚɡɵɜɚɟɬɫɹ ɬɟɨɪɟɦɨɣɂɉɋɥɟɞɫɬɜɢɟ ɢɡ ɩɟɪɜɨɣ ɬɟɨɪɟɦɵ Ƚɺɞɟɥɹ: Ɇɚɬɟɦɚɬɢɤɚ – ɧɟɚɤɫɢɨɦɚɬɢɡɢɪɭɟɦɚɹ ɧɚɭɤɚ.Ɉɩɪɟɞɟɥɟɧɢɟ. Ɍɪɨɣɤɨɣ ɏɨɚɪɚ ɧɚɡɵɜɚɟɬɫɹ ɮɨɪɦɭɥɚ ɜɢɞɚ {M } 3 ! {\ } , ɝɞɟ M ,\ - ɮɨɪɦɭɥɵ, ɚɉ – ɩɪɨɝɪɚɦɦɚ, ɩɪɢɱɟɦ ɟɫɥɢ ɧɚ ɜɯɨɞɟ ɩɪɨɝɪɚɦɦɵ ɉ ɜɵɩɨɥɧɹɟɬɫɹ ɭɬɜɟɪɠɞɟɧɢɟ M , ɬɨ ɧɚ ɟɟɜɵɯɨɞɟ ɜɵɩɨɥɧɹɟɬɫɹ ɨɬɧɨɲɟɧɢɟ \ . Ɏɨɪɦɭɥɚ M ɧɚɡɵɜɚɟɬɫɹ ɩɪɟɞɭɫɥɨɜɢɟɦ, ɮɨɪɦɭɥɚ \ ɩɨɫɬɭɫɥɨɜɢɟɦ.Ɉɩɪɟɞɟɥɟɧɢɟ.
ɉɪɨɝɪɚɦɦɚ ɉ ɧɚɡɵɜɚɟɬɫɹ ɱɚɫɬɢɱɧɨ ɤɨɪɪɟɤɬɧɨɣ ɨɬɧɨɫɢɬɟɥɶɧɨ ɩɪɟɞɭɫɥɨɜɢɹ Mɢ ɩɨɫɬɭɫɥɨɜɢɹ \ , ɟɫɥɢ ɨɛɳɟɡɧɚɱɢɦɚ ɮɨɪɦɭɥɚ {M } 3 ! {\ } . ɗɬɭ ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ ɫɥɟɞɭɟɬɩɨɧɢɦɚɬɶ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ: ɞɥɹ ɥɸɛɨɣ ɞɨɩɭɫɬɢɦɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɢ I ɢ ɥɸɛɨɝɨ ɧɚɛɨɪɚɡɧɚɱɟɧɢɣ ɫɜɨɛɨɞɧɵɯ ɩɟɪɟɦɟɧɧɵɯ {D1 , D 2 ,..., D n } VarM Var\ ɢɡ ɜɵɩɨɥɧɢɦɨɫɬɢ ɮɨɪɦɭɥɵ Mɉ ::=||||Ɉɩɪɟɞɟɥɟɧɢɟ. Ɏɨɪɦɭɥɚ M ɧɚɡɵɜɚɟɬɫɹ ɨɛɳɟɡɧɚɱɢɦɨɣ ɫ ɬɨɱɤɢ ɡɪɟɧɢɹ ɢɧɬɭɢɰɢɨɧɢɫɬɫɤɨɣɥɨɝɢɤɢ (ɢɧɬɭɢɰɢɨɧɢɫɬɫɤɢ ɨɛɳɟɡɧɚɱɢɦɨɣ, ɨɛɨɡɧɚɱɚɟɬɫɹ ɤɚɤ | M ), ɟɫɥɢ ɮɨɪɦɭɥɚ M ɛɭɞɟɬintɜɵɩɨɥɧɢɦɚ ɜ ɥɸɛɨɦ ɫɨɫɬɨɹɧɢɢ S ɥɸɛɨɣ ɢɧɬɟɪɩɪɟɬɚɰɢɢ I int S , R, [ ! .ɍɬɜɟɪɠɞɟɧɢɟ.
ȿɫɥɢ ɮɨɪɦɭɥɚ M ɢɧɬɭɢɰɢɨɧɢɫɬɫɤɢ ɨɛɳɟɡɧɚɱɢɦɚ, ɬɨ ɨɧɚ ɨɛɳɟɡɧɚɱɢɦɚ ɢ ɫɬɨɱɤɢ ɡɪɟɧɢɹ ɤɥɚɫɫɢɱɟɫɤɨɣ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ.ɍɬɜɟɪɠɞɟɧɢɟ. Ɏɨɪɦɭɥɵ p p ɢ p o p ɢɧɬɭɢɰɢɨɧɢɫɬɫɤɢ ɧɟɜɵɩɨɥɧɢɦɵ.ɢɫɱɢɫɥɟɧɢɹ ɩɪɟɞɢɤɚɬɨɜ.Ɍɟɨɪɟɦɚ (Ƚɺɞɟɥɹ; ɤɨɪɪɟɤɬɧɨɫɬɢ ɢ ɩɨɥɧɨɬɵ ɞɥɹ ɢɫɱɢɫɥɟɧɢɹ ɩɪɟɞɢɤɚɬɨɜ): Ɏɨɪɦɭɥɚɹɜɥɹɟɬɫɹ ɬɟɨɪɟɦɨɣ ɢɫɱɢɫɥɟɧɢɹ ɩɪɟɞɢɤɚɬɨɜ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɨɧɚ ɨɛɳɟɡɧɚɱɢɦɚ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɪɨɝɪɚɦɦɚ ɧɚɡɵɜɚɟɬɫɹ ɩɪɚɜɢɥɶɧɨɣ, ɟɫɥɢ ɧɚ ɟɟ ɜɵɯɨɞɟ ɜɫɟɝɞɚ ɩɨɹɜɥɹɟɬɫɹɪɟɡɭɥɶɬɚɬ, ɧɚɯɨɞɹɳɢɣɫɹ ɜ ɨɩɪɟɞɟɥɟɧɧɨɦ ɨɬɧɨɲɟɧɢɢ ɫ ɜɯɨɞɧɵɦɢ ɞɚɧɧɵɦɢ (ɬ.ɟ.| xin (M0 ( xin ) o xout ( R3 ( xin , xout ) & M1 ( xin , xout ))) ).Ɉɩɪɟɞɟɥɢɦ ɦɨɞɟɥɶɧɵɣ ɹɡɵɤ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ:ɂɡɦɟɧɹɟɬɫɹ ɢ ɩɨɧɹɬɢɟ ɥɨɝɢɱɟɫɤɨɝɨ ɡɚɤɨɧɚ.Ɉɩɪɟɞɟɥɟɧɢɟ.
Ʌɨɝɢɱɟɫɤɢɦ ɜɵɜɨɞɨɦ ɜ ɢɫɱɢɫɥɟɧɢɢ ɩɪɟɞɢɤɚɬɨɜ ɢɡ ɦɧɨɠɟɫɬɜɚ ɮɨɪɦɭɥ Ƚɧɚɡɵɜɚɟɬɫɹ ɤɨɧɟɱɧɚɹ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɫɬɶ ɮɨɪɦɭɥ M1 , M2 ,..., Mn , ɬɚɤɚɹ, ɱɬɨ ɞɥɹ ɥɸɛɨɝɨ i t 1- ɥɢɛɨ Mi * ;- ɥɢɛɨ Mi - ɨɞɧɚ ɢɡ 15 ɚɤɫɢɨɦ;ɉɭɫɬɶ ɉ – ɩɪɨɝɪɚɦɦɚ, R3 - ɨɬɧɨɲɟɧɢɟ ɦɟɠɞɭ ɟɟ ɜɯɨɞɧɵɦɢ ɢ ɜɵɯɨɞɧɵɦɢ ɞɚɧɧɵɦɢ (ɬ.ɟ. ɟɫɥɢɩɪɢ ɩɨɫɬɭɩɥɟɧɢɢ ɧɚ ɜɯɨɞ ɡɧɚɱɟɧɢɹ ɯ ɩɪɨɝɪɚɦɦɚ ɜɵɞɚɟɬ ɭ, ɬɨ ɜɵɪɚɠɟɧɢɟ R3 ( x, y ) ɹɜɥɹɟɬɫɹɢɫɬɢɧɧɵɦ).( I | M[d1 , d 2 ,..., d n ] ) ɛɭɞɟɬ ɫɥɟɞɨɜɚɬɶ, ɱɬɨ ɩɨɫɥɟ ɡɚɜɟɪɲɟɧɢɹ ɩɪɨɝɪɚɦɦɵ ɉ ɩɟɪɟɦɟɧɧɵɟɩɪɢɦɭɬ ɡɧɚɱɟɧɢɹ d '1 , d '2 ,..., d 'n , ɩɪɢɱɟɦ ɮɨɪɦɭɥɚ \ ɛɭɞɟɬ ɜɵɩɨɥɧɢɦɚ ɧɚ ɞɚɧɧɵɯ ɡɧɚɱɟɧɢɹɯɩɟɪɟɦɟɧɧɵɯ ( I | \ [d1 , d 2 ,..., d n ] ).I int , S | p o q S ' S : R( S , S ') & I int , S ' | p I int , S ' | qɩɨɫɵɥɤɢ.xMɈɩɪɟɞɟɥɟɧɢɟ.
ɂɧɬɭɢɰɢɨɧɢɫɬɫɤɚɹ ɢɧɬɟɪɩɪɟɬɚɰɢɹ – ɷɬɨ ɬɪɨɣɤɚ I int S , R, [ ! , ɝɞɟS – ɧɟɩɭɫɬɨɟ ɦɧɨɠɟɫɬɜɨ ɚɥɶɬɟɪɧɚɬɢɜɧɵɯ ɫɨɫɬɨɹɧɢɣ (ɫɨɫɬɨɹɧɢɣ ɡɧɚɧɢɣ);R S u S - ɨɬɧɨɲɟɧɢɟ ɧɟɫɬɪɨɝɨɝɨ ɱɚɫɬɢɱɧɨɝɨ ɩɨɪɹɞɤɚ, ɭɤɚɡɵɜɚɸɳɟɟ, ɱɬɨ ɧɟɤɨɬɨɪɨɟɫɨɫɬɨɹɧɢɟ ɡɧɚɧɢɣ ɦɨɠɟɬ ɛɵɬɶ ɞɨɫɬɢɝɧɭɬɨ ɢɡ ɞɪɭɝɨɝɨ ɢ ɨɛɥɚɞɚɸɳɟɟ ɫɜɨɣɫɬɜɚɦɢɬɪɚɧɡɢɬɢɜɧɨɫɬɢ, ɚɧɬɢɫɢɦɦɟɬɪɢɱɧɨɫɬɢ ɢ ɪɟɮɥɟɤɫɢɜɧɨɫɬɢ;[ : S u P o ^T , F ` - ɨɰɟɧɤɚ ɢɫɬɢɧɧɨɫɬɢ (ɫɩɨɫɨɛɧɨɫɬɶ ɪɟɲɚɬɶ ɡɚɞɚɱɢ ɜ ɨɩɪɟɞɟɥɟɧɧɨɦɫɨɫɬɨɹɧɢɢ).Ɉɬɧɨɲɟɧɢɟ ɜɵɩɨɥɧɢɦɨɫɬɢ ɞɥɹ ɢɧɬɭɢɰɢɨɧɢɫɬɫɤɨɣ ɥɨɝɢɤɢ ɛɭɞɟɬ ɜɵɝɥɹɞɟɬɶ ɫɥɟɞɭɸɳɢɦɨɛɪɚɡɨɦ:I int , S | p [ ( S , p ) TAx14 : x M o \ o M o x\ ; x VarMAx15 : x \ o M o x\ o M 2.4.3. Ʌɨɝɢɤɚ ɏɨɚɪɚɂɧɬɭɢɰɢɨɧɢɫɬɫɤɚɹ ɥɨɝɢɤɚ (ɥɨɝɢɤɚ Ȼɪɚɭɷɪɚ) – ɷɬɨ ɤɥɚɫɫɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɢɡ ɚɤɫɢɨɦ ɤɨɬɨɪɨɣɢɫɤɥɸɱɟɧ ɡɚɤɨɧ «ɢɫɤɥɸɱɟɧɧɨɝɨ ɬɪɟɬɶɟɝɨ».Ax6 : M o M \Ax7 :\ o M \Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ.
