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

в котором каждая скобка, согласно (2.51), является некоторым ЛО, причем из нее нельзя уже исключить ни одного элемента нельзя так­же исключить ни одной из n-2 изменяющихся конъюнкций. Отсюда с учетом (2.52) получаем минимальное разложение для ЛО

(2.53)

Рассмотрим общий случай.

Теорема 2.11. ЛО-толбец r-го ранга с п элементамиможет быть представлен в виде следующей ДНФ БЛ, являющейся минимальным раз­ложением типа (2.48) :

(2.54)

в которой- минимальное логическое дополнение элемента аі в

ЛО выражаемое как

(2.55)

Доказательство. Положим в (2.49) r = п-р, где р - любое натуральное число в интервале Получим такое выражение:

(2.56)

Поскольку соотношения между элементамис различными индек­сами ik неизвестны, то из любой скобки в (2.56) нельзя исключить ни одного элемента. С другой стороны, эти скобки являются некоторыми ЛО. Действительно, согласно (2.49)

и т. д. Далее, соотношения величин различных скобок оказываются тоже неизвестными. Поэтому неизвестны и соотношения величин

п — р конъюнк­ций в (2.56), так что ни одна из них не может быть исключена. Таким об­разом, из (2.49) вытекает следующая ДНФ представления произвольного ЛО-столбца с минимальным числом конъюнкций:

(2.57)

где - минимальное логическое дополнение элемента аi в ЛО

представляющее собой ЛО

(2.58)

Заменив в (2.57), (2.58) п - р на r, получим (2.54), (2.55).

Последовательное применение разложения (2.54) или (2.57) позво­ляет получать выражения ЛО меньшей сложности (т. е. с меньшим числом элементарных двухместных операций БЛ), чем с помощью разложения (2.46).

Основываясь на формуле (2.54) или (2.57), можно также получить явное и с меньшим числом операций, чем в (2.26) и (2.27), выражение произвольного ЛО-столбца через его элементы. Действительно, явное выражение ЛО уже получены в (2.50), (2.52), (2.53).

Далее, для ЛО согласно (2.57), можно записдть

(2.59)

Здесь s-e логическое дополнение

является ЛО с п - s элементами ранга (n -s) - 2, которое можно вычислить по формуле (2.53) :

В результате получаем явное выражение определителя

(2.60)

Этим же путем отыскиваются явные выражения ЛО последующих рангов: n—4, n — 5 и т. д. Общее явное выражение ЛО-столбца произвольного (п -р)-го ранга с п элементами

(2.61)

Заменив здесь п — р на r, получим симметричную с (2.61) формулу

(2.62)

Формулы (2.62) обозримы лишь для ЛО с большими (r≈ п) либо малыми (r ≈ 1) значениями ранга r. ЛО со средними значениями ранга удобнее раскрывать с помощью итерационного разложения (2.54)

2.10. Минимальное разложение общего логического определителя по элементам

Найдем минимальное разложение общего ЛО по элементам

(2.63)

которое подобно (2.47), но содержит минимальное число конъюнкций и в котором — минимальное логическое дополнение элемента в ЛО (см. § 2.9).

Введем единую нумерацию элементов ЛО Пусть— номер

элемента Нумерация элементов может быть строчной

(2.64)

столбцевой

(2.65)

или смешанной. Если не учитывать имеющуюся в ЛО упорядоченность элементов в строках, считая условно

ЛО-столбцом, то, согласно (2.57), такой ЛО можно разложить следующим образом (полагаем r = п — р, где

(2.66)

В (2.66) логическое дополнение — это ЛО, полученный из ЛО исключением всех элементов с номерами, не превышающими номерэлемента и изменением ранга с на

Теорема 2.12. Общий ЛО (n - р - 1)-го ранга q-го порядка можно пред­ставить в следующем виде, являющемся (после раскрытия всех скобок) минимальным разложением типа (2.63) :

В формуле (2.67) k означает номер той строки ЛОна элемен-

тах которой разложение (2.67) обрывается; при этом k определяется из неравенств

(2.68)

Структура правой части формулы (2.67) такова: в ее первой строке имеется дизъюнкция конъюнкций р + 1 крайних справа элементов первой cтроки ЛО(исключая последний, m1-й элемент) и их минимальных логических дополнений; во второй строке имеется дизъюнкция конъюнкций р + 1 крайних справа элементов второй строки ЛО (исклю­чая последний, m2-й элемент) и их минимальных логических дополнений, при этом первый учтенный элемент второй строки ЛО заменен его дизъюнк­цией с последним элементом первой строки; в третьей строке стоит дизъюнкция конъюнкций р + 1 крайних справа элементов третьей строки ЛО (исключая последний, m3-й, элемент) и их минимальных логических дополнений, но первый учтенный элемент третьей строки ЛО заменен его дизъюнкцией с последним элементом второй строки и т. д. Последняя k-я строка разложения (2.67) отличается лишь тем, что в ней дизъюнкция "усечена", и оканчивается конъюнкцией такого элемента определителя и его минимального дополнения, что

Доказательство. Обратимся к разложению (2.66). Оно лишь условно минимальное, так как в нем не учтена взаимная упорядоченность элементов ЛО. Для получения минимального разложения общего ЛО достаточно в разложении (2.66) учесть упорядоченность элементов в стро­ках ЛО. Развернем разложение (2.66) для ЛО имея в виду по­строчную нумерацию элементов

(2.69)

Здесь k означает номер той строки ЛО на элементе которой разложение обрывается. Так как этот элемент, согласно (2.66), имеет номер п - р, то k можно найти из (2.68).

Рассмотрим ЛО в первой строке разложения (2.69). Они обладают различными рангами и числом элементов, но имеют три общих свойства. Именно: 1) ранг s-гo ЛО с числом элементов ns равен ns - р. Действительно, в ЛО число элементов равно откуда ранг 2) ЛО имеют один и тот же порядок q и различаются лишь первыми строками; 3) число эле­ментов первой строки во всех ЛО причем р + 1 крайних справа элементов являются общими для всех ЛО. Согласно (2.24) любой ЛО выражается через r первых элементов всех его строк; аналогично, ЛО (где п— общее число элементов ЛО) выра­жается через р + 1 последних элементов всех строк. Из этого и трех пере­численных выше свойств вытекает равенство всех ЛО в первой строке разложения (2.69). ЛО в третьей, пятой,.. ., предпоследней строках разло­жения (2.69) рассматриваются аналогично. В результате устанавли­ваем, что в каждой из указанных строк все ЛО равны между собой.