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

(4.10)

Доказательство. Учитывая распределительный закон (1.39) и присутствие в каждой суммеровно одного элемента от каждого из Р столбцов ЛО, имеем

Лемма 4.8. ЛО, все элементы которого равны, равен произведению эле­мента на число столбцов

(4.11)

Доказательство. На основании определения ЛО (4.2) при имеем

Лемма 4.9. ЛО, содержащий в качестве элемента бесконечность, сам равен бесконечности

(4.12)

Доказательство. Оно следует непосредственно из определе­ния ЛО (4.2), ибо для каждого данного ЛО множество сумм разби­вается на два подмножества: 1) суммы, включающие от k-го столбца эле­мент и потому равные ∞; 2) конечные по величине суммы, вклю­чающие из k-гo столбца элемент, отличный от

Для изложения последующих свойств ЛО используется разложимость ЛО по любому столбцу (4.13) и следующее

Определение 4.2. Пусть - произвольный М×Р-ЛО (4.2). ЛО, по­лученный из вычеркиванием j-го (j = 1,..., Р) столбца, называет­ся логическим дополнением этого столбца и обозначается

Лемма 4.10. ЛО со столбцом из равных элементов равен сумме этого элемента и логического дополнения столбца

(4.13)

Доказательство формулы (4.13) следует из разложения (4.18), так как в данном случае

Лемма 4.11. Общее для всех элементов некоторого столбца слагаемое можно вынести за знак ЛО

(4.14)

Доказательство. Согласно (4.18) левый ЛО в (4.14)

где - огическое дополнение j-го столбца левого и правого ЛО. Но квадратная скобка в полученном выражении - это ЛО правой части (4.14), разложенный по формуле (4.18).

Лемма 4.12. Общий для всех положительных элементов некоторого

j-го столбца положительный множитель λ можно вынести за знак ЛО в виде слагаемого

(4.15)

Доказательство. Применив разложение (4.18) к левому ЛО в

и учитывая, что λ, aij>0, получаем

Квадратная скобка в полученном выражении есть ЛО правой части (4.15), разложенный согласно (4.18).

Лемма 4.13. Общий для всех положительных элементов некоторого

j-го столбца отрицательный множитель λ можно вынести за знак ЛО в виде слагаемого

(4.16)

Доказательство. Разложив левый ЛО (4.16) и учитывая, что получим

Квадратная скобка полученного выражения - это ЛО правой части (4.16), разложенный по формуле (4.18).

Лемма 4.14 (сложение ЛО). ЛО суммы двух М × Р-матриц и

не превосходит суммы ЛО этих матриц:

(4.17)

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

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

ЛО с ограничениями первого рода, как и порядковые ЛО (§ 2.8 - 2.12), можно представить через ЛО меньших размеров. Начнем с примера.

Пример 4.1. Рассмотрим некоторый 2 × 3-ЛО и распишем его соглас-

но (4.2):

В этом исходном выражении ЛО 23 элементарных операцийВос-

пользовавшись распределительным законом (1.37), вынесем из первых четырех скобок общее слагаемое а11, а из следующих четырех скобок - общее слагаемое а21:

Обе квадратные скобки здесь равны и потому могут быть вынесены за знак фигурных скобок. Окончательное выражение для ЛО:

Оно содержит девять элементарных операцийФигурные скобки

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

что является, очевидно, разложением ЛО по первому столбцу. Комбинируя скобки, из которых выносится общее слагаемое, по-другому, получим разложения ЛО по второму и третьему столбцам.

Важность полученного в примере 4.1 разложения в том, что оно: 1 По­низило размерность ЛО с 2 × 3 до 2 × 2; 2) уменьшило число элементарных операций в выражении ЛО (с 23 до 9) благодаря вынесению за скоб­ки общих слагаемых. Оказывается, что такому разложению можно подверг­нуть любой ЛО с ограничениями первого рода.

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

(4.18)

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

вида для матрицы А, из которой вычеркнут j-й столбец. Тогда ЛО можно расписать в виде

После вынесения за скобки общих слагаемых из одинаково подчеркнутых выражений получим

Вынося теперь за скобки общее слагаемое найдем Подставив последнее выраже­ние в предыдущее, получим (4.18). Разложение (4.18) можно рассматри­вать как некоторый принцип оптимальности, по которому максимальная сумма элементов вида в М × Р-матрице равна сумме максимального элемента произвольного j-го столбца и максимальной суммы элементов видав оставшейся М × (Р - 1)-матрице, получаемой из

матрицы A вычеркиванием j-го столбца.

Разложение ЛО по столбцу (4.18) можно обобщить.

Определение 4.3. Пусть А - произвольный М × Р-ЛО вида (4.2) для матри­цы А (4.1). ЛО, образованный столбцами ЛО называется минором r-го порядка и обозначается а ЛО, полученный из вычеркиванием столбцовназывается логическим дополнением указанных стобцов и обозначается

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

(4.19)