double arrow

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


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

Так, функции x1x2 , x1 ٧ x2, х, 0 – сохраняют ноль, функции x1 ® х2,`х, 1 – не сохраняют.

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

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

Φ (х1,...,хn) = f (f1 (x1,...,xn),..., fm (x1,...,xn))

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

f (f1 (0,...,0),... fm (0,...,0)) = f (0,...,0) = 0.

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


Сейчас читают про: