Дискретно-непрерывная математика (стр. 99 )

В итоге получим оценку

(3.44)

Найдем oценку ЛО сверху, используя для этого его точное выраже­ние в КНФ БЛ (2.38). Введем среднее арифметическое значение l второго индекса элемента аij одной дизъюнкции в (2.38). Поскольку в дизъюнк­ции q элементов, а сумма их вторых индексов равна r, то

(3.45)

Сохраним в выражении (2.38) одну дизъюнкцию: Здесь [l] означает округление l до ближайшего боль­шего целого числа, а k - неизвестный второй индекс, определяемый из ус­ловия, налагаемого на сумму вторых индексов:

(3.46)

В результате для оцениваемого ЛО получим неравенство

Так как то из (3.46) имеем Отсюда, учитывая, что элементы в строке ЛО упорядочены по величине, находим Если теперь в выписанном неравенстве для заменить то неравенство лишь усилится. Окончательно получим оценку

(3.47)

Лемма 3.1. Средние d и l связаны соотношением

(3.48)

Доказательство. Рассмотрим по отдельности три возможных слу­чая, полагая — целое; (2) — целое; (3) r/q и

(r — l)/q - дробные. В случае (1)

так что (3.48) справедливо. В случае (2)

так что (3.48) тоже справедливо. В случае (3)где k — целое и Поэтому

и (3.48) снова справедливо. Заметим, чго в общем случае d ≠l.

Теорема 3.2. Значение общего бесконечного ЛО q-го порядка r-го ранга заключено в симметричных границах:

(3.49)

где

Доказательство получается соединением оценок (3.44), (3.47) и с уче­том (3.48).

Для вырожденного ЛО в силу (3.34) и потому нижняя и верхняя оценки (3.49) совпадают, давая точное значение ЛО, т. е. найденные оценки удовлетворяют условию согласованности. Сложность вычисления этих оценок растет как q - 1 (линейно) с увеличением поряд­ка ЛО q. В то же время сложность точного вычисления общего бесконеч­ного ЛО по формулам (2.29), (2.38) растет как qr (выражение (3.8)), по методу дихотомического блочного разложения - как qr2 (выраже­ние (3.18)). Таким образом, и здесь переход к приближенным оценкам позволяет резко уменьшать сложность вычисления ЛО.

3.6. Приближенное вычисление общего конечного логического определителя

Общий конечный ЛО можно расширить до бесконечного (см, § 2.4):

(3.50)

Согласно (3.50) для оценивания конечного ЛО можно использовать нера­венства (3.49). Однако так както величина [l] из (3.49) находится в интервале где Значит, при когда существуют кактак и есть конечные ЛО таких рангов r, что соответствующее значение [l] превы­шает некоторое mk. Согласно (3.50) это означает, что элемент k-й строки ЛО, фигурирующий в оценках (3.49), равен элементу нового, расширенного ЛО. Численно а равен максимальному элементу ис­ходного ЛО. Поэтому оценки (3.49) преобразуются к виду

(3.51)

Но факт в (3.51) следует непосредственно из определения ЛО. Видим, что верхняя оценка (3.49) в применении к общему конечному ЛО с неравнымиможет оказаться тривиальной и малополезной.

Теорема 3.3. Значение общего конечного ЛО q-го порядка т-го ранга с равными длинами строк m заключено в следующих симметричных гра-нииах:

(3.52)

где

Доказательство. Для конечного ЛО с все mi

равны mср. Поэтому всегда [l] ≤ m и по (3.50) все элементы

(k = 1,..., п) из оценок (3.49) — это элементы исходного (нерасширенно­го) ЛО. Таким образом, в этом случае оценки (3.49) бесконечного ЛО сохраняют свой вид и для конечного ЛО.

Рассмотрим общий случай конечного ЛО с произвольными соотно­шениями Найдем оценкусверху, используя точное выражение ЛО в КНФ БЛ (2.39). Действуем по аналогии со случаем беско­нечного ЛО. Введем усредненное взвешенное значение lр второго индек­са ip элемента одной дизъюнкции в (.2.39). Это значит, что сумма вто­рых индексов ip элементов одной дизъюнкции, равная r, теперь распреде­лится между q индексами не поровну, как в (3.45), а пропорционально их весам kр, удовлетворяющим условиюВыбрав веса по формуле получим

(3.53)

Из (3.53) с учетом следует

(3.54)

так что новые индексы lр (р = 1, . . . , q) в сумме по-прежнему дают r, однако уже не превосходят соответствующих mр. Сохраним в выражении (2.39) лишь дизъюнкцию

Здесь k — неизвестный индекс, определяемый условием, налагаемым на сумму всех вторых индексов:

(3.55)

Тогда для оцениваемого ЛО получим неравенство

Поскольку то из (3.55) следует

Отсюда так что, заменив в выписанном неравенстве для элемент получим оценку

. (3.56)

где lр из (3.53).

Найдем оценку ЛО снизу, используя точное выражение определителя в ДНФ БЛ (2.30). Введем среднее взвешенное значение dp второго индек­са ip элемента одной конъюнкции. Так как сумма вторых индексов всех элементов конъюнкции равна q + r — 1, то, сохраняя те же, что и в (3.53), весовые коэффициенты (чтобы обеспечить симметричность верх­ней и нижней оценок), найдем