Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf

Теорема. Система, включающая константу 1 и операции х 4- у

можно представить в виде суперпозиции функций ху и х ', после чего

произвольная функция / (х) представляется в виде суммы некоторых из этих конституент.

Операции х + у (mod k) и ху . вязаны между собой соотношением

(х + у) {гг) = х {гг) + у {гг),

в справедливости которого легко удостовериться, взяв сначала z =

=1, а затем г ф 1.

Вработе [1 ] приведен также ряд полных систем, в которых для об­ разования одноместных конституент и конституент констант использу­ ется операция

(2.36)

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

а у х = x \J а =■ х,

ах — ха = а, {а£Ек)

(в рассмотренных примерах а — 0). При k = 2 эти операции превра­ щаются в обычные операции дизъюнкции и конъюнкции булевой ал­ гебры.

§2.5. Модулярная система операций

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

При синтезе схем вычислительных устройств, работающих в &-й системе счисления, среди типовых логических элементов желательно иметь элементы, реализующие операции сложения и умножения по mod k. В связи с этим представляют интерес такие формы представ­ ления многозначных функций, в которых вместо операций дизъюнк­ ции и конъюнкции используются операции модульного сложения и ум­ ножения. Одной из форм представления, использующего эти операции, является так называемая сигма — пи форма [16] (название происходит от греческих букв 2 и П, являющихся символами операций сложения и

51

умножения по mod k). Если в систему, содержащую константы, опе­

где f(a)* 0

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

внимание, что при фиксированном наборе а произведение, стоящее пос­ ле знака суммы в выражении (2.38), является конституентой константы

в справедливости которого легко убе­ диться при непосредственной проверке. Если же k — составное чис­ ло, однозначного соответствия между функцией Ф/- (х) и суперпозицией операций сложения и умножения по mod k построить не удается.

Рассмотрим пример. Запишем в форме (2.38) функцию переноса при умножении по mod 4, заданную табл. 13.

f (*i. хг) = 1 Фз (*i) Фз (*з) + 1 Фз (*г) Фз (*з) +

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

причем некоторых из членов, составляющих такое произведение, может и не быть. В выражении (2.40) а — константа; N ^ (хг) — функ­

ции одного переменного; (i =« 1, 2, ..., п), (J = 1, 2.......kk).

52

Найдем представление любой функции одного переменного в виде полинома

ление любой функции одного переменного вида (2.41), то можно найти такое представление и функций (2.37). Представляя их в (2.38) и про­ изводя умножение, получим полином относительно переменных xt(i=

= 1, 2, ..., п) и функций N2 (х с), N 3 (xt), ..., Nk_i (xt). В работе [16]

показано, что необходимым и достаточным условием единственности представления любой функции одного переменного в виде (2.41) яв­ ляется равенство единице определителя

1 k — l N t (k— l ) . . . N h- l (k— l)

Этому условию, например, удовлетворяет система функций, опре­ деленных в табл. 14.

Определитель Д этой системы функций принимает значение 1 при любом k. Условие единственности представления любой й-значной функции в виде (2.41) не что иное, как дополнение системы функций суммы и произведения по mod k одноместными функциями N z (х), N 3 (х)...... Nk—i (х) до полной системы функций.

Число одноместных функций, дополняющих двухместные операции х + у (mod k) и х X у (mod k) до полной системы, не обязательно

53

равно k — 2. При к = 4 представление функции одного переменного можно искать в виде [16]

/ (А-) = а„ + агх -[- а2Ы2(а) + a3x N 2(а).

Этому условию удовлетворяют 64 функции N2 (а).

Одноместные функции (табл. 14) Nt (а), (г = : , 3...... к — 1), можно представить как

N t (а) = min (г — 1, а).

Отсюда вытекает справедливость следующей теоремы.

Теорема. Функции а + у (mod k), х X у (mod k), min (а, у) обра­ зуют полную систему функций при любом к, позволяющую представить любую функцию из множества Рк в виде полинома.

Отметим, что помимо (2.41) существуют и другие представления одноместных функций, дающие возможность получить полиномиальные представления функций многих переменных. Если k — простое число, то одним из таких представлений может быть выражение (2.39). Под­

комый полином.

Рассмотрим пример. Представим в полиномиальном виде функцию, 2 — П форма которой имеет вид (к = 4):

/ (хи Х2) = q>! (Ai) ф0 (а2) + 2ф1 (хх) ф2 (х2) -I- Зфх (хх)Фз (а2).

Функции (2.37) в рассматриваемом случае можно представить как

Тогда

/ (xv хг) = (2 ^ 2 (*i) + 3N з (ах)) (1 + 3N 2 (х2) + 2N 2(а2) -]- N 3(а2) -(- -J- 2а2 -(- За2) = (2N 2 (Aj) -{- 3Nз (хх)) (1 -|- N2(а2) -(- N3(а2) -)- а2) =;

=2N2 (ах) + 3Nз (aj) -f- 2А;2 (ах) N а (а2) -f- 3N3(хх) N2 (х2) -|-

+2N 2(Ai) N3(а2) -|- 3Nз (Aj) iVg (а2) -f- 2N 2(ах) а2 -f- 3N3(XjJ х2.

§2.6. Другие полные системы операций

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

64

Затем построим функцию k — 1 — х.

/ = * - 1

позиции, мы построили функции полной системы Россера — Тьюкетта. Следовательно, и исходная система полная.

Далее формулируемые три теоремы можно доказать как следствие

—1 обычные, а не по mod k.

Особый интерес представляют системы операций, для которых

характерны канонические формы представления произвольных мно­ гозначных функций типа совершенных дизъюнктивных нормальных форм (СДНФ). С целью выяснения условий, которым должны удов­ летворять операции полной системы для того, чтобы в ней была

55