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

(2.39)

Доказательство. Представим по формуле (2.23) конечный ЛО как бесконечный. Раскрывая получившийся ЛО по формуле (2.38) и учитывая, что в данном случае любая буква приравна

а потому содержащая эти буквы дизъюнкция тоже равна и может быть исключена из выражения (2.38), получим (2.39) .

2.7. Логические определители второго порядка

ЛО второго порядка занимают особое место среди всех ЛО, так как минимальное число q упорядоченных подмножеств в множестве Aq (2.1) равно двум (случай q = 1 является тривиальным). Общий бесконечный ЛО второго порядка раскрывается по формуле (2.28), конечный —по сле­дующей, вытекающей из (230):

(2.40)

Практически более интересен вариант формулы (2.40), включающий в явном виде все элементы ЛО. Для получения такой формулы рассмотрим три случая, соответствующие трем областям значений r в предположении, что

Случай 1. Выполняется Тогда в каждой

конъюнкции формулы (2.40)и потому формула приоб-ретает такой же явный вид, как для бесконечного ЛО:

Случай 2. Выполняется При этом в (2.40)

так что но при некоторых i возможнo

Легко видеть, что такими являются i, удовлетворяющие условию

Формула (2.40) теперь переписывается в следующем виде:

Случай 3. ВыполняетсяВ этом случае в (2.40)

так что возможно Именно, при в конъюнкции при выполняется условие при справедливо

В соответствии с этим формула (2.40) приобретает вид

Сведя все три случая вместе, получим требуемую формулу

(2.41)

В случае т1 =т2=т вторая строка в (2.41) опускается и формула приоб­ретает вид

(2.42)

При вычислении по формуле (2.41) полубесконечного определителя в ней опускается третья строка. Можно получить аналогичное (2.41) выражение в КНФ.

2.8. Раскрытие логических определителей путем их разложения по элементам

Одним из способов раскрытия ЛО является использование формул раз­ложения, представляющих данный ЛО через ЛО меньших размеров. Прос­тейшей такой формулой является (2.21) . Покажем на примере ее исполь­зование для раскрытия ЛО.

Пример 2.4. ЛО 4-го порядка

(2.43)

можно записать как блочный ЛО 2-го порядка

в котором блоки

выражаются соответственно формулами (2.35), (2.32), и раскрыть его по правилу (2.41). Очевидно, возможны и другие блочные разбиения ЛО (2.43) . Эта неопределенность группирования элементов в блоки неудобна.

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

Определение 2.3. Логическим дополнением элемента в ЛО

называется ЛО, полученный из исключением элемента

Таким образом, для общего ЛО логическое дополнение

(2.44)

В частности, для ЛО-столбца

(2.45)

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

(2.46)

Доказательство. Раскроем ЛО правой части

(2.46) по правилу (2.26) — получим раскрытый по тому же правилу ЛО левой части

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

(2.47)

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

применим к нему формулу (2.46). Получим (2.47).

Согласно (2.46), (2.47) любой ЛО разлагается на дизъюнкцию конъюнк­ций его элементов и их логических дополнений. Поэтому (2.46), (2.47) можно назвать формулами разложения ЛО по элементам его строк или столбцов. Последовательное применение этих разложений приводит к по­нижению порядка ЛО, чем облегчает его вычисление. Однако логическое дополнение элемента в ЛО получается исключением из ЛО только данного элемента. Для уменьшения сложности (числа операций БЛ) раскрытия ЛО с помощью разложений (2.46), (2.47) желательно так видоизменить эти разложения, чтобы каждый раз из ЛО исключалось максимальное число элементов. Эта задача рассматривается в следующих параграфах, где поми­мо разложения ЛО собственно по элементам изучаются также разложения ЛО по блокам, т. е. по совокупностям элементов.

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

Найдем минимальное разложение ЛО-столбца по его элементам, т. е.

тжое, подобное (2.46), разложение в ДНФ БЛ

(2.48)

в котором содержится минимальное число конъюнкций аА; здесь—минимальное логическое дополнение элемента ai в ЛО т. е. ЛО, полу­ченный из исключением максимально возможного (зависящего от ai ) числа элементов и соответствующим изменением ранга r. Будем исходить из формулы раскрытия ЛО-столбца (2.26), конкретизировав ее в виде

(2.49)

Положив в (2.49) r = п, получим разложение ЛО

(2.50)

которое, очевидно, минимально. Далее, положив в (2.49) r =п — 1, найдем разложение ЛО

(2.51)

Вынесем за скобки общий элемент в каждой выделенной дизъюнкции. В результате, учитывая формулу (2.50), найдем разложение

(2.52)

которое является искомым минимальным разложением для определите­ля Действительно, из разложения любого логического дополне­ния в (2.52)

нельзя исключить ни одного элемента aj, так как соотношения между элементами aj с различными индексами j не­известны. Последнее показывает, что неизвестны и соотношения между различными конъюнкциями в (2.52), так что ни одну из них нельзя исклю­чить из разложения (2.52).

Аналогично, положив в (2.49) r = п — 2, найдем выражение ЛО