9. Частично симметрические функции

Будем говорить, что функция является «частично симметрической» или «симметрической относительно некоторого множества переменных», если эти переменные могут быть переставлены без изменения функции. Так, функция

симметрическая относительно X и Y. Это свойство, очевидно, представляет собой частный случай общей групповой инвариантности, которая уже рассмотрена. Известно, что любая функция, симметрическая относительно всех переменных, может быть реализована схемой не более чем с элементами, где есть число переменных. В данном разделе будет усилен и обобщен этот результат.

Теорема 15. Любая функция симметрическая относительно , может быть записана в виде

где — симметрическая функция от с -числом, равным

Эта теорема следует из того факта, что поскольку — симметрическая функция относительно то значение функции зависит только от числа которые равны нулю, и значений У. Если в точности ; равны 0, то значение есть но правая часть равенства (6) в этом случае также обращается в так как тогда

Разложение (6) имеет вид, удобный для нашего метода синтеза. Можно реализовать разделительные функции симметрической решеткой и продолжить обычными деревьями (рис. 24), по одному дереву для каждого уровня схемы для симметрических функций. Обрывая деревья на ярусе с переменной видим, что полная схема разделительная, и второе применение теоремы 1 позволяет нам реализовать функцию с двумя элементами для Таким образом, имеем следующую теорему.

Теорема 16. Любая функция переменных, симметрическая относительно из них, может быть реализована с числом элементов, не превосходящим меньшее из двух чисел

В частности, функция переменных, симметрическая относительно или более из них, может быть реализована не более чем с элементами.

Рис. 24. (см. скан) Схема М для частично симметрических функций

Если функция симметрическая относительно а также относительно но несимметрическая относительно то она может быть реализована тем же самым методом с использованием симметрической решетки вместо дерева для переменных У. Эта функция сначала разлагается по X (в предположении, что затем по У и, наконец, по 2. Часть схемы, содержащая переменные будет состоять из деревьев.