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

UptoLike

ВУЗ: 

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

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

Рубрика: 

72 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
Ä×ÁÖÄÙ, ÐÏÓËÏÌØËÕ ÅÇÏ ×ÙÈÏÄ ÉÓÐÏÌØÚÕÅÔÓÑ × ËÁÞÅÓÔ×Å ×ÈÏÄÁ Ä×ÕÈ ÄÒÕÇÉÈ
ÜÌÅÍÅÎÔÏ×. óÈÅÍÙ, × ËÏÔÏÒÙÈ ÔÁËÏÇÏ ×ÅÔ×ÌÅÎÉÑ ÎÅÔ (ÎÁ ÐÒÁËÔÉËÅ ×ÅÔ×ÌÅÎÉÅ
×ÐÏÌÎÅ ×ÏÚÍÏÖÎÏ, ÈÏÔÑ É ÏÇÒÁÎÉÞÅÎÏ ¥ÎÁÇÒÕÚÏÞÎÏÊ ÓÐÏÓÏÂÎÏÓÔØÀ ×ÙÈÏÄÁ¥,
ËÁË ÇÏ×ÏÒÑÔ ÉÎÖÅÎÅÒÙ), ËÁË ÒÁÚ É ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ÆÏÒÍÕÌÁÍ. îÏ × ÏÂÝÅÍ
ÓÌÕÞÁÅ ÐÏÌÕÞÅÎÎÁÑ ÉÚ ÄÁÎÎÏÊ ÓÈÅÍÙ ÆÏÒÍÕÌÁ ÍÏÖÅÔ ÂÙÔØ ÄÌÉÎÎÏÊ, ÄÁÖÅ
ÅÓÌÉ ÓÈÅÍÁ ÓÏÄÅÒÖÉÔ ÎÅÂÏÌØÛÏÅ ÞÉÓÌÏ ÜÌÅÍÅÎÔÏ×, ÐÏÓËÏÌØËÕ ÞÉÓÌÏ ËÏÐÉÊ
ÍÏÖÅÔ ÒÁÓÔÉ ÜËÓÐÏÎÅÎÃÉÁÌØÎÏ Ó ÒÏÓÔÏÍ ÇÌÕÂÉÎÙ ÓÈÅÍÙ.
èÏÔÑ ÉÄÅÑ ÏÂÒÁÚÏ×ÁÎÉÑ ÓÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×, ÒÅÁÌÉÚÕÀ-
ÝÉÈ ÂÕÌÅ×Ù ÆÕÎËÃÉÉ, ÄÏÓÔÁÔÏÞÎÏ ÎÁÇÌÑÄÎÁ, ÄÁÄÉÍ ÂÏÌÅÅ ÆÏÒÍÁÌØÎÏÅ ÏÐÒÅ-
ÄÅÌÅÎÉÅ. æÉËÓÉÒÕÅÍ ÎÅËÏÔÏÒÙÊ ÎÁÂÏÒ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ B. ðÕÓÔØ ÉÍÅÅÔÓÑ
n ÂÕÌÅ×ÙÈ (ÐÒÉÎÉÍÁÀÝÉÈ ÚÎÁÞÅÎÉÑ 0 É 1) ÐÅÒÅÍÅÎÎÙÈ x
1
, . . . , x
n
, ÎÁÚÙ×ÁÅ-
ÍÙÈ ×ÈÏÄÁÍÉ. ðÕÓÔØ ÔÁËÖÅ ÉÍÅÅÔÓÑ ÎÅËÏÔÏÒÏÅ ÞÉÓÌÏ ÂÕÌÅ×ÙÈ ÐÅÒÅÍÅÎÎÙÈ
y
1
, . . . , y
m
, ÎÁÚÙ×ÁÅÍÙÈ ÐÒÏ×ÏÄÎÉËÁÍÉ. ðÕÓÔØ ÄÌÑ ËÁÖÄÏÇÏ ÐÒÏ×ÏÄÎÉËÁ ÓÈÅ-
ÍÙ ÚÁÄÁÎÁ ÂÕÌÅ×Á ÆÕÎËÃÉÑ ÉÚ B, ×ÙÒÁÖÁÀÝÁÑ ÅÇÏ ÚÎÁÞÅÎÉÅ ÞÅÒÅÚ ÄÒÕÇÉÅ
ÐÒÏ×ÏÄÎÉËÉ É ×ÈÏÄÙ. ðÒÉ ÜÔÏÍ ÔÒÅÂÕÅÔÓÑ, ÞÔÏÂÙ ÎÅ ÂÙÌÏ ÃÉËÌÏ× (ÃÉËÌ ÏÂÒÁ-
ÚÕÅÔÓÑ, ËÏÇÄÁ y
i
ÚÁ×ÉÓÉÔ ÏÔ y
j
, ËÏÔÏÒÏÅ ÚÁ×ÉÓÉÔ ÏÔ y
k
, . . . , ËÏÔÏÒÏÅ ÚÁ×ÉÓÉÔ
ÏÔ y
i
). ðÕÓÔØ, ËÒÏÍÅ ÔÏÇÏ, ÓÒÅÄÉ ÐÒÏ×ÏÄÎÉËÏ× ×ÙÄÅÌÅÎ ÏÄÉÎ, ÎÁÚÙ×ÁÅÍÙÊ
×ÙÈÏÄÏÍ. ÷ ÔÁËÏÍ ÓÌÕÞÁÅ ÇÏ×ÏÒÑÔ, ÞÔÏ ÚÁÄÁÎÁ ÓÈÅÍÁ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ
ÜÌÅÍÅÎÔÏ× × ÂÁÚÉÓÅ B Ó n ×ÈÏÄÁÍÉ. þÉÓÌÏ m ÎÁÚÙ×ÁÀÔ ÒÁÚÍÅÒÏÍ ÓÈÅÍÙ. (ó
ÔÏÞËÉ ÚÒÅÎÉÑ ÉÎÖÅÎÅÒÁ ÒÁÚÍÅÒ ¡ ÜÔÏ ÞÉÓÌÏ ÉÓÐÏÌØÚÏ×ÁÎÎÙÈ ÜÌÅÍÅÎÔÏ×, Á
ÂÁÚÉÓ B ¡ ÜÔÏ ÁÓÓÏÒÔÉÍÅÎÔ ÄÏÓÔÕÐÎÙÈ ÅÍÕ ÜÌÅÍÅÎÔÏ×.)
ïÔÓÕÔÓÔ×ÉÅ ÃÉËÌÏ× ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ ÅÓÔØ ÐÒÏ×ÏÄÎÉË, ÚÁ×ÉÓÑÝÉÊ ÔÏÌØËÏ
ÏÔ ×ÈÏÄÏ× (ÉÎÁÞÅ ÍÏÖÎÏ ÂÙÌÏ ÂÙ ÎÁÊÔÉ ÃÉËÌ: ×ÏÚØÍ¾Í ËÁËÏÊ-ÔÏ ÐÒÏ×ÏÄÎÉË,
ÚÁÔÅÍ ×ÏÚØÍ¾Í ÔÏÔ ÐÒÏ×ÏÄÎÉË, ÏÔ ËÏÔÏÒÏÇÏ ÏÎ ÚÁ×ÉÓÉÔ É Ô. Ä.). úÎÁÞÅÎÉÅ
ÜÔÏÇÏ ÐÒÏ×ÏÄÎÉËÁ, ÔÁËÉÍ ÏÂÒÁÚÏÍ, ÏÄÎÏÚÎÁÞÎÏ ÏÐÒÅÄÅÌÑÅÔÓÑ ÓÉÇÎÁÌÁÍÉ ÎÁ
×ÈÏÄÁÈ. óÒÅÄÉ ÏÓÔÁ×ÛÉÈÓÑ ÐÒÏ×ÏÄÎÉËÏ× ÔÁËÖÅ ÎÅÔ ÃÉËÌÁ, ÐÏÜÔÏÍÕ ÍÏÖÎÏ
ÎÁÊÔÉ ÏÄÉÎ ÉÚ ÎÉÈ, ÚÁ×ÉÓÑÝÉÊ ÔÏÌØËÏ ÏÔ ÕÖÅ ÉÚ×ÅÓÔÎÙÈ, É ÏÐÒÅÄÅÌÉÔØ ÅÇÏ
ÚÎÁÞÅÎÉÅ. ðÅÒÅÎÕÍÅÒÏ×Á× ÐÒÏ×ÏÄÎÉËÉ × ÔÁËÏÍ ÐÏÒÑÄËÅ, ÍÙ ÍÏÖÅÍ ÚÁÐÉÓÁÔØ
ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÐÒÉÓ×ÁÉ×ÁÎÉÊ
y
1
:= f
1
(. . . );
y
2
:= f
2
(. . . );
. . . . . . . .
y
m
:= f
m
(. . . ),
× ÐÒÁ×ÙÈ ÞÁÓÔÑÈ ËÏÔÏÒÙÈ ÓÔÏÑÔ ÆÕÎËÃÉÉ ÉÚ B, ÐÒÉÍÅξÎÎÙÅ ËÏ ×ÈÏÄÁÍ É
ÕÖÅ ÎÁÊÄÅÎÎÙÍ ÚÎÁÞÅÎÉÑÍ. ðÒÉ ÜÔÏÍ ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÒÅÚÕÌØÔÁÔ ÓÈÅÍÙ
ÅÓÔØ y
m
(×ÓÅ ÐÏÓÌÅÄÕÀÝÉÅ ÐÒÉÓ×ÁÉ×ÁÎÉÑ ÕÖÅ ÎÅ ÎÕÖÎÙ). ôÁËÁÑ ÐÒÏÇÒÁÍÍÁ
ÏÐÒÅÄÅÌÑÅÔ y
m
ÐÒÉ ÉÚ×ÅÓÔÎÙÈ ÚÎÁÞÅÎÉÑÈ ×ÈÏÄÏ×, É ÔÅÍ ÓÁÍÙÍ ×ÙÞÉÓÌÑÅÔ
ÎÅËÏÔÏÒÕÀ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ.
72                                            çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

Ä×ÁÖÄÙ, ÐÏÓËÏÌØËÕ ÅÇÏ ×ÙÈÏÄ ÉÓÐÏÌØÚÕÅÔÓÑ × ËÁÞÅÓÔ×Å ×ÈÏÄÁ Ä×ÕÈ ÄÒÕÇÉÈ
ÜÌÅÍÅÎÔÏ×. óÈÅÍÙ, × ËÏÔÏÒÙÈ ÔÁËÏÇÏ ×ÅÔ×ÌÅÎÉÑ ÎÅÔ (ÎÁ ÐÒÁËÔÉËÅ ×ÅÔ×ÌÅÎÉÅ
×ÐÏÌÎÅ ×ÏÚÍÏÖÎÏ, ÈÏÔÑ É ÏÇÒÁÎÉÞÅÎÏ ¥ÎÁÇÒÕÚÏÞÎÏÊ ÓÐÏÓÏÂÎÏÓÔØÀ ×ÙÈÏÄÁ¥,
ËÁË ÇÏ×ÏÒÑÔ ÉÎÖÅÎÅÒÙ), ËÁË ÒÁÚ É ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ÆÏÒÍÕÌÁÍ. îÏ × ÏÂÝÅÍ
ÓÌÕÞÁÅ ÐÏÌÕÞÅÎÎÁÑ ÉÚ ÄÁÎÎÏÊ ÓÈÅÍÙ ÆÏÒÍÕÌÁ ÍÏÖÅÔ ÂÙÔØ ÄÌÉÎÎÏÊ, ÄÁÖÅ
ÅÓÌÉ ÓÈÅÍÁ ÓÏÄÅÒÖÉÔ ÎÅÂÏÌØÛÏÅ ÞÉÓÌÏ ÜÌÅÍÅÎÔÏ×, ÐÏÓËÏÌØËÕ ÞÉÓÌÏ ËÏÐÉÊ
ÍÏÖÅÔ ÒÁÓÔÉ ÜËÓÐÏÎÅÎÃÉÁÌØÎÏ Ó ÒÏÓÔÏÍ ÇÌÕÂÉÎÙ ÓÈÅÍÙ.
     èÏÔÑ ÉÄÅÑ ÏÂÒÁÚÏ×ÁÎÉÑ ÓÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×, ÒÅÁÌÉÚÕÀ-
ÝÉÈ ÂÕÌÅ×Ù ÆÕÎËÃÉÉ, ÄÏÓÔÁÔÏÞÎÏ ÎÁÇÌÑÄÎÁ, ÄÁÄÉÍ ÂÏÌÅÅ ÆÏÒÍÁÌØÎÏÅ ÏÐÒÅ-
ÄÅÌÅÎÉÅ. æÉËÓÉÒÕÅÍ ÎÅËÏÔÏÒÙÊ ÎÁÂÏÒ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ B. ðÕÓÔØ ÉÍÅÅÔÓÑ
n ÂÕÌÅ×ÙÈ (ÐÒÉÎÉÍÁÀÝÉÈ ÚÎÁÞÅÎÉÑ 0 É 1) ÐÅÒÅÍÅÎÎÙÈ x1, . . . , xn, ÎÁÚÙ×ÁÅ-
ÍÙÈ ×ÈÏÄÁÍÉ. ðÕÓÔØ ÔÁËÖÅ ÉÍÅÅÔÓÑ ÎÅËÏÔÏÒÏÅ ÞÉÓÌÏ ÂÕÌÅ×ÙÈ ÐÅÒÅÍÅÎÎÙÈ
y1 , . . . , ym , ÎÁÚÙ×ÁÅÍÙÈ ÐÒÏ×ÏÄÎÉËÁÍÉ. ðÕÓÔØ ÄÌÑ ËÁÖÄÏÇÏ ÐÒÏ×ÏÄÎÉËÁ ÓÈÅ-
ÍÙ ÚÁÄÁÎÁ ÂÕÌÅ×Á ÆÕÎËÃÉÑ ÉÚ B, ×ÙÒÁÖÁÀÝÁÑ ÅÇÏ ÚÎÁÞÅÎÉÅ ÞÅÒÅÚ ÄÒÕÇÉÅ
ÐÒÏ×ÏÄÎÉËÉ É ×ÈÏÄÙ. ðÒÉ ÜÔÏÍ ÔÒÅÂÕÅÔÓÑ, ÞÔÏÂÙ ÎÅ ÂÙÌÏ ÃÉËÌÏ× (ÃÉËÌ ÏÂÒÁ-
ÚÕÅÔÓÑ, ËÏÇÄÁ yi ÚÁ×ÉÓÉÔ ÏÔ yj , ËÏÔÏÒÏÅ ÚÁ×ÉÓÉÔ ÏÔ yk , . . . , ËÏÔÏÒÏÅ ÚÁ×ÉÓÉÔ
ÏÔ yi ). ðÕÓÔØ, ËÒÏÍÅ ÔÏÇÏ, ÓÒÅÄÉ ÐÒÏ×ÏÄÎÉËÏ× ×ÙÄÅÌÅÎ ÏÄÉÎ, ÎÁÚÙ×ÁÅÍÙÊ
×ÙÈÏÄÏÍ. ÷ ÔÁËÏÍ ÓÌÕÞÁÅ ÇÏ×ÏÒÑÔ, ÞÔÏ ÚÁÄÁÎÁ ÓÈÅÍÁ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ
ÜÌÅÍÅÎÔÏ× × ÂÁÚÉÓÅ B Ó n ×ÈÏÄÁÍÉ. þÉÓÌÏ m ÎÁÚÙ×ÁÀÔ ÒÁÚÍÅÒÏÍ ÓÈÅÍÙ. (ó
ÔÏÞËÉ ÚÒÅÎÉÑ ÉÎÖÅÎÅÒÁ ÒÁÚÍÅÒ ¡ ÜÔÏ ÞÉÓÌÏ ÉÓÐÏÌØÚÏ×ÁÎÎÙÈ ÜÌÅÍÅÎÔÏ×, Á
ÂÁÚÉÓ B ¡ ÜÔÏ ÁÓÓÏÒÔÉÍÅÎÔ ÄÏÓÔÕÐÎÙÈ ÅÍÕ ÜÌÅÍÅÎÔÏ×.)
     ïÔÓÕÔÓÔ×ÉÅ ÃÉËÌÏ× ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ ÅÓÔØ ÐÒÏ×ÏÄÎÉË, ÚÁ×ÉÓÑÝÉÊ ÔÏÌØËÏ
ÏÔ ×ÈÏÄÏ× (ÉÎÁÞÅ ÍÏÖÎÏ ÂÙÌÏ ÂÙ ÎÁÊÔÉ ÃÉËÌ: ×ÏÚØÍ¾Í ËÁËÏÊ-ÔÏ ÐÒÏ×ÏÄÎÉË,
ÚÁÔÅÍ ×ÏÚØÍ¾Í ÔÏÔ ÐÒÏ×ÏÄÎÉË, ÏÔ ËÏÔÏÒÏÇÏ ÏÎ ÚÁ×ÉÓÉÔ É Ô. Ä.). úÎÁÞÅÎÉÅ
ÜÔÏÇÏ ÐÒÏ×ÏÄÎÉËÁ, ÔÁËÉÍ ÏÂÒÁÚÏÍ, ÏÄÎÏÚÎÁÞÎÏ ÏÐÒÅÄÅÌÑÅÔÓÑ ÓÉÇÎÁÌÁÍÉ ÎÁ
×ÈÏÄÁÈ. óÒÅÄÉ ÏÓÔÁ×ÛÉÈÓÑ ÐÒÏ×ÏÄÎÉËÏ× ÔÁËÖÅ ÎÅÔ ÃÉËÌÁ, ÐÏÜÔÏÍÕ ÍÏÖÎÏ
ÎÁÊÔÉ ÏÄÉÎ ÉÚ ÎÉÈ, ÚÁ×ÉÓÑÝÉÊ ÔÏÌØËÏ ÏÔ ÕÖÅ ÉÚ×ÅÓÔÎÙÈ, É ÏÐÒÅÄÅÌÉÔØ ÅÇÏ
ÚÎÁÞÅÎÉÅ. ðÅÒÅÎÕÍÅÒÏ×Á× ÐÒÏ×ÏÄÎÉËÉ × ÔÁËÏÍ ÐÏÒÑÄËÅ, ÍÙ ÍÏÖÅÍ ÚÁÐÉÓÁÔØ
ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÐÒÉÓ×ÁÉ×ÁÎÉÊ
                                y1 := f1 (. . . );
                                y2 := f2 (. . . );
                                 . . . . . . . .
                               ym := fm (. . . ),
× ÐÒÁ×ÙÈ ÞÁÓÔÑÈ ËÏÔÏÒÙÈ ÓÔÏÑÔ ÆÕÎËÃÉÉ ÉÚ B, ÐÒÉÍÅξÎÎÙÅ ËÏ ×ÈÏÄÁÍ É
ÕÖÅ ÎÁÊÄÅÎÎÙÍ ÚÎÁÞÅÎÉÑÍ. ðÒÉ ÜÔÏÍ ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÒÅÚÕÌØÔÁÔ ÓÈÅÍÙ
ÅÓÔØ ym (×ÓÅ ÐÏÓÌÅÄÕÀÝÉÅ ÐÒÉÓ×ÁÉ×ÁÎÉÑ ÕÖÅ ÎÅ ÎÕÖÎÙ). ôÁËÁÑ ÐÒÏÇÒÁÍÍÁ
ÏÐÒÅÄÅÌÑÅÔ ym ÐÒÉ ÉÚ×ÅÓÔÎÙÈ ÚÎÁÞÅÎÉÑÈ ×ÈÏÄÏ×, É ÔÅÍ ÓÁÍÙÍ ×ÙÞÉÓÌÑÅÔ
ÎÅËÏÔÏÒÕÀ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ.

Страницы