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

Поэтому Отсюда, учитывая соотношение ЛО (5.14) и очевидное свойство А+ = В+, находим

Лемма 5.8. В суммирующем ЛО слагаемое любого отдельного элемента можно вынести за знак ЛО

(5.15)

Доказательство следует из определения (5.3) суммирующего ЛО.

5.4. Разложения логических определителей

ЛО с ограничениями на область разлагаются на ЛО меньших размеров, подобно ЛО уже рассмотренных типов (гл. 3,4).

Определение 5.3. Пусть- произвольный т ×n-ЛО (5.1). ЛО, получен­ный из вычеркиванием i- й строки, называется логическим дополнением этой строки и обозначается а ЛО, полученный из вычеркиванием j-го столбца, — логическим дополнением этого столбца и обозначается Аналогично определяются логические дополнения i-й строки и j-го столбца в ЛО

Теорема 5.1. ЛО вида (5.1) можно разложить по его угловому эле­менту а11 или атп, представив в виде суммы этого элемента, и дизъюнкции БЛ логических дополнений строки и столбца, на пересечении которых стоит этот элемент:

(5.16)

Доказательство. Множество всех нисходящих ступенчатых путей (1,1) в матрицей можно разделить на два клас­са В соответствии с этим имеем

что доказывает первое соотношение. Аналогично, но с разбиением множест­ва путей на классы и доказывается второе соотношение.

Теорема 5.2. ЛО вида (5.2) можно разложить по первой строке и первому столбцу или по последней строке и последнему столбцу, пред­ставив в виде конъюнкции БЛ сумм элементов указанных строк или столбцов и их логических дополнений:

(5.17)

Доказательство. Используя соотношение (5.14) между дизъюнк­тивным, конъюнктивным и суммирующем ЛО, разложение (5.16) и рас­пределительные законы (1.38), (1.47), получим

и после внесения в скобки внешних слагаемых получаем первое соотноше­ние (5.17). Доказательство второго соотношения аналогично.

Определение 5.4. Пусть — произвольный т×n-ЛО (5.1). ЛО, полу­ченный из вычеркиванием столбцов, стоящих правее элемента ark, и строк, стоящих ниженазывается левым логическим дополнением

элемента в ЛО и обозначается Далее, ЛО, полученный из вычеркиванием столбцов, стоящих левее и строк, стоящих выше называется правым логическим дополнением в ЛОи обозна­чается Аналогично определяются левое и правое логические дополнения элемента в ЛО

Теорема 5.3. ЛО вида (5.1) можно разложить по произвольной строке или столбцу в виде

(5.18)

Доказательство. Обозначим сумму эле-

ментов матрицы А, расположенных вдоль q-ro нисходящего ступенчатого пути, начинающегося клеткой (р, s), оканчивающегося клеткой (l, t) и проходящего через клетку (r, k) (если прохождение через клетку (r, k) не оговаривается, символ (r, k) опускается). Тогда ЛО можно вы­разить р виде

что доказывает второе соотношение (5.18). Первое соотношение доказы­вается аналогично.

Теорема 5.4. ЛО вида (5.1) можно разложить по произвольной строке или столбцу в виде следующего варианта разложения (5.17) :

(5.19)

Доказательство. ЛО можно выразить в виде

что дает второе соотношение (5.19). Первое соотношение доказывается аналогично.

Теорема 5.5. ЛО вида (5.2) можно разложить по произвольной строке и столбцу в виде

(5.20)

Здесь или

Доказательство. Используя соотношение (5.14) между дизъюнк­тивным, конъюнктивным и суммирующим ЛО, разложение (5.18) и рас­пределительные законы (1.38), (1.47), запишем

и после внесения в скобки внешних слагаемых получаем второе соотно­шение (5.20). Доказательство первого соотношения аналогично.

Отметим, что можно вывести родственные (5.20) разложения, бази­руясь не на (5.18), а на (5.19).

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

Вычисление ЛО с ограничениями на область понимается в том же смысле, что и вычисление ЛО с ограничениями на сумму элементов (§ 4.11).

Суммирующий ЛО А+ можно вычислять непосредственно по опреде­лению (5.3). Сложность такого вычисления (количество двухместных операций сложения)

(5.21)

растет достаточно медленно с увеличением размеров т×п ЛО, что позво­ляет вычислять большие суммирующие ЛО.

Дизъюнктивный ЛОможно вычислять непосредственно по опреде­лению (5.1) (путем перечисления всех ступенчатых сумм и последующего выбора максимальной суммы) либо с помощью последовательных разло­жений на меньшие ЛО на основании формул разложения (из которых наиболее удобны формулы (5.16)). В первом случае сложность вычис­лений (суммарное число двухместных операций

(5.22)

где М(т, п) — число нисходящих ступенчатых путей в т × n - матрице А. Это число удовлетворяет разностному уравнению

(5.23)

Действительно, при добавлении к т × n-матрице А снизу одной строки каждый нисходящий ступенчатый путь в А, где формирует один нисходящий ступенчатый путь из левой верхней в правую нижнюю клетку новой матрицы. Решая уравнение (5.23), последователь­но находим

(5.24)

Из (5.22), (5.24) видно, что при и фиксированных m сложность N

растет как Аналогично растет Т при и фиксированном п. Это принципиально позволяет вычислять довольно большие ЛО. Одна­ко для практической реализации этого метода вычислений надо еще иметь алгоритм перечисления всех ступенчатых путей (сумм) матрицы, что обычно бывает громоздко.