Дискретная математика

84 Действительно, если система такую функцию не включает, то, в соответствии с приведенной теоремой, нельзя получить из. этой системы функцию, не сохраняющз/го нуль на нулевом наборе, например, функцию х=^у и, следовательно, такая система не будет полной, Следствие 3.6. В полной системе функций должна содержаться хотя бы одна функция, не сохраняющая единицу. Действительно, в противном случае нельзя получить фушщию, не сохраняющую единицу, например, х=1у. 2. Ссшодвойственные функции. Булева функция f(X],X2, называется самодвойственной, если ' 7f(x,,X2, ...,x,J =f(lx,, 1X2, Ix^. Легко убедиться, что функция f f x ) = 1х самодвойственная, &f(x,y) = х&у не является самодвойственной. Нетрудно доказать следующую теорему. Теорема 3.21. Суперпозиция самодвойственных функций есть снова самодвойственная функция. Следствие 3.7, В полной системе функций должна содержаться хотя бы одна не самодвойственная функция. Действительно, в противном случае нельзя получить несамодвойствеккую функцию, например, х&у. 3. Монотонные функции. Рассмотрим различные наборы значений переменных х/,х2,...,х,„ когда каждое .г, принимает значение О либо I. Если значение каждого аргумента одного набора больше или равно значению того же аргумента второго набора, то говорят, что первый набор не меньше второго. Если же некоторые из значений аргументов первого набора больше или равны, а другие меньше значений второго набора, то такие наборы называются несравнимыми. Например, имеем, что (1,0,1) > (1,0,0), так как значения аргументов л-, и совпадают, а значение аргумента .vj на первом наборе больше, чем на втором. Аналогично имеем, что (0,0 ,1 ,1,1) > (0,0,1,0,1); (1,0,1,1) 2: (1,0,0,0). Очевидно, что любой набор не меньше набора, состоящего только из нулей. Наборы (1,0) и (0,1) несравнимы, ибо значение аргумента Xj больше на первом наборе, а аргумента д:2 - на втором. Булева функция f(xi,x2 х^ называется монотонной, если для любых наборов значений ее аргументов (а,,а2, ...,а^ и (b,.b2, таких, что (а,.02, >(b,,b2. имеет us.ciaf(a,.a2, > f(b,,b2, ....b,J. Например, учитывая, что наборы (0,1), и (1,0) несравнимы, легко установить, что функция jrcfejFv/Zxt&y монотонна.