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

(3.57)

Сохраним в выражении (2.30) одну конъюнкцию где k — неизвестный индекс, определяемый условием, налагаемым на сумму вторых индексов:

(3.58)

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

то из (3.58) следует

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

(3.59)

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

(3.60)

где

Доказательство получается соединением оценок (3.56), (3.59). Для оп­ределителя с равными длинами строк имеем

l 1 = l2 = . . . = lq = l = r/q,

причем в силу r≤ mq справедливо так что символы в (3.60) можно опустить. Учитывая еще (3.48), видим, что для названного ЛО оценки (3.60) переходят в полученные ранее оцен­ки (3.52).

Вырожденный конечный ЛО — это частный случай ЛО с равными длина­ми строк, в котором в силу (3.34) так что ниж­няя и верхняя оценки (3.52) совпадают, давая точное значение ЛО. Таким образом, полученные оценки (3.52), (3.60) удовлетворяют условию сог­ласованности.

Сложность вычисления найденных оценок растет как q — 1. Сложность точного вычисления общего конечного ЛО по формулам (2.30), (2.39) растет как qr (см. (3.8)), а по методу дихотомического блочного разло­жения - как qr2 (при r ≤ т) или mqr (при r > т) (см. (3.31)). Опять видим резкое уменьшение сложности вычисления ЛО при переходе к при­ближенным оценкам.

Пример 3.1. Оценить ЛО

Так как длины строк одинаковы (т = 15), то используем оценки (3.52). Здесь так что

или Применение к данному примеру наиболее экономного из точных методов — блочной дихотомии потребовало бы выполнения qr2 = 3 • 132 = 507 операций.

3.7. Вычисление семейств логических определителей

На практике часто необходимо вычислить не один ЛО, а целое семейство ЛО где n — число элементов ЛО. Использование для этого даже наименее трудоемкого из точных методов — метода последователь­ных блочных разложений — приводит к суммарной сложности вычислений порядка n3 (см. (3.31), (3.32)), что не всегда приемлемо. Применение же приближенного метода здесь не проходит, так как при этом можно полу­чить одинаковые границы для группы ЛО с несколькими последователь­ными значениями ранга r. Выходом из положения во многих случаях ока­зывается использование для вычислений усеченных поэлементных разложе­ний ЛО. Эти разложения отличаются от полных поэлементных разложе­ний (§2.8 — 2.10) тем, что содержат фиксированное, не зависящее от п число конъюнкций элементов с их логическими дополнениями. Мы рас­смотрим усеченное разложение только ЛО-столбца.

Теорема 3.5. ЛО-столбец r-го ранга с п+ 1 элементами

можно выразить через ЛО-столбцы с п элементами в виде

(3.61а) (3.61б) (3.61в)

Доказательство. Обозначим а(r)(n) r-й порядковый элемент а(r) множестваиз n элементов. По определению ЛО

Поэтому формулы (3.61) можно трактовать в терминах порядковых элементов множеств Запишем с помощью многоместной конъюнкции БЛ

Это доказыва­ет формулу (3.61а). Аналогично с использованием многоместной дизъюнк­ции БЛ имеем

что доказывает формулу (3.61в).

Докажем формулу (3.61б). То, какой из элементов множества Аn+ 1 окажется в нем r-м (r = 2, 3, . . . , п) порядковым элементом а (r)(n + 1), зависит от положения дополнительного элемента an+1, введение которого в множество Аn превращает его в множество Аn+ 1. Если an+ 1 больше эле­мента совпадает сЕсли an+ 1 заключено между то совпадает с ап+1. Наконец, если ап+1 меньше то совпадает с Таким образом,

(3.62)

Первые две строки выражения (3.62) можно объединить в одну, ис­пользуя конъюнкцию БЛ:

(3.63)

Условие первой строки в (3.63) эквивалентно следующему:

(3.64) Действительно, из левого условия (3.64) следует правое, так как по оп-ределению С другой стороны, из правого условия следует левое, так как первое, рассматриваемое как неравенство, имеет решение (см. гл. 1) : или

Условие второй строки в (3.63) тоже эквивалентно другому

(3.65)

В самом деле, из левого условия (3.65) следует правое, так как по опре­делению конъюнкции БЛ Из правого условия сле­дует левое, поскольку правое есть неравенство, имеющее единственное решение (второе формальное решение противоречит определению Заменим условия в формуле (3.63) эквивалентными им согласно (3.64) и (3.65) и получим

(3.66)

Обе строки в (3.66) объединим в одну, используя дизъюнкцию БЛ:

(3.67)

Полученное выражение есть записанная в других обозначениях форму­ла (3.61 б), что завершает доказательство теоремы.

Формулы (3.61) позволяют вычислять ЛО итерацией по числу эле­ментов п. Такая процедура вычислений особенно эффективна, когда, помимо отыскания ЛО для множества Аn требуется

находить ЛО для некоторых подмножеств множества Аn.

Оценим сложность N (n) вычисления семейства ЛО-столбцов с n элементами при помощи разложения (3.61). Допустим, что указанное семейство уже вычислено, и на его основе требуется вычислить новое семейство Как видно из (3.61), для этого придется выполнить одну операцию БЛ (двухместную конъюнкцию) для вы­числения ЛО одну операцию БЛ (двухместную дизъюнкцию) для вычисления ЛО и по две операции БЛ (конъюнкция и дизъюнкция) для вычисления каждого из ЛО Общее число выполненных операций Таким образом, искомая функция сложности N(n) удовлетворяет разностному уравнению