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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§3. áÒÉÆÍÅÔÉÞÎÏÓÔØ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ 185
Ó 2N + 2 ÐÅÒÅÍÅÎÎÙÍÉ, ËÏÔÏÒÁÑ ÕÔ×ÅÒÖÄÁÅÔ, ÞÔÏ ÄÁÎÎÁÑ ÐÒÏÇÒÁÍÍÁ P ÉÚ
ÓÏÓÔÏÑÎÉÑ, ÇÄÅ ÐÅÒÅÍÅÎÎÙÅ ÒÁ×ÎÙ s
1
, . . . , s
N
, Á ÓÞ¾ÔÞÉË ËÏÍÁÎÄ ÒÁ×ÅÎ p, ÚÁ
ÏÄÉÎ ÛÁÇ ÐÅÒÅÈÏÄÉÔ × ÓÏÓÔÏÑÎÉÅ, ÇÄÅ ÐÅÒÅÍÅÎÎÙÅ ÒÁ×ÎÙ s
0
1
, . . . , s
0
n
, Á ÓÞ¾ÔÞÉË
ËÏÍÁÎÄ ÒÁ×ÅÎ p
0
. (äÏÇÏ×ÏÒÉÍÓÑ, ÞÔÏ ÚÎÁÞÅÎÉÅ p
0
= 0 ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÏÓÔÁÎÏ×ËÅ
ÐÒÏÇÒÁÍÍÙ.) ôÁËÁÑ ÆÏÒÍÕÌÁ Ñ×ÌÑÅÔÓÑ ËÏÎßÀÎËÃÉÅÊ ÏÔÄÅÌØÎÙÈ ÕÔ×ÅÒÖÄÅ-
ÎÉÊ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ËÁÖÄÏÊ ÓÔÒÏËÅ ÐÒÏÇÒÁÍÍÙ. ðÕÓÔØ, ÎÁÐÒÉÍÅÒ, ÓÔÒÏ-
ËÁ 7 ÐÒÏÇÒÁÍÍÙ ÉÍÅÅÔ ×ÉÄ k
2
=k
3
. ôÏÇÄÁ × ËÏÎßÀÎËÃÉÉ ÂÕÄÅÔ ÞÌÅÎ ×ÉÄÁ
(p = 7) ⇒ ((s
0
1
= s
1
) ∧ (s
0
2
= s
3
) ∧ (s
0
3
= s
3
) ∧ . . . ∧ (s
0
N
= s
N
) ∧ (p
0
= 8)).
äÌÑ ÓÔÒÏËÉ Ó ÕÓÌÏ×ÎÙÍÉ ÐÅÒÅÈÏÄÁÍÉ ÔÉÐÁ
3: if (k
5
==0) goto 17; else goto 33;
× ÆÏÒÍÕÌÅ ÂÕÄÅÔ Ä×Á ËÏÎßÀÎËÔÉ×ÎÙÈ ÞÌÅÎÁ (ÎÁ Ä×Á ÓÌÕÞÁÑ ÐÅÒÅÈÏÄÁ)
((p = 3) ∧ (s
5
= 0))⇒((s
0
1
= s
1
) ∧ . . . ∧ (s
0
N
= s
N
) ∧ (p
0
= 17))
É
((p = 3) ∧ (s
5
6= 0))⇒((s
0
1
= s
1
) ∧ . . . ∧ (s
0
N
= s
N
) ∧ (p
0
= 33)).
îÁÄÏ Åݾ ÄÏÂÁ×ÉÔØ ÕÔ×ÅÒÖÄÅÎÉÅ Ï ÔÏÍ, ÞÔÏ ÐÒÉ p = 0 ÒÁÂÏÔÁ ÐÒÅËÒÁÝÁÅÔÓÑ,
ÔÏ ÅÓÔØ ÞÔÏ ÐÅÒÅÍÅÎÎÙÅ ÎÁ ÓÌÅÄÕÀÝÅÍ ÛÁÇÅ ÓÏÈÒÁÎÑÀÔ Ó×ÏÉ ÚÎÁÞÅÎÉÑ, É p
0
ÏÓÔÁ¾ÔÓÑ ÒÁ×ÎÙÍ 0.
ôÁËÉÍ ÏÂÒÁÚÏÍ, ÁÒÉÆÍÅÔÉÞÎÏÓÔØ ÏÄÎÏÇÏ ÛÁÇÁ ÒÁÂÏÔÙ ÐÒÏÇÒÁÍÍÙ ÄÏËÁ-
ÚÁÔØ ÎÅÓÌÏÖÎÏ. ïÓÔÁ¾ÔÓÑ ÇÌÁ×ÎÙÊ ×ÏÐÒÏÓ: ËÁË ÚÁÐÉÓÁÔØ × ×ÉÄÅ ÆÏÒÍÕÌÙ
ÔÏÔ ÆÁËÔ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÛÁÇÏ×, ËÏÔÏÒÁÑ ÎÁÞÉÎÁÅÔÓÑ
Ó ÉÓÈÏÄÎÏÇÏ ÓÏÓÔÏÑÎÉÑ, ÚÁËÁÎÞÉ×ÁÅÔÓÑ × ÄÁÎÎÏÍ É × ËÏÔÏÒÏÊ ËÁÖÄÙÊ ÛÁÇ
ÐÒÁ×ÉÌÅÎ. ôÒÕÄÎÏÓÔØ × ÔÏÍ, ÞÔÏ ÚÄÅÓØ ÎÕÖÎÏ ËÁË ÂÙ ÎÁÐÉÓÁÔØ ÐÅÒÅÍÅÎÎÏÅ
ÞÉÓÌÏ Ë×ÁÎÔÏÒÏ× ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ¡ ÉÌÉ Ë×ÁÎÔÏÒ ¥ÓÕÝÅÓÔ×ÕÅÔ ËÏÎÅÞÎÁÑ ÐÏ-
ÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ¥.
üÔÏ ÄÅÌÁÅÔÓÑ Ó ÐÏÍÏÝØÀ ÐÒɾÍÁ, ÔÒÁÄÉÃÉÏÎÎÏ ÎÁÚÙ×ÁÅÍÏÇÏ β-ÆÕÎËÃÉ-
ÅÊ ç¾ÄÅÌÑ. ÷ÏÔ ÞÔÏ ÉÍÅÅÔÓÑ × ×ÉÄÕ.
ìÅÍÍÁ 1. äÌÑ ÌÀÂÏÇÏ k ÍÏÖÎÏ ÎÁÊÔÉ ÓËÏÌØ ÕÇÏÄÎÏ ÂÏÌØÛÏÅ ÃÅÌÏÅ ÐÏ-
ÌÏÖÉÔÅÌØÎÏÅ ÞÉÓÌÏ b, ÐÒÉ ËÏÔÏÒÏÍ ÐÅÒ×ÙÅ k ÞÌÅÎÏ× ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ
b + 1, 2b + 1, 3b + 1, . . . ÐÏÐÁÒÎÏ ×ÚÁÉÍÎÏ ÐÒÏÓÔÙ.
äÏËÁÚÁÔÅÌØÓÔ×Ï. ìÀÂÏÊ ÏÂÝÉÊ ÐÒÏÓÔÏÊ ÄÅÌÉÔÅÌØ Ä×ÕÈ ÉÚ ÜÔÉÈ ÞÉÓÅÌ ÂÕ-
ÄÅÔ ÄÅÌÉÔÅÌÅÍ ÉÈ ÒÁÚÎÏÓÔÉ, ÔÏ ÅÓÔØ ÞÉÓÌÁ lb ÐÒÉ 0 < l < k; ×ÚÑ× b ËÒÁÔ-
ÎÙÍ k!, ÍÙ ÇÁÒÁÎÔÉÒÕÅÍ, ÞÔÏ ÏÎ ÂÕÄÅÔ ÄÅÌÉÔÅÌÅÍ ÞÉÓÌÁ b, ÎÏ ×ÓÅ ÞÌÅÎÙ
ÎÁÛÅÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ×ÚÁÉÍÎÏ ÐÒÏÓÔÙ Ó b. ìÅÍÍÁ ÄÏËÁÚÁÎÁ.
ìÅÍÍÁ 2. äÌÑ ÌÀÂÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ x
0
, x
1
, . . . , x
n
ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ
ÍÏÖÎÏ ÎÁÊÔÉ ÔÁËÉÅ ÞÉÓÌÁ a É b, ÞÔÏ x
i
ÅÓÔØ ÏÓÔÁÔÏË ÏÔ ÄÅÌÅÎÉÑ a ÎÁ b(i +
+ 1) + 1.
§3. áÒÉÆÍÅÔÉÞÎÏÓÔØ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ                                                   185

Ó 2N + 2 ÐÅÒÅÍÅÎÎÙÍÉ, ËÏÔÏÒÁÑ ÕÔ×ÅÒÖÄÁÅÔ, ÞÔÏ ÄÁÎÎÁÑ ÐÒÏÇÒÁÍÍÁ P ÉÚ
ÓÏÓÔÏÑÎÉÑ, ÇÄÅ ÐÅÒÅÍÅÎÎÙÅ ÒÁ×ÎÙ s1, . . . , sN , Á ÓÞ¾ÔÞÉË ËÏÍÁÎÄ ÒÁ×ÅÎ p, ÚÁ
ÏÄÉÎ ÛÁÇ ÐÅÒÅÈÏÄÉÔ × ÓÏÓÔÏÑÎÉÅ, ÇÄÅ ÐÅÒÅÍÅÎÎÙÅ ÒÁ×ÎÙ s01 , . . . , s0n , Á ÓÞ¾ÔÞÉË
ËÏÍÁÎÄ ÒÁ×ÅÎ p0 . (äÏÇÏ×ÏÒÉÍÓÑ, ÞÔÏ ÚÎÁÞÅÎÉÅ p0 = 0 ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÏÓÔÁÎÏ×ËÅ
ÐÒÏÇÒÁÍÍÙ.) ôÁËÁÑ ÆÏÒÍÕÌÁ Ñ×ÌÑÅÔÓÑ ËÏÎßÀÎËÃÉÅÊ ÏÔÄÅÌØÎÙÈ ÕÔ×ÅÒÖÄÅ-
ÎÉÊ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ËÁÖÄÏÊ ÓÔÒÏËÅ ÐÒÏÇÒÁÍÍÙ. ðÕÓÔØ, ÎÁÐÒÉÍÅÒ, ÓÔÒÏ-
ËÁ 7 ÐÒÏÇÒÁÍÍÙ ÉÍÅÅÔ ×ÉÄ k2=k3. ôÏÇÄÁ × ËÏÎßÀÎËÃÉÉ ÂÕÄÅÔ ÞÌÅÎ ×ÉÄÁ

    (p = 7) ⇒ ((s01 = s1 ) ∧ (s02 = s3 ) ∧ (s03 = s3 ) ∧ . . . ∧ (s0N = sN ) ∧ (p0 = 8)).

äÌÑ ÓÔÒÏËÉ Ó ÕÓÌÏ×ÎÙÍÉ ÐÅÒÅÈÏÄÁÍÉ ÔÉÐÁ
    3: if (k5==0) goto 17; else goto 33;
× ÆÏÒÍÕÌÅ ÂÕÄÅÔ Ä×Á ËÏÎßÀÎËÔÉ×ÎÙÈ ÞÌÅÎÁ (ÎÁ Ä×Á ÓÌÕÞÁÑ ÐÅÒÅÈÏÄÁ)
          ((p = 3) ∧ (s5 = 0))⇒((s01 = s1 ) ∧ . . . ∧ (s0N = sN ) ∧ (p0 = 17))

É
          ((p = 3) ∧ (s5 6= 0))⇒((s01 = s1 ) ∧ . . . ∧ (s0N = sN ) ∧ (p0 = 33)).
îÁÄÏ Åݾ ÄÏÂÁ×ÉÔØ ÕÔ×ÅÒÖÄÅÎÉÅ Ï ÔÏÍ, ÞÔÏ ÐÒÉ p = 0 ÒÁÂÏÔÁ ÐÒÅËÒÁÝÁÅÔÓÑ,
ÔÏ ÅÓÔØ ÞÔÏ ÐÅÒÅÍÅÎÎÙÅ ÎÁ ÓÌÅÄÕÀÝÅÍ ÛÁÇÅ ÓÏÈÒÁÎÑÀÔ Ó×ÏÉ ÚÎÁÞÅÎÉÑ, É p 0
ÏÓÔÁ¾ÔÓÑ ÒÁ×ÎÙÍ 0.
   ôÁËÉÍ ÏÂÒÁÚÏÍ, ÁÒÉÆÍÅÔÉÞÎÏÓÔØ ÏÄÎÏÇÏ ÛÁÇÁ ÒÁÂÏÔÙ ÐÒÏÇÒÁÍÍÙ ÄÏËÁ-
ÚÁÔØ ÎÅÓÌÏÖÎÏ. ïÓÔÁ¾ÔÓÑ ÇÌÁ×ÎÙÊ ×ÏÐÒÏÓ: ËÁË ÚÁÐÉÓÁÔØ × ×ÉÄÅ ÆÏÒÍÕÌÙ
ÔÏÔ ÆÁËÔ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÛÁÇÏ×, ËÏÔÏÒÁÑ ÎÁÞÉÎÁÅÔÓÑ
Ó ÉÓÈÏÄÎÏÇÏ ÓÏÓÔÏÑÎÉÑ, ÚÁËÁÎÞÉ×ÁÅÔÓÑ × ÄÁÎÎÏÍ É × ËÏÔÏÒÏÊ ËÁÖÄÙÊ ÛÁÇ
ÐÒÁ×ÉÌÅÎ. ôÒÕÄÎÏÓÔØ × ÔÏÍ, ÞÔÏ ÚÄÅÓØ ÎÕÖÎÏ ËÁË ÂÙ ÎÁÐÉÓÁÔØ ÐÅÒÅÍÅÎÎÏÅ
ÞÉÓÌÏ Ë×ÁÎÔÏÒÏ× ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ¡ ÉÌÉ Ë×ÁÎÔÏÒ ¥ÓÕÝÅÓÔ×ÕÅÔ ËÏÎÅÞÎÁÑ ÐÏ-
ÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ¥.
   üÔÏ ÄÅÌÁÅÔÓÑ Ó ÐÏÍÏÝØÀ ÐÒɾÍÁ, ÔÒÁÄÉÃÉÏÎÎÏ ÎÁÚÙ×ÁÅÍÏÇÏ β-ÆÕÎËÃÉ-
ÅÊ ç¾ÄÅÌÑ. ÷ÏÔ ÞÔÏ ÉÍÅÅÔÓÑ × ×ÉÄÕ.
   ìÅÍÍÁ 1. äÌÑ ÌÀÂÏÇÏ k ÍÏÖÎÏ ÎÁÊÔÉ ÓËÏÌØ ÕÇÏÄÎÏ ÂÏÌØÛÏÅ ÃÅÌÏÅ ÐÏ-
ÌÏÖÉÔÅÌØÎÏÅ ÞÉÓÌÏ b, ÐÒÉ ËÏÔÏÒÏÍ ÐÅÒ×ÙÅ k ÞÌÅÎÏ× ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ
b + 1, 2b + 1, 3b + 1, . . . ÐÏÐÁÒÎÏ ×ÚÁÉÍÎÏ ÐÒÏÓÔÙ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. ìÀÂÏÊ ÏÂÝÉÊ ÐÒÏÓÔÏÊ ÄÅÌÉÔÅÌØ Ä×ÕÈ ÉÚ ÜÔÉÈ ÞÉÓÅÌ ÂÕ-
ÄÅÔ ÄÅÌÉÔÅÌÅÍ ÉÈ ÒÁÚÎÏÓÔÉ, ÔÏ ÅÓÔØ ÞÉÓÌÁ lb ÐÒÉ 0 < l < k; ×ÚÑ× b ËÒÁÔ-
ÎÙÍ k!, ÍÙ ÇÁÒÁÎÔÉÒÕÅÍ, ÞÔÏ ÏÎ ÂÕÄÅÔ ÄÅÌÉÔÅÌÅÍ ÞÉÓÌÁ b, ÎÏ ×ÓÅ ÞÌÅÎÙ
ÎÁÛÅÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ×ÚÁÉÍÎÏ ÐÒÏÓÔÙ Ó b. ìÅÍÍÁ ÄÏËÁÚÁÎÁ.
   ìÅÍÍÁ 2. äÌÑ ÌÀÂÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ x0, x1, . . . , xn ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ
ÍÏÖÎÏ ÎÁÊÔÉ ÔÁËÉÅ ÞÉÓÌÁ a É b, ÞÔÏ xi ÅÓÔØ ÏÓÔÁÔÏË ÏÔ ÄÅÌÅÎÉÑ a ÎÁ b(i +
+ 1) + 1.

Страницы