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

Подождите немного. Документ загружается.

§5. ï ÎÅÐÏÓÔÉÖÉÍÏÊ ÜÆÆÅËÔÉ×ÎÏÓÔÉ ÍÁÔÅÍÁÔÉËÉ 191

ÓÔÁ×ÉÍ × ÓÏÏÔ×ÅÔÓÔ×ÉÅ ÎÅËÏÔÏÒÙÅ ÞÉÓÌÁ - ÉÈ Ç¾ÄÅÌÅ×ÓËÉÅ ÎÏÍÅÒÁ), ÔÏ É ×

ÒÁÓÛÉÒÅÎÎÏÊ ÓÉÓÔÅÍÅ ÍÏÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÎÅÒÁÚÒÅÛÉÍÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ.

éÎÁÞÅ ÇÏ×ÏÒÑ, ÉÚÂÅÖÁÔØ ÎÅÒÁÚÒÅÛÉÍÙÈ ÕÔ×ÅÒÖÄÅÎÉÊ É ÄÏËÁÚÁÔØ ÎÅÐÒÏÔÉ-

×ÏÒÅÞÉ×ÏÓÔØ ÍÏÖÎÏ ÌÉÛØ Ó ÐÏÍÏÝØÀ ÌÏÇÉÞÅÓËÉÈ ÐÒÉÎÃÉÐÏ×, ÎÅ ÏÔÏÂÒÁÖÁ-

ÅÍÙÈ × ÁÒÉÆÍÅÔÉËÕ. þÔÏÂÙ ÐÏÑÓÎÉÔØ ÓÕÔØ ÄÅÌÁ, ×ÏÓÐÏÌØÚÕÅÍÓÑ ÁÎÁÌÏÇÉÅÊ

(ÈÏÔÑ É ÎÅÓËÏÌØËÏ ÎÅÔÏÞÎÏÊ): ÅÓÌÉ ÂÙ ÌÏÇÉÞÅÓËÉÅ ÐÒÉÎÃÉÐÙ É ÍÁÔÅÍÁÔÉÞÅ-

ÓËÉÅ ÁËÓÉÏÍÙ ÂÙÌÉ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÙ ÎÁ ÑÐÏÎÓËÏÍ ÑÚÙËÅ, Á ÁÒÉÆÍÅÔÉÚÁÃÉÑ

ç¾ÄÅÌÑ ÏÚÎÁÞÁÌÁ ÂÙ ÐÅÒÅ×ÏÄ ÎÁ ÁÎÇÌÉÊÓËÉÊ ÑÚÙË, ÔÏ ÒÅÚÕÌØÔÁÔÙ ç¾ÄÅÌÑ ÐÏ-

ÌÕÞÁÌÉÓØ ÂÙ ÄÏ ÔÅÈ ÐÏÒ, ÐÏËÁ ÂÙÌ ÂÙ ÏÓÕÝÅÓÔ×ÉÍ ÐÅÒÅ×ÏÄ Ó ÑÐÏÎÓËÏÇÏ ÎÁ

ÁÎÇÌÉÊÓËÉÊ.

ôÁËÉÍ ÏÂÒÁÚÏÍ, ÔÅÏÒÅÍÁ ç¾ÄÅÌÑ Ï ÎÅÐÏÌÎÏÔÅ ÕÔ×ÅÒÖÄÁÅÔ, ÞÔÏ ÎÉ ÏÄÎÁ

ÓÉÓÔÅÍÁ ÍÁÔÅÍÁÔÉÞÅÓËÉÈ É ÌÏÇÉÞÅÓËÉÈ ÁËÓÉÏÍ, ÁÒÉÆÍÅÔÉÚÕÅÍÁÑ ÔÅÍ ÉÌÉ

ÉÎÙÍ ÓÐÏÓÏÂÏÍ (ÎÁÐÒÉÍÅÒ, ÔÁË, ËÁË ÜÔÏ ÓÄÅÌÁÌ ç¾ÄÅÌØ), ÎÅ ÐÏÚ×ÏÌÑÅÔ ÏÈ×Á-

ÔÉÔØ ÄÁÖÅ ×ÓÅ ÓÏÄÅÒÖÁÝÉÅÓÑ × ÎÅÊ ÉÓÔÉÎÙ, ÎÅ ÇÏ×ÏÒÑ ÕÖÅ Ï ×ÓÅÊ ÍÁÔÅÍÁ-

ÔÉËÅ, ÐÏÓËÏÌØËÕ ÌÀÂÁÑ ÓÉÓÔÅÍÁ ÁËÓÉÏÍ ÎÅÐÏÌÎÁ. ÷ ÌÀÂÏÊ ÁËÓÉÏÍÁÔÉÞÅÓËÏÊ

ÓÉÓÔÅÍÅ ÓÕÝÅÓÔ×ÕÀÔ ÕÔ×ÅÒÖÄÅÎÉÑ, ÎÅÄÏËÁÚÕÅÍÙÅ × ÒÁÍËÁÈ ÄÁÎÎÏÊ ÓÉÓÔÅÍÙ.

éÓÔÉÎÎÏÓÔØ ÔÁËÉÈ ÕÔ×ÅÒÖÄÅÎÉÊ ÍÏÖÅÔ ÂÙÔØ ÕÓÔÁÎÏ×ÌÅÎÁ ÌÉÛØ Ó ÐÏÍÏÝØÀ

ÎÅÆÏÒÍÁÌØÎÙÈ ÒÁÓÓÕÖÄÅÎÉÊ.

ôÅÏÒÅÍÁ ç¾ÄÅÌÑ Ï ÎÅÐÏÌÎÏÔÅ, ÐÏËÁÚÁ×ÛÁÑ, ÞÔÏ ÁËÓÉÏÍÁÔÉÚÁÃÉÑ ÉÍÅÅÔ Ó×ÏÉ

ÐÒÅÄÅÌÙ, ÒÁÚÉÔÅÌØÎÏ ÏÔÌÉÞÁÌÁÓØ ÏÔ ÇÏÓÐÏÄÓÔ×Ï×Á×ÛÉÈ × ËÏÎÃÅ XIX ×. ÐÒÅÄ-

ÓÔÁ×ÌÅÎÉÊ Ï ÍÁÔÅÍÁÔÉËÅ ËÁË Ï ÓÏ×ÏËÕÐÎÏÓÔÉ ÁËÓÉÏÍÁÔÉÚÉÒÕÅÍÙÈ (É ÁËÓÉ-

ÏÍÁÔÉÚÉÒÏ×ÁÎÎÙÈ) ÔÅÏÒÉÊ. ôÅÏÒÅÍÁ ç¾ÄÅÌÑ ÎÁÎÅÓÌÁ ÓÏËÒÕÛÉÔÅÌØÎÙÊ ÕÄÁÒ

ÐÏ ×ÓÅÏÂßÅÍÌÀÝÅÊ ÁËÓÉÏÍÁÔÉÚÁÃÉÉ. îÅÁÄÅË×ÁÔÎÏÓÔØ ÁËÓÉÏÍÁÔÉÞÅÓËÏÇÏ ÐÏÄ-

ÈÏÄÁ ÓÁÍÁ ÐÏ ÓÅÂÅ ÐÒÏÔÉ×ÏÒÅÞÉÅÍ ÎÅ ÂÙÌÁ; ÏÄÎÁËÏ ÏÎÁ Ñ×ÉÌÁÓØ ÐÏÌÎÏÊ ÎÅ-

ÏÖÉÄÁÎÎÏÓÔØÀ, ÐÏÓËÏÌØËÕ ÍÁÔÅÍÁÔÉËÉ, ÏÓÏÂÅÎÎÏ ÆÏÒÍÁÌÉÓÔÙ, ÐÒÅÄÐÏÌÁÇÁ-

ÌÉ, ÞÔÏ × ÒÁÍËÁÈ ÎÅËÏÔÏÒÏÊ ÁËÓÉÏÍÁÔÉÞÅÓËÏÊ ÓÉÓÔÅÍÙ ÌÀÂÏÅ ÉÓÔÉÎÎÏÅ ×

ÎÅÊ ÕÔ×ÅÒÖÄÅÎÉÅ ÚÁ×ÅÄÏÍÏ ÄÏËÁÚÕÅÍÏ. âÒÁÕÚÒ ÕÓÔÁÎÏ×ÉÌ, ÞÔÏ ÉÎÔÕÉÔÉ×ÎÏ

×ÏÓÐÒÉÎÉÍÁÅÍÙÅ ÉÓÔÉÎÙ ÞÁÓÔÏ ÌÅÖÁÔ ÄÁÌÅËÏ ÚÁ ÐÒÅÄÅÌÁÍÉ ÔÏÇÏ, ÞÔÏ ÂÙ-

ÌÏ ÄÏËÁÚÁÎÏ × ËÌÁÓÓÉÞÅÓËÏÊ ÍÁÔÅÍÁÔÉËÅ, Á ç¾ÄÅÌØ ÄÏËÁÚÁÌ, ÞÔÏ ÉÎÔÕÉÔÉ×ÎÏ

×ÏÓÐÒÉÎÉÍÁÅÍÙÅ ÉÓÔÉÎÙ ×ÏÏÂÝÅ ×ÙÈÏÄÑÔ ÚÁ ÒÁÍËÉ ÍÁÔÅÍÁÔÉÞÅÓËÏÇÏ ÄÏËÁ-

ÚÁÔÅÌØÓÔ×Á. ðÏ ×ÙÒÁÖÅÎÉÀ ðÁÕÌÑ âÅÒÎÁÊÓÁ, ÎÙÎÅ ÂÏÌÅÅ ÒÁÚÕÍÎÏ ÎÅ ÓÔÏÌØËÏ

ÒÅËÏÍÅÎÄÏ×ÁÔØ ÁËÓÉÏÍÁÔÉËÕ, ÓËÏÌØËÏ ÐÒÅÄÏÓÔÅÒÅÇÁÔØ ÐÒÏÔÉ× ÅÅ ÐÅÒÅÏÃÅÎËÉ,

ÒÁÚÕÍÅÅÔÓÑ, ÓËÁÚÁÎÎÏÅ ×ÙÛÅ ÎÅ ÉÓËÌÀÞÁÅÔ ×ÏÚÍÏÖÎÏÓÔÉ ÐÏÑ×ÌÅÎÉÑ ÎÏ×ÙÈ

ÍÅÔÏÄÏ× ÄÏËÁÚÁÔÅÌØÓÔ×Á, ËÏÔÏÒÙÅ ×ÙÈÏÄÑÔ ÚÁ ÐÒÅÄÅÌÙ ÄÏÐÕÓÔÉÍÏÇÏ ÌÏÇÉÞÅ-

ÓËÉÍÉ ÐÒÉÎÃÉÐÁÍÉ, ÐÒÉÎÑÔÙÍÉ ÒÁÚÌÉÞÎÙÍÉ ÛËÏÌÁÍÉ × ÏÓÎÏ×ÁÎÉÑÈ ÍÁÔÅ-

ÍÁÔÉËÉ.

ïÂÁ ÐÏÌÕÞÅÎÎÙÈ ç¾ÄÅÌÅÍ ÒÅÚÕÌØÔÁÔÁ ÐÏÔÒÑÓÌÉ ÍÁÔÅÍÁÔÉËÕ. üÔÏ ÏÚÎÁ-

ÞÁÌÏ, ÞÔÏ ÍÁÔÅÍÁÔÉËÁ ×ÙÎÕÖÄÅÎÁ ÂÅÓÐÏ×ÏÒÏÔÎÏ ÏÔËÁÚÁÔØÓÑ ÏÔ ÐÒÅÔÅÎÚÉÊ

ÎÁ ÁÂÓÏÌÀÔÎÕÀ ÄÏÓÔÏ×ÅÒÎÏÓÔØ ÉÌÉ ÚÎÁÞÉÍÏÓÔØ Ó×ÏÉÈ ÒÅÚÕÌØÔÁÔÏ×, Ô. Å. ÌÉ-

ÛÉÔØÓÑ ÏÄÎÏÊ ÉÚ ÏÓÎÏ×ÎÙÈ Ó×ÏÉÈ ÏÓÏÂÅÎÎÏÓÔÅÊ, ÎÁ ËÏÔÏÒÕÀ ÐÒÅÔÅÎÄÏ×ÁÌÁ

192 çÌÁ×Á XII. áÒÉÆÍÅÔÉÞÎÏÓÔØ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ

ÅÝÅ ÓÒÁ×ÎÉÔÅÌØÎÏ ÎÅÄÁ×ÎÏ.

ðÏÌÏÖÅÎÉÅ ÏÓÌÏÖÎÑÌÏÓØ ÎÅ×ÏÚÍÏÖÎÏÓÔØÀ ÄÏËÁÚÁÔØ ÎÅÐÒÏÔÉ×ÏÒÅÞÉ×ÏÓÔØ:

×ÅÄØ ×ÓÅ, Ï ÞÅÍ ÇÏ×ÏÒÉÌÉ ÍÁÔÅÍÁÔÉËÉ, ÍÏÇÌÏ ÏËÁÚÁÔØÓÑ ÂÅÓÓÍÙÓÌÉÃÅÊ, ÉÂÏ

ÔÅÐÅÒØ ÎÉËÔÏ ÎÅ ÍÏÇ ÇÁÒÁÎÔÉÒÏ×ÁÔØ, ÞÔÏ × ÂÕÄÕÝÅÍ ÎÅ ×ÏÚÎÉËÎÅÔ ÐÒÏÔÉ×Ï-

ÒÅÞÉÑ. óÌÕÞÉÓØ ÔÁËÏÅ É ÏËÁÖÉÓØ ÐÒÏÔÉ×ÏÒÅÞÉÅ ÎÅÒÁÚÒÅÛÉÍÙÍ - ×ÓÑ ÍÁÔÅÍÁ-

ÔÉËÁ ÏÂÒÁÔÉÌÁÓØ ÂÙ × ÐÒÁÈ. äÅÊÓÔ×ÉÔÅÌØÎÏ, ÏÄÎÏ ÉÚ Ä×ÕÈ ÐÒÏÔÉ×ÏÒÅÞÉ×ÙÈ

ÕÔ×ÅÒÖÄÅÎÉÊ ÄÏÌÖÎÏ ÂÙÔØ ÌÏÖÎÙÍ, Á ÓÏÇÌÁÓÎÏ ÐÒÉÎÑÔÏÊ ×ÓÅÍÉ ÍÁÔÅÍÁÔÉ-

ÞÅÓËÉÍÉ ÌÏÇÉËÁÍÉ ËÏÎÃÅÐÃÉÉ ÉÍÐÌÉËÁÃÉÉ, ÉÚ ÌÏÖÎÏÇÏ ÕÔ×ÅÒÖÄÅÎÉÑ ÍÏÖÅÔ

ÓÌÅÄÏ×ÁÔØ ÞÔÏ ÕÇÏÄÎÏ. éÔÁË, ÍÁÔÅÍÁÔÉËÉ ÒÁÂÏÔÁÌÉ ÐÏÄ ÕÇÒÏÚÏÊ ÐÏÌÎÏÇÏ ÐÒÏ-

×ÁÌÁ. åÝÅ ÏÄÉÎ ÕÄÁÒ ÎÁÎÅÓÌÁ ÔÅÏÒÅÍÁ Ï ÎÅÐÏÌÎÏÔÅ.

ôÅÏÒÅÍÕ ç¾ÄÅÌÑ Ï ÎÅÐÏÌÎÏÔÅ ÄÏ ÎÅËÏÔÏÒÏÊ ÓÔÅÐÅÎÉ ÍÏÖÎÏ ÒÁÓÓÍÁÔÒÉ-

×ÁÔØ ËÁË ÏÔÒÉÃÁÎÉÅ ÚÁËÏÎÁ ÉÓËÌÀÞÅÎÎÏÇÏ ÔÒÅÔØÅÇÏ. ëÁÖÄÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ

ÍÙ ÓÞÉÔÁÅÍ ÌÉÂÏ ÉÓÔÉÎÎÙÍ, ÌÉÂÏ ÌÏÖÎÙÍ. ÷ ÓÏ×ÒÅÍÅÎÎÙÈ ÏÓÎÏ×ÁÎÉÑÈ ÍÁ-

ÔÅÍÁÔÉËÉ ÜÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÏËÁÚÕÅÍÏ ÉÌÉ

ÎÅÄÏËÁÚÕÅÍÏ Ó ÐÏÍÏÝØÀ ÚÁËÏÎÏ× ÌÏÇÉËÉ É ÁËÓÉÏÍ ÔÏÇÏ ÒÁÚÄÅÌÁ ÍÁÔÅÍÁÔÉËÉ,

Ë ËÏÔÏÒÏÍÕ ÏÔÎÏÓÉÔÓÑ ÉÎÔÅÒÅÓÕÀÝÅÅ ÎÁÓ ÕÔ×ÅÒÖÄÅÎÉÅ. ç¾ÄÅÌØ ÖÅ ÄÏËÁÚÁÌ,

ÞÔÏ ÎÅËÏÔÏÒÙÅ ÕÔ×ÅÒÖÄÅÎÉÑ ÎÅÌØÚÑ ÎÉ ÄÏËÁÚÁÔØ, ÎÉ ÏÐÒÏ×ÅÒÇÎÕÔØ. îÅÐÒÏ-

ÔÉ×ÏÒÅÞÉ×ÏÓÔØ ÍÏÖÎÏ ÂÙÌÏ ÂÙ ÓÞÉÔÁÔØ ÄÏËÁÚÁÎÎÏÊ, ÅÓÌÉ ÂÙ × ÐÒÏÔÉ×Ï×ÅÓ

ÐÏÄÈÏÄÕ ç¾ÄÅÌÑ × ÓÉÓÔÅÍÅ ÕÄÁÌÏÓØ ÏÂÎÁÒÕÖÉÔØ ÎÅÒÁÚÒÅÛÉÍÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ:

×ÅÄØ ËÁË ÍÙ ÕÖÅ ÕÓÔÁÎÏ×ÉÌÉ, ÏÐÉÒÁÑÓØ ÎÁ Ó×ÏÊÓÔ×Á ÍÁÔÅÒÉÁÌØÎÏÊ ÉÍÐÌÉ-

ËÁÃÉÉ, ÅÓÌÉ × ÓÉÓÔÅÍÅ ÉÍÅÅÔÓÑ ÐÒÏÔÉ×ÏÒÅÞÉÅ, ÔÏ × ÎÅÊ ÍÏÖÎÏ ÄÏËÁÚÁÔØ ÞÔÏ

ÕÇÏÄÎÏ. ïÄÎÁËÏ ÄÏ ÓÉÈ ÐÏÒ ÏÂÎÁÒÕÖÉÔØ ÎÅÒÁÚÒÅÛÉÍÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÎÅ ÕÄÁ-

ÌÏÓØ.

ìÁÕÒÅÁÔ îÏÂÅÌÅ×ÓËÏÊ ÐÒÅÍÉÉ ÐÏ ÆÉÚÉËÅ àÄÖÉÎ ðÏÌ ÷ÉÇÎÅÒ, ÏÂÓÕÖÄÁÑ ×

1960 Ç. ÎÅÐÏÓÔÉÖÉÍÕÀ ÜÆÆÅËÔÉ×ÎÏÓÔØ ÍÁÔÅÍÁÔÉËÉ × ÅÓÔÅÓÔ×ÅÎÎÙÈ ÎÁÕËÁÈ

× ÓÔÁÔØÅ ÐÏÄ ÔÅÍ ÖÅ ÎÁÚ×ÁÎÉÅÍ, ÎÅ ÄÁÌ ÎÉËÁ ËÏÇÏ ÏÂßÑÓÎÅÎÉÑ É ÏÇÒÁÎÉÞÉÌÓÑ

ÌÉÛØ ËÏÎÓÔÁÔÁÃÉÅÊ ÓÐÏÒÎÏÇÏ ×ÏÐÒÏÓÁ: ¥íÁÔÅÍÁÔÉÞÅÓËÉÊ ÑÚÙË ÕÄÉ×ÉÔÅÌØ-

ÎÏ ÈÏÒÏÛÏ ÐÒÉÓÐÏÓÏÂÌÅÎ ÄÌÑ ÆÏÒÍÕÌÉÒÏ×ËÉ ÆÉÚÉÞÅÓËÉÈ ÚÁËÏÎÏ×. üÔÏ ÞÕ-

ÄÅÓÎÙÊ ÄÁÒ, ËÏÔÏÒÙÊ ÍÙ ÎÅ ÐÏÎÉÍÁÅÍ É ËÏÔÏÒÏÇÏ ÎÅ ÚÁÓÌÕÖÉ×ÁÅÍ. îÁÍ

ÏÓÔÁÅÔÓÑ ÌÉÛØ ÂÌÁÇÏÄÁÒÉÔØ ÚÁ ÎÅÇÏ ÓÕÄØÂÕ É ÎÁÄÅÑÔØÓÑ, ÞÔÏ É × ÂÕÄÕÝÉÈ

Ó×ÏÉÈ ÉÓÓÌÅÄÏ×ÁÎÉÑÈ ÍÙ ÓÍÏÖÅÍ ÐÏ-ÐÒÅÖÎÅÍÕ ÐÏÌØÚÏ×ÁÔØÓÑ ÉÍ. íÙ ÄÕÍÁ-

ÅÍ, ÞÔÏ ÓÆÅÒÁ ÅÇÏ ÐÒÉÍÅÎÉÍÏÓÔÉ (ÈÏÒÏÛÏ ÜÔÏ ÉÌÉ ÐÌÏÈÏ) ÂÕÄÅÔ ÎÅÐÒÅÒÙ×-

ÎÏ ×ÏÚÒÁÓÔÁÔØ, ÐÒÉÎÏÓÑ ÎÁÍ ÎÅ ÔÏÌØËÏ ÒÁÄÏÓÔØ, ÎÏ É ÎÏ×ÙÅ ÇÏÌÏ×ÏÌÏÍÎÙÅ

ÐÒÏÂÌÅÍÙ.¥

úÁÍÅÞÁÔÅÌØÎÁÑ ÔÏÞÎÏÓÔØ É ÜÆÆÅËÔÉ×ÎÏÓÔØ ÍÁÔÅÍÁÔÉËÉ × ÏÐÉÓÁÎÉÉ ÒÅÁÌØ-

ÎÏÇÏ ÍÉÒÁ ÐÏ-ÐÒÅÖÎÅÍÕ ÖÄÕÔ Ó×ÏÅÇÏ ÏÂßÑÓÎÅÎÉÑ. îÅÓÍÏÔÒÑ ÎÁ ÏÂÎÁÒÕÖÅÎ-

ÎÕÀ ÏÇÒÁÎÉÞÅÎÎÏÓÔØ ×ÏÚÍÏÖÎÏÓÔÅÊ, ÍÁÔÅÍÁÔÉËÅ ÅÓÔØ ÞÅÍ ÇÏÒÄÉÔØÓÑ. ïÎÁ

ÂÙÌÁ É ÏÓÔÁÅÔÓÑ ×ÙÓÛÉÍ ÉÎÔÅÌÌÅËÔÕÁÌØÎÙÍ ÄÏÓÔÉÖÅÎÉÅÍ É ÎÁÉÂÏÌÅÅ ÏÒÉ-

ÇÉÎÁÌØÎÙÍ Ô×ÏÒÅÎÉÅÍ ÞÅÌÏ×ÅÞÅÓËÏÇÏ ÄÕÈÁ. íÕÚÙËÁ ÍÏÖÅÔ ×ÏÚ×ÙÛÁÔØ ÉÌÉ

ÕÍÉÒÏÔ×ÏÒÑÔØ ÄÕÛÕ, ÖÉ×ÏÐÉÓØ - ÒÁÄÏ×ÁÔØ ÇÌÁÚ, ÐÏÜÚÉÑ ¡ ÐÒÏÂÕÖÄÁÔØ ÞÕ×-

§5. ï ÎÅÐÏÓÔÉÖÉÍÏÊ ÜÆÆÅËÔÉ×ÎÏÓÔÉ ÍÁÔÅÍÁÔÉËÉ 193

ÓÔ×Á, ÆÉÌÏÓÏÆÉÑ - ÕÄÏ×ÌÅÔ×ÏÒÑÔØ ÐÏÔÒÅÂÎÏÓÔÉ ÒÁÚÕÍÁ, ÉÎÖÅÎÅÒÎÏÅ ÄÅÌÏ - ÓÏ-

×ÅÒÛÅÎÓÔ×Ï×ÁÔØ ÍÁÔÅÒÉÁÌØÎÕÀ ÓÔÏÒÏÎÕ ÖÉÚÎÉ ÌÀÄÅÊ. îÏ ÍÁÔÅÍÁÔÉËÁ ÓÐÏ-

ÓÏÂÎÁ ÄÏÓÔÉÞØ ×ÓÅÈ ÜÔÉÈ ÃÅÌÅÊ. åÓÌÉ ÖÅ ÇÏ×ÏÒÉÔØ Ï ×ÏÚÍÏÖÎÏÓÔÑÈ ÞÅÌÏ×ÅÞÅ-

ÓËÏÇÏ ÒÁÚÕÍÁ, ÔÏ ÍÁÔÅÍÁÔÉËÉ ÎÅÍÁÌÏ ÐÏÔÒÕÄÉÌÉÓØ, ÞÔÏÂÙ ÄÏËÁÚÁÔØ, ÓËÏÌØ

×ÙÓÏËÕÀ ÎÁÄÅÖÎÏÓÔØ ÒÅÚÕÌØÔÁÔÏ× ÓÐÏÓÏÂÅÎ ÏÂÅÓÐÅÞÉÔØ ÞÅÌÏ×ÅÞÅÓËÉÊ ÒÁÚÕÍ.

îÅ ÓÌÕÞÁÊÎÏ ÍÁÔÅÍÁÔÉÞÅÓËÁÑ ÔÏÞÎÏÓÔØ ×ÏÛÌÁ × ÐÏÇÏ×ÏÒËÕ. íÁÔÅÍÁÔÉËÁ ÐÏ-

ÐÒÅÖÎÅÍÕ ÏÓÔÁÅÔÓÑ ÜÔÁÌÏÎÏÍ ÓÁÍÏÇÏ ÎÁÄÅÖÎÏÇÏ É ÔÏÞÎÏÇÏ ÚÎÁÎÉÑ, ËÏÔÏÒÏÇÏ

ÍÙ ÔÏÌØËÏ × ÓÏÓÔÏÑÎÉÉ ÄÏÓÔÉÞØ.

÷ÓÅ Ó×ÅÒÛÅÎÉÑ ÍÁÔÅÍÁÔÉËÉ - ÜÔÏ Ó×ÅÒÛÅÎÉÑ ÞÅÌÏ×ÅÞÅÓËÏÇÏ ÒÁÚÕÍÁ. ðÏËÁ-

ÚÁ×, ÎÁ ÞÔÏ ÓÐÏÓÏÂÅÎ ÞÅÌÏ×ÅË, ÍÁÔÅÍÁÔÉËÁ ×ÓÅÌÉÌÁ × ÌÀÄÅÊ ÓÍÅÌÏÓÔØ É Õ×Å-

ÒÅÎÎÏÓÔØ, ÐÏÚ×ÏÌÉ×ÛÉÅ ÉÍ ×ÐÌÏÔÎÕÀ ×ÚÑÔØÓÑ ÚÁ ÒÁÚÇÁÄËÕ ÒÁÎÅÅ, ËÁÚÁÌÏÓØ

ÂÙ, ÎÅÐÒÉÓÔÕÐÎÙÈ ÔÁÊÎ ËÏÓÍÏÓÁ, ÌÅÞÅÎÉÅ ÓÔÒÁÛÎÙÈ ÂÏÌÅÚÎÅÊ, ËÏÌÉÞÅÓÔ×ÅÎ-

ÎÙÊ ÁÎÁÌÉÚ ÐÒÏÂÌÅÍ, ÏÔÎÏÓÑÝÉÈÓÑ Ë ÜËÏÎÏÍÉËÅ É ÕÓÔÒÏÊÓÔ×Õ ÞÅÌÏ×ÅÞÅÓËÏÇÏ

ÏÂÝÅÓÔ×Á, ÞÔÏ ÐÏÚ×ÏÌÑÅÔ ÎÁÄÅÑÔØÓÑ ÎÁ ÄÁÌØÎÅÊÛÉÊ ÐÒÏÇÒÅÓÓ ÞÅÌÏ×ÅÞÅÓÔ×Á.

÷ ÒÅÛÅÎÉÉ ÜÔÉÈ ÐÒÏÂÌÅÍ ÉÍÅÎÎÏ Ó ÍÁÔÅÍÁÔÉËÏÊ Ó×ÑÚÁÎÙ ÏÓÎÏ×ÎÙÅ ÎÁÄÅÖÄÙ

ÎÁ ÕÓÐÅÈ.

çìá÷á XIII

òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

§1. ðÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

ðÒÏÇÒÁÍÍÙ Ó ËÏÎÅÞÎÙÍ ÞÉÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ ÎÁÐÏÍÉÎÁÌÉ ÁÓÓÅÍÂÌÅÒ; ÒÁÓ-

ÓÍÁÔÒÉ×ÁÅÍÙÅ × ÜÔÏÍ ÒÁÚÄÅÌÅ ÒÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ ÓËÏÒÅÅ ÎÁÐÏÍÉÎÁÀÔ

ÆÕÎËÃÉÏÎÁÌØÎÏÅ ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÅ, ËÏÇÄÁ ÏÄÎÉ ÆÕÎËÃÉÉ ÏÐÒÅÄÅÌÑÀÔÓÑ ÞÅ-

ÒÅÚ ÄÒÕÇÉÅ. íÙ ÂÕÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÆÕÎËÃÉÉ Ó ÎÁÔÕÒÁÌØÎÙÍÉ ÁÒÇÕÍÅÎ-

ÔÁÍÉ É ÚÎÁÞÅÎÉÑÍÉ. ÷ÏÏÂÝÅ ÇÏ×ÏÒÑ, ÆÕÎËÃÉÉ ÍÏÇÕÔ ÂÙÔØ ÎÅ ×ÓÀÄÕ ÏÐÒÅ-

ÄÅÌÅÎÎÙÍÉ, ÔÁË ÞÔÏ ÇÏ×ÏÒÑ Ï ÆÕÎËÃÉÉ n ÁÒÇÕÍÅÎÔÏ× (ÆÕÎËÃÉÉ ÉÚ N

× N,

n-ÍÅÓÔÎÏÊ ÆÕÎËÃÉÉ), ÍÙ ÉÍÅÅÍ × ×ÉÄÕ ÆÕÎËÃÉÀ, ÏÐÒÅÄÅÌ¾ÎÎÕÀ ÎÁ ÎÅËÏÔÏ-

ÒÏÍ ÐÏÄÍÎÏÖÅÓÔ×Å N

ÓÏ ÚÎÁÞÅÎÉÑÍÉ × N.

ðÕÓÔØ ÉÍÅÅÔÓÑ ÏÄÎÁ k-ÍÅÓÔÎÁÑ ÆÕÎËÃÉÑ f É k ÛÔÕË n-ÍÅÓÔÎÙÈ g

, . . . , g

ôÏÇÄÁ ÉÚ ÎÉÈ ÍÏÖÎÏ ÓÆÏÒÍÉÒÏ×ÁÔØ ÏÄÎÕ n-ÍÅÓÔÎÕÀ ÆÕÎËÃÉÀ

, . . . , x

i 7→ f(g

, . . . , x

), . . . , g

, . . . , x

)).

çÏ×ÏÒÑÔ, ÞÔÏ ÏÐÒÅÄÅÌ¾ÎÎÁÑ ÔÁËÉÍ ÏÂÒÁÚÏÍ ÆÕÎËÃÉÑ ÐÏÌÕÞÅÎÁ ÉÚ ÆÕÎËÃÉÊ f

É g

, . . . , g

Ó ÐÏÍÏÝØÀ ÏÐÅÒÁÃÉÉ ÐÏÄÓÔÁÎÏ×ËÉ.

äÒÕÇÁÑ ÏÐÅÒÁÃÉÑ, ÎÁÚÙ×ÁÅÍÁÑ ÏÐÅÒÁÃÉÅÊ ÒÅËÕÒÓÉÉ, ÉÌÉ

ÐÒÉÍÉÔÉ×ÎÏÊ ÒÅËÕÒÓÉÉ, ÐÒÉÍÅÎÑÅÔÓÑ Ë k-ÍÅÓÔÎÏÊ ÆÕÎËÃÉÉ f É (k +

+ 2)-ÍÅÓÔÎÏÊ ÆÕÎËÃÉÉ g. å¾ ÒÅÚÕÌØÔÁÔÏÍ ÂÕÄÅÔ (k + 1)-ÍÅÓÔÎÁÑ ÆÕÎËÃÉÑ h,

ÏÐÒÅÄÅÌÑÅÍÁÑ ÔÁË:

h(x

, . . . , x

, 0) = f(x

, . . . , x

); (1)

h(x

, . . . , x

, y + 1) = g(x

, . . . , x

, y, h(x

, . . . , x

, y)). (2)

÷ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ h(x

, . . . , x

, 0), h(x

, . . . , x

, 1), . . . ËÁÖÄÏÅ ÚÎÁÞÅÎÉÅ

ÏÐÒÅÄÅÌÑÅÔÓÑ ÞÅÒÅÚ ÐÒÅÄÙÄÕÝÅÅ, ÐÏÜÔÏÍÕ ÅÓÌÉ ËÁËÏÅ-ÔÏ ÉÚ ÚÎÁÞÅÎÉÊ ÎÅ ÏÐÒÅ-

ÄÅÌÅÎÏ, ÔÏ ÎÅ ÏÐÒÅÄÅÌÅÎÙ É ×ÓÅ ÐÏÓÌÅÄÕÀÝÉÅ.

äÌÑ ÅÄÉÎÏÏÂÒÁÚÉÑ ÂÕÄÅÍ ÓÞÉÔÁÔØ, ÞÔÏ ÎÕÌØ-ÍÅÓÔÎÙÅ ÆÕÎËÃÉÉ (ÆÕÎË-

ÃÉÉ ÂÅÚ ÁÒÇÕÍÅÎÔÏ×) ÓÕÔØ ËÏÎÓÔÁÎÔÙ; ÜÔÏ ÐÏÚ×ÏÌÑÅÔ ÒÅËÕÒÓÉ×ÎÏ ÏÐÒÅÄÅÌÑÔØ

ÆÕÎËÃÉÉ ÏÄÎÏÊ ÐÅÒÅÍÅÎÎÏÊ.

ðÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÍÉ ÎÁÚÙ×ÁÀÔ ÆÕÎËÃÉÉ, ËÏÔÏÒÙÅ ÍÏÖÎÏ ÐÏÌÕ-

ÞÉÔØ Ó ÐÏÍÏÝØÀ ÏÐÅÒÁÃÉÊ ÐÏÄÓÔÁÎÏ×ËÉ É ÒÅËÕÒÓÉÉ ÉÚ ÓÌÅÄÕÀÝÉÈ ÂÁÚÉÓÎÙÈ

ÆÕÎËÃÉÊ: ËÏÎÓÔÁÎÔÙ 0, ÏÐÅÒÁÃÉÉ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ s: x 7→ x + 1 É ÓÅ-

ÍÅÊÓÔ×Á ÆÕÎËÃÉÊ ÐÒÏÅËÃÉÉ: ÜÔÏ ÓÅÍÅÊÓÔ×Ï ÄÌÑ ËÁÖÄÏÇÏ k ÓÏÄÅÒÖÉÔ k ÛÔÕË

k-ÍÅÓÔÎÙÈ ÆÕÎËÃÉÊ π

, . . . , x

) = x

194

§2. ðÒÉÍÅÒÙ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÈ ÆÕÎËÃÉÊ 195

æÕÎËÃÉÉ ÐÒÏÅËÃÉÉ ÐÏÚ×ÏÌÑÀÔ ×ÙÐÏÌÎÑÔØ ¥ÎÅÏÄÎÏÒÏÄÎÙÅ¥ ÐÏÄÓÔÁÎÏ×ËÉ:

ÓËÁÖÅÍ, ÍÏÖÎÏ ÐÏÌÕÞÉÔØ ÆÕÎËÃÉÀ hx, yi 7→ f(g(x), h(y, x, y), x) ÉÚ ÆÕÎË-

ÃÉÊ f É h, ËÏÍÂÉÎÉÒÕÑ ÉÈ Ó ÆÕÎËÃÉÑÍÉ ÐÒÏÅËÃÉÉ: ÓÎÁÞÁÌÁ ÐÏÌÕÞÁÅÍ ÆÕÎË-

ÃÉÀ hx, yi 7→ g(x) (ÐÏÄÓÔÁÎÏ×ËÁ π

× g), ÚÁÔÅÍ hx, yi 7→ h(y, x, y) (ÐÏÄÓÔÁÎÏ×ËÁ

, π

× h), ÚÁÔÅÍ ÐÏÌÕÞÅÎÎÙÅ Ä×Å ÆÕÎËÃÉÉ ×ÍÅÓÔÅ Ó ÆÕÎËÃÉÅÊ π

ÐÏÄÓÔÁ-

×ÌÑÅÍ × f .

ðÏÄÓÔÁ×ÌÑÑ ËÏÎÓÔÁÎÔÕ 0 × ÆÕÎËÃÉÀ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ, ÐÏÌÕÞÁÅÍ

ËÏÎÓÔÁÎÔÕ (ÆÕÎËÃÉÀ ÎÕÌÑ ÁÒÇÕÍÅÎÔÏ×) 1. úÁÔÅÍ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ ËÏÎÓÔÁÎ-

ÔÙ 2, 3 É Ô. Ä.

§2. ðÒÉÍÅÒÙ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÈ ÆÕÎËÃÉÊ

ëÁË É Ó ÄÒÕÇÉÍÉ ×ÙÞÉÓÌÉÔÅÌØÎÙÍÉ ÍÏÄÅÌÑÍÉ, ×ÁÖÎÏ ÎÁËÏÐÉÔØ ÎÅËÏÔÏ-

ÒÙÊ ÐÒÏÇÒÁÍÍÉÓÔÓËÉÊ ÏÐÙÔ.

óÌÏÖÅÎÉÅ. æÕÎËÃÉÑ hx, yi 7→ sum(x, y) = x + y ÐÏÌÕÞÁÅÔÓÑ Ó ÐÏÍÏÝØÀ

ÒÅËÕÒÓÉÉ:

sum(x, 0) = x; (1)

sum(x, y + 1) = sum(x, y) + 1. (2)

îÁÄÏ, ËÏÎÅÞÎÏ, ÐÒÅÄÓÔÁ×ÉÔØ ÐÒÁ×ÕÀ ÞÁÓÔØ ×ÔÏÒÏÇÏ ÒÁ×ÅÎÓÔ×Á ËÁË ÒÅÚÕÌØ-

ÔÁÔ ÐÏÄÓÔÁÎÏ×ËÉ. æÏÒÍÁÌØÎÏ ÇÏ×ÏÒÑ, h(x, y, z) × ÏÐÒÅÄÅÌÅÎÉÉ ÒÅËÕÒÓÉÉ ÎÁÄÏ

ÐÏÌÏÖÉÔØ ÒÁ×ÎÙÍ s(z), ÇÄÅ s ¡ ÆÕÎËÃÉÑ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ.

õÍÎÏÖÅÎÉÅ. æÕÎËÃÉÑ hx, yi 7→ prod(x, y) = xy ÐÏÌÕÞÁÅÔÓÑ Ó ÐÏÍÏÝØÀ

ÒÅËÕÒÓÉÉ (Ó ÉÓÐÏÌØÚÏ×ÁÎÉÅÍ ÓÌÏÖÅÎÉÑ):

prod(x, 0) = 0; (3)

prod(x, y + 1) = prod(x, y) + x. (4)

áÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ ÍÏÖÎÏ ÐÅÒÅÊÔÉ ÏÔ ÕÍÎÏÖÅÎÉÑ Ë ×ÏÚ×ÅÄÅÎÉÀ × ÓÔÅ-

ÐÅÎØ.

õÓÅÞ¾ÎÎÏÅ ×ÙÞÉÔÁÎÉÅ. íÙ ÇÏ×ÏÒÉÍ ÏÂ ¥ÕÓÅÞ¾ÎÎÏÍ ×ÙÞÉÔÁÎÉÉ¥ x

‘

− y =

= x − y ÐÒÉ x > y É x

‘

− y = 0 ÐÒÉ x < y, ÐÏÓËÏÌØËÕ ÍÙ ÉÍÅÅÍ ÄÅÌÏ ÔÏÌØËÏ Ó

ÎÁÔÕÒÁÌØÎÙÍÉ (ÃÅÌÙÍÉ ÎÅÏÔÒÉÃÁÔÅÌØÎÙÍÉ) ÞÉÓÌÁÍÉ. ïÄÎÏÍÅÓÔÎÁÑ ÆÕÎË-

ÃÉÑ ÕÓÅÞ¾ÎÎÏÇÏ ×ÙÞÉÔÁÎÉÑ ÅÄÉÎÉÃÙ ÏÐÒÅÄÅÌÑÅÔÓÑ ÒÅËÕÒÓÉ×ÎÏ:

‘

− 1 = 0; (5)

(y + 1)

‘

− 1 = y. (6)

(òÅËÕÒÓÉÑ ÚÄÅÓØ ÆÏÒÍÁÌØÎÁ, ÔÁË ËÁË ÐÒÅÄÙÄÕÝÅÅ ÚÎÁÞÅÎÉÅ ÎÅ ÉÓÐÏÌØÚÕÅÔ-

ÓÑ.) ðÏÓÌÅ ÜÔÏÇÏ ÕÓÅÞ¾ÎÎÏÅ ×ÙÞÉÔÁÎÉÅ ÄÌÑ ÐÒÏÉÚ×ÏÌØÎÙÈ ÁÒÇÕÍÅÎÔÏ× ÍÏÖÎÏ

196 çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

ÏÐÒÅÄÅÌÉÔØ ÔÁË:

‘

− 0 = x; (7)

‘

− (y + 1) = (x

‘

− y)

‘

− 1. (8)

§3. ðÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ ÍÎÏÖÅÓÔ×Á

âÕÄÅÍ ÎÁÚÙ×ÁÔØ ÍÎÏÖÅÓÔ×Ï ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÍ, ÅÓÌÉ ÅÇÏ ÈÁÒÁËÔÅ-

ÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. (÷ÁÒÉÁÎÔ: ÅÓÌÉ ÏÎÏ Ñ×ÌÑÅÔÓÑ

ÍÎÏÖÅÓÔ×ÏÍ ÎÕÌÅÊ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ ÆÕÎËÃÉÉ; ÜÔÏ ÔÏ ÖÅ ÓÁÍÏÅ, ÔÁË

ËÁË ÍÏÖÎÏ ÓÄÅÌÁÔØ ÐÏÄÓÔÁÎÏ×ËÕ × ÆÕÎËÃÉÀ x 7→ 1

‘

− x.)

ðÅÒÅÓÅÞÅÎÉÅ É ÏÂßÅÄÉÎÅÎÉÅ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÈ ÍÎÏÖÅÓÔ× ÐÒÉÍÉ-

ÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ (ÓÌÏÖÉÍ ÉÌÉ ÐÅÒÅÍÎÏÖÉÍ ÆÕÎËÃÉÉ, ÍÎÏÖÅÓÔ×ÁÍÉ ÎÕÌÅÊ

ËÏÔÏÒÙÈ ÏÎÉ Ñ×ÌÑÀÔÓÑ). äÏÐÏÌÎÅÎÉÅ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÇÏ ÍÎÏÖÅÓÔ×Á

ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏ. ïÔÏÖÄÅÓÔ×ÌÑÑ ÍÎÏÖÅÓÔ×Á ÓÏ Ó×ÏÊÓÔ×ÁÍÉ, ÍÏÖÎÏ

ÓËÁÚÁÔØ, ÞÔÏ ËÏÎßÀÎËÃÉÉ, ÄÉÚßÀÎËÃÉÉ É ÏÔÒÉÃÁÎÉÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×-

ÎÙÈ Ó×ÏÊÓÔ× ÂÕÄÕÔ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ.

ó×ÏÊÓÔ×Á x = y É x 6= y ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ (x = y ÔÏÇÄÁ É ÔÏÌØËÏ

ÔÏÇÄÁ, ËÏÇÄÁ (x

‘

− y) + (y

‘

− x) = 0).

æÕÎËÃÉÑ f (x), ÚÁÄÁÎÎÁÑ ÓÏÏÔÎÏÛÅÎÉÅÍ

f(x) = [ if (R(x)) g(x); else h(x); ],

ÂÕÄÅÔ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ, ÅÓÌÉ ÔÁËÏ×Ù ÆÕÎËÃÉÉ g É h É Ó×ÏÊÓÔ×Ï R.

÷ ÓÁÍÏÍ ÄÅÌÅ, f (x) ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÁË r(x)g(x) + (1

‘

− r(x))h(x), ÇÄÅ r ¡

ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ Ó×ÏÊÓÔ×Á R.

ôÅÐÅÒØ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ÆÏÒÍÕÌÕ ÄÌÑ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ ÐÏ ÍÏÄÕÌÀ n

(ÄÌÑ ÞÉÓÅÌ, ÍÅÎØÛÉÈ n):

x + 1 mod n = [ if (x + 1 == n) 0; else x + 1; ]

ðÏÓÌÅ ÜÔÏÇÏ ÆÕÎËÃÉÀ x mod n (ÏÓÔÁÔÏË ÏÔ ÄÅÌÅÎÉÑ ÎÁ n) ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ

ÒÅËÕÒÓÉ×ÎÏ:

0 mod n = 0; (1)

(x + 1) mod n = (x mod n) + 1 mod n. (2)

ðÏËÁÖÅÍ, ÞÔÏ ÏÇÒÁÎÉÞÅÎÎÙÅ Ë×ÁÎÔÏÒÙ, ÐÒÉÍÅÎ¾ÎÎÙÅ Ë ÐÒÉÍÉÔÉ×ÎÏ ÒÅ-

ËÕÒÓÉ×ÎÙÍ Ó×ÏÊÓÔ×ÁÍ (ÍÎÏÖÅÓÔ×ÁÍ), ÄÁÀÔ ÓÎÏ×Á ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ

Ó×ÏÊÓÔ×Á. üÔÏ ÏÚÎÁÞÁÅÔ, ÎÁÐÒÉÍÅÒ, ÞÔÏ ÅÓÌÉ Ó×ÏÊÓÔ×Ï R(x, y) ÐÒÉÍÉÔÉ×ÎÏ

ÒÅËÕÒÓÉ×ÎÏ, ÔÏ Ó×ÏÊÓÔ×Á

S(x, z) = (∃y 6 z) R(x, y)

§3. ðÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ ÍÎÏÖÅÓÔ×Á 197

T (y, z) = (∀y 6 z) R(x, y)

ÔÁËÖÅ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ. þÔÏÂÙ ÕÂÅÄÉÔØÓÑ × ÜÔÏÍ, ÚÁÍÅÔÉÍ, ÞÔÏ ÄÌÑ

ÆÕÎËÃÉÊ ÏÇÒÁÎÉÞÅÎÎÙÊ Ë×ÁÎÔÏÒ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÐÅÒÅÍÎÏÖÅÎÉÀ ÉÌÉ ÓÕÍÍÉ-

ÒÏ×ÁÎÉÀ: ÅÓÌÉ Ó×ÏÊÓÔ×Ï R(x, y) ÒÁ×ÎÏÓÉÌØÎÏ r(x, y) = 0, ÔÏ

S(x, z) ⇔

y=0

r(x, y) = 0

á ÐÒÏÉÚ×ÅÄÅÎÉÅ ÌÅÇËÏ ÏÐÒÅÄÅÌÉÔØ ÒÅËÕÒÓÉ×ÎÏ:

y=0

r(x, y) = r(x, 0); (3)

t+1

y=0

r(x, y) =

y=0

r(x, y)

· r(x, t + 1); (4)

Ó ÓÕÍÍÉÒÏ×ÁÎÉÅÍ ÍÏÖÎÏ ÐÏÓÔÕÐÉÔØ ÁÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ.

ðÏÓÌÅ ÜÔÏÇÏ ÌÅÇËÏ ÚÁÍÅÔÉÔØ, ÞÔÏ Ó×ÏÊÓÔ×Ï ¥ÂÙÔØ ÐÒÏÓÔÙÍ¥ ÐÒÉÍÉÔÉ×ÎÏ

ÒÅËÕÒÓÉ×ÎÏ (ÌÀÂÏÅ ÍÅÎØÛÅÅ ÞÉÓÌÏ ÌÉÂÏ ÒÁ×ÎÏ ÎÕÌÀ, ÌÉÂÏ ÒÁ×ÎÏ 1, ÌÉÂÏ ÎÅ

Ñ×ÌÑÅÔÓÑ ÄÅÌÉÔÅÌÅÍ).

ðÏËÁÖÅÍ ÔÅÐÅÒØ, ÞÔÏ ÅÓÌÉ ÇÒÁÆÉË ÎÅËÏÔÏÒÏÊ ÆÕÎËÃÉÉ f ÐÒÉÍÉÔÉ×ÎÏ ÒÅ-

ËÕÒÓÉ×ÅÎ É Å¾ ÚÎÁÞÅÎÉÑ ÏÇÒÁÎÉÞÅÎÙ Ó×ÅÒÈÕ ÎÅËÏÔÏÒÏÊ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒ-

ÓÉ×ÎÏÊ ÆÕÎËÃÉÅÊ g, ÔÏ ÓÁÍÁ ÆÕÎËÃÉÑ f ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. ÷ ÓÁÍÏÍ

ÄÅÌÅ, ÅÓÌÉ r ¡ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ ÇÒÁÆÉËÁ, ÔÏ ÅÓÔØ r(x, y) = 1

ÐÒÉ y = f(x) É r(x, y) = 0 ÐÒÉ y 6= f (x) (ÄÌÑ ÐÒÏÓÔÏÔÙ ÍÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ

ÓÌÕÞÁÊ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ), ÔÏ

f(x) =

∞

i=0

y · r(x, y),

Á ÓÕÍÍÉÒÏ×ÁÎÉÅ ÍÏÖÎÏ ÏÇÒÁÎÉÞÉÔØ Ó×ÅÒÈÕ ×ÙÒÁÖÅÎÉÅÍ g(x) É ×ÏÓÐÏÌØÚÏ-

×ÁÔØÓÑ ÐÒÉÍÉÔÉ×ÎÏÊ ÒÅËÕÒÓÉ×ÎÏÓÔØÀ ÏÇÒÁÎÉÞÅÎÎÏÊ ÓÕÍÍÙ.

ïÔÓÀÄÁ ÌÅÇËÏ ×Ù×ÅÓÔÉ ÓÌÅÄÕÀÝÅÅ ÕÔ×ÅÒÖÄÅÎÉÅ: ÅÓÌÉ ÆÕÎËÃÉÑ g É Ó×ÏÊ-

ÓÔ×Ï R(x, y) ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ, ÔÏ ÆÕÎËÃÉÑ

x 7→ f(x) = ÎÁÉÍÅÎØÛÅÅ y 6 g(x), ÄÌÑ ËÏÔÏÒÏÇÏ R(x, y)

(ÅÓÌÉ ÄÌÑ ÎÅËÏÔÏÒÏÇÏ x ÔÁËÏÇÏ y ÎÅÔ, ÔÏ ÐÏÌÁÇÁÅÍ ÚÎÁÞÅÎÉÅ ÆÕÎËÃÉÉ ÒÁ×ÎÙÍ,

ÓËÁÖÅÍ, g(x) + 1) ÂÕÄÅÔ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÇÒÁÆÉË

ÆÕÎËÃÉÉ f ÌÅÇËÏ ÏÐÉÓÁÔØ Ó ÐÏÍÏÝØÀ ÏÇÒÁÎÉÞÅÎÎÙÈ Ë×ÁÎÔÏÒÏ×.

198 çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

ôÁËÏÊ ÓÐÏÓÏÂ ÏÐÒÅÄÅÌÅÎÉÑ ÆÕÎËÃÉÉ ÎÁÚÙ×ÁÀÔ ÏÇÒÁÎÉÞÅÎÎÙÍ ÏÐÅÒÁÔÏ-

ÒÏÍ ÍÉÎÉÍÉÚÁÃÉÉ ¡ × ÏÔÌÉÞÉÅ ÏÔ ÎÅÏÇÒÁÎÉÞÅÎÎÏÇÏ, ÇÄÅ ÎÅÔ ÚÁÒÁÎÅÅ ÉÚ×ÅÓÔ-

ÎÏÊ ÇÒÁÎÉÃÙ g(x). ëÁË ÍÙ Õ×ÉÄÉÍ, × ÎÅÏÇÒÁÎÉÞÅÎÎÏÍ ÓÌÕÞÁÅ ÐÏÌÕÞÁÀÝÁÑÓÑ

ÆÕÎËÃÉÑ ÎÅ ÏÂÑÚÁÎÁ ÂÙÔØ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ.

ïÇÒÁÎÉÞÅÎÎÙÊ ÏÐÅÒÁÔÏÒ ÍÉÎÉÍÉÚÁÃÉÉ ÍÏÖÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ, ÞÔÏÂÙ ÕÂÅ-

ÄÉÔØÓÑ, ÞÔÏ ÆÕÎËÃÉÑ x 7→ (ÍÉÎÉÍÁÌØÎÏÅ ÐÒÏÓÔÏÅ ÞÉÓÌÏ, ÂÏÌØÛÅÅ x) ÐÒÉÍÉ-

ÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ (ÒÁÓÓÕÖÄÅÎÉÅ å×ËÌÉÄÁ Ï ÂÅÓËÏÎÅÞÎÏÓÔÉ ÍÎÏÖÅÓÔ×Á ÐÒÏ-

ÓÔÙÈ ÞÉÓÅÌ ÕÓÔÁÎÁ×ÌÉ×ÁÅÔ, ÞÔÏ ÜÔÏ ÞÉÓÌÏ ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ x! + 1, Á ÆÁËÔÏÒÉ-

ÁÌ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÅÎ). ðÏÓÌÅ ÜÔÏÇÏ ÆÕÎËÃÉÑ n 7→ (n-Å ÐÒÏÓÔÏÅ ÞÉÓÌÏ)

ÌÅÇËÏ ÏÐÒÅÄÅÌÑÅÔÓÑ Ó ÐÏÍÏÝØÀ ÒÅËÕÒÓÉÉ.

§4. äÒÕÇÉÅ ×ÉÄÙ ÒÅËÕÒÓÉÉ

óÌÏ×Á ¥ÒÅËÕÒÓÉ×ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÆÕÎËÃÉÉ¥ ÍÏÖÎÏ ÐÏÎÉÍÁÔØ É × ÂÏÌÅÅ

ÛÉÒÏËÏÍ ÓÍÙÓÌÅ, ÎÅÖÅÌÉ ÍÙ ÜÔÏ ÄÅÌÁÌÉ (ÓÍ. ×ÙÛÅ ÏÐÒÅÄÅÌÅÎÉÅ ÒÅËÕÒÓÉÉ,

ÉÌÉ ÐÒÉÍÉÔÉ×ÎÏÊ ÒÅËÕÒÓÉÉ) ¡ ËÁË ÌÀÂÏÊ ÓÐÏÓÏÂ ÚÁÄÁÎÉÑ ÆÕÎËÃÉÉ, ËÏÔÏÒÙÊ

Ó×ÑÚÙ×ÁÅÔ ÚÎÁÞÅÎÉÅ ÆÕÎËÃÉÉ × ÄÁÎÎÏÊ ÔÏÞËÅ Ó ÄÒÕÇÉÍÉ Å¾ ÚÎÁÞÅÎÉÑÍÉ. ëÁË

ÍÙ Õ×ÉÄÉÍ ÎÉÖÅ ÐÒÉ ÏÂÓÕÖÄÅÎÉÉ ÆÕÎËÃÉÉ áËËÅÒÍÁÎÁ, ÅÓÔØ ÔÁËÉÅ ÓÈÅÍÙ

ÒÅËÕÒÓÉ×ÎÙÈ ÏÐÒÅÄÅÌÅÎÉÊ, ËÏÔÏÒÙÅ ×Ù×ÏÄÑÔ ÉÚ ËÌÁÓÓÁ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒ-

ÓÉ×ÎÙÈ ÆÕÎËÃÉÊ. îÏ ÅÓÔØ É ÔÁËÉÅ, ËÏÔÏÒÙÅ ÍÏÖÎÏ Ó×ÅÓÔÉ Ë ÒÁÓÓÍÏÔÒÅÎÎÏÊ

ÎÁÍÉ ÓÈÅÍÅ.

íÙ ÐÒÉ×ÅÄ¾Í Ä×Á ÐÒÉÍÅÒÁ ÐÏÓÌÅÄÎÅÇÏ ÔÉÐÁ: ÓÏ×ÍÅÓÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÎÅ-

ÓËÏÌØËÉÈ ÆÕÎËÃÉÊ É ÉÓÐÏÌØÚÏ×ÁÎÉÅ ÐÒÏÉÚ×ÏÌØÎÙÈ ÍÅÎØÛÉÈ ÚÎÁÞÅÎÉÊ ÁÒÇÕ-

ÍÅÎÔÁ.

óÏ×ÍÅÓÔÎÁÑ ÒÅËÕÒÓÉÑ. ðÕÓÔØ Ä×Å ÏÄÎÏÍÅÓÔÎÙÅ ÆÕÎËÃÉÉ f É g ÚÁÄÁÎÙ ÓÏ-

ÏÔÎÏÛÅÎÉÑÍÉ:

f(0) = a, (1)

g(0) = b, (2)

f(n + 1) = F (n, f (n), g(n)), (3)

g(n + 1) = G(n, f (n), g(n)), (4)

ÇÄÅ a É b ¡ ÎÅËÏÔÏÒÙÅ ÞÉÓÌÁ, Á ÆÕÎËÃÉÉ F É G ¡ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ

ÆÕÎËÃÉÉ ÔÒ¾È ÁÒÇÕÍÅÎÔÏ×. ðÏËÁÖÅÍ, ÞÔÏ ÔÏÇÄÁ ÆÕÎËÃÉÉ f É g ÐÒÉÍÉÔÉ×ÎÏ

ÒÅËÕÒÓÉ×ÎÙ.

þÔÏÂÙ ÄÏËÁÚÁÔØ ÜÔÏ, ÎÁÍ ÐÏÔÒÅÂÕÅÔÓÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁÑ ÎÕÍÅ-

ÒÁÃÉÑ ÐÁÒ ¡ ÔÁËÁÑ ÆÕÎËÃÉÑ hx, yi → [x, y] (ÎÏÍÅÒ ÐÁÒÙ ÍÙ ÏÂÏÚÎÁÞÁÅÍ

Ë×ÁÄÒÁÔÎÙÍÉ ÓËÏÂËÁÍÉ), ËÏÔÏÒÁÑ ÂÙÌÁ ÂÙ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ ×ÍÅÓÔÅ

Ó Ä×ÕÍÑ ÏÂÒÁÔÎÙÍÉ ÆÕÎËÃÉÑÍÉ (ÄÁÀÝÉÍÉ ÐÏ ÎÏÍÅÒÕ ÐÁÒÙ Å¾ ÐÅÒ×ÙÊ É

×ÔÏÒÏÊ ÞÌÅÎÙ). ôÏÇÄÁ ÍÙ ÓÍÏÖÅÍ ÎÁÐÉÓÁÔØ ÒÅËÕÒÓÉ×ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÄÌÑ

§4. äÒÕÇÉÅ ×ÉÄÙ ÒÅËÕÒÓÉÉ 199

ÆÕÎËÃÉÉ h(n) = [f(n), g(n)]:

h(0) =[a, b], (5)

h(n + 1) =[F (n, p

(h(n)), p

(h(n))), (6)

G(n, p

(h(n)), p

(h(n)))], (7)

ÇÄÅ ÆÕÎËÃÉÉ p

É p

ÄÁÀÔ ÐÏ ÎÏÍÅÒÕ ÐÁÒÙ ÐÅÒ×ÙÊ É ×ÔÏÒÏÊ Å¾ ÞÌÅÎÙ. åÓÌÉ

ÆÕÎËÃÉÑ h ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ, ÔÏ É ÆÕÎËÃÉÉ f É g (ËÏÍÐÏÚÉÃÉÉ h Ó

ÆÕÎËÃÉÑÍÉ p

É p

) ÔÁËÖÅ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ.

ïÓÔÁÌÏÓØ ÏÂßÑÓÎÉÔØ, ËÁË ÎÁÊÔÉ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÕÀ ÎÕÍÅÒÁÃÉÀ

ÐÁÒ. íÏÖÎÏ ÚÁÍÅÔÉÔØ, ÞÔÏ ÅÓÔØ ÍÎÏÇÏÞÌÅÎ ×ÔÏÒÏÇÏ ÐÏÒÑÄËÁ Ó Ä×ÕÍÑ ÐÅÒÅ-

ÍÅÎÎÙÍÉ, ÚÁÄÁÀÝÉÊ ×ÚÁÉÍÎÏ ÏÄÎÏÚÎÁÞÎÏÅ ÓÏÏÔ×ÅÔÓÔ×ÉÅ N × N → N. üÔÏ

ÓÏÏÔ×ÅÔÓÔ×ÉÅ ×ÉÄÎÏ ÉÚ ÔÁÂÌÉÃÙ:

3 7

1 4 8

0 2 5 9

ðÒÉÍÉÔÉ×ÎÕÀ ÒÅËÕÒÓÉ×ÎÏÓÔØ ÏÂÒÁÔÎÙÈ ÏÔÏÂÒÁÖÅÎÉÊ p

É p

ÍÏÖÎÏ ÕÓÔÁ-

ÎÏ×ÉÔØ, ×ÏÓÐÏÌØÚÏ×Á×ÛÉÓØ ÏÇÒÁÎÉÞÅÎÎÏÊ ÍÉÎÉÍÉÚÁÃÉÅÊ, ÔÁË ËÁË p

(n) ÅÓÔØ

ÍÉÎÉÍÁÌØÎÏÅ x 6 n, ÄÌÑ ËÏÔÏÒÏÇÏ ÎÁÊÄ¾ÔÓÑ y 6 n, ÐÒÉ ËÏÔÏÒÏÍ [x, y] = n.

íÅÎÅÅ ÓÉÍÍÅÔÒÉÞÎÁÑ ÎÕÍÅÒÁÃÉÑ ÐÁÒ ÍÏÖÅÔ ÂÙÔØ ÚÁÄÁÎÁ ÆÏÒÍÕÌÏÊ [a, b] =

= (2a + 1)2

. íÏÖÎÏ ÔÁËÖÅ ÚÁÍÅÔÉÔØ, ÞÔÏ ÎÁÍ ÎÅ ÎÕÖÎÏ, ÞÔÏÂÙ ×ÓÅ ÞÉÓÌÁ

ÂÙÌÉ ÎÏÍÅÒÁÍÉ ËÁËÉÈ-ÔÏ ÐÁÒ, É ×ÏÓÐÏÌØÚÏ×ÁÔØÓÑ ÎÕÍÅÒÁÃÉÅÊ [a, b] = 2

úÁÍÅÔÉÍ × ÚÁËÌÀÞÅÎÉÅ, ÞÔÏ ÁÎÁÌÏÇÉÞÎÁÑ ËÏÎÓÔÒÕËÃÉÑ ÐÒÉÍÅÎÉÍÁ ÄÌÑ

ÂÏÌØÛÅÇÏ ÞÉÓÌÁ ÏÄÎÏ×ÒÅÍÅÎÎÏ ÏÐÒÅÄÅÌÑÅÍÙÈ ÆÕÎËÃÉÊ É ÄÌÑ ÆÕÎËÃÉÊ ÏÔ

ÂÏÌØÛÅÇÏ ÞÉÓÌÁ ÁÒÇÕÍÅÎÔÏ×.

÷ÏÚ×ÒÁÔÎÁÑ ÒÅËÕÒÓÉÑ. óÌÅÄÕÀÝÅÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÐÏËÁÚÙ×ÁÅÔ, ÞÔÏ ÐÒÉ ÒÅ-

ËÕÒÓÉ×ÎÏÍ ÏÐÒÅÄÅÌÅÎÉÉ ÍÏÖÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ ÎÅ ÔÏÌØËÏ ÚÎÁÞÅÎÉÅ × ÐÒÅÄÙÄÕ-

ÝÅÊ ÔÏÞËÅ, ÎÏ É ÌÀÂÏÅ ÐÒÅÄÛÅÓÔ×ÕÀÝÅÅ ÚÎÁÞÅÎÉÅ.

ôÅÏÒÅÍÁ 74. ðÕÓÔØ ÆÕÎËÃÉÑ g ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒ-

ÓÉ×ÎÁ, ÐÒÉÞ¾Í g(x) < x ÐÒÉ x > 0; ÐÕÓÔØ F ¡ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×-

ÎÁÑ ÆÕÎËÃÉÑ Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×; ÐÕÓÔØ c ¡ ÐÒÏÉÚ×ÏÌØÎÁÑ ËÏÎÓÔÁÎÔÁ. ôÏÇÄÁ

ÆÕÎËÃÉÑ h, ÏÐÒÅÄÅÌ¾ÎÎÁÑ ÓÏÏÔÎÏÛÅÎÉÑÍÉ

h(0) = c, (8)

h(x) = F (x, h(g(x))) ÐÒÉ x > 0 (9)

ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ.

 þÔÏÂÙ ÄÏËÁÚÁÔØ ÜÔÕ ÔÅÏÒÅÍÕ, ÉÓÐÏÌØÚÕÅÍ ÓÌÅÄÕÀÝÕÀ ÎÕÍÅÒÁÃÉÀ ËÏ-

ÎÅÞÎÙÈ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ: ÎÏÍÅÒÏÍ ÐÕÓÔÏÊ ÐÏÓÌÅÄÏ-

200 çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

×ÁÔÅÌØÎÏÓÔÉ ÓÞÉÔÁÅÍ ÞÉÓÌÏ 1, ÎÏÍÅÒÏÍ ÏÄÎÏÜÌÅÍÅÎÔÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ-

ÓÔÉ hai ÓÞÉÔÁÅÍ ÞÉÓÌÏ 2

a+1

, ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ha, bi ÉÍÅÅÔ ÎÏÍÅÒ 2

a+1

b+1

ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ha, b, ci ÉÍÅÅÔ ÎÏÍÅÒ 2

a+1

b+1

c+1

É ÔÁË ÄÁÌÅÅ (ÏÓÎÏ×Á-

ÎÉÑ ÓÔÅÐÅÎÅÊ ¡ ÐÒÏÓÔÙÅ ÞÉÓÌÁ). âÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ ÎÏÍÅÒ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ-

ÓÔÉ ha, b, . . . , zi ÞÅÒÅÚ [a, b, . . . , z]. üÔÁ ÎÕÍÅÒÁÃÉÑ × ÎÅËÏÔÏÒÏÍ ÓÍÙÓÌÅ ÐÒÉ-

ÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. ëÏÎÅÞÎÏ, ÂÕË×ÁÌØÎÏ ÜÔÏ ÐÏÎÉÍÁÔØ ÎÅÌØÚÑ, ÔÁË ËÁË ÎÕ-

ÍÅÒÁÃÉÑ ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ ¥ÆÕÎËÃÉÀ Ó ÐÅÒÅÍÅÎÎÙÍ ÞÉÓÌÏÍ ÁÒÇÕÍÅÎÔÏ×¥.

îÏ ÒÁÚÎÙÅ Ó×ÑÚÁÎÎÙÅ Ó ÎÅÊ ÆÕÎËÃÉÉ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ. ÷ ÞÁÓÔÎÏÓÔÉ,

ÔÁËÏ×Ù ÆÕÎËÃÉÉ

• Length(x) = ÄÌÉÎÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x;

• Select(i, x) = i-ÙÊ ÞÌÅÎ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x;

• Append(x, y) = ÎÏÍÅÒ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ, ËÏÔÏÒÁÑ ÐÏÌÕÞÁÅÔÓÑ ÐÒÉÐÉ-

ÓÙ×ÁÎÉÅÍ ÞÉÓÌÁ y Ë ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x.

÷ÓÅ ÜÔÉ ÆÕÎËÃÉÉ (É ÄÒÕÇÉÅ ÁÎÁÌÏÇÉÞÎÙÅ) Ó×ÏÄÑÔÓÑ Ë ÒÁÚÌÉÞÎÙÍ ÏÐÅÒÁÃÉÑÍ Ó

ÐÒÏÓÔÙÍÉ ÞÉÓÌÁÍÉ É ÍÎÏÖÉÔÅÌÑÍÉ, ËÏÔÏÒÙÅ ÍÙ × ÓÕÝÎÏÓÔÉ ÕÖÅ ÒÁÚÂÉÒÁÌÉ.

ôÅÐÅÒØ ÍÙ ÄÏËÁÖÅÍ, ÞÔÏ ÆÕÎËÃÉÑ

x 7→ H(x) = [h(0), h(1), . . . , h(x)]

ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. ÷ ÓÁÍÏÍ ÄÅÌÅ, H(0) = [c], Á

H(k + 1) = Append(H(k), F (k + 1, Select(g(k + 1), H(k)))). 

§5. íÁÛÉÎÙ ôØÀÒÉÎÇÁ É ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ ÆÕÎË-

ÃÉÉ

íÙ ÒÁÓÓÍÏÔÒÅÌÉ ÎÅÓËÏÌØËÏ ÒÁÚÌÉÞÎÙÈ ÐÒÉ¾ÍÏ× ÐÏÓÔÒÏÅÎÉÑ ÐÒÉÍÉÔÉ×ÎÏ

ÒÅËÕÒÓÉ×ÎÙÈ ÆÕÎËÃÉÊ. ôÅÍ ÎÅ ÍÅÎÅÅ ÏÓÔÁ¾ÔÓÑ ÎÅ ×ÐÏÌÎÅ ÑÓÎÙÍ, ÎÁÓËÏÌØËÏ

ÜÔÏÔ ËÌÁÓÓ ÛÉÒÏË. óÅÊÞÁÓ ÍÙ ÐÏËÁÖÅÍ, ÞÔÏ ÏÎ ×ËÌÀÞÁÅÔ × ÓÅÂÑ ×ÓÅ ÄÏÓÔÁ-

ÔÏÞÎÏ ÂÙÓÔÒÏ ×ÙÞÉÓÌÉÍÙÅ ÆÕÎËÃÉÉ.

ôÅÏÒÅÍÁ 75. ìÀÂÁÑ ÆÕÎËÃÉÑ, ×ÙÞÉÓÌÉÍÁÑ ÎÁ ÍÁÛÉÎÅ ôØÀÒÉÎÇÁ ÎÅ ÂÏ-

ÌÅÅ ÞÅÍ ÚÁ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÅ (ÏÔ ÄÌÉÎÙ ×ÈÏÄÁ) ×ÒÅÍÑ, ÐÒÉÍÉÔÉ×ÎÏ

ÒÅËÕÒÓÉ×ÎÁ.

äÏËÁÚÁÔÅÌØÓÔ×Ï. îÁÐÏÍÎÉÍ, ÞÔÏ ÍÙ ÓÞÉÔÁÅÍ ×ÈÏÄÏÍ É ×ÙÈÏÄÏÍ ÍÁÛÉ-

ÎÙ ôØÀÒÉÎÇÁ ÓÌÏ×Á ÉÚ ÎÕÌÅÊ É ÅÄÉÎÉÃ. ðÏÓËÏÌØËÕ ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅ-

ÎÉÑÍÉ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÈ ÆÕÎËÃÉÊ Ñ×ÌÑÀÔÓÑ ÞÉÓÌÁ, ÔÅÏÒÅÍÁ ÂÕÄÅÔ

ÉÍÅÔØ ÓÍÙÓÌ, ÔÏÌØËÏ ÅÓÌÉ ÍÙ ÄÏÇÏ×ÏÒÉÍÓÑ ÏÔÏÖÄÅÓÔ×ÌÑÔØ ÞÉÓÌÁ É ÓÌÏ×Á.

ëÁË ÕÖÅ ÇÏ×ÏÒÉÌÏÓØ, ÍÙ ÏÔÏÖÄÅÓÔ×ÌÑÅÍ ÞÉÓÌÏ n ÓÏ ÓÌÏ×ÏÍ, ËÏÔÏÒÏÅ ÐÏÌÕÞÁ-

ÅÔÓÑ ÐÏÓÌÅ ÕÄÁÌÅÎÉÑ ÓÔÁÒÛÅÇÏ ÂÉÔÁ 1 × Ä×ÏÉÞÎÏÍ ÒÁÚÌÏÖÅÎÉÉ ÞÉÓÌÁ n + 1.