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

110                                         çÌÁ×Á V. ñÚÙËÉ ÐÅÒ×ÏÇÏ ÐÏÒÑÄËÁ

          ÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ × ÆÏÒÍÕÌÁÈ, ËÁË ÅÓÌÉ ÂÙ ÏÎ ×ÈÏÄÉÌ × ÓÉÇÎÁÔÕÒÕ, ÐÏ-
          ÓËÏÌØËÕ ÅÇÏ ×ÓÅÇÄÁ ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁ ×ÙÒÁÖÁÀÝÕÀ ÅÇÏ ÆÏÒÍÕÌÕ.
      •   ðÒÅÄÉËÁÔ x|y (ÞÉÓÌÏ x Ñ×ÌÑÅÔÓÑ ÄÅÌÉÔÅÌÅÍ ÞÉÓÌÁ y), ÏÞÅ×ÉÄÎÏ, ÁÒÉÆ-
          ÍÅÔÉÞÅÎ (ÆÏÒÍÕÌÁ ∃z (xz = y)).
      •   ðÒÅÄÉËÁÔ ¥x ¡ ÐÒÏÓÔÏÅ ÞÉÓÌÏ¥ ÁÒÉÆÍÅÔÉÞÅÎ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÞÉÓÌÏ ÐÒÏ-
          ÓÔÏ, ÅÓÌÉ ÏÎÏ ÏÔÌÉÞÎÏ ÏÔ 1 É ÌÀÂÏÊ ÅÇÏ ÄÅÌÉÔÅÌØ ÒÁ×ÅÎ 1 ÉÌÉ ÓÁÍÏÍÕ
          ÞÉÓÌÕ. üÔÏ ÓÒÁÚÕ ÖÅ ÚÁÐÉÓÙ×ÁÅÔÓÑ × ×ÉÄÅ ÆÏÒÍÕÌÙ.
      •   ïÐÅÒÁÃÉÉ ÞÁÓÔÎÏÇÏ É ÏÓÔÁÔËÁ ÐÒÉ ÄÅÌÅÎÉÉ ÁÒÉÆÍÅÔÉÞÎÙ (× ÔÏÍ ÓÍÙ-
          ÓÌÅ, ÞÔÏ ÔÒ¾ÈÍÅÓÔÎÙÅ ÐÒÅÄÉËÁÔÙ ¥q ÅÓÔØ ÞÁÓÔÎÏÅ ÐÒÉ ÄÅÌÅÎÉÉ a ÎÁ b¥
          É ¥r ÅÓÔØ ÏÓÔÁÔÏË ÐÒÉ ÄÅÌÅÎÉÉ a ÎÁ b¥ ÁÒÉÆÍÅÔÉÞÎÙ. îÁÐÒÉÍÅÒ, ÐÅÒ-
          ×ÙÊ ÉÚ ÎÉÈ ÚÁÐÉÓÙ×ÁÅÔÓÑ ÆÏÒÍÕÌÏÊ ∃r ((a = bq + r) ∧ (r < b)) (ËÁË ÍÙ
          ÕÖÅ ÇÏ×ÏÒÉÌÉ, ÉÓÐÏÌØÚÏ×ÁÎÉÅ ÁÒÉÆÍÅÔÉÞÅÓËÏÇÏ ÐÒÅÄÉËÁÔÁ (r < b) ÎÅ
          ÓÏÚÄÁ¾Ô ÐÒÏÂÌÅÍ).
      •   üÔÏÔ ÓÐÉÓÏË ÍÏÖÎÏ ÐÒÏÄÏÌÖÁÔØ: ÄÌÑ ÍÎÏÇÉÈ ÐÒÅÄÉËÁÔÏ× ÉÈ ÏÐÒÅÄÅ-
          ÌÅÎÉÅ ÐÏ ÓÕÝÅÓÔ×Õ ÕÖÅ Ñ×ÌÑÅÔÓÑ ÎÕÖÎÏÊ ÆÏÒÍÕÌÏÊ. îÁÐÒÉÍÅÒ, Ó×ÏÊ-
          ÓÔ×Á ¥ÂÙÔØ ÎÁÉÂÏÌØÛÉÍ ÏÂÝÉÍ ÄÅÌÉÔÅÌÅÍ¥, ¥ÂÙÔØ ÎÁÉÍÅÎØÛÉÍ ÏÂ-
          ÝÉÍ ËÒÁÔÎÙÍ¥, ¥ÂÙÔØ ×ÚÁÉÍÎÏ ÐÒÏÓÔÙÍÉ¥ ×ÓÅ ÏÔÎÏÓÑÔÓÑ Ë ÜÔÏÊ ËÁÔÅ-
          ÇÏÒÉÉ.
      •   ðÒÅÄÉËÁÔ ¥ÂÙÔØ ÓÔÅÐÅÎØÀ Ä×ÏÊËÉ¥ Ñ×ÌÑÅÔÓÑ ÁÒÉÆÍÅÔÉÞÅÓËÉÍ (ÈÏÔÑ
          ÜÔÏ É ÎÅ ÓÔÏÌØ ÏÞÅ×ÉÄÎÏ, ËÁË × ÐÒÅÄÙÄÕÝÉÈ ÐÒÉÍÅÒÁÈ). ÷ ÓÁÍÏÍ ÄÅ-
          ÌÅ, ÜÔÏ Ó×ÏÊÓÔ×Ï ÍÏÖÎÏ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÔØ ÔÁË: ÌÀÂÏÊ ÄÅÌÉÔÅÌØ ÌÉÂÏ
          ÒÁ×ÅÎ ÅÄÉÎÉÃÅ, ÌÉÂÏ Þ¾ÔÅÎ.
   ðÏÓÌÅÄÎÅÅ ÉÚ ÎÁÛÉÈ ÒÁÓÓÕÖÄÅÎÉÊ ÇÏÄÉÔÓÑ ÄÌÑ ÓÔÅÐÅÎÅÊ ÔÒÏÊËÉ É ×ÏÏÂÝÅ
ÄÌÑ ÓÔÅÐÅÎÅÊ ÌÀÂÏÇÏ ÐÒÏÓÔÏÇÏ ÞÉÓÌÁ. ïÄÎÁËÏ ÕÖÅ ÄÌÑ ÓÔÅÐÅÎÅÊ ÞÅÔ×¾ÒËÉ
ÏÎÏ ÎÅ ÐÒÏÈÏÄÉÔ, É, ÐÏÖÁÌÕÊ, ÍÙ ÐÏÄÏÛÌÉ Ë ÇÒÁÎÉÃÅ, ÇÄÅ ÂÅÚ ÎÅËÏÔÏÒÏÇÏ
ÏÂÝÅÇÏ ÍÅÔÏÄÁ ÎÅ ÏÂÏÊÔÉÓØ.
   ä×Á ÎÁÉÂÏÌÅÅ ÉÚ×ÅÓÔÎÙÈ ÓÐÏÓÏÂÁ ÄÏËÁÚÙ×ÁÔØ ÁÒÉÆÍÅÔÉÞÎÏÓÔØ ÏÓÎÏ×ÁÎÙ
ÎÁ ×ÏÚÍÏÖÎÏÓÔÉ ¥ËÏÄÉÒÏ×ÁÎÉÑ¥ ËÏÎÅÞÎÙÈ ÍÎÏÖÅÓÔ× É ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ.
ïÄÉÎ ×ÏÓÈÏÄÉÔ Ë ç¾ÄÅÌÀ (ÔÁË ÎÁÚÙ×ÁÅÍÁÑ β-ÆÕÎËÃÉÑ ç¾ÄÅÌÑ), ×ÔÏÒÏÊ ÉÚÌÏ-
ÖÅÎ × ËÎÉÇÅ ¥ôÅÏÒÉÑ ÆÏÒÍÁÌØÎÙÈ ÓÉÓÔÅÍ. å¾ ÎÁÐÉÓÁÌ ò. óÍÁÌÌÉÁÎ, ÉÚ×ÅÓÔ-
ÎÙÊ ÔÁËÖÅ ËÁË Á×ÔÏÒ ÐÏÐÕÌÑÒÎÙÈ ÓÂÏÒÎÉËÏ× ¥ÌÏÇÉÞÅÓËÉÈ ÚÁÄÁÞ¥ É ÁÎÅË-
ÄÏÔÏ×. (ïÄÉÎ ÉÚ ÔÁËÉÈ ÓÂÏÒÎÉËÏ× ÉÍÅÅÔ ÐÁÒÁÄÏËÓÁÌØÎÏÅ ÎÁÚ×ÁÎÉÅ ¥ëÁË ÖÅ
ÎÁÚÙ×ÁÅÔÓÑ ÜÔÁ ËÎÉÇÁ?).
   ÷ ÎÅËÏÔÏÒÙÈ ÏÔÎÏÛÅÎÉÑÈ ÍÅÔÏÄ ç¾ÄÅÌÑ ÐÒÅÄÐÏÞÔÉÔÅÌØÎÅÊ, É ÍÙ ÒÁÓÓËÁ-
ÚÙ×ÁÅÍ Ï Î¾Í ÎÉÖÅ, ÎÏ ÓÅÊÞÁÓ ÄÌÑ ÒÁÚÎÏÏÂÒÁÚÉÑ ÒÁÓÓÍÏÔÒÉÍ ÄÒÕÇÏÊ ÓÐÏÓÏÂ.
úÁÆÉËÓÉÒÕÅÍ ×ÚÁÉÍÎÏ ÏÄÎÏÚÎÁÞÎÏÅ ÓÏÏÔ×ÅÔÓÔ×ÉÅ ÍÅÖÄÕ ÎÁÔÕÒÁÌØÎÙÍÉ ÞÉ-
ÓÌÁÍÉ É Ä×ÏÉÞÎÙÍÉ ÓÌÏ×ÁÍÉ:
                        0 1 2 3 4 5 6 7        8 ...
                        ˜ 0 1 00 01 10 11 000 001 . . .