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

§3. íÁÛÉÎÙ ôØÀÒÉÎÇÁ: ÏÂÓÕÖÄÅÎÉÅ                                     177

ÑÎÉÅ Ñ×ÌÑÅÔÓÑ ÏÄÎÉÍ ÉÚ ÚÁËÌÀÞÉÔÅÌØÎÙÈ, ÒÁÂÏÔÁ ÍÁÛÉÎÙ ÚÁËÁÎÞÉ×ÁÅÔÓÑ.
ïÓÔÁ¾ÔÓÑ ÄÏÇÏ×ÏÒÉÔØÓÑ, ËÁË ÍÙ ÐÏÄÁ¾Í ÉÎÆÏÒÍÁÃÉÀ ÎÁ ×ÈÏÄ ÍÁÛÉÎÙ É ÞÔÏ
ÓÞÉÔÁÅÔÓÑ ÒÅÚÕÌØÔÁÔÏÍ Å¾ ÒÁÂÏÔÙ. âÕÄÅÍ ÓÞÉÔÁÔØ, ÞÔÏ ÁÌÆÁ×ÉÔ ÍÁÛÉÎÙ,
ÐÏÍÉÍÏ ÐÒÏÂÅÌÁ, ÓÏÄÅÒÖÉÔ ÓÉÍ×ÏÌÙ 0 É 1 (Á ÔÁËÖÅ, ×ÏÚÍÏÖÎÏ, Åݾ ËÁËÉÅ-ÔÏ
ÓÉÍ×ÏÌÙ). ÷ÈÏÄÏÍ É ×ÙÈÏÄÏÍ ÍÁÛÉÎÙ ÂÕÄÕÔ ËÏÎÅÞÎÙÅ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ
ÎÕÌÅÊ É ÅÄÉÎÉà (Ä×ÏÉÞÎÙÅ ÓÌÏ×Á). ÷ÈÏÄÎÏÅ ÓÌÏ×Ï ÚÁÐÉÓÙ×ÁÅÔÓÑ ÎÁ ÐÕÓÔÏÊ
ÌÅÎÔÅ, ÇÏÌÏ×ËÁ ÍÁÛÉÎÙ ÓÔÁ×ÉÔÓÑ × ÅÇÏ ÐÅÒ×ÕÀ ËÌÅÔËÕ, ÍÁÛÉÎÁ ÐÒÉ×ÏÄÉÔÓÑ
× ÎÁÞÁÌØÎÏÅ ÓÏÓÔÏÑÎÉÅ É ÚÁÐÕÓËÁÅÔÓÑ. åÓÌÉ ÍÁÛÉÎÁ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ, ÒÅ-
ÚÕÌØÔÁÔÏÍ ÓÞÉÔÁÅÔÓÑ Ä×ÏÉÞÎÏÅ ÓÌÏ×Ï, ËÏÔÏÒÏÅ ÍÏÖÎÏ ÐÒÏÞÅÓÔØ, ÎÁÞÉÎÁÑ Ó
ÐÏÚÉÃÉÉ ÇÏÌÏ×ËÉ É Ä×ÉÇÁÑÓØ ÎÁÐÒÁ×Ï (ÐÏËÁ ÎÅ ÐÏÑ×ÉÔÓÑ ÓÉÍ×ÏÌ, ÏÔÌÉÞÎÙÊ
ÏÔ 0 É 1).
   ôÁËÉÍ ÏÂÒÁÚÏÍ, ÌÀÂÁÑ ÍÁÛÉÎÁ ôØÀÒÉÎÇÁ ÚÁÄÁ¾Ô ÎÅËÏÔÏÒÕÀ ÞÁÓÔÉÞÎÕÀ
ÆÕÎËÃÉÀ ÎÁ Ä×ÏÉÞÎÙÈ ÓÌÏ×ÁÈ. ÷ÓÅ ÔÁËÉÅ ÆÕÎËÃÉÉ ÅÓÔÅÓÔ×ÅÎÎÏ ÎÁÚ×ÁÔØ ×Ù-
ÞÉÓÌÉÍÙÍÉ ÎÁ ÍÁÛÉÎÁÈ ôØÀÒÉÎÇÁ.


  §3. íÁÛÉÎÙ ôØÀÒÉÎÇÁ: ÏÂÓÕÖÄÅÎÉÅ
   òÁÚÕÍÅÅÔÓÑ, ÎÁÛÅ ÏÐÒÅÄÅÌÅÎÉÅ ÓÏÄÅÒÖÉÔ ÍÎÏÇÏ ËÏÎËÒÅÔÎÙÈ ÄÅÔÁÌÅÊ, ËÏ-
ÔÏÒÙÅ ÍÏÖÎÏ ÂÙÌÏ ÂÙ ÉÚÍÅÎÉÔØ. îÁÐÒÉÍÅÒ, ÌÅÎÔÁ ÍÏÖÅÔ ÂÙÔØ ÂÅÓËÏÎÅÞÎÏÊ
ÔÏÌØËÏ × ÏÄÎÕ ÓÔÏÒÏÎÕ. íÏÖÎÏ ÐÒÉÄÁÔØ ÍÁÛÉÎÅ Ä×Å ÌÅÎÔÙ. íÏÖÎÏ ÓÞÉÔÁÔØ,
ÞÔÏ ÍÁÛÉÎÁ ÍÏÖÅÔ ÌÉÂÏ ÎÁÐÉÓÁÔØ ÎÏ×ÙÊ ÓÉÍ×ÏÌ, ÌÉÂÏ ÓÄ×ÉÎÕÔØÓÑ, ÎÏ ÎÅ ÔÏ
É ÄÒÕÇÏÅ ×ÍÅÓÔÅ. íÏÖÎÏ ÏÇÒÁÎÉÞÉÔØ ÁÌÆÁ×ÉÔ, ÓÞÉÔÁÑ, ÓËÁÖÅÍ, ÞÔÏ × Î¾Í
ÄÏÌÖÎÏ ÂÙÔØ ÒÏ×ÎÏ 10 ÓÉÍ×ÏÌÏ×. íÏÖÎÏ ÐÏÔÒÅÂÏ×ÁÔØ, ÞÔÏÂÙ × ËÏÎÃÅ ÎÁ
ÌÅÎÔÅ ÎÉÞÅÇÏ ÎÅ ÂÙÌÏ, ËÒÏÍÅ ÒÅÚÕÌØÔÁÔÁ ÒÁÂÏÔÙ (ÏÓÔÁÌØÎÙÅ ËÌÅÔËÉ ÄÏÌÖ-
ÎÙ ÂÙÔØ ÐÕÓÔÙ). ÷ÓÅ ÐÅÒÅÞÉÓÌÅÎÎÙÅ É ÍÎÏÇÉÅ ÄÒÕÇÉÅ ÉÚÍÅÎÅÎÉÑ ÎÅ ÍÅÎÑÀÔ
ËÌÁÓÓÁ ×ÙÞÉÓÌÉÍÙÈ ÎÁ ÍÁÛÉÎÁÈ ôØÀÒÉÎÇÁ ÆÕÎËÃÉÊ. ëÏÎÅÞÎÏ, ÅÓÔØ É ÎÅÂÅ-
ÚÏÂÉÄÎÙÅ ÉÚÍÅÎÅÎÉÑ. îÁÐÒÉÍÅÒ, ÅÓÌÉ ÚÁÐÒÅÔÉÔØ ÍÁÛÉÎÅ Ä×ÉÇÁÔØÓÑ ÎÁÌÅ×Ï,
ÔÏ ÜÔÏ ÒÁÄÉËÁÌØÎÏ ÐÏÍÅÎÑÅÔ ÄÅÌÏ ¡ ÐÏ ÓÕÝÅÓÔ×Õ ÌÅÎÔÁ ÓÔÁÎÅÔ ÂÅÓÐÏÌÅÚÎÏÊ,
ÔÁË ËÁË Ë ÓÔÁÒÙÍ ÚÁÐÉÓÑÍ ÕÖÅ ÎÅÌØÚÑ ÂÕÄÅÔ ×ÅÒÎÕÔØÓÑ.
   ëÁË ÐÏÎÑÔØ, ËÁËÉÅ ÉÚÍÅÎÅÎÉÑ ÂÅÚÏÂÉÄÎÙ, Á ËÁËÉÅ ÎÅÔ? ÷ÉÄÉÍÏ, ÔÕÔ ÎÅÏÂ-
ÈÏÄÉÍ ÎÅËÏÔÏÒÙÊ ÏÐÙÔ ÐÒÁËÔÉÞÅÓËÏÇÏ ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÑ ÎÁ ÍÁÛÉÎÁÈ ôØÀ-
ÒÉÎÇÁ, ÈÏÔÑ ÂÙ ÎÅÂÏÌØÛÏÊ. ðÏÓÌÅ ÜÔÏÇÏ ÕÖÅ ÍÏÖÎÏ ÐÒÅÄÓÔÁ×ÌÑÔØ ÓÅÂÅ ×ÏÚ-
ÍÏÖÎÏÓÔÉ ÍÁÛÉÎÙ, ÎÅ ×ÙÐÉÓÙ×ÁÑ ÐÒÏÇÒÁÍÍÙ ÐÏÌÎÏÓÔØÀ, Á ÒÕËÏ×ÏÄÓÔ×ÕÑÓØ
ÌÉÛØ ÐÒÉÂÌÉÚÉÔÅÌØÎÙÍ ÏÐÉÓÁÎÉÅÍ. ÷ ËÁÞÅÓÔ×Å ÐÒÉÍÅÒÁ ÏÐÉÛÅÍ ÍÁÛÉÎÕ,
ËÏÔÏÒÁÑ ÕÄ×ÁÉ×ÁÅÔ ×ÈÏÄÎÏÅ ÓÌÏ×Ï (ÉÚÇÏÔÁ×ÌÉ×ÁÅÔ ÓÌÏ×Ï XX, ÅÓÌÉ ÎÁ ×ÈÏÄÅ
ÂÙÌÏ ÓÌÏ×Ï X).
   åÓÌÉ ÍÁÛÉÎÁ ×ÉÄÉÔ ÐÒÏÂÅÌ (×ÈÏÄÎÏÅ ÓÌÏ×Ï ÐÕÓÔÏ), ÏÎÁ ËÏÎÞÁÅÔ ÒÁÂÏÔÕ.
åÓÌÉ ÎÅÔ, ÏÎÁ ÚÁÐÏÍÉÎÁÅÔ ÔÅËÕÝÉÊ ÓÉÍ×ÏÌ É ÓÔÁ×ÉÔ ÐÏÍÅÔËÕ (× ÁÌÆÁ×ÉÔÅ
ÐÏÍÉÍÏ ÓÉÍ×ÏÌÏ× 0 É 1 ÂÕÄÕÔ Åݾ ÉÈ ¥ÐÏÍÅÞÅÎÎÙÅ ×ÁÒÉÁÎÔÙ¥ 0 É 1). úÁÔÅÍ