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

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

(2.13)

Доказательство вытекает из того, что прибавление общего слагаемого ко всем элементам не изменяет взаимной упорядоченности элементов согласно (2.9).

Лемма 2.4. Общий для всех элементов дизъюнктивный член можно

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

(2.14)

Лемма 2.5. Общий для всех элементов конъюнктивный член можно вынести за знак ЛО, не изменив его величины

(2.15)

Доказательства лемм 2.4 и 2.5 следуют из того, что введение общего для всех элементовдизъюнктивного (конъюнктивного) члена с не изменяет взаимной упорядоченности элементов, а лишь приводит к заме­не на с тех из них, которые первоначально были меньше (больше) с.

Лемма 2.6. Общий для всех элементов сомножитель с можно вынести за знак ЛО с сохранением первоначального ранга r, если с > 0, и с заменой его на дополнительный п — r + 1, если с < 0; в результате величина ЛО не изменится:

(2.16)

Доказательство. Действительна, при с > 0 упорядоченность множества величин и одинаковая, а при с < 0 — противоположная (т. е. при умножении на с < 0 максимальное из переходит в минимальное из предмаксимальное из - в послеминимальное из и т. д.).

Доказательства лемм 2.7 — 2.10 вытекают непосредственно из опреде­ления ЛО.

Лемма 2.7. Величина ЛО не меняется при добавлении к нему справа столбца из равных по величине элементов

(2.17)

Здесь элементы с в силу (2.7) должны удовлетворять условию

Лемма 2.8. При добавлении к ЛО слева столбца из равных по величине элементов величина ЛО остается неизменной, если ранг уменьшить на число его строк:

(2.18)

Здесь элементы с в силу (2.7) должны удовлетворять условию

Лемма 2.9. Величина ЛО не меняется при исключении из него элемен­та ∞, расположенного в конце какой-либо строки:

(2.19)

Лемма 2.10. Величина ЛО не изменится, если из него исключить эле­мент стоящий в начале какой-либо строки, а ранг уменьшить на еди­ницу:

(2.20)

Формулы (2.17) —(2.20) можно применять повторно, если в ЛО имеется несколько столбцов или элементов указанных типов.

Лемма 2.11. Величина ЛО не изменится, если произвольную совокуп­ность строк заменить строкой расположенных в порядке возрастания ранга р блочных ЛОсоставленных uз указанных строк:

(2.21)

Здесь - квазиматрица, полученная из исходной квазиматри-

цы Aq исключением строк- ЛО р-го ранга k-го порядка, составленный из строк квазиматрицы Aq.

Доказательство. Действительно, указанная замена означает лишь совместное упорядочение элементов строк и потому не может влиять на величину любого порядкового элемента а(r) множества Aq, a следовательно, и на величину ЛО Формулу (2.21) можно рассматривать как правило разложения, позволяющее путем последовательного пониже­ния порядка привести любой ЛО к ЛО второго порядка.

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

(2.22)

Доказательство немедленно следует из леммы 2.11, если принять и учесть, что

Лемма2.13. Любой конечный ЛО можно представить как некоторый бесконечный или полубесконечный ЛО того же порядка и ранга:

(2.23)

Доказательство соотношений (2.23), получается повторным примене­нием формулы (2.19). Заметим, что ∞ в (2.23) можно заменить любыми конечными элементами такими, чтобы сохранилась упорядоченность (2.7) элементов каждой строки и выполнялись неравенства

Лемма 2.14. Величина ЛО r-го ранга не изменится, если в любой его i-й строке исключить элементы т. е.

(2.24)

где mi — конечные величины или бесконечности, а

Доказательство. Действительно, r-м порядковым элементом любой квазиматрицы Aq может быть только один из r первых элементов какой-либо ее строки.

Лемма 2.15. Пусть - некоторый конечный ЛО,

а - конечный ЛО, полученный из инвер-

сией всех строк и переходом к обратным величинам элементов. Тогда ЛО для всех

Доказательство следует из того, что упорядоченность множеств вели­чин ипротивоположная (максималь­ному aij соответствует минимальное и т. д.).

Лемма 2.16 (распределительный закон).

(2.25)

и

В частности,

(2.25а)

Доказательство следует из леммы 2.1, по которой упорядочение мно­жества ЛО.различных рангов r от одной и той же квазиматрицы Aq можно заменить упорядочением множества рангов.

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

Раскрыть ЛО - значит указать функцию, выражающую его величину че­рез величины его элементов.

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

(2.26)

а также следующей конъюнктивной нормальной формой (КНФ) БЛ:

(2.27)

Доказательство. Пусть- упорядоченные согласно (2.9) элементы Каждая конъюнкция в (2.26) состоит из

п - r + 1 различных элементов: одна конъюнкция

остальные конъюнкции видагде s < r. Отсюда в силу (1.16), (1.17) и правая часть (2.26) равна т. е. равна левой части.

Каждая дизъюнкция в (2.27) состоит из r различных элементов: одна дизъюнкцияостальные дизъюнкции вида где s>r. Отсюда в силу (1.16), (1.18) и правая часть (2.27) равна т. е. равна левой части.