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

9 значений n аргументов равно 2 n , то число  P 2 (n)  различных функций n переменных равно n 2 2 . Введенное понятие функции несовершенно, поскольку оно не позволяет рассматривать функции от меньшего числа аргументов как функции от большего числа аргументов. Для устранения этого недостатка введем следующее определение. Определение. Функция f(x 1 ,…,x i-1 ,x i ,x i+1 ,…x n ) из P 2 зависит существенным образом от аргумента x i , если существуют такие значения  1 ,…,  i-1 ,  i ,  i+1 ,…,  n переменных x 1 ,…,x i- 1 ,x i ,x i+1 ,…,x n , что f(  1 ,…,  i-1 ,0,  i+1 ,…,  n )  f (  1 ,…,  i-1 ,1,  i+1 ,…,  n ). В этом случае переменная x i называется существенной. Если x i не является существенной переменной, то она называется несущественной или фиктивной. Если переменная x i является фиктивной переменной, то функция f(x 1 ,…,x i-1 ,x i ,x i+1 ,…,x n ) по существу зависит лишь от (n-1)-й переменной, т.е. представляет собой функцию g(x 1 ,…,x i-1 ,x i+1 ,…x n ) от ( n-1 ) переменной. Будем говорить, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной. Определение. Функции f и g называются равными, если функцию g можно получить из функции f путем добавления или изъятия фиктивных переменных. В дальнейшем все функции мы будем рассматривать с точностью до фиктивных переменных. Смысл удаления или введения фиктивных переменных в том, что любую конечную совокупность функций можно считать зависящей от одного и того же множества переменных, что часто бывает удобно. В частности, равенство n 2 2 P n 2  ( ) справедливо при условии, что P 2 (n) содержит все функции n переменных, в том числе и функции с фиктивными переменными.