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

где N(1) = 0. (4.47)

Полагаем, что r фиксировано и не зависит от М; М имеет вид М =kr, задано, ибо получающиеся в результате последователь­ного разложения по (4.43), (4.44) r × r - ЛО уже нельзя вычислить разложе­нием по r строкам (столбцам). В этих условиях из (4.47) можно последо­вательно найти

(4.48)

Заменив в (4.48) kr на М, выразив через факториалы и отбросив

константы 1 (что завышает оценку N), после упрощения получим оконча­тельно

где k велико. (4.49)

Сравнив оценки сложности (4.46) и (4.49), видим, что разложение по со­вокупности r строк или столбцов приводит к существенно более простому представлению ЛО, чем разложение по строке или столбцу.

4.9. Логические определители четвертого рода и их свойства

Будем рассматривать вместе с основной М ×P"-матрицей (4.1) также М × Р-матрицу ограничений

(4.50)

В обеих матрицах вводим все возможные суммы элементов содержащие каждая точно один элемент из каждого столбца своей матрицы. Общее число таких сумм Мр. Номера q сумм считаются одинаковыми, если эти суммы образованы соответственными элементами матриц А и В.

Определение 4.10. Назовем ЛО с ограничениями четвертого рода для матрицы А при матрице ограничений В и границе b выражения

(4.51)

(4.52)

т. е. дизъюнкцию (конъюнкцию) БЛ всех сумм элементов A, содержащих каждая ровно один элемент из каждого столбца А и таких, что соответст­вующая сумма элементов В не превосходит границы b. Как и выше, не ограничивая общности, можно рассматривать только один ЛО - (4.51).

Теорема 4.9. Для существования у матрицы А ЛО вида (4.51) и вида (4.52) при матрице ограничений В и границе b необходимо и

достаточно, чтобы ЛО вида (4.3) от матрицы В удовлетворял неравен­ству

(4.53)

Доказательство. Согласно (4.51), (4.52) ЛО равны

соответственно максимальной и минимальной из множества сумм удовлетворяющих ограничениям Поэтому указанные ЛО существуют, только если множество сумм не пусто. Последнее выполняется, только если хотя бы одна сумма удовлетворяет ограничениюЭто значит, что хотя бы одна из сумм должна не превосходить b, что имеет место, лишь когда минимальная из сумм не превосходит b, т. е. Последнее неравенство — развернутая запись неравенства (4.53).

ЛО четвертого рода обладают свойствами ЛО первого рода, сформули­рованными в леммах 4.3 - 4.8, что доказывается так же. Далее, они обла­дают тремя нижеследующими свойствами, аналогичными свойствам из лемм 4.1, 4.2, 4.9.

Лемма 4.19. Перестановка местами двух строк основной матрицы А одновременно с перестановкой соответствующих строк матрицы ограни­чений В не меняет величины ЛО:

(4.54)

Здесь- новая матрица ограничений, полученная из исход-

ной путем перестановки r-й и k-й строк.

Доказательство. При указанной перестановке множество сумм из определения ЛО (4.51) не меняется.

Лемма 4.20. Перестановка местами двух столбцов основной матрицы А одновременно с перестановкой соответствующих столбцов матрицы огра­ничений В не меняет величины ЛО:

(4.55)

Здесь— новая матрица ограничений, полученная из исходной перестановкой r-го и k-ro столбцов.

Доказательство аналогично предыдущему.

Лемма 4.21. ЛО, содержащий в качестве элемента ark бесконечность, сам равен бесконечности, если среди сумм включающих элемент , есть хотя бы одна, удовлетворяющая ограничению

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

Нижеследующие два свойства ЛО вытекают из разложимости ЛО по любому столбцу (4.59) и используют

Определение 4.11. Пусть - произвольный М×Р- ЛО (4.51). Логическим дополнением элемента в этом ЛО называется ЛО, полученный из вычеркиванием k-го столбца, в котором расположен элемент (при этом вычеркивается и k-й столбец матрицы ограничений В) и уменьшением границы b на Таким образом,

(4.56)

Лемма 4.22. ЛО со столбцом из равных элементов равен сумме этого элемента и дизъюнкции БЛ логических дополнений всех элементов столбца

(4.57)

Доказательство (4.57) получается из разложения (4.59) с учетом того, чго в данном случаеи потому а можно вынести за

знак .

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

(4.58)

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

где—логическое дополнение (r, k)-го элемента левого и правого ЛО. Но квадратная скобка в полученном выражении — это ЛО правой части (4.58), разложенный согласно (4.59).

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

Разложение ЛО с ограничениями четвертого рода на меньшие ЛО по своим целям аналогично разложениям уже рассмотренных ЛО.

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

(4.59)

Д о к а з ат е л ь с т в о. Распишем ЛО в виде

Вынесем за знаки не зависящие от q слагаемые

Сравнив вторые слагаемые скобок с выражением (4.56), получим (4.59).

Определение 4.12. Пусть -произвольный M×P- ЛО (4.51). Назовем р-м минором r-го порядка образованным из множества столбцов ЛО р-ю сумму вида

удовлетворяющую ограничениюТаким образом,

(4.60)

Назовем далее логическим дополнением минора в ЛО ЛО, полученный из :

1) вычеркиванием всех столбцов множества Вr;

2) отнесением ограничений к столбцам оставшегося множества ;