Cтраница 3
Универсальная схема, изображенная на рис. 25, содержит п ( п 1) элементов. Покажем, что при любом выборе а-чисел по крайней мере п элементов излишни. Каждое число от 1 до п - 1 включительно, которое не входит в множества а-чисел, порождает два элемента, не являющиеся необходимыми; 0 и п, не являющиеся а-числами, порождают один лишний элемент. В каждом из этих случаев легко видеть, что п элементов будут лишними. [31]
Это следует из того, что имеется п 1 чисел, каждое из которых может быть взято ( или не взято) в качестве а - числа. Однако две из этих функций тривиальны, а именно те, для которых выбраны все числа или не выбрано ни одно число. Это дает функции 0 и 1 соответственно. Конструкция схемы, реализующей любую симметрическую функцию, основана на а-числах, и предполагается, что эти числа известны. [32]