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

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

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

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

§2.2. Система Россера — Тьюкетта

Вработах, относящихся к синтезу многозначных схем, очень часто встречаются ссылки именно на систему Россера — Тьюкетта [28], что связано с относительной простотой представления про­ извольной fe-значной функции в этой системе. Система Россера—Тью­

*1 V*2

Приведем некоторые тождественные соотношения, характерные для рассматриваемой системы

40

Таблица 6 Таблица 7 Таблица 8

J 0 (x) A M J-i W

где х — двоичная операция инверсии.

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

которая при к — 2 сводится к предыдущей.

41

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

Теорема. Произвольную функцию из множества Р к можно пред­

(2.12) будем называть совершенной дизъюнктивной нормальной фор­

мой многозначной переключательной функции / (х). Доказательство этой теоремы одновременно устанавливает факт функциональной пол­ ноты системы Россера — Тьюкетта.

Доказательство. Предположим, что есть фиксированный набор

Учитывая приведенные выше соотношения (2.9) и (2.11), легко убедить­ ся в том, что

(2.12) для заданного набора Рдоказана. Подобные же рассуждения мож­ но привести для любого набора. Следовательно, теорема доказана.

Произведение функций J s (х), взятых по одной для каждого ар­ гумента из некоторого множества аргументов, называют конституентой.

Рассмотрим пример представления совершенной дизъюнктивной нормальной формой СДНФ функции, заданной табл. 9,

Здесь нет дизъюнктивных членов, соответствующих нулевым значениям

42

функции, так как они получаются согласно соотношению (2.13). Кроме того, коэффициенты 3, которые должны стоять при некоторых конституентах, опущены в силу соотношения (2.9).

Заметим, что в системе Россера — Тьюкетта можно образовать совершенную конъюнктивную нормальную форму переключательной функции, членами которой будут дизъюнкции вида

Рассмотрим пример. Пусть задана табл. 10 истинности неполностью определенной трехзначной функции. Представим ее в виде совершенной конъюнктивной нормальной формы (СКИФ)

/ (хь х2) = (0 V 4 (Xj) V Jo (х2)) (1 V J\ (xi) V J ' (x2)) x

x (2 V A (x i) V A (x2)) (0 V A (xx) V Jo (x2)).

Учитывая соотношения (2.8) н (2.10), последнее выражение можно

43

§ 2.3. Системы, содержащие теоретико-множественные операции

Особенностью некоторых принципов представления информации, например фазо-импульсного и частотно-гармонического [15], является возможность одновременного присутствия множества различных зна­ чений информационных сигналов в одной точке схемы. Учет этой осо­ бенности при практической реализации переключательных схем требует привлечения теоретико-множественного аппарата для синте­ за схем. Вместе с тем, как будет показано в главе 3, теоретико-множе­ ственные операции можно реализовать простыми физическими схемами.

Напомним, что Ек — множество возможных значений, принимае­ мых /г-значной функцией. Образуем множество М к, элементами кото­ рого будут все подмножества множества Ек. Переменные, принимаю­

Рассмотрим известные в теории м-ножеств операции объединения X \J Y = X U У' и пересечения X Y = X f| У- Эти операции ассо­ циативны, коммутативны и связаны между собой законами дистрибу­ тивности. Кроме того, справедливы соотношения

X v е = X, XQ = Q,

г, е 0 — пустое множество.

Введем характеристические функции, определенные на множестве М к

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

по всем

а

где ia — значение функции на наборе а. Доказательство. Рассмотрим выражение

K * i)'“ K * 2)'a • • • (<хпхп]1а.

Легко проверить, что

44

Так как аналогичные рассуждения справедливы для любого набо­

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

Следует отметить, что для получения канонической формы (2.16) представления &-значной функции вместо операции пересечения достаточно операции совпадения

\ х при х = у,

хсо у = \ а

{0 при X Ф у.

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

Действительно, раскрывая правую часть соотношения (2.20), по­ лучим

(Ах У Ау)‘(Вх У By)1= ((Ах)‘ у (Ау)1) ((Вх)1У (By)1) =

=(Ах)1(Вх)1У (Ах)1 (Ву)1У (Ау)1(Вх)1 У (Ay)1 (By)1=

=(АВх)‘ У (Ах)1(By)1 У (Ау)1(Вх)‘ У (АВу)1=

=(Ах)1(Ву)‘ у ( А у ) 1(Вх)‘.

45

Рассмотрим пример. Пусть f (х1у х2) задана табл. 11. Представим эту функцию согласно (2.16). В отличие от системы Россера — Тьюкетта, здесь необходимо учитывать и те наборы, на которых / (хх, х2) принима­ ет нулевые значения

Применяя к первым двум членам этого выражения соотношение (2.19), а также учитывая, что X X = X, получим

= 0х2 V Зх2 V 0ххх2 V lxxx2 \J 2xi 2 V Зххх2 =;

= (О V 3 V 0хх V lx, V 2хх V Зхр х2.

Из соотношения (2.1 Эг) имеем

Fi = (0 \ / 3 \ / х р х 2.

46

В выражении для F2вынесем за скобки общие члены

F2= (0х1)2( ( ^ 2)2 V (2*а)а) V (Зх1)2((1х2)2 V (2*2)2) =

= ((0*х)2 V (3*х)2) ((1*2)2 V (2^)2)-

Здесь объединения в скобках удовлетворяют соотношению (2.19а). Поэтому

f 2 = (^ (0 V 3 ))2(x2(l V 2))2.

К выражению для F3 применим соотношение (2.20)

F3 = (2Xl)' (lx,)1 V ( ^ i) 1 (2-^г)1 = (1 (xt V х2)У (2 (х, V ^г))1-

Последнее выражение удовлетворяет соотношению (2.196). Следо­ вательно,

F3 = (x1 V * 2)(2(*i V ^ ))1-

Таким образом, упрощенное представление функции f (xv х2) имеет вид

f(Xl, х2) = (0 V 3 V xL)x2 V (Хг(0 V 3))2(*2(1 V 2))2 V

V (*1 V х2) (2(Xl М х 2))К

Введем в рассматриваемую систему вместо одноместных функций

Б этом случае, помимо приведенных выше, справедливы следующие

47

ражении (2.24) степень i выбирается произвольно.

Функция (2.15) является частным случаем функции (2.21), имеющим место при подстановке в (2.21) константы вместо переменного Y.

В рассматриваемой системе, помигло формы (2.16), представляют интерес также другие канонические формы, которые в ряде случаев

U— 1, 2.......п)\ у — степень, выбираемая произвольно. Справедливость (2.26) доказывается применением соотношений

(2.24) и (2.25) к канонической форме (2.16).

Теорема. Произвольную функцию из множества Рк можно пред­

Доказательство теоремы получаем, применяя к (2.16) тождественное соотношение (2.2').

Исходя из канонической формы (2.27) и применяя тождественные соотношения (2.23) и (2.25), можно получить еще две разновидности форм представления многозначных функций

а (О

Канонические формы (2.16), (2.26)—(2.29) имеют свои преиму­ щества и недостатки, которые определяются используемым принципом представления информации и сложностью применяемых базисных сис­ тем многозначных логических элементов (гл. 3).

48

§ 2.4. Некоторые системы с каноническими формами типа дизъюнктивных нормальных форм

Рассмотрим систему [1 ], включающую операции ху, х \/ у и х 1, опре­ деленные следующим образом:

Укажем основные тождественные соотношения в этой системе, справедливость которых вытекает непосредственно из определения операций ху и х \/ у

Введем обозначение хг для г-кратного применения операции (2.32)

где 1 — t = 1 — i (mod k).

Доказательство. При х — i правая часть (2.33) принимает значение