Математическая логика и теория алгоритмов. Самохин А.В. - 50 стр.

50                                 çÌÁ×Á II. õÐÏÒÑÄÏÞÅÎÎÙÅ ÍÎÏÖÅÓÔ×Á

ÖÅÓÔ× ÓÞ¾ÔÎÏ, ÐÒÏÎÕÍÅÒÕÅÍ ÅÇÏ ÜÌÅÍÅÎÔÙ É ÂÕÄÅÍ ×ÙÂÉÒÁÔØ ÎÅÏÈ×ÁÞÅÎÎÙÊ
ÜÌÅÍÅÎÔ Ó ÎÁÉÍÅÎØÛÉÍ ÎÏÍÅÒÏÍ (ÎÁ ÎÅÞ¾ÔÎÙÈ ÛÁÇÁÈ ¡ ÉÚ X, ÎÁ Þ¾ÔÎÙÈ ¡
ÉÚ Y ). üÔÏ ÓÏÏÂÒÁÖÅÎÉÅ ÚÁ×ÅÒÛÁÅÔ ÄÏËÁÚÁÔÅÌØÓÔ×Ï.
   úÁÄÁÞÁ 96. óËÏÌØËÏ ÓÕÝÅÓÔ×ÕÅÔ ÎÅÉÚÏÍÏÒÆÎÙÈ ÓÞ¾ÔÎÙÈ ÐÌÏÔÎÙÈ ÌÉ-
ÎÅÊÎÏ ÕÐÏÒÑÄÏÞÅÎÎÙÈ ÍÎÏÖÅÓÔ× (ÐÒÏ ÎÁÉÍÅÎØÛÉÊ É ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔÙ
ÎÉÞÅÇÏ ÎÅ ÉÚ×ÅÓÔÎÏ). (ïÔ×ÅÔ: 4.)
   úÁÄÁÞÁ 97. ðÒÉ×ÅÄÉÔÅ ÐÒÉÍÅÒ Ä×ÕÈ ÐÌÏÔÎÙÈ ÌÉÎÅÊÎÏ ÕÐÏÒÑÄÏÞÅÎÎÙÈ
ÍÎÏÖÅÓÔ× ÍÏÝÎÏÓÔÉ ËÏÎÔÉÎÕÕÍ ÂÅÚ ÎÁÉÍÅÎØÛÅÇÏ É ÎÁÉÂÏÌØÛÅÇÏ ÜÌÅÍÅÎ-
ÔÏ×, ÎÅ Ñ×ÌÑÀÝÉÈÓÑ ÉÚÏÍÏÒÆÎÙÍÉ. (õËÁÚÁÎÉÅ: ×ÏÚØÍÉÔÅ ÍÎÏÖÅÓÔ×Á Q+R
É R + Q.)
  ôÅÏÒÅÍÁ 14. ÷ÓÑËÏÅ ÓÞ¾ÔÎÏÅ ÌÉÎÅÊÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÍÎÏÖÅÓÔ×Ï ÉÚÏ-
ÍÏÒÆÎÏ ÎÅËÏÔÏÒÏÍÕ ÐÏÄÍÎÏÖÅÓÔ×Õ ÍÎÏÖÅÓÔ×Á Q.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. úÁÍÅÔÉÍ ÓÒÁÚÕ ÖÅ, ÞÔÏ ×ÍÅÓÔÏ ÍÎÏÖÅÓÔ×Á Q ÍÏÖÎÏ ÂÙ-
ÌÏ ×ÚÑÔØ ÌÀÂÏÅ ÐÌÏÔÎÏÅ ÓÞ¾ÔÎÏÅ ×ÓÀÄÕ ÐÌÏÔÎÏÅ ÍÎÏÖÅÓÔ×Ï ÂÅÚ ÐÅÒ×ÏÇÏ É
ÐÏÓÌÅÄÎÅÇÏ ÜÌÅÍÅÎÔÏ×, ÔÁË ËÁË ÏÎÉ ×ÓÅ ÉÚÏÍÏÒÆÎÙ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï ÜÔÏÇÏ ÕÔ×ÅÒÖÄÅÎÉÑ ÐÒÏÉÓÈÏÄÉÔ ÔÁË ÖÅ, ËÁË É × ÔÅÏÒÅ-
ÍÅ 13 ¡ Ó ÔÏÊ ÒÁÚÎÉÃÅÊ, ÞÔÏ ÎÏ×ÙÅ ÎÅÏÂÒÁÂÏÔÁÎÎÙÅ ÜÌÅÍÅÎÔÙ ÂÅÒÕÔÓÑ ÔÏÌØ-
ËÏ Ó ÏÄÎÏÊ ÓÔÏÒÏÎÙ (ÉÚ ÄÁÎÎÏÇÏ ÎÁÍ ÍÎÏÖÅÓÔ×Á), Á ÐÁÒÙ Ë ÎÉÍ ÐÏÄÂÉÒÁÀÔÓÑ
× ÍÎÏÖÅÓÔ×Å ÒÁÃÉÏÎÁÌØÎÙÈ ÞÉÓÅÌ.


     §3. æÕÎÄÉÒÏ×ÁÎÎÙÅ ÍÎÏÖÅÓÔ×Á
   ðÒÉÎÃÉÐ ÍÁÔÅÍÁÔÉÞÅÓËÏÊ ÉÎÄÕËÃÉÉ × ÏÄÎÏÊ ÉÚ ×ÏÚÍÏÖÎÙÈ ÆÏÒÍ Ú×ÕÞÉÔ
ÔÁË:
   ðÕÓÔØ A(n) ¡ ÎÅËÏÔÏÒÏÅ Ó×ÏÊÓÔ×Ï ÎÁÔÕÒÁÌØÎÏÇÏ ÞÉÓÌÁ n. ðÕÓÔØ ÎÁÍ ÕÄÁ-
ÌÏÓØ ÄÏËÁÚÁÔØ A(n) × ÐÒÅÄÐÏÌÏÖÅÎÉÉ, ÞÔÏ A(m) ×ÅÒÎÏ ÄÌÑ ×ÓÅÈ m, ÍÅÎØ-
ÛÉÈ n. ôÏÇÄÁ Ó×ÏÊÓÔ×Ï A(n) ×ÅÒÎÏ ÄÌÑ ×ÓÅÈ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ n.
   (úÁÍÅÔÉÍ, ÞÔÏ ÐÏ ÕÓÌÏ×ÉÀ ÄÏËÁÚÁÔÅÌØÓÔ×Ï A(0) ×ÏÚÍÏÖÎÏ ÂÅÚ ×ÓÑËÉÈ
ÐÒÅÄÐÏÌÏÖÅÎÉÊ, ÐÏÓËÏÌØËÕ ÍÅÎØÛÉÈ ÞÉÓÅÌ ÎÅÔ.)
   äÌÑ ËÁËÉÈ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÙÈ ÍÎÏÖÅÓÔ× ×ÅÒÅÎ ÁÎÁÌÏÇÉÞÎÙÊ ÐÒÉÎ-
ÃÉÐ? ïÔ×ÅÔ ÄÁ¾ÔÓÑ ÓÌÅÄÕÀÝÅÊ ÐÒÏÓÔÏÊ ÔÅÏÒÅÍÏÊ:
  ôÅÏÒÅÍÁ 15. óÌÅÄÕÀÝÉÅ ÔÒÉ Ó×ÏÊÓÔ×Á ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏ-
ÖÅÓÔ×Á X ÒÁ×ÎÏÓÉÌØÎÙ:
  (Á) ÌÀÂÏÅ ÎÅÐÕÓÔÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï X ÉÍÅÅÔ ÍÉÎÉÍÁÌØÎÙÊ ÜÌÅÍÅÎÔ;
  (Â) ÎÅ ÓÕÝÅÓÔ×ÕÅÔ ÂÅÓËÏÎÅÞÎÏÊ ÓÔÒÏÇÏ ÕÂÙ×ÁÀÝÅÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ-
ÓÔÉ x0 > x1 > x2 > . . . ÜÌÅÍÅÎÔÏ× ÍÎÏÖÅÓÔ×Á X;