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

§6. ï ×Ù×ÏÄÁÈ É ÄÏËÁÚÁÔÅÌØÓÔ×ÁÈ                                       143

ÍÁÔÅÍÁÔÉËÉ ÐÒÏÞÌÉ ÉÈ ÓËÏÌØËÏ-ÎÉÂÕÄØ ÐÏÄÒÏÂÎÏ.¥
   çÏ×ÏÒÑ ÐÒÑÍÏ, ËÏÍÐØÀÔÅÒÎÕÀ ÞÁÓÔØ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÎÅ×ÏÚÍÏÖÎÏ ÐÒÏ×Å-
ÒÉÔØ ×ÒÕÞÎÕÀ, Á ÔÒÁÄÉÃÉÏÎÎÁÑ ÞÁÓÔØ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÄÌÉÎÎÁ É ÓÌÏÖÎÁ ÎÁ-
ÓÔÏÌØËÏ, ÞÔÏ ÅÅ ÎÉËÔÏ ÃÅÌÉËÏÍ É ÎÅ ÐÒÏ×ÅÒÑÌ. íÅÖÄÕ ÔÅÍ, ÄÏËÁÚÁÔÅÌØÓÔ×Ï,
ÎÅ ÐÏÄÄÁÀÝÅÅÓÑ ÐÒÏ×ÅÒËÅ, ÅÓÔØ ÎÏÎÓÅÎÓ. óÏÇÌÁÓÉÔØÓÑ Ó ÐÏÄÏÂÎÙÍ ÄÏËÁÚÁ-
ÔÅÌØÓÔ×ÏÍ ÏÚÎÁÞÁÅÔ ÐÒÉÍÅÒÎÏ ÔÏ ÖÅ, ÞÔÏ ÐÒÏÓÔÏ ÐÏ×ÅÒÉÔØ Á×ÔÏÒÁÍ. îÏ É
ÚÄÅÓØ ÎÅ ×ÓÅ ÔÁË ÐÒÏÓÔÏ.
   íÎÏÇÉÅ ÜÌÅÍÅÎÔÁÒÎÙÅ ÒÁÓÓÕÖÄÅÎÉÑ ¡ ÎÁÐÒÉÍÅÒ, ÆÏÒÍÕÌÁ üÊÌÅÒÁ Ï ÇÒÁ-
ÆÁÈ, ×ÈÏÄÑÝÁÑ × ÄÏËÁÚÁÔÅÌØÓÔ×Ï, ÏÓÎÏ×ÁÎÁ ÎÁ ÕÔ×ÅÒÖÄÅÎÉÑÈ ÔÉÐÁ: ¥ðÌÏÓËÉÊ
ÇÒÁÆ ÒÁÚÒÅÚÁÅÔ ÐÌÏÓËÏÓÔØ ÎÁ ÓÏ×ÏËÕÐÎÏÓÔØ D(G) ÎÅÐÅÒÅËÒÙ×ÁÀÝÉÈÓÑ ÍÎÏ-
ÇÏÕÇÏÌØÎÙÈ ÏÂÌÁÓÔÅÊ¥, ÞÔÏ ×ÒÏÄÅ ÂÙ ÎÅÔÒÕÄÎÏ ÐÒÏ×ÅÒÉÔØ, ×ÚÑ× ÌÉÓÔ ÂÕÍÁÇÉ
É ËÁÒÁÎÄÁÛ.. ë ÓÏÖÁÌÅÎÉÀ, ÜÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ ÎÅ ÐÒÉÎÁÄÌÅÖÉÔ Ë ÞÉÓÌÕ ÁËÓÉ-
ÏÍ ÉÌÉ ÛËÏÌØÎÙÈ ÔÅÏÒÅÍ ÐÌÏÓËÏÊ ÇÅÏÍÅÔÒÉÉ É ÅÇÏ ÎÕÖÎÏ ÄÏËÁÚÙ×ÁÔØ. óÏÏÔ-
×ÅÔÓÔ×ÕÀÝÁÑ ÔÅÏÒÅÍÁ, ÓÆÏÒÍÕÌÉÒÏ×ÁÎÎÁÑ öÏÒÄÁÎÏÍ, ÄÏËÁÚÙ×ÁÅÔÓÑ ÏÞÅÎØ
ÎÅÐÒÏÓÔÏ, ÏÄÎÁËÏ ÏÓÎÏ×ÎÙÅ ÔÒÕÄÎÏÓÔÉ Ó×ÑÚÁÎÙ Ó ÔÅÍ, ËÁË ÓÌÅÄÕÅÔ ÐÏÎÉÍÁÔØ
ÓÌÏ×Á ÔÉÐÁ ¥ÒÁÚÒÅÚÁÅÔ¥, ÉÎÔÕÉÔÉ×ÎÏ ×ÐÏÌÎÅ ÑÓÎÙÅ, ÎÏ Ó ÔÒÕÄÏÍ ÐÏÄÄÁÀ-
ÝÉÍÓÑ ÆÏÒÍÁÌÉÚÁÃÉÉ. ÷ Ó×ÅÔÅ ÜÔÏÇÏ ÚÁÍÅÞÁÎÉÑ ÓÔÁÎÏ×ÉÔÓÑ ÕÖÅ ÎÅ ÓÏ×ÓÅÍ
ÐÏÎÑÔÎÙÍ, ÄÏËÁÚÁÎÁ ÌÉ ÆÏÒÍÕÌÁ üÊÌÅÒÁ ÉÌÉ ÍÙ ÐÏ×ÅÒÉÌÉ ÐÒÁ×ÄÏÐÏÄÏÂÎÙÍ
ÒÁÓÓÕÖÄÅÎÉÑÍ, ÏÓÎÏ×ÁÎÎÙÍ ÎÁ ÉÎÔÕÉÔÉ×ÎÙÈ ÐÒÅÄÓÔÁ×ÌÅÎÉÑÈ Ï Ó×ÏÊÓÔ×ÁÈ
ÇÅÏÍÅÔÒÉÞÅÓËÉÈ ÆÉÇÕÒ.
   äÏÌÇÏÅ ×ÒÅÍÑ ÉÄÅÁÌÏÍ ÍÁÔÅÍÁÔÉÞÅÓËÏÊ ÓÔÒÏÇÏÓÔÉ ÂÙÌÉ ÆÏÒÍÕÌÉÒÏ×ËÉ
É ÄÏËÁÚÁÔÅÌØÓÔ×Á ü×ËÌÉÄÁ, × ËÏÔÏÒÙÈ ÏÓÕÝÅÓÔ×ÌÑÌÁÓØ ÐÒÏÇÒÁÍÍÁ ×Ù×ÏÄÁ
ÔÅÏÒÅÍ ÉÚ ÁËÓÉÏÍ ÐÏ ÏÐÒÅÄÅÌÅÎÎÙÍ ÐÒÁ×ÉÌÁÍ (ÔÁË ÎÁÚÙ×ÁÅÍÙÊ ÍÅÔÏÄ ÄÅ-
ÄÕËÃÉÉ, ÐÏÚ×ÏÌÑÀÝÉÊ ÐÏÌÕÞÁÔØ ÎÅÏÞÅ×ÉÄÎÙÅ ÕÔ×ÅÒÖÄÅÎÉÑ ÉÚ ÏÞÅ×ÉÄÎÙÈ
ÐÏÓÒÅÄÓÔ×ÏÍ ÒÑÄÁ Ñ×ÎÏ ÐÒÅÄßÑ×ÌÑÅÍÙÈ ÜÌÅÍÅÎÔÁÒÎÙÈ, ÏÞÅ×ÉÄÎÏ ÚÁËÏÎÎÙÈ,
ÕÍÏÚÁËÌÀÞÅÎÉÊ). üÔÏÔ ÏÂÒÁÚÅÃ ÓÔÒÏÇÏÓÔÉ É × ÎÁÛÅ ×ÒÅÍÑ ÎÅÄÏÓÔÉÖÉÍ ×
ËÕÒÓÅ ÛËÏÌØÎÏÊ ÍÁÔÅÍÁÔÉËÉ, ÎÏ ÄÌÑ ÓÏ×ÒÅÍÅÎÎÏÊ ÞÉÓÔÏÊ ÍÁÔÅÍÁÔÉËÉ ÓÔÁÎ-
ÄÁÒÔÙ ü×ËÌÉÄÁ ÎÅÄÏÓÔÁÔÏÞÎÙ. ü×ËÌÉÄ ÐÏ-×ÉÄÉÍÏÍÕ ÎÅ ÚÁÄÕÍÙ×ÁÌÓÑ Ï ÔÏÍ,
ÐÏÞÅÍÕ ÐÒÑÍÁÑ ÄÅÌÉÔ ÐÌÏÓËÏÓÔØ ÎÁ Ä×Å ÞÁÓÔÉ (É ÞÔÏ ÜÔÏ ÚÎÁÞÉÔ), ÏÎ ÎÅ ÏÐÒÅ-
ÄÅÌÑÌ ÐÏÎÑÔÉÑ ¥ÍÅÖÄÕ¥, ÓÞÉÔÁÑ ÜÔÏ ÐÏÎÑÔÉÅ ÏÞÅ×ÉÄÎÙÍ É Ô.Ä. (âÏÌØÛÁÑ
ÞÁÓÔØ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ÕÔ×ÅÒÖÄÅÎÉÊ ×ËÌÀÞÅÎÁ × ÁËÓÉÏÍÁÔÉËÕ ÇÅÏÍÅÔÒÉÉ
ÔÏÌØËÏ × ÐÏÓÌÅÄÎÀÀ ÓÏÔÎÀ ÌÅÔ). æÏÒÍÁÌØÎÙÅ ×Ù×ÏÄÙ ÉÚ ÎÏ×ÏÊ ÓÉÓÔÅÍÙ ÁË-
ÓÉÏÍ ÓÔÁÌÉ ÇÏÒÁÚÄÏ ÄÌÉÎÎÅÅ, ÞÅÍ × ÁÎÔÉÞÎÙÅ ×ÒÅÍÅÎÁ. ôÒÕÄÎÏ ÄÁÖÅ ×ÏÏÂÒÁ-
ÚÉÔØ ÄÌÉÎÕ ÐÏÌÎÏÇÏ ×Ù×ÏÄÁ ÆÏÒÍÕÌÙ üÊÌÅÒÁ × ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó ÓÏ×ÒÅÍÅÎÎÙ-
ÍÉ ÓÔÁÎÄÁÒÔÁÍÉ ÍÁÔÅÍÁÔÉÞÅÓËÏÊ ÌÏÇÉËÉ É ÓÉÓÔÅÍÙ ÁËÓÉÏÍ ÇÅÏÍÅÔÒÉÉ.
   îÏ ÞÔÏ ÓÏ×ÅÒÛÅÎÎÏ ÔÏÞÎÏ, ÔÁË ÜÔÏ ÔÏ, ÞÔÏ ÜÔÏ ÔÁËÏÅ ÒÁÓÓÕÖÄÅÎÉÅ ÎÉËÏÇÄÁ
ÎÅ ÂÙÌÏ ÐÒÏÄÅÌÁÎÏ ÉÚ-ÚÁ ÂÅÓÐÏÌÅÚÎÏÓÔÉ ÜÔÏÇÏ ÚÁÎÑÔÉÑ: ÆÏÒÍÁÌØÎÙÅ ×Ù×ÏÄÙ
ÐÒÁËÔÉÞÅÓËÉ ÎÅ ÐÏÄÄÁÀÔÓÑ ÐÒÏ×ÅÒËÅ × ÓÉÌÕ Ó×ÏÊÓÔ× ÞÅÌÏ×ÅÞÅÓËÏÊ ÐÓÉÈÉËÉ:
ÐÏÍÉÍÏ ÉÈ ÇÏÒÁÚÄÏ ÂÏÌØÛÅÊ (ÐÏ ÓÒÁ×ÎÅÎÉÀ Ó ÐÒÉ×ÙÞÎÙÍÉ ÒÁÓÓÕÖÄÅÎÉÑÍÉ)
ÄÌÉÎÙ ÉÈ ÓÏÚÎÁÔÅÌØÎÏÅ ÕÓ×ÏÅÎÉÅ ÉÄÅÔ ÇÏÒÁÚÄÏ ÍÅÄÌÅÎÎÅÅ. ðÏÜÔÏÍÕ ÏÂÙÞÎÏ