Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.07.2024
Просмотров: 142
Скачиваний: 0
В выражении для 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))К
Введем в рассматриваемую систему вместо одноместных функций
(2.15) двухместные функции |
|
|
|
= { д |
ПРИ^ |
00’ |
(2-21) |
(0 |
при X = |
0. |
|
Б этом случае, помимо приведенных выше, справедливы следующие
тождественные соотношения: |
|
|
|
|
|||
0х = |
0, |
|
(Xy)z = x yZ, |
|
X V XY = X, |
||
Iх = |
X, |
|
X yZ = Y xZ, |
|
x yz = |
x yx z, |
|
Xх - |
X, |
x yX = Y x. |
|
XyXz = FXZ, |
|||
AryW |
X WZY, |
XXy = XF, |
|
X Y x = |
Y x, |
|
|
X YZW = |
|
|
|||||
x 'z " |
= |
x 2 m , |
(iX)Y (iZ)w = (iXZ) |
(XY)x (XF)y = XV, |
|||
X yY x = XY, |
X XY = XY, |
x yvZ = |
x y v |
* z, |
|||
|
|
|
(X V Y)XY = XY, |
|
к—I |
v |
v |
X \ J Y * |
= X, |
|
v (iX)y = x y, |
||||
|
|
|
|
|
i= 0 |
|
|
(ixyf |
= {xyf (i (x V y )f, |
|
|
|
|
||
( A x f (By)Y V ( B x f (Ay)Y = (A(x\J y ) f (В {x V y ) f , |
|
||||||
|
|
|
X yZy = X zY, |
|
|
(2.22) |
|
|
|
|
Xyz = |
FXZ, |
|
|
(2.23) |
47
|
X yZ y = |
( X !Z l)y, |
(2 .24) |
|
(X |
V y f |
= |
Xz V y Z, |
(2.25) |
где Л, S, X, Y, Z, W, Э £ |
Afft; |
Л 5 |
= 0; x, y, z, i £ Ek, причем |
в вы |
ражении (2.24) степень i выбирается произвольно.
Функция (2.15) является частным случаем функции (2.21), имеющим место при подстановке в (2.21) константы вместо переменного Y.
В рассматриваемой системе, помигло формы (2.16), представляют интерес также другие канонические формы, которые в ряде случаев
[8] |
более удобны для |
практического синтеза многозначных схем. |
|||||
|
Теорема. |
Произвольную |
многозначную функцию из множества Рк |
||||
можно представить в виде |
|
|
|
||||
|
|
/(*) |
= V |
( V |
(a;1*1)v(cc,yr2)v |
. . . (а;пхпУ)1, |
(2.26) |
|
|
|
i=0 |
по всем |
|
|
|
|
|
|
|
а (о |
|
|
|
где |
ct(() = |
(a,-, |
а ,........... а,-п); i = f(ait, |
а-...........а,п); |
а ;/, у 6 Ек, |
||
U— 1, 2.......п)\ у — степень, выбираемая произвольно. Справедливость (2.26) доказывается применением соотношений
(2.24) и (2.25) к канонической форме (2.16).
Теорема. Произвольную функцию из множества Рк можно пред
ставить канонической формой |
|
|
|
/( * ) = |
V J “ A ) |
• |
(2.27) |
|
по всем а |
|
|
Доказательство теоремы получаем, применяя к (2.16) тождественное соотношение (2.2').
Исходя из канонической формы (2.27) и применяя тождественные соотношения (2.23) и (2.25), можно получить еще две разновидности форм представления многозначных функций
/ W = V ( |
V |
*„(*n-i (•••(*« (<*/Л)"1’) •••) <п) ’ |
(2-28) |
/=0 |
по всем |
|
|
|
а (О |
|
|
/(*) = V ( |
V |
^ „ ^ . ( ...( « „ ( а / Л ) * * ) ... ) '" ) '. |
(2.29) |
/=0 |
по всем |
|
|
а (О
Канонические формы (2.16), (2.26)—(2.29) имеют свои преиму щества и недостатки, которые определяются используемым принципом представления информации и сложностью применяемых базисных сис тем многозначных логических элементов (гл. 3).
48
§ 2.4. Некоторые системы с каноническими формами типа дизъюнктивных нормальных форм
Рассмотрим систему [1 ], включающую операции ху, х \/ у и х 1, опре деленные следующим образом:
|
■х при у = |
1, |
|
|
|||
ху = |
у |
при х = |
1, |
|
(2.30) |
||
|
. 0 |
при х Ф 1, |
у ф 1, |
|
|||
( X при у = |
0 |
, |
|
|
|
||
х У у = \ у |
при х = |
0 |
, |
|
|
(2.31) |
|
'm in(x, у) |
при х Ф 0, у ф 0, |
|
|||||
х1 = х + |
1 (mod k), |
|
|
(х, у g Ek). |
(2.32) |
||
Укажем основные тождественные соотношения в этой системе, справедливость которых вытекает непосредственно из определения операций ху и х \/ у
ху = ух, |
х V У = У У |
х\ = х, |
х У 0 = х, |
хО = 0, |
x V 1 = 1. |
{ху) z = х (г/г), (х У у) У 2 = х У (У V 2). хх . . . х = хх, |
||
x\J х = х, |
х V ху = х, |
{х \J у) г = хг \J уг. |
Введем обозначение хг для г-кратного применения операции (2.32)
к переменному х. Нетрудно проверить, что |
|
|
|||||
|
х у |
х 1 У х*У |
••• V **“ *= 1, |
|
|||
|
|
|
(хх V М/)1 = |
(хх)1(г/г/)1. |
|
||
Будем |
называть одноместными |
конституентами |
единицы функции |
||||
|
| |
1 |
при х = г, |
|
. . . , |
|
|
|
/г (■ *) = | |
о |
ПрИ х ф i, |
(г = 0, 1, |
& — 1). |
||
Лемма. |
В системе операций (2.30)—(2.32) |
одноместные конституен- |
|||||
ты единицы можно представить в виде |
|
|
|||||
|
|
|
fl (x) = |
(xl- i) ( x x- \ |
|
(2.33) |
|
где 1 — t = 1 — i (mod k).
Доказательство. При х — i правая часть (2.33) принимает значение
(i + 1 — г) |
(i + 1 — t) — 1, а при х = b Ф г — значение (b + 1 — |
— г) {b + 1 |
— г) = 0, так как b — i Ф 0. |
4 |
896 |
49 |
Теорема. Любую многозначную функцию из множества Рк можно представить в виде
/( * ) = |
v |
^ |
f(a )(x \-a')(x'ra')(x'2- a‘) ( x t a*) ... |
|
|
по всем а, |
где /(а)^ 0 |
|
|
|
|
. .. |
(Хп~ап) |
(2.34) |
Доказательство. Зафиксировав произвольный набор а=(а,, а.,, ...
...,g„), а также принимая во внимание свойства функции (2.30) и со отношение (2.33), убеждаемся, что выражение
|
х2 |
|
|
0 |
1 |
2 |
3 |
0 |
2 |
3 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
3 |
0 |
1 |
1 |
0 |
0 |
(х\~а') (а-,1-* 1) ( x t a!) ( х ^ ) . .. |
|
• • • (*;-“») (* '-“") |
(2.35) |
равно 1 при хг = сеь |
х.г = а 2, • •• |
... , х п — а п и равно 0 в остальных слу чаях. Дальнейший ход доказательства такой же, как и в § 2.1.
Рассмотрим пример. Представим в форме (2.34) функцию / (хъ х2), заданную табл. 12.
/ (а1, х2) = 1 (а! - 3) (а{ -3) ( x t 0) (А'2_°) V 2 (а[-°) (а|-°) |
(аГ ) (а^ 1) V |
||||
v |
1(a! - 3) (a} -3) ( x t l) U ~ ' ) |
V 3 (а!-0) (а!-0) |
(аП |
(х\ ~2) V |
|
V |
3 (а! - 2) (а!“ 2) (Xl2- 2) ( x t 2) |
V 1 (а!_ ‘) (а! - 1) |
(Аз-3 ) (А2_3) - |
||
|
= (А?) (А?) (А2) (а2) V (ХЬ (ХЬ (*2) (А2) V (*1 W |
(-^2) (Аг) V |
|||
V 2 (а!) (а!) (а2) (а2) V 3 (а!) (а!) (а2) (а2) V 3 (а?) (а?) (а3) (а2). |
|||||
Назовем кснституентами константы |
а функции |
|
|
||
|
f а при At = а и |
х2 = а2, . . . . |
хп = |
ап, |
|
|
fa W = ( 0 в остальных |
случаях ( a £ E k, |
а^=0). |
||
Любую конституенту константы можно получить в результате выпол нения операции (2.30) над константой а и выражением (2.35). Таким образом, каноническая форма (2.34) представляет собой дизъюнкцию конституент констант.
Используя взаимооднозначные отображения множества Ek на себя, можно определить полные системы операций, являющихся изоморф ными отображениями операций (2.30)—(2.32). Примеры таких систем приведены в [1 ].
При построении вычислительных устройств иногда целесообразно использовать в качестве одной из основных операций сложение по mod k.
50
