Спирина, М.С. Дискретная математика

Жегалкина имеет вид многочлена первой степени: f ( x \x 2...xn) = = ко © fcj*! ® к2х г ® ... © к„х„, аналогичного обычному алгебраи­ ческому многочлену первой степени, но с коэффициентами к, в виде 0 или 1. Число таких линейных функций от п аргументов равно 2Я+1, при и = 2 их восемь из шестнадцати. Они образуют функционально замкнутый класс. В гл. 1 было доказано это утверж­ дение для непрерывных линейных отображений одного перемен­ ного. Можно доказать, что оно справедливо и для композиции булевых линейных функций g = / o f , где / , / , , ..., f m e Кл. Для этого в многочлен / ( / , , / 2, ..., / J = ко ® kxf © к ^ 2 © ". © kmf m нужно подставить многочлены f ( x ) = k(]i ф к их х Ф k2ix2 Ф ... Ф ктхп и затем, используя переместительный и сочетательный законы для операции суммы по модулю два, привести подобные слагаемые. Тогда при каждом аргументе х2 (j = 1, ..., п) будет коэффициент k\kj\ ф k2kj2 ф ... ф kmkjm, который нужно просто вычислить. К л а с с м он о т онны х ф ункций (Км). В гл. 1 бьши определены поня­ тия порядок и упорядоченное множество. Для бесконечных множеств это означает возможность введения бинарного отношения для не более чем счетных — возможность перенумерования элементов и тем самым также введения ч. При этом эталоном сравнения слу­ жат натуральные числа. «) . Можно ли сравнивать булевы функции, упорядочить их? На множестве В введем полный порядок: 0 ч 0, 0 ч 1, 1 ч 1 по аналогии с отношением < на множестве целых чисел Z. На мно ­ жестве В" введем частичный порядок, означающий, что неравен­ ство а = (aia2...a„) ч (Рфг - Рп) = Р выполняется тогда и только тогда, когда V/ е {1, 2, ..., п} а , ч р,. Например, 001100 ч 001110. Два элемента а и р называются ср а вн имы м и между собой, если а ч р или р ч а. Частичным такой порядок является потому, что не все элементы Вп сравнимы. Например, кортежи 1100 и 0110 не сравнимы с помощью ч. Поэтому не стоит путать частичный порядок ч на Вп и полное упорядочивание, использовавшееся для табличного и строчного задания булевой функции (назовем его здесь <). Очевидно, что если а ч р, то а < р. Функция f ( x x 2...x„) называется м о н о т о н н о й , если для любых двух элементов а , р € В", сравнимых между собой, из ( а ^ . - . а , , ) ч ч (р,р2...р„) следует, что / ( а , а 2...а„) ч / (P ip 2 -P„) - Монотонными будут х х 2 и JC] v х2, а х не является монотон­ ной. Монотонные функции также образуют функционально замк­ нутый класс. Действительно, пусть f ( x lx2...x„), g(xlx2. . .хт) е Км. Тогда композиция А= g ° /б у д е т иметь вид h(x) = g ( / ( x ) , / 2(х), ..., / ш(х)), где х = (ххх2...х„) е Вп. Пусть х ч у. Тогда V/ е {1, ..., т} Мх) ч / ( у ) и а = ( / (х ) , / 2(х), . . . , / и(х)) ч Ш у ) , / 2( у ), f j y } ) = р, а поскольку g — монотонна, то g(a) ч g(P). Подставляя сюда 195