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

UptoLike

ВУЗ: 

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

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

Рубрика: 

146 çÌÁ×Á VII. ÷ÙÞÉÓÌÉÍÏÓÔØ, ÒÁÚÒÅÛÉÍÏÓÔØ É ÐÅÒÅÞÉÓÌÉÍÏÓÔØ
4. îÅÓËÏÌØËÏ ÄÅÓÑÔÉÌÅÔÉÊ ÎÁÚÁÄ ÐÏÎÑÔÉÅ ÁÌÇÏÒÉÔÍÁ ÔÒÅÂÏ×ÁÌÏ ÓÐÅÃÉÁÌØ-
ÎÏÇÏ ÒÁÚßÑÓÎÅÎÉÑ. óÅÊÞÁÓ (¥ËÏÍÐØÀÔÅÒÎÁÑ ÇÒÁÍÏÔÎÏÓÔØ¥?) ÔÁËÉÅ ÏÂßÑÓÎÅ-
ÎÉÑ ×Ó¾ ÒÁ×ÎÏ ÎÉËÔÏ ÞÉÔÁÔØ ÎÅ ÂÕÄÅÔ, ÐÏÓËÏÌØËÕ É ÔÁË ÑÓÎÏ, ÞÔÏ ÔÁËÏÅ ÁÌ-
ÇÏÒÉÔÍ. îÏ ×Ó¾ ÖÅ ÎÁÄÏ ÓÏÂÌÀÄÁÔØ ÏÓÔÏÒÏÖÎÏÓÔØ, ÞÔÏÂÙ ÎÅ ÐÒÉÎÑÔØ ÚÁ ÁÌ-
ÇÏÒÉÔÍ ÔÏ, ÞÔÏ ÉÍ ÎÅ Ñ×ÌÑÅÔÓÑ. ÷ÏÔ ÐÒÉÍÅÒ ÎÅ×ÅÒÎÏÇÏ ÒÁÓÓÕÖÄÅÎÉÑ:
¥äÏËÁÖÅÍ¥, ÞÔÏ ×ÓÑËÁÑ ×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ f Ó ÎÁÔÕÒÁÌØÎÙÍÉ ÁÒÇÕ-
ÍÅÎÔÁÍÉ É ÚÎÁÞÅÎÉÑÍÉ ÍÏÖÅÔ ÂÙÔØ ÐÒÏÄÏÌÖÅÎÁ ÄÏ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÊ ×Ù-
ÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ g : N → N. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÓÌÉ f ×ÙÞÉÓÌÑÅÔÓÑ ÁÌÇÏÒÉÔ-
ÍÏÍ A, ÔÏ ÓÌÅÄÕÀÝÉÊ ÁÌÇÏÒÉÔÍ B ×ÙÞÉÓÌÑÅÔ ÆÕÎËÃÉÀ g, ÐÒÏÄÏÌÖÁÀÝÕÀ f:
¥ÅÓÌÉ A ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ n, ÔÏ B ÄÁ¾Ô ÔÏÔ ÖÅ ÒÅÚÕÌØÔÁÔ, ÞÔÏ É A; ÅÓ-
ÌÉ A ÎÅ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ n, ÔÏ B ÄÁ¾Ô ÒÅÚÕÌØÔÁÔ (ÓËÁÖÅÍ) 0¥. (÷ Þ¾Í
ÏÛÉÂËÁ × ÜÔÏÍ ÒÁÓÓÕÖÄÅÎÉÉ?)
§2. òÁÚÒÅÛÉÍÙÅ ÍÎÏÖÅÓÔ×Á
íÎÏÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ X ÎÁÚÙ×ÁÅÔÓÑ ÒÁÚÒÅÛÉÍÙÍ, ÅÓÌÉ ÓÕÝÅ-
ÓÔ×ÕÅÔ ÁÌÇÏÒÉÔÍ, ËÏÔÏÒÙÊ ÐÏ ÌÀÂÏÍÕ ÎÁÔÕÒÁÌØÎÏÍÕ n ÏÐÒÅÄÅÌÑÅÔ, ÐÒÉÎÁÄ-
ÌÅÖÉÔ ÌÉ ÏÎÏ ÍÎÏÖÅÓÔ×Õ X.
äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, X ÒÁÚÒÅÛÉÍÏ, ÅÓÌÉ ÅÇÏ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ
χ(n) = (if n ∈ X then 1 else 0 ¦) ×ÙÞÉÓÌÉÍÁ.
ïÞÅ×ÉÄÎÏ, ÐÅÒÅÓÅÞÅÎÉÅ, ÏÂßÅÄÉÎÅÎÉÅ É ÒÁÚÎÏÓÔØ ÒÁÚÒÅÛÉÍÙÈ ÍÎÏÖÅÓÔ×
ÒÁÚÒÅÛÉÍÙ. ìÀÂÏÅ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï ÒÁÚÒÅÛÉÍÏ.
áÎÁÌÏÇÉÞÎÏ ÏÐÒÅÄÅÌÑÀÔ ÒÁÚÒÅÛÉÍÏÓÔØ ÍÎÏÖÅÓÔ× ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ ÞÉ-
ÓÅÌ, ÍÎÏÖÅÓÔ× ÒÁÃÉÏÎÁÌØÎÙÈ ÞÉÓÅÌ É Ô. Ð.
úÁÄÁÞÁ 166. äÏËÁÖÉÔÅ, ÞÔÏ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÒÁÃÉÏÎÁÌØÎÙÈ ÞÉÓÅÌ,
ÍÅÎØÛÉÈ ÞÉÓÌÁ e (ÏÓÎÏ×ÁÎÉÑ ÎÁÔÕÒÁÌØÎÙÈ ÌÏÇÁÒÉÆÍÏ×), ÒÁÚÒÅÛÉÍÏ.
úÁÄÁÞÁ 167. äÏËÁÖÉÔÅ, ÞÔÏ ÎÅÐÕÓÔÏÅ ÍÎÏÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ
ÒÁÚÒÅÛÉÍÏ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÏÎÏ ÅÓÔØ ÍÎÏÖÅÓÔ×Ï ÚÎÁÞÅÎÉÊ
×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÊ ÎÅÕÂÙ×ÁÀÝÅÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ Ó ÎÁÔÕÒÁÌØÎÙÍÉ
ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅÎÉÑÍÉ.
ïÔÍÅÔÉÍ ÔÏÎËÉÊ ÍÏÍÅÎÔ: ÍÏÖÎÏ ÄÏËÁÚÁÔØ ÒÁÚÒÅÛÉÍÏÓÔØ ÍÎÏÖÅÓÔ×Á ÎÅ-
ËÏÎÓÔÒÕËÔÉ×ÎÏ, ÎÅ ÐÒÅÄßÑ×ÌÑÑ ÁÌÇÏÒÉÔÍÁ. ÷ÏÔ ÔÒÁÄÉÃÉÏÎÎÙÊ ÐÒÉÍÅÒ: ÍÎÏ-
ÖÅÓÔ×Ï ÔÅÈ n, ÄÌÑ ËÏÔÏÒÙÈ × ÞÉÓÌÅ π ÅÓÔØ ÎÅ ÍÅÎÅÅ n ÄÅ×ÑÔÏË ÐÏÄÒÑÄ, ÒÁÚÒÅ-
ÛÉÍÏ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÜÔÏ ÍÎÏÖÅÓÔ×Ï ÓÏÄÅÒÖÉÔ ÌÉÂÏ ×ÓÅ ÎÁÔÕÒÁÌØÎÙÅ ÞÉÓÌÁ,
ÌÉÂÏ ×ÓÅ ÎÁÔÕÒÁÌØÎÙÅ ÞÉÓÌÁ ×ÐÌÏÔØ ÄÏ ÎÅËÏÔÏÒÏÇÏ. ÷ ÏÂÏÉÈ ÓÌÕÞÁÑÈ ÏÎÏ
ÒÁÚÒÅÛÉÍÏ. ôÅÍ ÎÅ ÍÅÎÅÅ ÍÙ ÔÁË É ÎÅ ÐÒÅÄßÑ×ÉÌÉ ÁÌÇÏÒÉÔÍÁ, ËÏÔÏÒÙÊ ÐÏ n
ÕÚÎÁ×ÁÌ ÂÙ, ÅÓÔØ ÌÉ × π ÎÅ ÍÅÎÅÅ n ÄÅ×ÑÔÏË ÐÏÄÒÑÄ.
146          çÌÁ×Á VII. ÷ÙÞÉÓÌÉÍÏÓÔØ, ÒÁÚÒÅÛÉÍÏÓÔØ É ÐÅÒÅÞÉÓÌÉÍÏÓÔØ

   4. îÅÓËÏÌØËÏ ÄÅÓÑÔÉÌÅÔÉÊ ÎÁÚÁÄ ÐÏÎÑÔÉÅ ÁÌÇÏÒÉÔÍÁ ÔÒÅÂÏ×ÁÌÏ ÓÐÅÃÉÁÌØ-
ÎÏÇÏ ÒÁÚßÑÓÎÅÎÉÑ. óÅÊÞÁÓ (¥ËÏÍÐØÀÔÅÒÎÁÑ ÇÒÁÍÏÔÎÏÓÔØ¥?) ÔÁËÉÅ ÏÂßÑÓÎÅ-
ÎÉÑ ×Ó¾ ÒÁ×ÎÏ ÎÉËÔÏ ÞÉÔÁÔØ ÎÅ ÂÕÄÅÔ, ÐÏÓËÏÌØËÕ É ÔÁË ÑÓÎÏ, ÞÔÏ ÔÁËÏÅ ÁÌ-
ÇÏÒÉÔÍ. îÏ ×Ó¾ ÖÅ ÎÁÄÏ ÓÏÂÌÀÄÁÔØ ÏÓÔÏÒÏÖÎÏÓÔØ, ÞÔÏÂÙ ÎÅ ÐÒÉÎÑÔØ ÚÁ ÁÌ-
ÇÏÒÉÔÍ ÔÏ, ÞÔÏ ÉÍ ÎÅ Ñ×ÌÑÅÔÓÑ. ÷ÏÔ ÐÒÉÍÅÒ ÎÅ×ÅÒÎÏÇÏ ÒÁÓÓÕÖÄÅÎÉÑ:
   ¥äÏËÁÖÅÍ¥, ÞÔÏ ×ÓÑËÁÑ ×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ f Ó ÎÁÔÕÒÁÌØÎÙÍÉ ÁÒÇÕ-
ÍÅÎÔÁÍÉ É ÚÎÁÞÅÎÉÑÍÉ ÍÏÖÅÔ ÂÙÔØ ÐÒÏÄÏÌÖÅÎÁ ÄÏ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÊ ×Ù-
ÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ g : N → N. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÓÌÉ f ×ÙÞÉÓÌÑÅÔÓÑ ÁÌÇÏÒÉÔ-
ÍÏÍ A, ÔÏ ÓÌÅÄÕÀÝÉÊ ÁÌÇÏÒÉÔÍ B ×ÙÞÉÓÌÑÅÔ ÆÕÎËÃÉÀ g, ÐÒÏÄÏÌÖÁÀÝÕÀ f :
¥ÅÓÌÉ A ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ n, ÔÏ B ÄÁ¾Ô ÔÏÔ ÖÅ ÒÅÚÕÌØÔÁÔ, ÞÔÏ É A; ÅÓ-
ÌÉ A ÎÅ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ n, ÔÏ B ÄÁ¾Ô ÒÅÚÕÌØÔÁÔ (ÓËÁÖÅÍ) 0¥. (÷ Þ¾Í
ÏÛÉÂËÁ × ÜÔÏÍ ÒÁÓÓÕÖÄÅÎÉÉ?)


  §2. òÁÚÒÅÛÉÍÙÅ ÍÎÏÖÅÓÔ×Á
   íÎÏÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ X ÎÁÚÙ×ÁÅÔÓÑ ÒÁÚÒÅÛÉÍÙÍ, ÅÓÌÉ ÓÕÝÅ-
ÓÔ×ÕÅÔ ÁÌÇÏÒÉÔÍ, ËÏÔÏÒÙÊ ÐÏ ÌÀÂÏÍÕ ÎÁÔÕÒÁÌØÎÏÍÕ n ÏÐÒÅÄÅÌÑÅÔ, ÐÒÉÎÁÄ-
ÌÅÖÉÔ ÌÉ ÏÎÏ ÍÎÏÖÅÓÔ×Õ X.
   äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, X ÒÁÚÒÅÛÉÍÏ, ÅÓÌÉ ÅÇÏ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ
χ(n) = (if n ∈ X then 1 else 0 ¦) ×ÙÞÉÓÌÉÍÁ.
   ïÞÅ×ÉÄÎÏ, ÐÅÒÅÓÅÞÅÎÉÅ, ÏÂßÅÄÉÎÅÎÉÅ É ÒÁÚÎÏÓÔØ ÒÁÚÒÅÛÉÍÙÈ ÍÎÏÖÅÓÔ×
ÒÁÚÒÅÛÉÍÙ. ìÀÂÏÅ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï ÒÁÚÒÅÛÉÍÏ.
   áÎÁÌÏÇÉÞÎÏ ÏÐÒÅÄÅÌÑÀÔ ÒÁÚÒÅÛÉÍÏÓÔØ ÍÎÏÖÅÓÔ× ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ ÞÉ-
ÓÅÌ, ÍÎÏÖÅÓÔ× ÒÁÃÉÏÎÁÌØÎÙÈ ÞÉÓÅÌ É Ô. Ð.

  úÁÄÁÞÁ 166. äÏËÁÖÉÔÅ, ÞÔÏ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÒÁÃÉÏÎÁÌØÎÙÈ ÞÉÓÅÌ,
ÍÅÎØÛÉÈ ÞÉÓÌÁ e (ÏÓÎÏ×ÁÎÉÑ ÎÁÔÕÒÁÌØÎÙÈ ÌÏÇÁÒÉÆÍÏ×), ÒÁÚÒÅÛÉÍÏ.

   úÁÄÁÞÁ 167. äÏËÁÖÉÔÅ, ÞÔÏ ÎÅÐÕÓÔÏÅ ÍÎÏÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ
ÒÁÚÒÅÛÉÍÏ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÏÎÏ ÅÓÔØ ÍÎÏÖÅÓÔ×Ï ÚÎÁÞÅÎÉÊ
×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÊ ÎÅÕÂÙ×ÁÀÝÅÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ Ó ÎÁÔÕÒÁÌØÎÙÍÉ
ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅÎÉÑÍÉ.

   ïÔÍÅÔÉÍ ÔÏÎËÉÊ ÍÏÍÅÎÔ: ÍÏÖÎÏ ÄÏËÁÚÁÔØ ÒÁÚÒÅÛÉÍÏÓÔØ ÍÎÏÖÅÓÔ×Á ÎÅ-
ËÏÎÓÔÒÕËÔÉ×ÎÏ, ÎÅ ÐÒÅÄßÑ×ÌÑÑ ÁÌÇÏÒÉÔÍÁ. ÷ÏÔ ÔÒÁÄÉÃÉÏÎÎÙÊ ÐÒÉÍÅÒ: ÍÎÏ-
ÖÅÓÔ×Ï ÔÅÈ n, ÄÌÑ ËÏÔÏÒÙÈ × ÞÉÓÌÅ π ÅÓÔØ ÎÅ ÍÅÎÅÅ n ÄÅ×ÑÔÏË ÐÏÄÒÑÄ, ÒÁÚÒÅ-
ÛÉÍÏ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÜÔÏ ÍÎÏÖÅÓÔ×Ï ÓÏÄÅÒÖÉÔ ÌÉÂÏ ×ÓÅ ÎÁÔÕÒÁÌØÎÙÅ ÞÉÓÌÁ,
ÌÉÂÏ ×ÓÅ ÎÁÔÕÒÁÌØÎÙÅ ÞÉÓÌÁ ×ÐÌÏÔØ ÄÏ ÎÅËÏÔÏÒÏÇÏ. ÷ ÏÂÏÉÈ ÓÌÕÞÁÑÈ ÏÎÏ
ÒÁÚÒÅÛÉÍÏ. ôÅÍ ÎÅ ÍÅÎÅÅ ÍÙ ÔÁË É ÎÅ ÐÒÅÄßÑ×ÉÌÉ ÁÌÇÏÒÉÔÍÁ, ËÏÔÏÒÙÊ ÐÏ n
ÕÚÎÁ×ÁÌ ÂÙ, ÅÓÔØ ÌÉ × π ÎÅ ÍÅÎÅÅ n ÄÅ×ÑÔÏË ÐÏÄÒÑÄ.

Страницы