способ воспроизведения симметричных булевых функций

Формула изобретения

Способ воспроизведения симметричных булевых функций, в котором для воспроизведения фундаментальной симметричной булевой функции индекса m (m{0,...,n}), зависящей от n аргументов - двоичных сигналов, предварительно подают указанные сигналы на блок вычисления простых симметричных булевых функций ₀-_n+1, отличающийся тем, что значения m-й и (m+1)-й простых симметричных булевых функций суммируют сумматором по модулю 2.

Описание изобретения к патенту

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

Известны способы воспроизведения симметричных булевых функций (см., например рис. 2 в статье Савченко Ю.Г., Хмелевая А.В. О методах последовательной реализации симметричных булевых функций // Автоматика и вычислительная техника. 1974, №3, С.24-29), в которых аргументы указанных функций двоичные сигналы подают на блок вычисления простых симметричных булевых функций.

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

Наиболее близким способом того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип способ воспроизведения симметричных булевых функций (см. рис.3 в статье Савченко Ю.Г., Хмелевая А.В. О методах последовательной реализации симметричных булевых функций // Автоматика и вычислительная техника. 1974, №3, С.24-29), в котором для воспроизведения фундаментальной симметричной булевой функции n аргументов - двоичных сигналов указанные сигналы предварительно подают на блок вычисления простых симметричных булевых функций ₀,... , _n+1. Здесь m {0,... ,n} есть заданное - число (индекс) функции . Как известно, только тогда, когда точно m ее аргументов равны 1, а остальные ее аргументы равны 0.

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в способе воспроизведения симметричных булевых функций, в котором для воспроизведения фундаментальной симметричной булевой функции индекса m (m {0,... ,n}), зависящей от n аргументов - двоичных сигналов, предварительно подают указанные сигналы на блок вычисления нулевой (n+1)-й простых симметричных булевых функций, особенность заключается в том, что значения m-й и (m+1)-й простых симметричных булевых функций суммируют сумматором по модулю 2.

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

В предлагаемом способе для воспроизведения фундаментальной симметричной булевой функции индекса m (m {0,... ,n}), зависящей от n аргументов - двоичных сигналов ₁,... ,x_n, указанные сигналы предварительно подают на блок вычисления простых симметричных булевых функций ₀,... _n+1, где

а значения функций _m и _m+1 суммируют сумматором по модулю 2, т.е.

В выражении (1) x_il ... x_ik {x₁,... ,x_n}; k,... ,n есть -числа (индексы) угарной функции ;, есть количество неповторяющихся минтермов x_i1 ... x_ik, определяемое как число сочетаний из n по k. Функция равна 1 только тогда, когда k или больше переменных из х₁,... ,х_n равны 1, а остальные переменные равны 0.

Сначала докажем справедливость (2) при 0&; m&; n, воспользовавшись известными соотношениями (см. стр. 143, 144 в книге Миллер Р. Теория переключательных схем. М.: Наука, 1970. T.1.)

где

где

где . С учетом (1) и (3.1)-(3.3) можно записать

Теперь покажем справедливость (2) при m=0 (m=n). Если m=0 либо m=n, то согласно (1) и (3.3) получим соответственно либо . Справедливость (2) доказана.

Пример. Пусть n=4, m=2, тогда согласно (1) получим

₂=(x₁ x₂) (x₁ x₃) (x₁ x₄) (x₂ x₃) (x₂ x₄) (x₃ x₄);

₃=(x₁ x₂ x₃) (x₁ x₂ x₄) (x₁ x₃ x₄) (x₂ x₃ x₄).

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

Таким образом,

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