4. Синтез схем

Некоторые основные теоремы о схемах и функциях

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

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

Теорема. Число функций, зависящих от переменных, равно

Каждая из этих сумм представляет отличную от других функцию, но некоторые из функций могут фактически зависеть менее чем от переменных (т. е. они имеют такой вид, что для одной или большего числа из переменных, скажем для имеем тождественно так что ни при каких условиях значение функции не зависит от значения ). Так, для двух переменных X и Y среди 16 функций имеются функции X, Y, X, Y, 0 и 1, которые не зависят по крайней мере от одной из переменных X и Y. Чтобы найти число функций, существенно зависящих от всех переменных, поступим следующим образом. Пусть это число есть Тогда по только что приведенной теореме

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

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

С ростом это выражение асимптотически приближается к его главному члену При погрешность при использовании только этого члена не превышает 0,01%.

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

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

Имеют место также формулы

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

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

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

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

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

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

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

Чтобы доказать, что они требуют элементов, обозначим число требуемых элементов через Тогда из равенства (19) получаем разностное уравнение

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

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

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

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