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

UptoLike

ВУЗ: 

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

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

Рубрика: 

148 çÌÁ×Á VII. ÷ÙÞÉÓÌÉÍÏÓÔØ, ÒÁÚÒÅÛÉÍÏÓÔØ É ÐÅÒÅÞÉÓÌÉÍÏÓÔØ
É ÔÁË ÄÁÌÅÅ). ÷ÓÅ ÁÒÇÕÍÅÎÔÙ, ÎÁ ËÏÔÏÒÙÈ ÁÌÇÏÒÉÔÍ B ÚÁËÁÎÞÉ×ÁÅÔ ÒÁÂÏÔÕ,
ÐÅÞÁÔÁÔØ ÐÏ ÍÅÒÅ ÏÂÎÁÒÕÖÅÎÉÑ.
éÔÁË, ÍÙ ÕÓÔÁÎÏ×ÉÌÉ ÜË×É×ÁÌÅÎÔÎÏÓÔØ ÉÓÈÏÄÎÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ ÏÐÒÅÄÅÌÅ-
ÎÉÑÍ 1 É 3. åÓÌÉ × ÔÏÌØËÏ ÞÔÏ ÐÒÉ×ÅľÎÎÏÍ ÏÐÉÓÁÎÉÉ ÁÌÇÏÒÉÔÍÁ A ÐÅÞÁÔÁÔØ
ÎÅ ÁÒÇÕÍÅÎÔÙ, ÎÁ ËÏÔÏÒÙÈ B ÚÁËÁÎÞÉ×ÁÅÔ ÒÁÂÏÔÕ, Á ÒÅÚÕÌØÔÁÔÙ ÜÔÏÊ ÒÁÂÏ-
ÔÙ, ÔÏ ÐÏÌÕÞÁÅÔÓÑ ÁÌÇÏÒÉÔÍ, ÐÅÒÅÞÉÓÌÑÀÝÉÊ ÏÂÌÁÓÔØ ÚÎÁÞÅÎÉÊ ÆÕÎËÃÉÉ f.
ïÓÔÁÌÏÓØ Åݾ ÕÂÅÄÉÔØÓÑ, ÞÔÏ ×ÓÑËÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÅÓÔØ ÏÂÌÁÓÔØ
ÚÎÁÞÅÎÉÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ. üÔÏ ÍÏÖÎÏ ÓÄÅÌÁÔØ, ÎÁÐÒÉÍÅÒ, ÔÁË: ÐÕÓÔØ
X ÅÓÔØ ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ, ×ÙÞÉÓÌÑÅÍÏÊ ÎÅËÏÔÏÒÙÍ
ÁÌÇÏÒÉÔÍÏÍ A. ôÏÇÄÁ X ÅÓÔØ ÏÂÌÁÓÔØ ÚÎÁÞÅÎÉÊ ÆÕÎËÃÉÉ
b(x) =
x, ÅÓÌÉ A ÚÁËÁÎÞÉ×ÁÅÔ ÒÁÂÏÔÕ ÎÁ x,
ÎÅ ÏÐÒÅÄÅÌÅÎÏ × ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ.
÷ÙÞÉÓÌÑÀÝÉÊ ÜÔÕ ÆÕÎËÃÉÀ ÁÌÇÏÒÉÔÍ ÄÅÊÓÔ×ÕÅÔ ÔÁË ÖÅ, ËÁË É A, ÎÏ ÔÏÌØËÏ
×ÍÅÓÔÏ ÒÅÚÕÌØÔÁÔÁ ÒÁÂÏÔÙ ÁÌÇÏÒÉÔÍÁ A ×ÙÄÁ¾Ô ËÏÐÉÀ ×ÈÏÄÁ.
åݾ ÏÄÎÏ ÜË×É×ÁÌÅÎÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÐÅÒÅÞÉÓÌÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á: ÍÎÏ-
ÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ ÐÅÒÅÞÉÓÌÉÍÏ, ÅÓÌÉ ÏÎÏ ÌÉÂÏ ÐÕÓÔÏ, ÌÉÂÏ ÅÓÔØ
ÍÎÏÖÅÓÔ×Ï ÚÎÁÞÅÎÉÊ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ (ÄÒÕÇÉÍÉ
ÓÌÏ×ÁÍÉ, ÅÇÏ ÜÌÅÍÅÎÔÙ ÍÏÖÎÏ ÒÁÓÐÏÌÏÖÉÔØ × ×ÙÞÉÓÌÉÍÕÀ ÐÏÓÌÅÄÏ×ÁÔÅÌØ-
ÎÏÓÔØ).
÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï X, ÐÅÒÅÞÉÓÌÑÅÍÏÅ ÁÌÇÏÒÉÔ-
ÍÏÍ A, ÎÅÐÕÓÔÏ. ÷ÏÚØÍ¾Í × Î¾Í ËÁËÏÊ-ÔÏ ÜÌÅÍÅÎÔ x
0
. ôÅÐÅÒØ ÒÁÓÓÍÏÔÒÉÍ ÔÁ-
ËÕÀ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÕÀ ÆÕÎËÃÉÀ a: ÅÓÌÉ ÎÁ n-Í ÛÁÇÅ ÒÁÂÏÔÙ ÁÌÇÏÒÉÔÍÁ A
ÐÏÑ×ÌÑÅÔÓÑ ÞÉÓÌÏ t, ÔÏ ÐÏÌÏÖÉÍ a(n) = t; ÅÓÌÉ ÖÅ ÎÉÞÅÇÏ ÎÅ ÐÏÑ×ÌÑÅÔÓÑ, ÔÏ
ÐÏÌÏÖÉÍ a(n) = x
0
. (íÙ ÐÒÅÄÐÏÌÁÇÁÅÍ, ÞÔÏ ÎÁ ÄÁÎÎÏÍ ÛÁÇÅ ÒÁÂÏÔÙ ÁÌÇÏ-
ÒÉÔÍÁ ÍÏÖÅÔ ÐÏÑ×ÉÔØÓÑ ÔÏÌØËÏ ÏÄÎÏ ÞÉÓÌÏ ¡ × ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ ÒÁÂÏÔÕ
ÎÁÄÏ ÒÁÚÂÉÔØ ÎÁ ÂÏÌÅÅ ÍÅÌËÉÅ ÛÁÇÉ.)
úÁÍÅÔÉÍ, ÞÔÏ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ ÎÅËÏÎÓÔÒÕËÔÉ×ÎÏ ¡ ÉÍÅÑ ÁÌÇÏÒÉÔÍ A, ÍÙ
ÍÏÖÅÍ ÎÅ ÚÎÁÔØ, ÐÕÓÔÏ ÌÉ ÐÅÒÅÞÉÓÌÑÅÍÏÅ ÉÍ ÍÎÏÖÅÓÔ×Ï ÉÌÉ ÎÅÔ.
ôÅÏÒÅÍÁ 47. ðÅÒÅÓÅÞÅÎÉÅ É ÏÂßÅÄÉÎÅÎÉÅ ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏÖÅÓÔ× ÐÅ-
ÒÅÞÉÓÌÉÍÙ.
äÏËÁÚÁÔÅÌØÓÔ×Ï. åÓÌÉ X É Y ÐÅÒÅÞÉÓÌÑÀÔÓÑ ÁÌÇÏÒÉÔÍÁÍÉ A É B, ÔÏ ÉÈ
ÏÂßÅÄÉÎÅÎÉÅ ÐÅÒÅÞÉÓÌÑÅÔÓÑ ÁÌÇÏÒÉÔÍÏÍ, ËÏÔÏÒÙÊ ÐÁÒÁÌÌÅÌØÎÏ ×ÙÐÏÌÎÑÅÔ
ÐÏ ÛÁÇÁÍ A É B É ÐÅÞÁÔÁÅÔ ×Ó¾, ÞÔÏ ÐÅÞÁÔÁÀÔ A É B. ó ÐÅÒÅÓÅÞÅÎÉÅÍ
ÎÅÍÎÏÇÏ ÓÌÏÖÎÅÅ ¡ ÒÅÚÕÌØÔÁÔÙ ÒÁÂÏÔÙ A É B ÎÁÄÏ ÎÁËÁÐÌÉ×ÁÔØ É Ó×ÅÒÑÔØ
ÄÒÕÇ Ó ÄÒÕÇÏÍ; ÞÔÏ ÐÏÑ×ÉÔÓÑ ÏÂÝÅÇÏ ¡ ÐÅÞÁÔÁÔØ.
úÁÄÁÞÁ 169. ðÒÏ×ÅÄÉÔÅ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ, ÉÓÐÏÌØÚÕÑ ËÁËÏÅ-ÌÉÂÏ ÄÒÕ-
ÇÏÅ ÜË×É×ÁÌÅÎÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÐÅÒÅÞÉÓÌÉÍÏÓÔÉ.
148          çÌÁ×Á VII. ÷ÙÞÉÓÌÉÍÏÓÔØ, ÒÁÚÒÅÛÉÍÏÓÔØ É ÐÅÒÅÞÉÓÌÉÍÏÓÔØ

É ÔÁË ÄÁÌÅÅ). ÷ÓÅ ÁÒÇÕÍÅÎÔÙ, ÎÁ ËÏÔÏÒÙÈ ÁÌÇÏÒÉÔÍ B ÚÁËÁÎÞÉ×ÁÅÔ ÒÁÂÏÔÕ,
ÐÅÞÁÔÁÔØ ÐÏ ÍÅÒÅ ÏÂÎÁÒÕÖÅÎÉÑ.
   éÔÁË, ÍÙ ÕÓÔÁÎÏ×ÉÌÉ ÜË×É×ÁÌÅÎÔÎÏÓÔØ ÉÓÈÏÄÎÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ ÏÐÒÅÄÅÌÅ-
ÎÉÑÍ 1 É 3. åÓÌÉ × ÔÏÌØËÏ ÞÔÏ ÐÒÉ×ÅľÎÎÏÍ ÏÐÉÓÁÎÉÉ ÁÌÇÏÒÉÔÍÁ A ÐÅÞÁÔÁÔØ
ÎÅ ÁÒÇÕÍÅÎÔÙ, ÎÁ ËÏÔÏÒÙÈ B ÚÁËÁÎÞÉ×ÁÅÔ ÒÁÂÏÔÕ, Á ÒÅÚÕÌØÔÁÔÙ ÜÔÏÊ ÒÁÂÏ-
ÔÙ, ÔÏ ÐÏÌÕÞÁÅÔÓÑ ÁÌÇÏÒÉÔÍ, ÐÅÒÅÞÉÓÌÑÀÝÉÊ ÏÂÌÁÓÔØ ÚÎÁÞÅÎÉÊ ÆÕÎËÃÉÉ f .
ïÓÔÁÌÏÓØ Åݾ ÕÂÅÄÉÔØÓÑ, ÞÔÏ ×ÓÑËÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÅÓÔØ ÏÂÌÁÓÔØ
ÚÎÁÞÅÎÉÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ. üÔÏ ÍÏÖÎÏ ÓÄÅÌÁÔØ, ÎÁÐÒÉÍÅÒ, ÔÁË: ÐÕÓÔØ
X ÅÓÔØ ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ, ×ÙÞÉÓÌÑÅÍÏÊ ÎÅËÏÔÏÒÙÍ
ÁÌÇÏÒÉÔÍÏÍ A. ôÏÇÄÁ X ÅÓÔØ ÏÂÌÁÓÔØ ÚÎÁÞÅÎÉÊ ÆÕÎËÃÉÉ
                      
                        x, ÅÓÌÉ A ÚÁËÁÎÞÉ×ÁÅÔ ÒÁÂÏÔÕ ÎÁ x,
               b(x) =
                        ÎÅ ÏÐÒÅÄÅÌÅÎÏ × ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ.
÷ÙÞÉÓÌÑÀÝÉÊ ÜÔÕ ÆÕÎËÃÉÀ ÁÌÇÏÒÉÔÍ ÄÅÊÓÔ×ÕÅÔ ÔÁË ÖÅ, ËÁË É A, ÎÏ ÔÏÌØËÏ
×ÍÅÓÔÏ ÒÅÚÕÌØÔÁÔÁ ÒÁÂÏÔÙ ÁÌÇÏÒÉÔÍÁ A ×ÙÄÁ¾Ô ËÏÐÉÀ ×ÈÏÄÁ.
   åݾ ÏÄÎÏ ÜË×É×ÁÌÅÎÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÐÅÒÅÞÉÓÌÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á: ÍÎÏ-
ÖÅÓÔ×Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ ÐÅÒÅÞÉÓÌÉÍÏ, ÅÓÌÉ ÏÎÏ ÌÉÂÏ ÐÕÓÔÏ, ÌÉÂÏ ÅÓÔØ
ÍÎÏÖÅÓÔ×Ï ÚÎÁÞÅÎÉÊ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ (ÄÒÕÇÉÍÉ
ÓÌÏ×ÁÍÉ, ÅÇÏ ÜÌÅÍÅÎÔÙ ÍÏÖÎÏ ÒÁÓÐÏÌÏÖÉÔØ × ×ÙÞÉÓÌÉÍÕÀ ÐÏÓÌÅÄÏ×ÁÔÅÌØ-
ÎÏÓÔØ).
   ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï X, ÐÅÒÅÞÉÓÌÑÅÍÏÅ ÁÌÇÏÒÉÔ-
ÍÏÍ A, ÎÅÐÕÓÔÏ. ÷ÏÚØÍ¾Í × Î¾Í ËÁËÏÊ-ÔÏ ÜÌÅÍÅÎÔ x0. ôÅÐÅÒØ ÒÁÓÓÍÏÔÒÉÍ ÔÁ-
ËÕÀ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÕÀ ÆÕÎËÃÉÀ a: ÅÓÌÉ ÎÁ n-Í ÛÁÇÅ ÒÁÂÏÔÙ ÁÌÇÏÒÉÔÍÁ A
ÐÏÑ×ÌÑÅÔÓÑ ÞÉÓÌÏ t, ÔÏ ÐÏÌÏÖÉÍ a(n) = t; ÅÓÌÉ ÖÅ ÎÉÞÅÇÏ ÎÅ ÐÏÑ×ÌÑÅÔÓÑ, ÔÏ
ÐÏÌÏÖÉÍ a(n) = x0. (íÙ ÐÒÅÄÐÏÌÁÇÁÅÍ, ÞÔÏ ÎÁ ÄÁÎÎÏÍ ÛÁÇÅ ÒÁÂÏÔÙ ÁÌÇÏ-
ÒÉÔÍÁ ÍÏÖÅÔ ÐÏÑ×ÉÔØÓÑ ÔÏÌØËÏ ÏÄÎÏ ÞÉÓÌÏ ¡ × ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ ÒÁÂÏÔÕ
ÎÁÄÏ ÒÁÚÂÉÔØ ÎÁ ÂÏÌÅÅ ÍÅÌËÉÅ ÛÁÇÉ.)
   úÁÍÅÔÉÍ, ÞÔÏ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ ÎÅËÏÎÓÔÒÕËÔÉ×ÎÏ ¡ ÉÍÅÑ ÁÌÇÏÒÉÔÍ A, ÍÙ
ÍÏÖÅÍ ÎÅ ÚÎÁÔØ, ÐÕÓÔÏ ÌÉ ÐÅÒÅÞÉÓÌÑÅÍÏÅ ÉÍ ÍÎÏÖÅÓÔ×Ï ÉÌÉ ÎÅÔ.
   ôÅÏÒÅÍÁ 47. ðÅÒÅÓÅÞÅÎÉÅ É ÏÂßÅÄÉÎÅÎÉÅ ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏÖÅÓÔ× ÐÅ-
ÒÅÞÉÓÌÉÍÙ.
  äÏËÁÚÁÔÅÌØÓÔ×Ï. åÓÌÉ X É Y ÐÅÒÅÞÉÓÌÑÀÔÓÑ ÁÌÇÏÒÉÔÍÁÍÉ A É B, ÔÏ ÉÈ
ÏÂßÅÄÉÎÅÎÉÅ ÐÅÒÅÞÉÓÌÑÅÔÓÑ ÁÌÇÏÒÉÔÍÏÍ, ËÏÔÏÒÙÊ ÐÁÒÁÌÌÅÌØÎÏ ×ÙÐÏÌÎÑÅÔ
ÐÏ ÛÁÇÁÍ A É B É ÐÅÞÁÔÁÅÔ ×Ó¾, ÞÔÏ ÐÅÞÁÔÁÀÔ A É B. ó ÐÅÒÅÓÅÞÅÎÉÅÍ
ÎÅÍÎÏÇÏ ÓÌÏÖÎÅÅ ¡ ÒÅÚÕÌØÔÁÔÙ ÒÁÂÏÔÙ A É B ÎÁÄÏ ÎÁËÁÐÌÉ×ÁÔØ É Ó×ÅÒÑÔØ
ÄÒÕÇ Ó ÄÒÕÇÏÍ; ÞÔÏ ÐÏÑ×ÉÔÓÑ ÏÂÝÅÇÏ ¡ ÐÅÞÁÔÁÔØ.
   úÁÄÁÞÁ 169. ðÒÏ×ÅÄÉÔÅ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ, ÉÓÐÏÌØÚÕÑ ËÁËÏÅ-ÌÉÂÏ ÄÒÕ-
ÇÏÅ ÜË×É×ÁÌÅÎÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÐÅÒÅÞÉÓÌÉÍÏÓÔÉ.

Страницы