Часть III. СПЕЦИАЛЬНЫЕ ФУНКЦИИ

8. Функциональные отношения

Было показано, что почти все функции требуют для своей реализации порядка элементов на реле. Тем не менее для практических целей это число слишком велико. В телеграфном аппарате, например, где реализуется много функций, некоторые из которых зависят от большого числа переменных, реле в среднем содержат 7 или 8 контактов. Фактически почти все реле, с которыми мы сталкиваемся на практике, имеют меньше 20 элементов. В чем причина этого парадокса? Ответ, конечно, состоит в том, что функции, с которыми сталкиваются на практике, далеки от случайных. Здесь снова имеется аналогия с трансцендентными числами. Хотя почти все числа траисцендентны, вероятность встретить трансцендентное число в открытой наудачу математической книге, конечно, гораздо меньше единицы. Встречающиеся обычно функции гораздо проще, чем основная масса булевых функций в силу по крайней мере двух основных причин.

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

2. Большинство условий, предъявляемых переключательным схемам, имеет логически простую природу. Наиболее важным аспектом этой простоты является то, что большинство схем может быть разбито на большое число малых схем. Вместо реализации функции от большого числа переменных реализуется много функций от малого числа переменных и затем некоторая функция от этих функций. Чтобы показать эффективность этого метода, рассмотрим следующий пример. Предположим, что требуется реализовать функцию

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

то можно реализовать примерно с элементами, что имеет

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

и можно найти более простую схему по сравнению со средней функцией того же числа переменных.

Этот тип функциональных соотношений может быть назван функциональной разделимостью. Ее часто можно обнаружить из условий функционирования схемы и можно использовать для уменьшения числа требуемых элементов. Покажем теперь, что большинство функций не являются функционально разделимыми.

Теорема 12. Доля функций переменных, которые могут быть записаны в виде

где стремится к 0 при .

Можно выбрать переменных, входящих в способами; функция при этом имеет возможностей и имеет возможностей, поскольку зависит от аргументов. Общее число функционально разделимых функций, следовательно, не превосходит

и отношение этого числа к стремится к 0 при

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

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

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

групповой инвариантностью; ее специальный случай — симметрия функций относительно всех переменных — был рассмотрен в цитированной на стр. 60 работе автора.

Рис. 20. Использование разделимости для уменьшения числа элементов.

Рис. 21. Использование разделимости для двух множеств переменных.

Функцию будем называть симметричной относительно если она удовлетворяет соотношению

функция симметрична относительно если выполнено равенство

Это частные случаи рассматриваемого типа функциональных соотношений. Обозначим через

— операцию оставления переменных в функции такими, как они есть,

— операцию отрицания первой (т. е. стоящей на первом месте) переменной,

операцию отрицания второй переменной,

— операцию отрицания первых двух переменных и т. д., так что

Совокупность всех образует абелеву группу с тем важным свойством, что каждый элемент является обратным самому себе, Произведение двух элементов можно легко найти, но где есть число, находящееся посредством сложения как двоичных чисел без переноса.

Заметим, что эта «отрицающая» группа состоит из 2" элементов. Пусть теперь

операция сохранения переменных функции на прежних местах,

— операция перестановки первых двух переменных,

— операция перестановки первого и третьего переменных и т. д.

Так,

Совокупность всех также образует группу, знаменитую группу «подстановок» или «симметрическую» группу. Она имеет порядок Правда, она не обладает простыми свойствами отрицающей группы — она не абелева и не каждый ее элемент является обратным себе. Отрицающая группа не является циклической, если симметрическая группа не является циклической, если

Полупрямое произведение этих двух групп образует группу общий элемент которой имеет вид и так как может принимать значений, а может принимать значений, порядок группы равен

Легко видеть, что где получается из преобразования рассматриваемого как упорядоченная последовательность нулей и единиц, перестановкой Так

При помощи этого правила любые произведения вида могут быть приведены к виду что преобразуется к стандартному виду

Будем говорить, что функция имеет нетривиальную группу инвариантности, если имеются элементы группы отличные от I и такие, что

Очевидно, что множество всех таких элементов для данной функции образует подгруппу группы так как произведение двух входящих в нее элементов есть такой же элемент; элемент, обратный к такому элементу, - есть элемент такого же типа, и все функции инвариантны относительно

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

Если удовлетворяет соотношению то покажем, что имеется по крайней мере равенств между функциями

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

и имеется самое большее независимых функций Пусть преобразует

где символ может означать или штрих, или его отсутствие, но не может быть Дадим переменной значение 0. Это фиксирует некоторый элемент в В, а именно где Возможны два случая.

1). Если этот элемент есть первый член, то имеем

Давая переменным все их возможных значений,

получим равенств между различными функциями так как они на самом деле суть

с фиксированными

2) Если элемент, о котором идет речь, есть другой член, скажем дадим переменной в ряде А противоположное значение Теперь, поступая так же, как и выше, с оставшимися переменными, установим равенств между .

Далее, имеется не более чем соотношений

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

имеем следующую теорему.

Теорема 13. Почти все функции не имеют нетривиальной группы, инвариантности.

Из теорем 12 и 13, а также из других результатов вытекает, что почти все функции имеют крайне хаотическую природу и не проявляют никакой симметрии или каких-либо других функциональных соотношений. Это можно было бы предсказать на основании того, что такие соотношения вообще ведут к значительному уменьшению числа требуемых элементов, а было показано, что почти все функции имеют довольно большую «сложность».

Если синтезировать функцию методом разделительного дерева и функция имеет группу инвариантности, включающую переменные

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

что можно ожидать, показывает, что вовсе не обязательно рассматривать для всех а достаточно рассмотреть

Теорема 14. Необходимым и достаточным условием того, что является выполнение равенства

Это непосредственно вытекает. из свойств быть обратным себе. Конечно, групповую инвариантность часто можно определить, исходя непосредственно из требований к схеме в задаче синтеза.

Таблица I (см. скан) Групповая инвариантность для двух переменных (рис. 22)

Таблица II (см. скан) Групповая инвариантность для трех переменных (рис. 23)

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

Соответствующее место групповой таблицы отсылает нас к схеме 9 рис. 23.

Рис. 22. Схемы групповой инвариантности двух переменных.

Звездочки показывают, что схема может быть использована непосредственно; отсутствие их означает, что требуется перестановка переменных. Разложим по переменным только две различные функции будут содержаться в сомножителях. Эти две функции реализуются двумя деревьями, исходящими из полюсов схемы 9.

Рис. 23. Схемы групповой инвариантности трех переменных.

Любая такая функция может быть реализована схемой (с использованием одного переменного в схеме с

оценка гораздо лучше, чем для произвольной функции.