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

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

(2.28)

т. е. равен дизъюнкции всех конъюнкций, включающих по одному элементу из каждой строки, таких, что сумма их вторых индексов постоянна и равна r + 1.

Доказательство. Согласно лемме 2.14 рассматриваемый ЛО можно представить в виде конечного ЛО с r элементами в каждой строке

Последний, не учитывая условий (2.7) упорядоченности элементов в стро­ках, можно представить как ЛО-столбец

Раскроем этот ЛО-столбец по формуле (2.26). В данном случае каждая конъюнкция в (2.26) включает r + 1 различных элементов, из них хотя бы один вида и хотя бы один вида Пусть есть s-я из конъюнк­ций, включающих k элементов вида и r + 1 —k элементов вида Тог­да, согласно (2.26), По условию (2.7) максимальна та из конъюнкцийв которую входят элементы ; ; она равна Подставив это значение конъюнкции в последнее выражение, получим (2.28).

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

(2.29)

т. е. равен дизъюнкции всех конъюнкций, включающих по одному элементу из каждой строки, таких, что сумма их вторых индексов постоянна и рав­на r + q - 1.

Доказательство проведем индукцией по q. При q = 1 (2.29) переходит в установленное ранее соотношение (2.12), а при q = 2 - в уже доказанное соотношение (2.28). Допустим, что форму­ла (2.29) верна для некоторого q = р. Покажем, что тогда она верна и при q = р + 1. Представим по правилу разложения (2.21) в виде блочного ЛО второго порядка

Раскроем последний по формуле (2.28) Согласно допущению можно выразить в виде (2.29). Отсюда

или опустив условие (лемма 2.14)

что и требовалось доказать.

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

(2.30)

Здесь запись означает, что элемент не входит в те конъюнкции, для которых из условия на сумму вторых индексов формально получается ik>m.

Доказательство. Конечный ЛО r-го ранга q-ro порядка по форму­ле (2.23) можно представить в виде бесконечного ЛО того же ранга и по­рядка. Применив к последнему правило раскрытия (2.29) и учитывая, что получим (2.30). Аналогично (2.30) получается правило раскрытия полубесконечного определителя; в этом случае ограничение накладывается лишь на вхождение элементов, принадлежащих строкам с конечным числом элементов.

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

(2.31)

Доказательство аналогично доказательству теоремы 2.4. Заметим, что из выражения (2.30) общего определителя нетрудно формально получить выражение (2.26) определителя-столбца. Действительно, для последнего q = n и из условия следует, что каждая конъюнкция в (2.30) из п конъюнктивных членов содержит лишь п-r + 1 членов, отвечающих условию и потому реально присутствующих; остальные r —1 членов отвечают условию т. е. отсутствуют.

Пример 2.2. Раскроем два определителя-столбца при всевозможных шачениях ранга, используя для этого формулу (2.26):

(2.32)

(2.33)

Пример 2.3. По формуле (2.30) раскроем два общих определителя второго порядка при всевозможных значениях ранга

(2.34)

(2.35)

2.6. Раскрытие логических определителей в конъюнктивной форме

Все приведенные в § 2.5 формулы, кроме (2.27), выражают ЛО в ДНФ БЛ. На практике иногда полезно иметь двойственные формулы, выражаю­щие логический определитель в КНФ БЛ. Для ЛО-столбца такой формулой является (2.27) . Для других типов ЛО выражения в КНФ можно получить исходя из (2.27).

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

(2.36)

где и - пустые буквы, которые можно опустить.

Доказательство. ЛО равен одному из r первых элементов первой или второй строки. Поэтому его можно записать как конечный ЛО:

Записанный ЛО, если не учитывать упорядоченности элементов в строках, можнопредставить в виде ЛО-столбца:

Раскроем данный ЛО-столбец по формуле (2.27). В ней каждая дизъюнк­ция включает r различных элементов. Пусть означает

s-ю дизъюнкцию, включающую k элементов вида и

r -k элементов вида На основании (2.27)

По условию (2.7) минимальна та из дизъюнкций

которая состоит из элементов она равна Подставив ее значение в выражение получим (2.36).

Учитывая, что в (2.36) можно опустить, эту формулу перепишем в виде

(2.37)

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

(2.38)

где — пустые буквы, которые можно опустить.

Доказательство. Проведем его индукцией по q. При q = 1 (2.38) принимает вид соотношения подобного (2.12), при q = 2 - вид уже доказанного соотношения (2.36). Допустим, что (2.38) справедливо при некотором q =p. Покажем, что тогда (2.38) справедливо и при q = р + 1. Представим как блочный определитель второго порядка, в котором роль новых элементов играют блоки-определители , r =1,2,...

Раскрыв теперь ЛО в правой части по формуле (2.36), получим

Согласно допущениюможно выразить в виде (2.38) . Отсюда

что и требовалось доказать.

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