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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§2. ðÏÌÎÙÅ ÓÉÓÔÅÍÙ Ó×ÑÚÏË 69
ËÏÍÐÏÚÉÃÉÉ ÆÕÎËÃÉÊ ÉÚ ÎÁÂÏÒÁ, Ô. Å. ÚÁÐÉÓÙ×ÁÅÔÓÑ × ×ÉÄÅ ÆÏÒÍÕÌÙ, ÇÄÅ Ó×ÑÚ-
ËÁÍÉ ÓÌÕÖÁÔ ÆÕÎËÃÉÉ ÎÁÂÏÒÁ.) ðÏÄÏÂÎÙÅ ×ÏÐÒÏÓÙ ×ÙÚÙ×ÁÌÉ × Ó×Ͼ ×ÒÅÍÑ
ÂÏÌØÛÏÊ ÉÎÔÅÒÅÓ É ÂÙÌÉ ÈÏÒÏÛÏ ÉÚÕÞÅÎÙ. îÁÞÁÌØÎÙÍ ÜÔÁÐÏÍ Ñ×ÉÌÏÓØ ÔÁËÏÅ
ÕÔ×ÅÒÖÄÅÎÉÅ:
ôÅÏÒÅÍÁ 22 (ËÒÉÔÅÒÉÊ ðÏÓÔÁ). îÁÂÏÒ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ Ñ×ÌÑÅÔÓÑ ÐÏÌ-
ÎÙÍ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÏÎ ÎÅ ÓÏÄÅÒÖÉÔÓÑ ÃÅÌÉËÏÍ ÎÉ × ÏÄÎÏÍ
ÉÚ ÐÑÔÉ ÓÌÅÄÕÀÝÉÈ ¥ÐÒÅÄÐÏÌÎÙÈ ËÌÁÓÓÏ×¥:
• ÍÏÎÏÔÏÎÎÙÅ ÆÕÎËÃÉÉ;
• ÆÕÎËÃÉÉ, ÓÏÈÒÁÎÑÀÝÉÅ ÎÕÌØ;
• ÆÕÎËÃÉÉ, ÓÏÈÒÁÎÑÀÝÉÅ ÅÄÉÎÉÃÕ;
• ÌÉÎÅÊÎÙÅ ÆÕÎËÃÉÉ;
• ÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÙÅ ÆÕÎËÃÉÉ.
(æÕÎËÃÉÑ f ÍÏÎÏÔÏÎÎÁ, ÅÓÌÉ ÏÎÁ ÍÏÎÏÔÏÎÎÏ ÎÅÕÂÙ×ÁÅÔ ÐÏ ËÁÖÄÏÍÕ ÉÚ Ó×Ï-
ÉÈ ÁÒÇÕÍÅÎÔÏ×. æÕÎËÃÉÑ f ÓÏÈÒÁÎÑÅÔ ÎÕÌØ/ ÅÄÉÎÉÃÕ, ÅÓÌÉ f(0, . . . , 0) = 0
(ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ f(1, . . ., 1) = 1). æÕÎËÃÉÑ f ÌÉÎÅÊÎÁ, ÅÓÌÉ ÏÎÁ ÐÒÅÄÓÔÁ-
×ÉÍÁ ÍÎÏÇÏÞÌÅÎÏÍ, × ËÏÔÏÒÏÍ ×ÓÅ ÍÏÎÏÍÙ ÓÏÄÅÒÖÁÔ ÎÅ ÂÏÌÅÅ ÏÄÎÏÊ ÐÅ-
ÒÅÍÅÎÎÏÊ. îÁËÏÎÅÃ, ÆÕÎËÃÉÑ f ÎÁÚÙ×ÁÅÔÓÑ ÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÏÊ, ÅÓÌÉ f(1 −
− p
1
, . . . , 1 − p
n
) = 1 − f(p
1
, . . . , p
n
).)
äÏËÁÚÁÔÅÌØÓÔ×Ï. åÓÌÉ ÎÁÂÏÒ ÓÏÄÅÒÖÉÔÓÑ × ÏÄÎÏÍ ÉÚ ËÌÁÓÓÏ×, ÔÏ É ×ÓÅ
ËÏÍÐÏÚÉÃÉÉ ÔÁËÖÅ ÎÅ ×ÙÈÏÄÑÔ ÚÁ ÐÒÅÄÅÌÙ ÜÔÏÇÏ ËÌÁÓÓÁ (ÌÅÇËÏ ÐÒÏ×ÅÒÉÔØ
ÄÌÑ ËÁÖÄÏÇÏ ÉÚ ËÌÁÓÓÏ× × ÏÔÄÅÌØÎÏÓÔÉ) É ÐÏÜÔÏÍÕ ÎÁÂÏÒ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÏÌ-
ÎÙÍ. äÏËÁÖÅÍ ÏÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ. ðÕÓÔØ ÄÌÑ ËÁÖÄÏÇÏ ËÌÁÓÓÁ ×ÙÂÒÁÎÁ
ËÁËÁÑ-ÔÏ ÆÕÎËÃÉÑ, × Î¾Í ÎÅ ÌÅÖÁÝÁÑ. õÂÅÄÉÍÓÑ, ÞÔÏ Ó ÐÏÍÏÝØÀ ËÏÍÂÉÎÁÃÉÊ
×ÙÂÒÁÎÎÙÈ ÆÕÎËÃÉÊ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ ×ÓÅ ÂÕÌÅ×Ù ÆÕÎËÃÉÉ.
õ ÎÁÓ ÅÓÔØ ÆÕÎËÃÉÑ, ÎÅ ÓÏÈÒÁÎÑÀÝÁÑ ÎÕÌØ. ðÏÄÓÔÁ×ÉÍ ×ÍÅÓÔÏ ×ÓÅÈ ÁÒÇÕ-
ÍÅÎÔÏ× ÏÄÎÕ É ÔÕ ÖÅ ÐÅÒÅÍÅÎÎÕÀ. ðÏÌÕÞÉÔÓÑ ÆÕÎËÃÉÑ ÏÔ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ,
ÏÔÏÂÒÁÖÁÀÝÁÑ ÎÕÌØ × ÅÄÉÎÉÃÕ, ÔÏ ÅÓÔØ ÌÉÂÏ ËÏÎÓÔÁÎÔÁ 1, ÌÉÂÏ ÏÔÒÉÃÁÎÉÅ.
óÄÅÌÁ× ÔÏ ÖÅ ÓÁÍÏÅ Ó ÆÕÎËÃÉÅÊ, ÎÅ ÓÏÈÒÁÎÑÀÝÅÊ ÅÄÉÎÉÃÕ, ÐÏÌÕÞÉÍ ÌÉÂÏ
ËÏÎÓÔÁÎÔÕ ÎÕÌØ, ÌÉÂÏ ÏÔÒÉÃÁÎÉÅ. ôÁËÉÍ ÏÂÒÁÚÏÍ, Õ ÎÁÓ ÌÉÂÏ ÅÓÔØ ÏÔÒÉÃÁ-
ÎÉÅ, ÌÉÂÏ ÏÂÅ ËÏÎÓÔÁÎÔÙ 0 É 1.
åÓÌÉ ÅÓÔØ ÏÂÅ ËÏÎÓÔÁÎÔÙ, ÔÏ ×Ó¾ ÒÁ×ÎÏ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ ÏÔÒÉÃÁÎÉÅ. ÷ÏÚØ-
Í¾Í ÎÅÍÏÎÏÔÏÎÎÕÀ ÆÕÎËÃÉÀ. ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÏÎÁ ÄÏÌÖÎÁ ÍÅÎÑÔØ ÚÎÁÞÅ-
ÎÉÅ Ó ÅÄÉÎÉÃÙ ÎÁ ÎÕÌØ ÐÒÉ ÉÚÍÅÎÅÎÉÉ ËÁËÏÇÏ-ÔÏ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ Ó ÎÕÌÑ ÎÁ
ÅÄÉÎÉÃÕ (× ÓÁÍÏÍ ÄÅÌÅ, ÂÕÄÅÍ Õ×ÅÌÉÞÉ×ÁÔØ ÁÒÇÕÍÅÎÔÙ ÐÏ ÏÄÎÏÍÕ, × ËÁËÏÊ-ÔÏ
ÍÏÍÅÎÔ ÚÎÁÞÅÎÉÅ ÆÕÎËÃÉÉ ÕÍÅÎØÛÉÔÓÑ.) úÁÆÉËÓÉÒÏ×Á× ÚÎÁÞÅÎÉÑ ÏÓÔÁÌØÎÙÈ
ÁÒÇÕÍÅÎÔÏ× (×ÅÄØ ÍÙ ÓÞÉÔÁÅÍ, ÞÔÏ ËÏÎÓÔÁÎÔÙ ÅÓÔØ), ÐÏÌÕÞÁÅÍ ÏÔÒÉÃÁÎÉÅ.
éÍÅÑ ÏÔÒÉÃÁÎÉÅ É ÎÅÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÕÀ ÆÕÎËÃÉÀ, ÌÅÇËÏ ÐÏÌÕÞÉÔØ ËÏÎ-
ÓÔÁÎÔÙ (ÅÓÌÉ ÉÈ ÎÅ ÂÙÌÏ). ÷ ÓÁÍÏÍ ÄÅÌÅ, ÎÅÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÏÓÔØ ÏÚÎÁÞÁÅÔ,
§2. ðÏÌÎÙÅ ÓÉÓÔÅÍÙ Ó×ÑÚÏË                                               69

ËÏÍÐÏÚÉÃÉÉ ÆÕÎËÃÉÊ ÉÚ ÎÁÂÏÒÁ, Ô. Å. ÚÁÐÉÓÙ×ÁÅÔÓÑ × ×ÉÄÅ ÆÏÒÍÕÌÙ, ÇÄÅ Ó×ÑÚ-
ËÁÍÉ ÓÌÕÖÁÔ ÆÕÎËÃÉÉ ÎÁÂÏÒÁ.) ðÏÄÏÂÎÙÅ ×ÏÐÒÏÓÙ ×ÙÚÙ×ÁÌÉ × Ó×Ͼ ×ÒÅÍÑ
ÂÏÌØÛÏÊ ÉÎÔÅÒÅÓ É ÂÙÌÉ ÈÏÒÏÛÏ ÉÚÕÞÅÎÙ. îÁÞÁÌØÎÙÍ ÜÔÁÐÏÍ Ñ×ÉÌÏÓØ ÔÁËÏÅ
ÕÔ×ÅÒÖÄÅÎÉÅ:

   ôÅÏÒÅÍÁ 22 (ËÒÉÔÅÒÉÊ ðÏÓÔÁ). îÁÂÏÒ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ Ñ×ÌÑÅÔÓÑ ÐÏÌ-
ÎÙÍ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÏÎ ÎÅ ÓÏÄÅÒÖÉÔÓÑ ÃÅÌÉËÏÍ ÎÉ × ÏÄÎÏÍ
ÉÚ ÐÑÔÉ ÓÌÅÄÕÀÝÉÈ ¥ÐÒÅÄÐÏÌÎÙÈ ËÌÁÓÓÏ×¥:
    • ÍÏÎÏÔÏÎÎÙÅ ÆÕÎËÃÉÉ;
    • ÆÕÎËÃÉÉ, ÓÏÈÒÁÎÑÀÝÉÅ ÎÕÌØ;
    • ÆÕÎËÃÉÉ, ÓÏÈÒÁÎÑÀÝÉÅ ÅÄÉÎÉÃÕ;
    • ÌÉÎÅÊÎÙÅ ÆÕÎËÃÉÉ;
    • ÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÙÅ ÆÕÎËÃÉÉ.
(æÕÎËÃÉÑ f ÍÏÎÏÔÏÎÎÁ, ÅÓÌÉ ÏÎÁ ÍÏÎÏÔÏÎÎÏ ÎÅÕÂÙ×ÁÅÔ ÐÏ ËÁÖÄÏÍÕ ÉÚ Ó×Ï-
ÉÈ ÁÒÇÕÍÅÎÔÏ×. æÕÎËÃÉÑ f ÓÏÈÒÁÎÑÅÔ ÎÕÌØ/ ÅÄÉÎÉÃÕ, ÅÓÌÉ f (0, . . . , 0) = 0
(ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ f (1, . . . , 1) = 1). æÕÎËÃÉÑ f ÌÉÎÅÊÎÁ, ÅÓÌÉ ÏÎÁ ÐÒÅÄÓÔÁ-
×ÉÍÁ ÍÎÏÇÏÞÌÅÎÏÍ, × ËÏÔÏÒÏÍ ×ÓÅ ÍÏÎÏÍÙ ÓÏÄÅÒÖÁÔ ÎÅ ÂÏÌÅÅ ÏÄÎÏÊ ÐÅ-
ÒÅÍÅÎÎÏÊ. îÁËÏÎÅÃ, ÆÕÎËÃÉÑ f ÎÁÚÙ×ÁÅÔÓÑ ÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÏÊ, ÅÓÌÉ f (1 −
− p1, . . . , 1 − pn ) = 1 − f (p1, . . . , pn).)

   äÏËÁÚÁÔÅÌØÓÔ×Ï. åÓÌÉ ÎÁÂÏÒ ÓÏÄÅÒÖÉÔÓÑ × ÏÄÎÏÍ ÉÚ ËÌÁÓÓÏ×, ÔÏ É ×ÓÅ
ËÏÍÐÏÚÉÃÉÉ ÔÁËÖÅ ÎÅ ×ÙÈÏÄÑÔ ÚÁ ÐÒÅÄÅÌÙ ÜÔÏÇÏ ËÌÁÓÓÁ (ÌÅÇËÏ ÐÒÏ×ÅÒÉÔØ
ÄÌÑ ËÁÖÄÏÇÏ ÉÚ ËÌÁÓÓÏ× × ÏÔÄÅÌØÎÏÓÔÉ) É ÐÏÜÔÏÍÕ ÎÁÂÏÒ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÏÌ-
ÎÙÍ. äÏËÁÖÅÍ ÏÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ. ðÕÓÔØ ÄÌÑ ËÁÖÄÏÇÏ ËÌÁÓÓÁ ×ÙÂÒÁÎÁ
ËÁËÁÑ-ÔÏ ÆÕÎËÃÉÑ, × Î¾Í ÎÅ ÌÅÖÁÝÁÑ. õÂÅÄÉÍÓÑ, ÞÔÏ Ó ÐÏÍÏÝØÀ ËÏÍÂÉÎÁÃÉÊ
×ÙÂÒÁÎÎÙÈ ÆÕÎËÃÉÊ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ ×ÓÅ ÂÕÌÅ×Ù ÆÕÎËÃÉÉ.
   õ ÎÁÓ ÅÓÔØ ÆÕÎËÃÉÑ, ÎÅ ÓÏÈÒÁÎÑÀÝÁÑ ÎÕÌØ. ðÏÄÓÔÁ×ÉÍ ×ÍÅÓÔÏ ×ÓÅÈ ÁÒÇÕ-
ÍÅÎÔÏ× ÏÄÎÕ É ÔÕ ÖÅ ÐÅÒÅÍÅÎÎÕÀ. ðÏÌÕÞÉÔÓÑ ÆÕÎËÃÉÑ ÏÔ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ,
ÏÔÏÂÒÁÖÁÀÝÁÑ ÎÕÌØ × ÅÄÉÎÉÃÕ, ÔÏ ÅÓÔØ ÌÉÂÏ ËÏÎÓÔÁÎÔÁ 1, ÌÉÂÏ ÏÔÒÉÃÁÎÉÅ.
óÄÅÌÁ× ÔÏ ÖÅ ÓÁÍÏÅ Ó ÆÕÎËÃÉÅÊ, ÎÅ ÓÏÈÒÁÎÑÀÝÅÊ ÅÄÉÎÉÃÕ, ÐÏÌÕÞÉÍ ÌÉÂÏ
ËÏÎÓÔÁÎÔÕ ÎÕÌØ, ÌÉÂÏ ÏÔÒÉÃÁÎÉÅ. ôÁËÉÍ ÏÂÒÁÚÏÍ, Õ ÎÁÓ ÌÉÂÏ ÅÓÔØ ÏÔÒÉÃÁ-
ÎÉÅ, ÌÉÂÏ ÏÂÅ ËÏÎÓÔÁÎÔÙ 0 É 1.
   åÓÌÉ ÅÓÔØ ÏÂÅ ËÏÎÓÔÁÎÔÙ, ÔÏ ×Ó¾ ÒÁ×ÎÏ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ ÏÔÒÉÃÁÎÉÅ. ÷ÏÚØ-
Í¾Í ÎÅÍÏÎÏÔÏÎÎÕÀ ÆÕÎËÃÉÀ. ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÏÎÁ ÄÏÌÖÎÁ ÍÅÎÑÔØ ÚÎÁÞÅ-
ÎÉÅ Ó ÅÄÉÎÉÃÙ ÎÁ ÎÕÌØ ÐÒÉ ÉÚÍÅÎÅÎÉÉ ËÁËÏÇÏ-ÔÏ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ Ó ÎÕÌÑ ÎÁ
ÅÄÉÎÉÃÕ (× ÓÁÍÏÍ ÄÅÌÅ, ÂÕÄÅÍ Õ×ÅÌÉÞÉ×ÁÔØ ÁÒÇÕÍÅÎÔÙ ÐÏ ÏÄÎÏÍÕ, × ËÁËÏÊ-ÔÏ
ÍÏÍÅÎÔ ÚÎÁÞÅÎÉÅ ÆÕÎËÃÉÉ ÕÍÅÎØÛÉÔÓÑ.) úÁÆÉËÓÉÒÏ×Á× ÚÎÁÞÅÎÉÑ ÏÓÔÁÌØÎÙÈ
ÁÒÇÕÍÅÎÔÏ× (×ÅÄØ ÍÙ ÓÞÉÔÁÅÍ, ÞÔÏ ËÏÎÓÔÁÎÔÙ ÅÓÔØ), ÐÏÌÕÞÁÅÍ ÏÔÒÉÃÁÎÉÅ.
   éÍÅÑ ÏÔÒÉÃÁÎÉÅ É ÎÅÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÕÀ ÆÕÎËÃÉÀ, ÌÅÇËÏ ÐÏÌÕÞÉÔØ ËÏÎ-
ÓÔÁÎÔÙ (ÅÓÌÉ ÉÈ ÎÅ ÂÙÌÏ). ÷ ÓÁÍÏÍ ÄÅÌÅ, ÎÅÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÏÓÔØ ÏÚÎÁÞÁÅÔ,

Страницы