Класс функций, сохраняющих ноль

Функция f(х₁,..., х_n) называется сохраняющей ноль,если она на нулевом наборе принимает значение 0, то есть f(0,..., 0) = 0.

Пример. f(х) = 0, f(х) = х, f(х₁, х₂) = х₁ • х₂, f(х₁, х₂) =
х₁ Ú х₂ сохраняют ноль; f(х) = 1, f(х) =`х, f(х₁, х₂) = х₁ ® х₂ не сохраняют ноль.

Лемма 1. Из функций, сохраняющих ноль, супер­позицией можно получить только функции, сохраняющие ноль.

Доказательство. Функции, равные переменным, сох­ра­няют ноль. Поэтому достаточно показать, что функция

Ф(х₁,..., х_n) = f(f₁(х₁,..., х_n),..., f_m(х₁,..., х_n))

сохраняет ноль, если функции f, f_l, …, f_m сохраняют ноль. Последнее следует из

f(f₁(0,..., 0),... f_m(0,..., 0)) = f(0,..., 0) = 0.

Следствие. Полная система функций должна содер­жать хотя бы одну функцию, не сохраняющую ноль.

Класс функций, сохраняющих единицу

Функция f(х₁,..., х_n) называется сохраняющей едини­цу, если она на единичном наборе принимает значение 1, то есть f (1,..., 1) = 1.

Пример. Функции f(х) = 1, f(х) = х – сохраняют единицу; функции f(х) = 0, f(х) =`х, f(х₁, х₂) = х₁ Å х₂ – не сохраняют единицу.

Лемма 2. Из функций, сохраняющих единицу, суперпози­цией можно получить только функции, сохраняющие единицу. Доказательствоочевидно.

Следствие. Полная система функций должна содер­жать хотя бы одну функцию, не сохраняющую единицу.

Класс самодвойственных функций

Функция f (х₁,..., х_n) называется самодвойственной,если f(х₁,..., х_n) = `f(`х₁,...,`х_n).

Пример. f(х) = х, f(х) =`х – самодвойствен­ные функ­ции; f(х₁, х₂) = х₁ • х₂, f(х₁, х₂) = х₁ Ú х₂ – несамо­двой­ственные.

Лемма 3. Из самодвойственных функций суперпози­цией можно получить только самодвойственные функции.

Следствие. Полная система функций должна содер­жать хотя бы одну несамодвойственную функцию.

Класс монотонных функций

Набор a = (a₁,..., a_n) предшествуетнабору b = (b₁,..., b_n), если a_i £ b_i (i = l, 2,..., n). Это обозначаем как a £ b. Наборы, которые находятся в отношении £называются сравнимыми.

Функция f(х₁,..., х_n) называется монотонной,если для любой пары наборов a и b таких, что при a £ b: f(a) £ f(b).

Пример. f(х) = х, f(х₁, х₂) = х₁ • х₂, f(х₁, х₂) = х₁ Ú х₂ – монотонные функции, а f(х) =`х – немо­нотонная функция.

Лемма 5. Из монотонных функций суперпозицией мож­но получить только монотонные функции.

Следствие. Полная система функций должна содер­жать хотя бы одну немонотонную функцию.