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

Рассмотрим ЛО во второй строке разложения (2.69). Они обладают общими свойствами 1) и 2). Однако в первом из ЛО число элементов в первой строке равно р, во втором р — 1, ... , в последнем 1. Но s-й ЛО имеет ранг ns — р и потому выражается через р + 1 последних элементов строки, т. е. в нашем случае все элементы строки. Таким образом, ЛО во второй строке разложения (2.69), вообще говоря, не равны между собой, ЛО в четвертой, шестой, . .. , последней строках разложения (2.69) рас­сматриваются аналогично. В результате находим, что в каждой из указанных строк ЛО в общем случае не равны между собой.

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

После этой операции число конъюнк­цийв разложении (2.69) становится минимальным. Очевидно, что при выполнении этой операции за скобки следует выносить крайний спра­ва ЛО каждой нечетной строки, как содержащий наименьшее число элемен­тов среди всех равных между собой ЛО. При этом в получающемся из (2.69) разложении типа (2.63) ЛО являются минимальными логическими дополнениями соответствующих элементов В результате всех преобра­зований, проделанных над (2.69), получаем разложение (2.67), которое, как следует из вышесказанного, минимально.

Последовательное использование разложения (2.67) позволяет получать выражения ЛО меньшей сложности, чем при помощи разложения (2.47). Этим же путем можно находить явные выражения ЛО последовательных рангов, содержащие меньшее число операций, чем соответствующие выражения (2.30).Действительно,

(2.70)

Далее, положив в (2.67) р = 0, получим выражение дляПри этом

все дизъюнкции вида в (2.67) исчезают, а согласно (2.68) так что, учитывая выражение п из (2.66), полу­чаем k = q. Кроме того, каждый ЛО в правой части (2.67) имеет ранг равный числу элементов в нем и, следовательно, вычисляется по формуле типа (2.70). Таким образом, находим

Подставив эти результаты в (2.67), получим нужное выражение

(2.71)

Здесь символпоказывает, что соответствующий член присутствует толь­ко при

Аналогично, но уже с использованием формул типа (2.71), находится

выражениеи т. д.

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

Возможны более общие разложения ЛО, чем предложенные выше разло­жения по элементам, а именно разложения по блокам. Теорема2.13. Пусть

— общий бесконечный ЛО q-го порядка r-го ранга. Пусть — блок ЛО s-го ранга, составленный из строк в ЛО Тогда справедливо следующее разложение ЛО вДНФ БЛ:

(2.72)

Доказательство. Представим по лемме 2.11 в блочном виде:

Рассматривая теперь блоки как элементы ЛО раскрываем его

по формуле (2.29). В результате получим (2.72).

Теорема 2.14. Пусть

—общий конечный ЛО q-го порядка r-го ранга. Тогда справедливо сле­дующее разложение определителя в ДНФ БЛ:

(2.73)

Здесь Mi — число элементов в соответствующем блок-ЛО — а запись означает, что ЛО не входит в те конъюнкции, для которых из условия на формально получаетсяДоказательство повторяет ход доказательства теоремы 2.13, но с раскрытием ЛО по формуле (2.30).

Изменяя число р блок-ЛО правой части (2.72), (2.73) и их поря-

док, можно получить разные выражения для ЛО Например, при

р = q (тогда порядок блок-ЛО равен единице и получим выражение общего ЛО через его элементы в виде ДНФ (2.29) или (2.30). Отсюда уже обычным путем получается выражение ЛО-столбца в аналогич­ной форме (2.26) (см. замечание в конце § 2.5) .

Полагая, что в правой части формул (2.72), (2.73) имеется произволь­ное число ЛО произвольного порядка, получаем наиболее общее пред­ставление ЛО через ЛО низшего порядка. Это представление не содержит в явном виде элементов ЛО Однако ЛО в (2.72), (2.73) можно снова представить по таким же формулам — например, для бесконечного ЛО

(2.74)

выразив их тем самым через ЛО еще меньшего порядка и т. д., пока не при­дем к ЛО первого порядка, т. е. элементам

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

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

В многошаговой иерархической процедуре раскрытия ЛО, предложен­ной в § 2.11, мы не определили порядок блок-ЛО, выбираемых на каждом шаге, и соответствующее общее число шагов. Выберем теперь эти пара­метры так, чтобы минимизировать получаемое выражение ЛО. С этой целью рассмотрим указанную процедуру подробнее.

Согласно § 2.11 алгоритм вычисления общего бесконечного ЛО q-го порядка r-го ранга основанный на разложении (2.72), состоит в сле­дующем. На 1-м этапе строки в группируются так: первые q1 строк образуют 1-ю группу, следующие q2 строк — 2-ю,..., последние qp строк — р-ю группу. Из каждой группы строк составляются соответствующие ЛО которые затем выражаются по форму­ле (2.29) через элементы аij для всех значений ранга s, не превышающих r.

В результате получаются р (р < q) новых строк, составленных из най­денных ЛО, расположенных в порядке возрастания ранга

(2.75)

На 2-м этапе группируются строки (2.75) из ЛО, полученные на 1-м этапе: первые l1 строк образуют 1-ю группу, следующие l2 строк -2-ю,

. . . , последние ld строк — d-ю группу. Эти группы образуют соот­ветствующие ЛО Последние по формуле (2.72) выражаются через найденные на 1-м этапе ЛО меньших порядков для всех значений ранга В результате получаем d(d<p) новых строк, составленных из полученных ЛО, упорядоченных по возрастанию ранга