Синтез схем, реализующих симметрические функции

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

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

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

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

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

Этот метод основан на следующей теореме.

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

Это легко вытекает из определения. Множество может быть любым множеством целых чисел от 0 до где — число переменных симметрической функции. Условимся их называть -числами функции. Симметрическая функция имеет а-числа 2 и 3, так как функция равна нулю только тогда, когда две или три переменные равны нулю. Чтобы найти а-числа данной симметрической функции, необходимо только вычислить значение функции, когда переменных равны нулю. Те числа, при которых результат есть нуль, являются а-числами функции.

Теорема. Существует симметрических функций от переменных.

Это следует из того, что имеется чисел, каждое из которых может быть взято (или не взято) в качестве а-числа. Однако две из этих функций тривиальны, а именно те, для которых выбраны все числа или не выбрано ни одно число. Это дает функции 0 и 1 соответственно. Симметрическую функцию от «переменных с а-числами будем в дальнейшем обозначать через Например, рассматриваемая нами функция будет обозначаться через Конструкция схемы, реализующей любую симметрическую функцию, основана на -числах, и предполагается, что эти числа известны.

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

Так,

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

Так,

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

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

Так,

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

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

одной переменной, и четыре уровня, помеченных справа числами 0, 1, 2 и 3. Полюс соединен с уровнями, соответствующими -числам реализуемой функции, в данном случае — с уровнем, помеченным цифрой 2. Напряжение подается на полюс а. Если то напряжение переключается на уровень, помеченный цифрой 1, что соответствует равенству нулю одной переменной. Если то напряжение остается на прежнем уровне (полюс а лежит на нулевом уровне).

Рис. 23. Схема, реализующая

Затем переходим к переменной Если то напряжение переключается на следующий уровень, если же то напряжение остается на том же уровне. Таким же образом действует ярус, соответствующий переменной

Рис. 24. Упрощение схемы, изображенной на рис. 23.

Достигнув в конце концов полюсов, расположенных справа, напряжение будет подключено к уровню, номер которого совпадает с общим числом переменных, равных нулю. Так как полюс соединен с уровнем с пометкой 2, то схема будет замкнута тогда и только тогда, когда 2 из переменных равны нулю. Если бы рассматривалась функция полюс надо было бы соединить с уровнями 0 и 3. На рис. 23 некоторые из элементов, очевидно, лишние. Схема может быть упрощена до вида, изображенного на рис. 24.

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

но сопротивление каждого отрезка можно легко усмотреть по аналогии с рис. 23. После того как полюс будет присоединен, все лишние элементы могут быть отброшены.

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

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

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

Рис. 26. Схема для полученная с использованием процесса совмещения уровней.

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

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

реализации, указанным методом реализуются очень простыми схемами. Можно легко показать, что есть симметрическая функция и что, если четное, -числами ее являются все четные числа, а если нечетно, то — все нечетные числа.

Рис. 27. Упрощение схемы, изображенной на рис. 26.

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

Рис. 28. Схема для при нечетном и для при четном

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

Рис. 29. Схема для при четном и для при нечетном

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

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

Универсальная схема, изображенная на рис. 25, содержит элементов. Покажем, что при любом выборе -чисел по крайней мере элементов излишни. Каждое число от 1 до включительно, которое не входит в множества -чисел, порождает два элемента, не являющиеся необходимыми; 0 и не являющиеся -числами, порождают один лишний элемент. Если два -числа отли-. чаются только на единицу, то два элемента излишни. Если имеется более.двух соседних -чисел или если два или более соседних числа не являются -числами, то каждое из них порождает более одного лишнего элемента. Тогда очевидно, что наихудшим будет случай, когда -числами являются все нечетные или все четные числа от 0 до . В каждом из этих случаев легко видеть, что элементов будут лишними. В этих случаях процесс совмещения уровней может быть применен, если так что максимальное число элементов будет необходимо только для реализации четырех функций