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

Класс функций, сохраняющих константу 0 (А„). Так называют функции, для которых выполняется / (0 0 . . .0 ) = 0. Итак, A q = = { /1 /(00 ...0) = 0}. В строчной записи функции через ее значения они начинаются на 0, _например/ = (01111111). _ Покажем, что F= xxx2 \/ ХуХ 2 х 3 е Л / Действительно, /-’(000) = 0 • •0 v 0 •0 •0 = 0. Для п аргументов имеется 22"~ 1 функций от п аргументов, со­ храняющих константу, поскольку на одном из двоичных наборов, а именно на х = (0...0), значение /фиксировано , и для функции с п аргументами возможно подобрать лишь 2" - 1 произвольных на­ боров аргументов. Такой класс функционально замкнут по определению, посколь­ ку е с л и / , / , , . . . ,/„ е Лои * = (0...0), т о / ( / , ( х ) , ...,/ .(* )) = / ( 0 . . .0 ) = 0. Класс функций, сохраняющих константу 1 (АД. Так называют функции , для которых выполняется / (1 1 . . . 1) = 1. Итак, А, = = { /1 /(И —1)=1}- В строчной записи функции, сохраняющие кон­ станту 1, оканчиваются на 1, например / = (11101111). Покажем, что F(xyx 2 x 3) = х, v х 3 х 2 v ХуХ^х± сохраняет 1 /Э то м о ж ­ н о проверить подстановкой: F ( l l l ) = 1 v 1 1 v 1 • 1 ■1 = 1. Для К{ справедливо все то же, что и для А0. Класс самодвойственных функций (At). Функция f * ( x y x 2. . . x n) , удовлетворяющая условию f*(xyx2...xn) = f ( x y х2...хп), называется двойственной по отношению к функции/ ( х хх2...х„). Очевидно, что (/*)* = / Таким образом, если f* = g, то g* =f т.е. множество булевых функций разбивается на пары взаимно-двойственных функций. Обратим внимание на свойства важнейших функций (0)* = 1, (х)* - х, (х)* = х , (ху)* = х v у. Подобная двойственность лежит в основе построения противоположных высказываний. Функция f(xyx2...x„) е Р2 называется самодвойственной, если / = / * . Например, самодвойственна функция / (х ) = х. Самодвойственная функция полностью определяется своими значениями на половине наборов аргументов, поэтому число та­ ких функций при п аргументах равно 22"/2 = 22” ". Множество самодвойственных функций образует функциональ­ но замкнутый класс. Пусть/ , / , , . . . , /„ е А^, a g = / ° f ik. Обозначим^гротивоположный элемент на булевом кубе через х = (хь х2, х„) е Вп. Тогда «*(*) = g(x) = f j { f x (х), ..., / m(x)) = j f ( / , ( x ) , . . . . / т (х)) = = f j i f у (х), .... f m(x)) = f j ( f il(x), . . . , f m(x)) = g(x), откуда следует, что любая композиция самодвойственных функ­ ций не выходит из этого класса. Класс линейных функций (Ал). Функцию алгебры логики вида f ( x y x 2 -..х„) называют линейной, если ее канонический полином 194