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

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Составители: 

Рубрика: 

§2. éÚÏÍÏÒÆÉÚÍÙ 47
ÐÒÉ ×ÓÅÈ i. äÏËÁÖÉÔÅ, ÞÔÏ ÜÔÏ ÍÎÏÖÅÓÔ×Ï ÉÚÏÍÏÒÆÎÏ ÍÎÏÖÅÓÔ×Õ ×ÓÅÈ
ÐÏÌÏÖÉÔÅÌØÎÙÈ ÃÅÌÙÈ ÞÉÓÅÌ Ó ÏÔÎÏÛÅÎÉÅÍ ÂÙÔØ ÄÅÌÉÔÅÌÅÍ × ËÁÞÅÓÔ×Å
ÐÏÒÑÄËÁ.
÷ÚÁÉÍÎÏ ÏÄÎÏÚÎÁÞÎÏÅ ÏÔÏÂÒÁÖÅÎÉÅ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅ-
ÓÔ×Á A × ÓÅÂÑ, Ñ×ÌÑÀÝÅÅÓÑ ÉÚÏÍÏÒÆÉÚÍÏÍ, ÎÁÚÙ×ÁÀÔ Á×ÔÏÍÏÒÆÉÚÍÏÍ ÞÁ-
ÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á A. ôÏÖÄÅÓÔ×ÅÎÎÏÅ ÏÔÏÂÒÁÖÅÎÉÅ ×ÓÅÇÄÁ
Ñ×ÌÑÅÔÓÑ Á×ÔÏÍÏÒÆÉÚÍÏÍ, ÎÏ ÄÌÑ ÎÅËÏÔÏÒÙÈ ÍÎÏÖÅÓÔ× ÓÕÝÅÓÔ×ÕÀÔ É ÄÒÕÇÉÅ
Á×ÔÏÍÏÒÆÉÚÍÙ. îÁÐÒÉÍÅÒ, ÏÔÏÂÒÁÖÅÎÉÅ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ (x 7→ x + 1)
Ñ×ÌÑÅÔÓÑ Á×ÔÏÍÏÒÆÉÚÍÏÍ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á Z ÃÅÌÙÈ ÞÉ-
ÓÅÌ (Ó ÅÓÔÅÓÔ×ÅÎÎÙÍ ÐÏÒÑÄËÏÍ). äÌÑ ÍÎÏÖÅÓÔ×Á ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ ÔÁ ÖÅ
ÆÏÒÍÕÌÁ ÎÅ ÄÁ¾Ô Á×ÔÏÍÏÒÆÉÚÍÁ (ÎÅÔ ×ÚÁÉÍÎÏÊ ÏÄÎÏÚÎÁÞÎÏÓÔÉ).
úÁÄÁÞÁ 88. ðÏËÁÖÉÔÅ, ÞÔÏ ÎÅ ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍÁ ÕÐÏÒÑÄÏ-
ÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á N ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ, ÏÔÌÉÞÎÏÇÏ ÏÔ ÔÏÖÄÅÓÔ×ÅÎÎÏ-
ÇÏ.
úÁÄÁÞÁ 89. òÁÓÓÍÏÔÒÉÍ ÍÎÏÖÅÓÔ×Ï P (A) ×ÓÅÈ ÐÏÄÍÎÏÖÅÓÔ× ÎÅËÏÔÏ-
ÒÏÇÏ k-ÜÌÅÍÅÎÔÎÏÇÏ ÍÎÏÖÅÓÔ×Á A, ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÐÏ ×ËÌÀÞÅ-
ÎÉÀ. îÁÊÄÉÔÅ ÞÉÓÌÏ Á×ÔÏÍÏÒÆÉÚÍÏ× ÜÔÏÇÏ ÍÎÏÖÅÓÔ×Á.
úÁÄÁÞÁ 90. ðÏËÁÖÉÔÅ, ÞÔÏ ÍÎÏÖÅÓÔ×Ï ÃÅÌÙÈ ÐÏÌÏÖÉÔÅÌØÎÙÈ ÞÉÓÅÌ,
ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÏÔÎÏÛÅÎÉÅÍ x ÄÅÌÉÔ y, ÉÍÅÅÔ ËÏÎÔÉÎÕÕÍ ÒÁÚ-
ÌÉÞÎÙÈ Á×ÔÏÍÏÒÆÉÚÍÏ×.
÷ÏÔ ÎÅÓËÏÌØËÏ ÐÒÉÍÅÒÏ× ÒÁ×ÎÏÍÏÝÎÙÈ, ÎÏ ÎÅ ÉÚÏÍÏÒÆÎÙÈ ÌÉÎÅÊÎÏ ÕÐÏ-
ÒÑÄÏÞÅÎÎÙÈ ÍÎÏÖÅÓÔ× (× ÓÉÌÕ ÔÅÏÒÅÍÙ 12 ÏÎÉ ÄÏÌÖÎÙ ÂÙÔØ ÂÅÓËÏÎÅÞÎÙÍÉ).
• ïÔÒÅÚÏË [0, 1] (Ó ÏÂÙÞÎÙÍ ÏÔÎÏÛÅÎÉÅÍ ÐÏÒÑÄËÁ) ÎÅ ÉÚÏÍÏÒÆÅÎ ÍÎÏÖÅ-
ÓÔ×Õ R, ÔÁË ËÁË Õ ÐÅÒ×ÏÇÏ ÅÓÔØ ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ, Á Õ ×ÔÏÒÏÇÏ ÎÅÔ.
(ðÒÉ ÉÚÏÍÏÒÆÉÚÍÅ ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ, ÅÓÔÅÓÔ×ÅÎÎÏ, ÄÏÌÖÅÎ ÓÏÏÔ×ÅÔ-
ÓÔ×Ï×ÁÔØ ÎÁÉÂÏÌØÛÅÍÕ.)
• íÎÏÖÅÓÔ×Ï Z (ÃÅÌÙÅ ÞÉÓÌÁ Ó ÏÂÙÞÎÙÍ ÐÏÒÑÄËÏÍ) ÎÅ ÉÚÏÍÏÒÆÎÏ ÍÎÏÖÅ-
ÓÔ×Õ Q (ÒÁÃÉÏÎÁÌØÎÙÅ ÞÉÓÌÁ). ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ α: Z → Q Ñ×ÌÑÅÔÓÑ
ÉÚÏÍÏÒÆÉÚÍÏÍ. ÷ÏÚØÍ¾Í Ä×Á ÓÏÓÅÄÎÉÈ ÃÅÌÙÈ ÞÉÓÌÁ, ÓËÁÖÅÍ, 2 É 3. ðÒÉ
ÉÚÏÍÏÒÆÉÚÍÅ α ÉÍ ÄÏÌÖÎÙ ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÔØ ËÁËÉÅ-ÔÏ Ä×Á ÒÁÃÉÏÎÁÌØ-
ÎÙÈ ÞÉÓÌÁ α(2) É α(3), ÐÒÉÞ¾Í α(2) < α(3), ÔÁË ËÁË 2 < 3. îÏ ÔÏÇÄÁ
ÒÁÃÉÏÎÁÌØÎÙÍ ÞÉÓÌÁÍ ÍÅÖÄÕ α(2) É α(3) ÄÏÌÖÎÙ ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÔØ
ÃÅÌÙÅ ÞÉÓÌÁ ÍÅÖÄÕ 2 É 3, ËÏÔÏÒÙÈ ÎÅÔ.
• âÏÌÅÅ ÓÌÏÖÎÙÊ ÐÒÉÍÅÒ ¡ ÍÎÏÖÅÓÔ×Á Z É Z + Z. ÷ÏÚØÍ¾Í × Z + Z
Ä×Å ËÏÐÉÉ ÎÕÌÑ (ÉÚ ÔÏÊ É ÄÒÕÇÏÊ ËÏÍÐÏÎÅÎÔÙ); ÍÙ ÏÂÏÚÎÁÞÁÌÉ ÉÈ 0
É
0. ðÒÉ ÜÔÏÍ 0 < 0. ðÒÉ ÉÚÏÍÏÒÆÉÚÍÅ ÉÍ ÄÏÌÖÎÙ ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÔØ
Ä×Á ÃÅÌÙÈ ÞÉÓÌÁ a É b, ÄÌÑ ËÏÔÏÒÙÈ a < b. ôÏÇÄÁ ×ÓÅÍ ÜÌÅÍÅÎÔÁÍ
§2. éÚÏÍÏÒÆÉÚÍÙ                                                      47

ÐÒÉ ×ÓÅÈ i. äÏËÁÖÉÔÅ, ÞÔÏ ÜÔÏ ÍÎÏÖÅÓÔ×Ï ÉÚÏÍÏÒÆÎÏ ÍÎÏÖÅÓÔ×Õ ×ÓÅÈ
ÐÏÌÏÖÉÔÅÌØÎÙÈ ÃÅÌÙÈ ÞÉÓÅÌ Ó ÏÔÎÏÛÅÎÉÅÍ ÂÙÔØ ÄÅÌÉÔÅÌÅÍ × ËÁÞÅÓÔ×Å
ÐÏÒÑÄËÁ.

   ÷ÚÁÉÍÎÏ ÏÄÎÏÚÎÁÞÎÏÅ ÏÔÏÂÒÁÖÅÎÉÅ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅ-
ÓÔ×Á A × ÓÅÂÑ, Ñ×ÌÑÀÝÅÅÓÑ ÉÚÏÍÏÒÆÉÚÍÏÍ, ÎÁÚÙ×ÁÀÔ Á×ÔÏÍÏÒÆÉÚÍÏÍ ÞÁ-
ÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á A. ôÏÖÄÅÓÔ×ÅÎÎÏÅ ÏÔÏÂÒÁÖÅÎÉÅ ×ÓÅÇÄÁ
Ñ×ÌÑÅÔÓÑ Á×ÔÏÍÏÒÆÉÚÍÏÍ, ÎÏ ÄÌÑ ÎÅËÏÔÏÒÙÈ ÍÎÏÖÅÓÔ× ÓÕÝÅÓÔ×ÕÀÔ É ÄÒÕÇÉÅ
Á×ÔÏÍÏÒÆÉÚÍÙ. îÁÐÒÉÍÅÒ, ÏÔÏÂÒÁÖÅÎÉÅ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ (x 7→ x + 1)
Ñ×ÌÑÅÔÓÑ Á×ÔÏÍÏÒÆÉÚÍÏÍ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á Z ÃÅÌÙÈ ÞÉ-
ÓÅÌ (Ó ÅÓÔÅÓÔ×ÅÎÎÙÍ ÐÏÒÑÄËÏÍ). äÌÑ ÍÎÏÖÅÓÔ×Á ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ ÔÁ ÖÅ
ÆÏÒÍÕÌÁ ÎÅ ÄÁ¾Ô Á×ÔÏÍÏÒÆÉÚÍÁ (ÎÅÔ ×ÚÁÉÍÎÏÊ ÏÄÎÏÚÎÁÞÎÏÓÔÉ).
   úÁÄÁÞÁ 88. ðÏËÁÖÉÔÅ, ÞÔÏ ÎÅ ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍÁ ÕÐÏÒÑÄÏ-
ÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á N ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ, ÏÔÌÉÞÎÏÇÏ ÏÔ ÔÏÖÄÅÓÔ×ÅÎÎÏ-
ÇÏ.
   úÁÄÁÞÁ 89. òÁÓÓÍÏÔÒÉÍ ÍÎÏÖÅÓÔ×Ï P (A) ×ÓÅÈ ÐÏÄÍÎÏÖÅÓÔ× ÎÅËÏÔÏ-
ÒÏÇÏ k-ÜÌÅÍÅÎÔÎÏÇÏ ÍÎÏÖÅÓÔ×Á A, ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÐÏ ×ËÌÀÞÅ-
ÎÉÀ. îÁÊÄÉÔÅ ÞÉÓÌÏ Á×ÔÏÍÏÒÆÉÚÍÏ× ÜÔÏÇÏ ÍÎÏÖÅÓÔ×Á.
  úÁÄÁÞÁ 90. ðÏËÁÖÉÔÅ, ÞÔÏ ÍÎÏÖÅÓÔ×Ï ÃÅÌÙÈ ÐÏÌÏÖÉÔÅÌØÎÙÈ ÞÉÓÅÌ,
ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÏÔÎÏÛÅÎÉÅÍ x ÄÅÌÉÔ y, ÉÍÅÅÔ ËÏÎÔÉÎÕÕÍ ÒÁÚ-
ÌÉÞÎÙÈ Á×ÔÏÍÏÒÆÉÚÍÏ×.
  ÷ÏÔ ÎÅÓËÏÌØËÏ ÐÒÉÍÅÒÏ× ÒÁ×ÎÏÍÏÝÎÙÈ, ÎÏ ÎÅ ÉÚÏÍÏÒÆÎÙÈ ÌÉÎÅÊÎÏ ÕÐÏ-
ÒÑÄÏÞÅÎÎÙÈ ÍÎÏÖÅÓÔ× (× ÓÉÌÕ ÔÅÏÒÅÍÙ 12 ÏÎÉ ÄÏÌÖÎÙ ÂÙÔØ ÂÅÓËÏÎÅÞÎÙÍÉ).
   • ïÔÒÅÚÏË [0, 1] (Ó ÏÂÙÞÎÙÍ ÏÔÎÏÛÅÎÉÅÍ ÐÏÒÑÄËÁ) ÎÅ ÉÚÏÍÏÒÆÅÎ ÍÎÏÖÅ-
     ÓÔ×Õ R, ÔÁË ËÁË Õ ÐÅÒ×ÏÇÏ ÅÓÔØ ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ, Á Õ ×ÔÏÒÏÇÏ ÎÅÔ.
     (ðÒÉ ÉÚÏÍÏÒÆÉÚÍÅ ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ, ÅÓÔÅÓÔ×ÅÎÎÏ, ÄÏÌÖÅÎ ÓÏÏÔ×ÅÔ-
     ÓÔ×Ï×ÁÔØ ÎÁÉÂÏÌØÛÅÍÕ.)
   • íÎÏÖÅÓÔ×Ï Z (ÃÅÌÙÅ ÞÉÓÌÁ Ó ÏÂÙÞÎÙÍ ÐÏÒÑÄËÏÍ) ÎÅ ÉÚÏÍÏÒÆÎÏ ÍÎÏÖÅ-
     ÓÔ×Õ Q (ÒÁÃÉÏÎÁÌØÎÙÅ ÞÉÓÌÁ). ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ α : Z → Q Ñ×ÌÑÅÔÓÑ
     ÉÚÏÍÏÒÆÉÚÍÏÍ. ÷ÏÚØÍ¾Í Ä×Á ÓÏÓÅÄÎÉÈ ÃÅÌÙÈ ÞÉÓÌÁ, ÓËÁÖÅÍ, 2 É 3. ðÒÉ
     ÉÚÏÍÏÒÆÉÚÍÅ α ÉÍ ÄÏÌÖÎÙ ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÔØ ËÁËÉÅ-ÔÏ Ä×Á ÒÁÃÉÏÎÁÌØ-
     ÎÙÈ ÞÉÓÌÁ α(2) É α(3), ÐÒÉÞ¾Í α(2) < α(3), ÔÁË ËÁË 2 < 3. îÏ ÔÏÇÄÁ
     ÒÁÃÉÏÎÁÌØÎÙÍ ÞÉÓÌÁÍ ÍÅÖÄÕ α(2) É α(3) ÄÏÌÖÎÙ ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÔØ
     ÃÅÌÙÅ ÞÉÓÌÁ ÍÅÖÄÕ 2 É 3, ËÏÔÏÒÙÈ ÎÅÔ.
   • âÏÌÅÅ ÓÌÏÖÎÙÊ ÐÒÉÍÅÒ ¡ ÍÎÏÖÅÓÔ×Á Z É Z + Z. ÷ÏÚØÍ¾Í × Z + Z
     Ä×Å ËÏÐÉÉ ÎÕÌÑ (ÉÚ ÔÏÊ É ÄÒÕÇÏÊ ËÏÍÐÏÎÅÎÔÙ); ÍÙ ÏÂÏÚÎÁÞÁÌÉ ÉÈ 0
     É 0. ðÒÉ ÜÔÏÍ 0 < 0. ðÒÉ ÉÚÏÍÏÒÆÉÚÍÅ ÉÍ ÄÏÌÖÎÙ ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÔØ
     Ä×Á ÃÅÌÙÈ ÞÉÓÌÁ a É b, ÄÌÑ ËÏÔÏÒÙÈ a < b. ôÏÇÄÁ ×ÓÅÍ ÜÌÅÍÅÎÔÁÍ

Страницы