Изменения
→Доказательство
|id=theorem6.13.
|statement=Пусть <tex>O_{ij}</tex> — операция, которую планируют строчкой (*) или (**) и <tex>t = LAST(i) > T1(T2)</tex>. Тогда <tex>A(t) = \emptyset</tex> <tex>(B(t) = \emptyset)</tex>
|proof=Предположим что <tex> A(t) \neq \emptyset</tex> <tex> (B(t) \neq \emptyset)</tex>. Поскольку <tex> A(T1) = \emptyset</tex> <tex> (B(T2) = \emptyset )</tex>, из предыдущей леммы следует, что <tex> A(t) </tex> и <tex> B(t-1) </tex> <tex> (B(t) </tex> и <tex> A(t-1)) </tex> являются операциями одной и той же задачи <tex> k</tex>. Так как <tex> LAST (i)= t</tex>, у нас то должно быть значение <tex> k \neq i</tex>. Это невозможно, т.к. при <tex> LAST (i) = t</tex> и <tex> \mu_{ij} = A(\mu_{ij} = B) </tex> , <tex> B(t - 1) = O_{i,j-1}</tex> <tex>(A(t - 1) = O_{i,j-1})</tex>.
}}
