книги из ГПНТБ / Цифровые многозначные элементы и структуры учеб. пособие

Теорема. Любую многозначную функцию из множества Рк можно представить в виде

Доказательство. Зафиксировав произвольный набор а=(а,, а.,, ...

...,g„), а также принимая во внимание свойства функции (2.30) и со­ отношение (2.33), убеждаемся, что выражение

Любую конституенту константы можно получить в результате выпол­ нения операции (2.30) над константой а и выражением (2.35). Таким образом, каноническая форма (2.34) представляет собой дизъюнкцию конституент констант.

Используя взаимооднозначные отображения множества Ek на себя, можно определить полные системы операций, являющихся изоморф­ ными отображениями операций (2.30)—(2.32). Примеры таких систем приведены в [1 ].

При построении вычислительных устройств иногда целесообразно использовать в качестве одной из основных операций сложение по mod k.

50

Теорема. Система, включающая константу 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

набора а, то теорема доказана.

Рассмотренная система полна при любом доопределении функций х У у, ху и / , (х). Условиям (2.42) удовлетворяют, например, функции шах (х, у), min (х, у), х + // (mod k), ху (mod k) и др. Таким образом, существует класс полных систем, в каждой из которых прэи:-вольную многозначную функцию можно представить канонической формой ти­ па СДНФ. Признаком принадлежности системы функций к этому клас­ су служат условия (2.42).

56

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

§2.7. Минимизация многозначных функций

вклассе дизъюнктивных нормальных форм ( Д Н Ф )

Рассмотрим более подробно систему Россера — Тьюкетта, в кото­ рой, как нетрудно убедиться, канонические представления принадле­ жат к классу СДНФ (§ 2.6). При этом а = k — 1,6 = 0. Будем счи­

тать, что функция fi (х) накрывает функцию /2 (х) на наборе а, если

на этом наборе fx (а) > /2 (а) [19]. Функция /у (х) поглощает функцию

/2 (х), если на всех наборах fx (а) >. f2 (а).

Если функция fx {х) поглощает функции /2 (д), /3 (х), ..., fm (х),

то она поглощает и их дизъюнкцию. Кроме того, соотношение погло-

—¥ —►

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

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

Элементарное произведение — импликанта данной функции — не поглощаемое никаким другим произведением, которое является им­ пликантой этой же функции, называется простой импликантой данной функции.

Любое конечное число элементарных произведений, объединенных знаками дизъюнкции, называется дизъюнктивной нормальной формой этой функции {ДНФ).

57

Дизъюнкцию всех простых импликант называют сокращенной ДНФ. Представление заданной переключательной функции в виде дизъ­ юнкции простых импликант, из которых ни одну нельзя исключить,

называется тупиковой ДНФ.

Рассмотрим следующие тождественные соотношения, полученные на основе (2.6) и (2.7):

форму функции / (х) привести к совершенной ДНФ.

Рассмотрим пример. Восстановим совершенную ДНФ функции, за­ данной в виде (к = 4),

/4*1, х2) = 2У2(Xi) \/ 2У2(х2) V A (*i)x 2 V *iA (*2) V

V 1A (*1) А (-^г) V A (*i) A (*2)-

Применим к первому и второму дизъюнктивным членам этого выра­ жения соотношение (2.44), а к третьему и четвертому — соотношение (2.45). Тогда можно записать, что

2У2(Xj) = 2У2(хх) J 0 (x2) V 2У2(xt) У, (x2) V 2J 2(xx) J 2 (x2) V

V 2У2 (*1) У3 (x2),

2 J 2 (x 2) = 2У0(xx) У2(xa) V 2У1 (*i) У2(*2) V 2Л (X j) У2(x2) V V 2У3(xx) J 2(x2),

A (Xj) x2 = 1У2 (Xx) У! (x2) \ f 2 J j (Xj) У2 (x2) V A (*1) А (*2)» х Д i (x2) — 17i (xi) Уi (x2) V 2У2 (xx) Уj (x2) V A (*1) A (x2).

Следовательно, совершенная ДНФ рассматриваемой функции имеет вид

/(х1, х2) = 2У2(х1)Уп(х2) V 2У2(х1)У, (*2)V 2У2(х1)У2(х2) V V 2У2(Xj) У3(х2) V 2У„ (Xj) У2(х2) V 2У1 (*Д Уа (*а) V

58

причем is Ф ls, так как в противном случае соответствующая перемен­ ная величина xis превращается в константу, например x3J5 (х3) =

= 5Jb (х 3).

Рассмотрим выражение

В двух последних дизъюнктивных членах этого выражения константы меньше индексов при функциях Ji (х2). Наименьшей из этих констант является единица. Следовательно, согласно (2.48), можно записать

F1 = F1 y P l = F 1 y i J 1(x1).

59