\input style
\chapter{6 o proektirovanii pravil'no zavershaemyh konstrukcij}

oSNOVNAYA TEOREMA DLYA KONSTRUKCII POVTORENIYA  PRIMENITELXNO K 
USLOVIYU $P$, SOHRANYAEMOMU INVARIANTNO ISTINNYM, UTVERZHDAET, CHTO
$$ 
(P \and \wp (DO, T) ) \Rightarrow (DO, P \and \non BB) 
$$

zDESX CHLEN $\wp(DO, T)$ PREDSTAVLYAET SOBOJ SLABEJSHEE PREDUSLOVIE, 
TAKOE, CHTO KONSTRUKCIYA POVTORENIYA ZAVVERSHITSYA. eSLI ZADANA 
PROIZVOLXNAYA KONSTRUKCIYA DO, TO V OBSHCHEM SLUCHAE OCHENX TRUDNO (A 
MOZHET BYTX, NEVOZMOZHNO) OPREDELITX $\wp (DO, T)$. pO|TOMU YA 
PREDLAGAYU PROEKTIROVATX NASHI KONSTRUKCII POVTORENIYA, POSTOYANNO 
POMNYA O TREBOVANII ZAVERSHIMOSTI, T. E. PREDLAGAYU ISKATX 
PODHODYASHCHEE DOKAZATELXSTVO ZAVERSHIMOSTI I STROITX PROGRAMMU TAKIM 
SPOSOBOM, CHTOBY ONA UDOVLETVORYALA PREDPOLOZHENIYAM, NA KOTORYH 
OSNOVYVAETSYA |TO DOKAZATELXSTVO. 

pREDPOLOZHIM OPYATX, CHTO $P$ --- OTNOSHENIE, KOTOROE SOHRANYAETSYA 
INVARIANTNO ISTINNYM, T.E.
$$ 
(P \and BB) \Rightarrow \wp(IF, P)\qquad\hbox{ DLYA VSEH SOSTOYANIJ }
$$
pUSTX $t$ --- KONECHNAYA CELOCHISLENNAYA FUNKCIYA OT TEKUSHCHEGO 
SOSTOYANIYA, TAKAYA, CHTO
$$
 (P \and BB) \Rightarrow (t>0) \qquad\hbox{DLYA VSEH SOSTOYANIJ }
$$
I, KROME TOGO, DLYA LYUBOGO ZNACHENIYA $t_0$ I DLYA VSEH 
$$
 (P \and BB \and t\le t_0+1) \Rightarrow \wp(IF, t\le t_0) \eqno (3) 
$$
tOGDA MY DOKAZHEM, CHTO 
$$ 
P \Rightarrow \wp(DO, T)\qquad\hbox{ DLYA VSEH SOSTOYANIJ }\eqno(4) 
$$
sOPOSTAVIV |TOT FAKT S OSNOVNOJ TEOREMOJ DLYA POVTORENIYA, MY MOZHEM 
ZAKLYUCHITX, CHTO IMEEM DLYA VSEH SOSTOYANIJ
$$ 
P \Rightarrow \wp(DO, P \and \non BB)\eqno(5)
$$

mY POKAZHEM |TO, DOKAZAV SNACHALA METODOM MATEMATICHESKOJ INDUKCII, 
CHTO
$$ 
(P \and t\le k) \Rightarrow H_k(T)\qquad\hbox{DLYA VSEH 
SOSTOYANIJ}\eqno(6) 
$$
SPRAVEDLIVO PRI VSEH $k\ge 0$. nACHNEM S OBOSNOVANIYA ISTINNOSTI 
(6) PRI $k=0$. pOSKOLXKU $n_0(t)=\non vv$, NAM TREBUETSYA 
POKAZATX, CHTO
$$ 
(P \and t \le 0) \Rightarrow \non BB \qquad\hbox{DLYA VSEH SOSTOYANIJ}
\eqno (7) 
$$
oDNAKO 7 --- |TO PROSTO DRUGAYA FORMA ZAPISI VYRAZHENIYA (2): OBA 
ONI RAVNY VYRAZHENIYU
$$ 
\non P \or \non BB \or (t>0) 
$$ 
I PO|TOMU (6) SPRAVEDLIVO PRI $k=0$. 

pREDPOLOZHIM TEPERX, CHTO (6) SPRAVEDLIVO PRI $k=K$; TOGDA
$$ 
\eqalign{ 
(P \and BB \and t\le K+l) & \Rightarrow \wp(IF, P \and t \le K)\cr 
& \Rightarrow \wp(IF,H_K(T));\cr 
} (P \and \non BB \and t\le K+1) \Rightarrow \non BB=H_0(T) 
$$
i |TI DVA LOGICHESKIH SLEDOVANIYA MOZHNO OB®EDINITX (IZ $A \Rightarrow B$ I 
$B \Rightarrow D$  MY MOZHEM ZAKLYUCHITX, CHTO SPRAVEDLIVO $(A \or B \Rightarrow C \or 
D)$):
$$ 
(P \and t\le K+1) \Rightarrow \wp(IF,H_K(T)) \or H_0(t)=H_{K+1}(T) 
$$
I TEM SAMYM ISTINNOSTX (6) DOKAZANA DLYA VSEH $k\ge 0$. pOSKOLXKU 
$t$ --- OGRANICHENNAYA FUNKCIYA, MY IMEEM
$$ 
(\exists k: k\ge 0 : t\le k) 
$$ 
I
$$ 
\eqalign{ 
P& \Rightarrow (\exists k: k\ge 0 : P \and t\le k)\cr  
& \Rightarrow (\exists k:k\ge 0: H_k(T))\cr  
&=\wp(DO, T)\cr 
}
$$
I TEM SAMYM DOKAZANO (4).

iNTUITIVNO TEOREMA SOVERSHENNO YASNA. s ODNOJ STORONY, $P$ 
OSTANETSYA ISTINOJ, A SLEDOVATELXNO, $t\ge 0$ TOZHE OSTANETSYA 
ISTINOJ; S DRUGOJ STORONY, IZ OTNOSHENIYA (3) SLEDUET, CHTO KAZHDAYA 
VYBORKA OHRANYAEMOJ KOMANDY PRIVEDET K |FFEKTIVNOMU UMENXSHENIYU $t$  
PO KRAJNEJ MERE NA 1. nEOGRANICHENNOE KOLICHESTVO VYBOROK 
OHRANYAEMYH KOMAND UMENXSHILO BY ZNACHENIE $t$ NIZHE LYUBOGO PREDELA, 
CHTO PRIVELO BY K PROTIVORECHIYU. 

pRIMENIMOSTX |TOJ TEOREMY OSNOVYVAETSYA NA VYPOLNENII USLOVIJ (2) 
I (3). oTNOSHENIE (2) YAVLYAETSYA DOSTATOCHNO PROSTYM, OTNOSHENIE (3) 
VYGLYADIT BOLEE ZAPUTANNYM. nASHA OSNOVNAYA TEOREMA DLYA KONSTRUKCII 
POVTORENIYA PRI 
$$ 
\eqalign{ 
Q&= (P \and BB \and t\le t_0+1)\cr 
R&=(t\le t_0)\cr 
}
$$
(PRISUTSTVIE SVOBODNOJ PEREMENNOJ $t_0$ V OBOIH PREDIKATAH 
YAVLYAETSYA PRICHINOJ TOGO, CHTO MY GOVORILI O "PARE PREDIKATOV") 
POZVOLYAET NAM ZAKLYUCHITX, CHTO USLOVIE (3) SPRAVEDLIVO, ESLI
$$ 
(\forall j: 1\le j \le n: (P \and B_j \and t\le 
t_0+1) \Rightarrow \wp(SL_j, t\le t_0)) 
$$

iNACHE GOVORYA, NAM NUZHNO DOKAZATX DLYA VSYAKOJ OHRANYAEMOJ KOMANDY, 
CHTO VYBORKA PRIVEDET K |FFEKTIVNOMU yMENXSHENIYU $t$. pOMNYA O TOM, 
CHTO $t$ YAVLYAETSYA FUNKCIEJ OT TEKUSHCHEGO SOSTOYANIYA, MY MOZHEM 
RASSMOTRETX
$$ 
\wp(SL_j, t\le t_0) \eqno (8)
$$
eTO PREDIKAT, VKLYUCHAYUSHCHIJ, POMIMO KOORDINATNYH PEREMENNYH 
PROSTRANSTVA SOSTOYANIJ, TAKZHE I SVOBODNUYU PEREMENNUYU $t_0$. dO 
SIH POR MY RASSMATRIVALI TAKOJ PREDIKAT KAK PREDIKAT, 
HARAKTERIZUYUSHCHIJ NEKOE PODMNOZHESTVO SOSTOYANIJ. oDNAKO DLYA LYUBOGO 
ZADANNOGO SOSTOYANIYA MY MOZHEM TAKZHE RASSMATRIVATX PREDIKAT KAK 
USLOVIE, NALAGAEMOE NA $t_0$. pUSTX $t_0=t_{min}$ 
PREDSTAVLYAET SOBOJ MINIMALXNOE RESHENIE URAVNENIYA (8) OTNOSITELXNO 
$t_0$, TOGDA MY MOZHEM INTERPRETIROVATX ZNACHENIE $t_{min}$ KAK 
NAIMENXSHUYU VERHNYUYU GRANICU DLYA KONECHNOGO ZNACHENIYA $t$. eSLI 
VSPOMNITX, CHTO, PODOBNO FUNKCII $t$, $t_{min}$ TAKZHE YAVLYAETSYA 
FUNKCIEJ OT TEKUSHCHEGO SOSTOYANIYA, TO MOZHNO INTERPRETIROVATX 
PREDIKAT
$$ 
t_{min}\le t-1 
$$
KAK SLABEJSHEE PREDUSLOVIE, PRI KOTOROM GARANTIRUETSYA, CHTO 
VYPOLNENIE $SL_j$, uMENXSHIT ZNACHENIE $t$ PO KRAJNEJ MERE NA 1.

oBOZNACHIM |TO PREDUSLOVIE, GDE --- MY POVTORYAEM ---ARGUMENT 
YAVLYAETSYA CELOCHISLENNOJ FUNKCIEJ OT TEKUSHCHEGO SOSTOYANIYA, CHEREZ

$$ 
\wdec(SL_j, t) 
$$
pRI |TOM INVARIANTNOSTX $P$ I |FFEKTIVNOE UMENXSHENIE $t$ 
GARANTIRUYUTSYA, ESLI MY IMEEM PRI VSEH ZNACHENIYAH $j$
$$ 
(P \and B_j) \Rightarrow (\wp(SL_j, P)  \and \wdec (SL_j,t) ) 
$$

oBYCHNO PRAKTICHESKIJ SPOSOB OTYSKANIYA PODHODYASHCHEGO PREDOHRANITELYA 
$B_j$ SOSTOIT V SLEDUYUSHCHEM. uRAVNENIE (9) OTNOSITSYA K TIPU
$$ 
(P \and Q) \Rightarrow R 
$$
GDE (PRAKTICHESKI VYCHISLIMOE!) ZNACHENIE $Q$ NUZHNO NAJTI DLYA 
ZADANNYH ZNACHENIJ $P$ I $R$. mY ZAMECHAEM, CHTO

\medskip
\item{1.} $Q=R$ YAVLYAETSYA RESHENIEM.
\item{2.} $Q=(Q1 \and Q2)$ YAVLYAETSYA RESHENIEM I $r \Rightarrow Q2$, TO $Q1$ 
TOZHE YAVLYAETSYA RESHENIEM.
\item{3.} eSLI $Q=(Q1 \or Q2)$ YAVLYAETSYA RESHENIEM I $r \Rightarrow \non Q2$, 
(ILI, CHTO SVODITSYA K TOMU ZHE SAMOMU, $(P \and Q2) = F)$, TO $Q1$ 
TOZHE YAVLYAETSYA RESHENIEM.
\item{4.} eSLI $Q$ YAVLYAETSYA RESHENIEM I $Q1 \Rightarrow Q$, TO $Q1$ TOZHE 
YAVLYAETSYA RESHENIEM.
\medskip

{\sl zAMECHANIE 1.} eSLI, DEJSTVUYA TAKIM OBRAZOM, MY PRIHODIM K 
KANDIDATURE $Q$ DLYA $B_j$, TAKOJ, CHTO $r \Rightarrow \non Q$, TO |TA 
KANDIDATURA MOZHET BYTX DALEE UPROSHCHENA (V SOOTVETSTVII S 
PREDYDUSHCHIM NABLYUDENIEM 3, POSKOLXKU PRI LYUBOM $Q$ MY IMEEM 
$Q=(\var{LOZHX} \or Q))$ K VIDU $Q=\var{LOZHX}$; |TO OZNACHAET, CHTO 
RASSMATRIVAEMAYA OHRANYAEMAYA KOMANDA VVEDENA NEUDACHNO: EE MOZHNO 
ISKLYUCHITX IZ NABORA, POTOMU CHTO ONA NIKOGDA NE BUDET VYBIRATXSYA. 
{\sl(kONEC ZAMECHANIYA 1.)}

{\sl zAMECHANIE 2.} chASTO NA PRAKTIKE RASSHCHEPLYAYUT URAVNENIE (9) NA 
DVA URAVNENIYA:
$$ 
\eqalignno{ 
(P \and B_j)& \Rightarrow \wp(SL_j, P ) &  (9A)\cr
(P \and B_j)& \Rightarrow \wdec(SL_j, t) & (9B)\cr
}
$$
I RASSMATRIVAYUT IH PO OTDELXNOSTI. tEM SAMYM RAZDELYAYUTSYA DVE 
ZADACHI: $(9A)$ OTNOSITSYA K TOMU, CHTO OSTAETSYA INVARIANTNYM, TOGDA 
KAK $(9B)$ OTNOSITSYA K TOMU, CHTO OBESPECHIVAET PRODVIZHENIE VPERED. 
eSLI, IMEYA DELO S URAVNENIEM $(9A)$, MY PRIHODIM K RESHENIYU 
$B_j$, TAKOMU, CHTO $r \Rightarrow v_j$, TO TOGDA OCHEVIDNO, CHTO |TO 
USLOVIE NE BUDET UDOVLETVORYATX URAVNENIYU $(9B)$, POSKOLXKU PRI 
TAKOM $B_j$ INVARIANTNOSTX $r$ PRIVELA BY K 
NEDETERMINIROVANNOSTI {\sl(kONEC ZAMECHANIYA 2.)}


tAKIM OBRAZOM, MY MOZHEM POSTROITX KONSTRUKCIYU DO, TAKUYU, CHTO
$$ 
P \Rightarrow \wp(DO, r \and \non BB) 
$$
nASHI USLOVIYA $B_j$ DOLZHNY BYTX DOSTATOCHNO SILXNYMI, CHTOBY 
UDOVLETVORYALISX SLEDOVANIYA (9); V REZULXTATE |TOGO NOVOE 
GARANTIRUEMOE POSTUSLOVIE $P \and \non BB$  MOZHET OKAZATXSYA 
SLISHKOM SLABYM I NE OBESPECHITX NAM ZHELAEMOGO POSTUSLOVIYA $R$. v 
TAKOM SLUCHAE MY VSE-TAKI NE RESHILI NASHU PROBLEMU I NAM SLEDUET 
RASSMOTRETX DRUGIE VOZMOZHNOSTI.

\bye