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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов. Техническим результатом изобретения является упрощение воспроизведения фундаментальных симметричных булевых функций за счет исключения инвертора. Указанный технический результат достигается за счет того, что для воспроизведения фундаментальной симметричной булевой функции индекса m (m∈{0,...,n}), зависящей от n аргументов - двоичных сигналов, подают указанные сигналы на блок вычисления простых симметричных булевых функций, а значения 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₄).

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

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

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

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

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