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

§6. ôÅÏÒÅÍÁ ëÁÎÔÏÒÁ                                                   25

   • îÉ A ÎÅ ÒÁ×ÎÏÍÏÝÎÏ ÎÉËÁËÏÊ ÞÁÓÔÉ B, ÎÉ B ÎÅ ÒÁ×ÎÏÍÏÝÎÏ ÎÉËÁËÏÊ
     ÞÁÓÔÉ A. (üÔÏÔ ÓÌÕÞÁÊ ÎÁ ÓÁÍÏÍ ÄÅÌÅ ÎÅ×ÏÚÍÏÖÅÎ).
  úÁÄÁÞÁ 47. äÏËÁÖÉÔÅ, ÞÔÏ ÓÞ¾ÔÎÏÅ ÍÎÏÖÅÓÔ×Ï ÉÍÅÅÔ ÍÅÎØÛÕÀ
ÍÏÝÎÏÓÔØ, ÞÅÍ ÌÀÂÏÅ ÎÅÓÞ¾ÔÎÏÅ.
  úÁÄÁÞÁ 48. ðÒÏ×ÅÒØÔÅ ÁËËÕÒÁÔÎÏ, ÞÔÏ ÅÓÌÉ A ÉÍÅÅÔ ÍÅÎØÛÕÀ ÍÏÝ-
ÎÏÓÔØ, ÞÅÍ B, Á B ÉÍÅÅÔ ÍÅÎØÛÕÀ ÍÏÝÎÏÓÔØ, ÞÅÍ C, ÔÏ A ÉÍÅÅÔ ÍÅÎØ-
ÛÕÀ ÍÏÝÎÏÓÔØ, ÞÅÍ C (ÔÒÁÎÚÉÔÉ×ÎÏÓÔØ ÓÒÁ×ÎÅÎÉÑ ÍÏÝÎÏÓÔÅÊ).
   úÁÍÅÔÉÍ, ÞÔÏ ÍÙ ÕÖÅ ÄÏÌÇÏ ÇÏ×ÏÒÉÍ Ï ÓÒÁ×ÎÅÎÉÉ ÍÏÝÎÏÓÔÅÊ, ÎÏ ×ÏÚÄÅÒ-
ÖÉ×ÁÅÍÓÑ ÏÔ ÕÐÏÍÉÎÁÎÉÑ ÍÏÝÎÏÓÔÉ ÍÎÏÖÅÓÔ×Á ËÁË ÓÁÍÏÓÔÏÑÔÅÌØÎÏÇÏ ÏÂß-
ÅËÔÁ, Á ÔÏÌØËÏ ÓÒÁ×ÎÉ×ÁÅÍ ÍÏÝÎÏÓÔÉ ÒÁÚÎÙÈ ÍÎÏÖÅÓÔ×. ÷ ÐÒÉÎÃÉÐÅ ÍÏÖÎÏ
ÂÙÌÏ ÂÙ ÏÐÒÅÄÅÌÉÔØ ÍÏÝÎÏÓÔØ ÍÎÏÖÅÓÔ×Á A ËÁË ËÌÁÓÓ ×ÓÅÈ ÍÎÏÖÅÓÔ×, ÒÁ×-
ÎÏÍÏÝÎÙÈ A. ôÁËÉÅ ËÌÁÓÓÙ ÄÌÑ ÍÎÏÖÅÓÔ× A É B ÓÏ×ÐÁÄÁÀÔ × ÔÏÍ É ÔÏÌØËÏ
ÔÏÍ ÓÌÕÞÁÅ, ËÏÇÄÁ A É B ÒÁ×ÎÏÍÏÝÎÙ, ÔÁË ÞÔÏ ÓÌÏ×Á ÉÍÅÀÔ ÒÁ×ÎÕÀ ÍÏÝ-
ÎÏÓÔØ ÐÒÉÏÂÒÅÌÉ ÂÙ ÂÕË×ÁÌØÎÙÊ ÓÍÙÓÌ. ðÒÏÂÌÅÍÁ ÔÕÔ × ÔÏÍ, ÞÔÏ ÔÁËÉÈ
ÍÎÏÖÅÓÔ× (ÒÁ×ÎÏÍÏÝÎÙÈ ÍÎÏÖÅÓÔ×Õ A) ÓÌÉÛËÏÍ ÍÎÏÇÏ, ÐÏÓËÏÌØËÕ ×Ó¾ ÎÁ
Ó×ÅÔÅ ÍÏÖÅÔ ÂÙÔØ ÉÈ ÜÌÅÍÅÎÔÁÍÉ. éÈ ÎÁÓËÏÌØËÏ ÍÎÏÇÏ, ÞÔÏ ÏÂÒÁÚÏ×ÁÔØ ÉÚ
ÎÉÈ ÍÎÏÖÅÓÔ×Ï ÚÁÔÒÕÄÎÉÔÅÌØÎÏ, ÜÔÏ ÍÏÖÅÔ ÐÒÉ×ÅÓÔÉ Ë ÐÁÒÁÄÏËÓÁÍ (ÓÍ. ÒÁÚ-
ÄÅÌ 6, Ó. 28).
   éÚ ÜÔÏÊ ÓÉÔÕÁÃÉÉ ÅÓÔØ ÎÅÓËÏÌØËÏ ×ÙÈÏÄÏ×. óÁÍÙÊ ÐÒÏÓÔÏÊ ¡ ÐÏ-ÐÒÅÖ-
ÎÅÍÕ ÇÏ×ÏÒÉÔØ ÔÏÌØËÏ Ï ÓÒÁ×ÎÅÎÉÉ ÍÏÝÎÏÓÔÅÊ, ÎÏ ÎÅ Ï ÓÁÍÉÈ ÍÏÝÎÏÓÔÑÈ.
íÏÖÎÏ ÔÁËÖÅ ××ÅÓÔÉ ÐÏÎÑÔÉÅ ËÌÁÓÓÁ ¡ ÔÁËÏÊ ÂÏÌØÛÏÊ ÓÏ×ÏËÕÐÎÏÓÔÉ ÏÂß-
ÅËÔÏ×, ÞÔÏ Å¾ ÕÖÅ ÎÅÌØÚÑ ÓÞÉÔÁÔØ ÜÌÅÍÅÎÔÏÍ ÄÒÕÇÉÈ ÓÏ×ÏËÕÐÎÏÓÔÅÊ (ÅÓÌÉ ×Ù
ÐÏÎÉÍÁÅÔÅ, Ï Þ¾Í Ñ ÔÕÔ ÔÏÌËÕÀ), É ÓÞÉÔÁÔØ ÍÏÝÎÏÓÔØÀ ÍÎÏÖÅÓÔ×Á A ËÌÁÓÓ
×ÓÅÈ ÍÎÏÖÅÓÔ×, ÒÁ×ÎÏÍÏÝÎÙÈ A. åݾ ÏÄÉÎ ×ÙÈÏÄ ¡ ÄÌÑ ËÁÖÄÏÇÏ A ×ÙÂÒÁÔØ
ÎÅËÏÔÏÒÏÅ ÓÔÁÎÄÁÒÔÎÏÅ ÍÎÏÖÅÓÔ×Ï, ÒÁ×ÎÏÍÏÝÎÏÅ A, É ÎÁÚ×ÁÔØ ÅÇÏ ÍÏÝÎÏ-
ÓÔØÀ ÍÎÏÖÅÓÔ×Á A. ïÂÙÞÎÏ × ËÁÞÅÓÔ×Å ÓÔÁÎÄÁÒÔÎÏÇÏ ÍÎÏÖÅÓÔ×Á ÂÅÒÕÔ ÍÉ-
ÎÉÍÁÌØÎÙÊ ÏÒÄÉÎÁÌ, ÒÁ×ÎÏÍÏÝÎÙÊ A, ¡ ÎÏ ÜÔÏ ÐÏÓÔÒÏÅÎÉÅ ÕÖÅ ÔÒÅÂÕÅÔ
ÂÏÌÅÅ ÆÏÒÍÁÌØÎÏÇÏ (ÁËÓÉÏÍÁÔÉÞÅÓËÏÇÏ) ÐÏÓÔÒÏÅÎÉÑ ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ×.
   ôÁË ÉÌÉ ÉÎÁÞÅ, ÍÙ ÂÕÄÅÍ ÕÐÏÔÒÅÂÌÑÔØ ÏÂÏÚÎÁÞÅÎÉÅ |A| ÄÌÑ ÍÏÝÎÏÓÔÉ
ÍÎÏÖÅÓÔ×Á A ÈÏÔÑ ÂÙ ËÁË ×ÏÌØÎÏÓÔØ ÒÅÞÉ: |A| = |B| ÏÚÎÁÞÁÅÔ, ÞÔÏ ÍÎÏÖÅÓÔ×Á
A É B ÒÁ×ÎÏÍÏÝÎÙ; |A| 6 |B| ÏÚÎÁÞÁÅÔ, ÞÔÏ A ÒÁ×ÎÏÍÏÝÎÏ ÎÅËÏÔÏÒÏÍÕ
ÐÏÄÍÎÏÖÅÓÔ×Õ ÍÎÏÖÅÓÔ×Á B, Á |A| < |B| ÏÚÎÁÞÁÅÔ, ÞÔÏ A ÉÍÅÅÔ ÍÅÎØÛÕÀ
ÍÏÝÎÏÓÔØ, ÞÅÍ B (ÓÍ. Ó. 24).


  §6. ôÅÏÒÅÍÁ ëÁÎÔÏÒÁ
  ëÌÁÓÓÉÞÅÓËÉÊ ÐÒÉÍÅÒ ÎÅÒÁ×ÎÏÍÏÝÎÙÈ ÂÅÓËÏÎÅÞÎÙÈ ÍÎÏÖÅÓÔ× (ÄÏ ÓÉÈ ÐÏÒ
ÔÁËÏÇÏ ÐÒÉÍÅÒÁ Õ ÎÁÓ ÎÅ ÂÙÌÏ!) ÄÁ¾Ô ÄÉÁÇÏÎÁÌØÎÁÑ ËÏÎÓÔÒÕËÃÉÑ ëÁÎÔÏÒÁ.