Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

40 Как и выше, можно проверить, что добавление равных функций не выводит за пределы класса S . Очевидно, что функции х, x – самодвойственны. Из определения самодвойственной функции: ) ,..., ) ( ,..., ( n 1 n 1 f x x f x x  , следует, что на противоположных наборах ) ,..., ( n 1   и ) ,..., ( n 1   самодвойственная функция принимает противоположные значения. Следовательно, самодвойственная функция полностью определяется своими значениями на первой половине строк. Поэтому число всех самодвойственных функций, зависящих от переменных x 1 ,…,x n , равно n 1 2 2  . Докажем, что класс S замкнут. Поскольку класс S содержит тождественную функцию, то достаточно показать, что функция  :  =f(f 1 ,…,f n ) является самодвойственной, если f, f 1 ,…,f n – самодвойственны. Это проверяется непосредственно          ( , , ) ( , , ) n 1 n 1 f f f f f f   . Лемма (о несамодвойственной функции). Если f(x 1 ,…,x n )  S , то из нее путем подстановки функций x и x можно получить несамодвойственную функцию одной переменной, т.е. константу. Доказательство. Т.к. f  S то найдется набор (  1 ,…,  n ) такой, что ) ,..., ) f ( ,..., f ( n 1 n 1      . Рассмотрим функции ( x ) x , i 1,n i i     и положим ( x )) ),..., ( x ) f ( ( x n 1     . Тогда имеем ( 1) ( 1)) ),..., ,...,1 ) f ( ( 1 ) f ( 1 ,..., f ( ) ,..., ,...,0 ) f ( ( 0 )) f ( 0 ),..., ( 0 ) f ( ( 0 n 1 n 1 n 1 n 1 n 1 n 1                       что и требовалось доказать.