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

§2. íÁÛÉÎÙ ôØÀÒÉÎÇÁ É ÐÒÏÇÒÁÍÍÙ                                       183

ÐÒÉ ÄÅÌÅÎÉÉ ÎÁ 2, Á ÕÄÁÌÅÎÉÅ ×ÅÒÈÎÅÇÏ ÜÌÅÍÅÎÔÁ ÅÓÔØ ÄÅÌÅÎÉÅ ÎÁ 2 (Ó ÏÔÂÒÁ-
ÓÙ×ÁÎÉÅÍ ÏÓÔÁÔËÁ). äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÍÙ ×ÏÓÐÒÉÎÉÍÁÅÍ Ä×ÏÉÞÎÕÀ ÚÁÐÉÓØ
ÞÉÓÌÁ ËÁË ÓÔÅË, ×ÅÒÛÉÎÁ ËÏÔÏÒÏÇÏ ÎÁÈÏÄÉÔÓÑ ÓÐÒÁ×Á, Õ ÍÌÁÄÛÅÇÏ ÒÁÚÒÑÄÁ.
ôÏÞÎÏ ÔÁË ÖÅ ÍÏÖÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ n-ÉÞÎÕÀ ÓÉÓÔÅÍÕ ÓÞÉÓÌÅÎÉÑ É ÐÒÅÄÓÔÁ-
×ÉÔØ ÓÔÅË Ó n ×ÏÚÍÏÖÎÙÍÉ ÓÉÍ×ÏÌÁÍÉ × ËÁÖÄÏÊ ÐÏÚÉÃÉÉ.
   ôÅÐÅÒØ ÏÓÎÏ×ÎÏÊ ÃÉËÌ ÍÁÛÉÎÙ ôØÀÒÉÎÇÁ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÁË ÐÒÏÇÒÁÍ-
ÍÕ, ÏÐÅÒÉÒÕÀÝÕÀ Ó ÕËÁÚÁÎÎÙÍÉ ÞÅÔÙÒØÍÑ ÞÉÓÌÁÍÉ (ÓÉÍ×ÏÌ, ÓÏÓÔÏÑÎÉÅ, ÌÅ-
×ÙÊ ÓÔÅË É ÐÒÁ×ÙÊ ÓÔÅË) ¡ ÂÅÚ ÏÓÏÂÙÈ ÈÉÔÒÏÓÔÅÊ. îÏ ÎÅÓËÏÌØËÏ ×ÅÝÅÊ
×Ó¾-ÔÁËÉ ÎÁÄÏ ÉÍÅÔØ × ×ÉÄÕ.
   ÷Ï-ÐÅÒ×ÙÈ, ÓÔÅËÉ ËÏÎÅÞÎÙ, Á ÌÅÎÔÁ ÂÅÓËÏÎÅÞÎÁ ¡ ÍÙ ÄÏÌÖÎÙ ÄÏÇÏ×Ï-
ÒÉÔØÓÑ, ÞÔÏ ÅÓÌÉ ÓÔÅË ÏÐÕÓÔÏÛÁÅÔÓÑ, ÔÏ × ÎÅÇÏ Á×ÔÏÍÁÔÉÞÅÓËÉ ÄÏÂÁ×ÌÑÅÔÓÑ
ÓÉÍ×ÏÌ ÐÒÏÂÅÌÁ. ôÅÍ ÓÁÍÙÍ ÂÅÓËÏÎÅÞÎÙÊ ÐÕÓÔÏÊ È×ÏÓÔ ÌÅÎÔÙ ÍÏÖÅÔ ÐÒÉ-
ÓÕÔÓÔ×Ï×ÁÔØ × ÓÔÅËÅ, ËÁË ÔÅÐÅÒØ ÇÏ×ÏÒÑÔ, ×ÉÒÔÕÁÌØÎÏ.
   ÷Ï-×ÔÏÒÙÈ, ÎÁÐÏÍÎÉÍ, ÞÔÏ ÍÙ ÄÏÇÏ×ÏÒÉÌÉÓØ ÏÔÏÖÄÅÓÔ×ÌÑÔØ Ä×ÏÉÞÎÙÅ
ÓÌÏ×Á (ËÏÔÏÒÙÅ ÐÏÄÁÀÔÓÑ ÎÁ ×ÈÏÄ ÍÁÛÉÎÙ ôØÀÒÉÎÇÁ) É ÉÈ ËÏÄÙ (ËÏÔÏÒÙÅ
ÈÒÁÎÑÔÓÑ × ÐÅÒÅÍÅÎÎÙÈ ÎÁÛÅÊ ÐÒÏÇÒÁÍÍÙ). ðÏÜÔÏÍÕ, ÐÏÌÕÞÉ× ËÏÄ ×ÈÏÄÎÏ-
ÇÏ ÓÌÏ×Á, ÎÁÄÏ ÅÇÏ ÒÁÚÏÂÒÁÔØ ÐÏ ÓÉÍ×ÏÌÁÍ É ÐÏÌÏÖÉÔØ ÜÔÉ ÓÉÍ×ÏÌÙ ÏÄÉÎ
ÚÁ ÄÒÕÇÉÍ × ÓÔÅË (ÏÓÎÏ×ÁÎÉÑ ÓÉÓÔÅÍ ÓÞÉÓÌÅÎÉÑ ÒÁÚÎÙÅ, ÔÁË ÞÔÏ ÐÒÏÓÔÏ ÔÁË
ÐÅÒÅÐÉÓÁÔØ ÜÔÏ ÎÅÌØÚÑ). áÎÁÌÏÇÉÞÎÙÅ ÐÒÏÂÌÅÍÙ ×ÏÚÎÉËÁÀÔ É ÐÒÉ ÐÒÅ×ÒÁÝÅ-
ÎÉÉ ×ÙÈÏÄÁ (ÞÁÓÔÉ ÓÏÄÅÒÖÉÍÏÇÏ ÐÒÁ×ÏÇÏ ÓÔÅËÁ) × ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÅ ÞÉÓÌÏ,
ÎÏ ×ÓÅ ÏÎÉ ÌÅÇËÏ ÐÒÅÏÄÏÌÉÍÙ, É ÍÙ ÎÅ ÂÕÄÅÍ ×ÄÁ×ÁÔØÓÑ × ÐÏÄÒÏÂÎÏÓÔÉ.
  ÷ÅÒÎÏ É ÏÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ:
   ôÅÏÒÅÍÁ 70. ÷ÓÑËÁÑ ÆÕÎËÃÉÑ, ×ÙÞÉÓÌÉÍÁÑ ÐÒÏÇÒÁÍÍÏÊ Ó ËÏÎÅÞÎÙÍ ÞÉ-
ÓÌÏÍ ÐÅÒÅÍÅÎÎÙÈ, ×ÙÞÉÓÌÉÍÁ ÎÁ ÍÁÛÉÎÅ ôØÀÒÉÎÇÁ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. îÁÍ ÎÁÄÏ ÍÏÄÅÌÉÒÏ×ÁÔØ ÐÏ×ÅÄÅÎÉÅ ÐÒÏÇÒÁÍÍÙ Ó ÐÏÍÏ-
ÝØÀ ÍÁÛÉÎÙ ôØÀÒÉÎÇÁ. âÕÄÅÍ ÓÞÉÔÁÔØ, ÞÔÏ ÚÎÁÞÅÎÉÑ ÐÅÒÅÍÅÎÎÙÈ ÚÁÐÉ-
ÓÁÎÙ ÎÁ ÌÅÎÔÅ (× Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ) É ÒÁÚÄÅÌÅÎÙ ÓÐÅÃÉÁÌØÎÙÍ ÒÁÚÄÅÌÉ-
ÔÅÌØÎÙÍ ÓÉÍ×ÏÌÏÍ. ôÏÇÄÁ ÍÁÛÉÎÁ ÍÏÖÅÔ ÎÁÊÔÉ ÌÀÂÕÀ ÐÅÒÅÍÅÎÎÕÀ, ÉÄÑ
ÏÔ ÎÁÞÁÌÁ ÌÅÎÔÙ É ÓÞÉÔÁÑ ÒÁÚÄÅÌÉÔÅÌØÎÙÅ ÓÉÍ×ÏÌÙ, ÓÄÅÌÁÔØ ÞÔÏ-ÔÏ Ó ÜÔÏÊ
ÐÅÒÅÍÅÎÎÏÊ É ÚÁÔÅÍ ×ÅÒÎÕÔØÓÑ ÏÂÒÁÔÎÏ × ÎÁÞÁÌÏ. (îÅÔ ÎÅÏÂÈÏÄÉÍÏÓÔÉ ÚÁÐÉ-
ÓÙ×ÁÔØ ÎÁ ÌÅÎÔÅ ÎÏÍÅÒ ÉÓÐÏÌÎÑÅÍÏÊ ËÏÍÁÎÄÙ, ÐÏÓËÏÌØËÕ ËÏÍÁÎÄ ËÏÎÅÞÎÏÅ
ÞÉÓÌÏ É ÍÁÛÉÎÁ ÍÏÖÅÔ ÐÏÍÎÉÔØ ÎÏÍÅÒ ÔÅËÕÝÅÊ ËÏÍÁÎÄÙ ËÁË ÞÁÓÔØ Ó×ÏÅÇÏ
ÓÏÓÔÏÑÎÉÑ.) ïÐÅÒÁÃÉÉ ÐÒÉÂÁ×ÌÅÎÉÑ É ×ÙÞÉÔÁÎÉÑ ÅÄÉÎÉÃÙ ÔÁËÖÅ ÌÅÇËÏ ×Ù-
ÐÏÌÎÉÍÙ × Ä×ÏÉÞÎÏÊ ÚÁÐÉÓÉ (ÅÓÌÉ ÉÄÔÉ ÓÐÒÁ×Á ÎÁÌÅ×Ï). îÁÄÏ ÔÏÌØËÏ ÉÍÅÔØ ×
×ÉÄÕ, ÞÔÏ ÒÁÚÍÅÒ ÞÉÓÌÁ ÍÏÖÅÔ Õ×ÅÌÉÞÉÔØÓÑ, É ÔÏÇÄÁ ÎÕÖÎÏ ÄÌÑ ÎÅÇÏ ÏÓ×ÏÂÏ-
ÄÉÔØ ÍÅÓÔÏ, ÓÄ×ÉÎÕ× ×ÓÅ ÓÉÍ×ÏÌÙ ÓÐÒÁ×Á ÏÔ ÇÏÌÏ×ËÉ ÎÁ ÏÄÎÕ ÐÏÚÉÃÉÀ. (ðÒÉ
ÕÍÅÎØÛÅÎÉÉ ÎÕÖÎÏ ÓÄ×ÉÎÕÔØ ×ÌÅ×Ï.) ñÓÎÏ, ÞÔÏ ÜÔÏ ÔÁËÖÅ ÌÅÇËÏ ×ÙÐÏÌÎÉÔØ
Ó ÐÏÍÏÝØÀ ÍÁÛÉÎÙ ôØÀÒÉÎÇÁ.