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

Вычисление ЛО с помощью разложений (5.16) оказывается идейно более простым и лучше приспособленным для машинного и ручного счета. Оно основано на следующей интерпретации указанных разложений. Обозна­чим через дизъюнктивный ЛО, образованный r первыми строками и k первыми столбцами матрицы А, где Тогда раз­ложение (5.16) ЛО по его нижнему правому элементу таково:

(5.25)

Ясно, что искомый ЛОесть ЛО Поэтому для вычислений

достаточно ввести в рассмотрение присоединенную к А матрицу

(5.26)

и вычислить ее нижний правый элемент Вычисление элементов матрицы А* производится по следующему рекуррентному правилу 1, выте­кающему из (5.25): элемент равен максимальному из элементов, стоящих слева от него и над ним, сложенному с соответствующим эле­ментом матрицы А. При этом элементы первой строки и первого столб­ца матрицы А* должны задаваться в виде некоторых начальных условий. Эти условия получаются непосредственно из определения ЛО

Таким образом, процедура вычисления дизъюнктивного ЛО такова 1) по формулам (5.27) вычисляются все элементы первой строки и пер­вого столбца присоединенной матрицы А*; 2) по правилу 1 вычисляются рекуррентно остальные элементы матрицы А , при этом вычисление идет в направлении от левого верхнего к правому нижнему углу матрицы, так что последним вычисляется элемент равный искомому ЛО

Изложенный алгоритм естественно назвать волновым.

Пример 5.1. Вычислить ЛО для матрицы А, заданной табл. 3.

Вычисление ведем прямо в таблице, располагая подсчитываемые эле­менты присоединенной матрицы А* в углах соответствующих клеток таблицы. Последовательно находим

и т. д. В итоге получаем

Существует двойственная по отношению к изложенной процедура вы­числения дизъюнктивного ЛО. Она основана на введении присоединенной к А матрицы, где — ЛО, образованный r последними строками и k последними столбцами матрицы Далее применяется рекуррентное правило 2 вычисления элементов матрицы: элемент равен максимальному из элементов, стоящих справа от него и под ним, сложенному с соответствующим элементом ark матрицы А. Это позволяет вычислить рекуррентно все элементы матрицы A, двигаясь в направлении от правого нижнего к левому верхнему углу матрицы. Последним вычисляется элемент равный, очевидно, искомому ЛО

Сложность вычисления m ×n-ЛО с помощью изложенного

волнового алгоритма складывается из п - 1 двухместных операций + на вычисление первой строки матрицы А* и m — 1 таких операций на вычисле­ние ее первого столбца; двух двухместных операций (одна и одна +) на вычисление любого другого элемента в А*.

Таблица 3

Таким образом,

(5.28)

Из (5.28) следует возможность вычисления с помощью разложений ЛО практически неограниченных размеров т×п.

Конъюнктивный ЛОпроще всего вычислять, сводя, согласно (5.14), к вычислению пары ЛО А+ и от той же самой матрицы А. Сложность N(m,n) такого вычисления т×п - ЛО в предположении, что ЛО будет вычисляться разложением, равна

(5.29)

Из (5.29) видна возможность вычисления ЛОпрактически любых размеров т×п.

ЛО с ограничениями на область формирования сумм элементов был введен при решении задачи об оптимальном порядке запуска п работ в систему из т последовательно соединенных блоков. Там же были приве­дены некоторые свойства указанных ЛО. Различные типы введенных выше ЛО (порядковые ЛО - гл. 2, ЛО с ограничениями на сумму элементов - гл. 4, ЛО с ограни­чениями на область — гл. 5) обусловлены различием классов нелинейных систем, для которых мы пытаемся решить проблему размерности системы путем перехода к ее блочному описанию. Интересно отметить, что и в клас­се линейных систем, где решение проблемы размерности уже давно связано с определенной блочной конструкцией - матрицей, дальнейшего продви­жения ищут на том же пути - дифференциации систем и математических конструкций для их изучения (структурные числа Беллерта-Возняцки для изучения электрических схем, структурные матрицы Шатихина для исследования систем автоуправления).

ПРИЛОЖЕНИЕ

БУЛЕВЫ РЕШЕТКИ

ИМПЛИКАТИВНЫХ ЛОГИК

Импликативные логики, т. е. логики, в которых единственной логи­ческой связкой является импликация →, по вполне понятным при­чинам всегда вызывали особый интерес. Периодически делались попытки классифицировать импликативные логики, но всегда на­талкивались на проблему расширения интуиционистской имплика­ции до классической

((Ранее классическая логика обозначалась нами посредством С2, а интуиционист­ская логика посредством Int.)

Для решения этой проблемы потре­буется метод доказательства независимости аксиом, использующий многозначные логические матрицы (см. выше раздел 2.3). В ре­зультате будут построены различные булевы решетки наиболее ин­тересных импликативных логик (см. [Кагрепко 2000]).

1. Проблема классификации импликативных логик. Комбинаторы

В [Смирнов 1979] проведена двоякая классификация импликатив­ных систем: по виду теорем дедукции и по структурным правилам в секвенциальной форме.

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

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

счет добавления закона Пирса

Но структурного правила, соответствущего этой формуле, не существует, а переход от интуиционистской логики к классической осуществляется трансформацией односукцедентного секвенциаль­ного исчисления в многосукцендетное.

К классификации импликативных логик можно подойти с со­вершенно иной стороны, используя свойства базисных (исходных) комбинаторов I, В, С, W, К и S, впервые введенных М. Шейнфинкелем в 1924 г. (см. Шейфинкелъ 2009]), а затем X. Карри (см. [Cwiy and Feys 1958]). Комбинаторы можно рас­сматривать как простейшие операции, которые переставляют мес­тами, берут в скобки, сокращают и/или воспроизводят термины, к которым они применены, т. е.