Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.07.2024
Просмотров: 139
Скачиваний: 0
Такое с х о д с т е о операций системы Россера — Тьюкетта с операция ми булевой алгебры позволяет сделать предположение о существова нии канонической формы представления произвольной &-значной функ ции, которая аналогична совершенной дизъюнктивной нормальной форме представления двоичных функций. Покажем, что это действи тельно так.
Теорема. Произвольную функцию из множества Р к можно пред
ставить канонической формой |
|
|
|
|
/ (х) = |
V J |
Й Лх, (х2) . .. |
Jan (хп), |
(2.12) |
|
по всем а, |
|
|
|
|
где /(а)=А0 |
•+ |
■+ |
|
где / (а) — значение функции f |
|
|||
(х) на наборе а. В дальнейшем форму |
||||
(2.12) будем называть совершенной дизъюнктивной нормальной фор
мой многозначной переключательной функции / (х). Доказательство этой теоремы одновременно устанавливает факт функциональной пол ноты системы Россера — Тьюкетта.
Доказательство. Предположим, что есть фиксированный набор
аргументов рь р2, •••, |
Р«- Рассмотрим произведение |
= |
Ja, (Pi) Ja, (Рг) • • • Jan (Pn)- |
Учитывая приведенные выше соотношения (2.9) и (2.11), легко убедить ся в том, что
|
Js (х) J, (х) — 0 |
при |
s Ф г. |
(2.13) |
|
Поэтому |
|
|
|
|
|
k — 1 |
при |
= Pj, а 2 = |
р,, . . . . ап = |
р„, |
|
5 = |
|
на всех остальных наборах. |
|||
О |
|
||||
Так как f (Р) = |
(k — 1) / (Р), |
то справедливость |
выражения |
||
(2.12) для заданного набора Рдоказана. Подобные же рассуждения мож но привести для любого набора. Следовательно, теорема доказана.
Произведение функций J s (х), взятых по одной для каждого ар гумента из некоторого множества аргументов, называют конституентой.
Рассмотрим пример представления совершенной дизъюнктивной нормальной формой СДНФ функции, заданной табл. 9,
/ (*1> — 2*^з (-Д) J 0 (x z) V |
(xi) А (хг) V ^2 (Д) ^ \ (х г) V |
V ^2 (x i) ^2 (х 2) V Л (-Д) |
(*2) V 1A (*i) *^з (хг)' |
Здесь нет дизъюнктивных членов, соответствующих нулевым значениям
42
функции, так как они получаются согласно соотношению (2.13). Кроме того, коэффициенты 3, которые должны стоять при некоторых конституентах, опущены в силу соотношения (2.9).
Таблица 9 |
Таблица 10 |
i
1° |
0 |
|
0 |
||
i 1 |
||
2 |
0 |
|
|
СО |
2 |
° !
2
1
0
|
|
О |
1 |
|
0 |
3 |
0 |
— |
— |
0 |
I |
— |
1 |
2 |
3 |
0 |
0 |
— |
— |
0 |
0 |
|
|
|
Заметим, что в системе Россера — Тьюкетта можно образовать совершенную конъюнктивную нормальную форму переключательной функции, членами которой будут дизъюнкции вида
/ (а ) V Ja, |
(Xi) V Ja-i (х2) V |
' ' ‘ |
V ^а„ (хп)> |
|
|||
где |
|
|
|
|
|
|
|
J<H (x i) — |
V |
^а. ' (xi) — |
О |
при |
xt — ah |
(2.14) |
|
k — 1 |
при хг^ а г. |
||||||
для всех ш |
|
||||||
а. |
фа{ |
|
|
|
|
||
‘ т |
|
1 |
|
|
|
|
|
Рассмотрим пример. Пусть задана табл. 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), последнее выражение можно
записать следующим образом: |
|
|
|
|
||
f (*i. хг) = |
2 ( А (хх) V А (х2))(1 |
V J * (Xi) V J * (х2)) {J*2 (xi) V J o (х2)). |
||||
Заменив, |
наконец, каждую |
функцию |
J *s (х) ее |
представлением, |
||
согласно (2.14), |
получим |
|
|
|
|
|
f (xi, х2) = |
2 (Jx (хх) V J2 (xt) V J 1 (x2) \ / |
J 2 (x2)) (1 |
V |
(Xj) V |
||
V J 2 (Xi) V |
(x2) V J^ (x2)) (•/„ (Xi) V A (Xi) V Ji (x2) V |
(Xi)). |
||||
Отсюда видно, что функция f (xlt x2) принимает |
значение k — 1 |
|||||
на тех наборах, где она не определена. |
|
|
|
|||
43
§ 2.3. Системы, содержащие теоретико-множественные операции
Особенностью некоторых принципов представления информации, например фазо-импульсного и частотно-гармонического [15], является возможность одновременного присутствия множества различных зна чений информационных сигналов в одной точке схемы. Учет этой осо бенности при практической реализации переключательных схем требует привлечения теоретико-множественного аппарата для синте за схем. Вместе с тем, как будет показано в главе 3, теоретико-множе ственные операции можно реализовать простыми физическими схемами.
Напомним, что Ек — множество возможных значений, принимае мых /г-значной функцией. Образуем множество М к, элементами кото рого будут все подмножества множества Ек. Переменные, принимаю
щие значения из множества |
М к, обозначим большими буквами |
(Хь |
||||
Х2, •••), а переменные, принимающие значения |
из |
множества |
Ек,— |
|||
малыми (хц х2, ...)■ Так как |
из |
х £ |
Е к следует |
х £ |
М к, то все соот |
|
ношения, справедливые для |
X lt |
Х 2, |
... £ М к, будут справедливы и для |
|||
Хи х2, ... £ Ек. |
|
|
|
|
|
|
Рассмотрим известные в теории м-ножеств операции объединения X \J Y = X U У' и пересечения X Y = X f| У- Эти операции ассо циативны, коммутативны и связаны между собой законами дистрибу тивности. Кроме того, справедливы соотношения
X v е = X, XQ = Q,
г, е 0 — пустое множество.
Введем характеристические функции, определенные на множестве М к
Фг (х) |
i |
при |
X Ф 0 |
(2.15) |
|
0 |
при |
X — 0, (t £ Ек). |
|||
|
|
Теорема. В системе, содержащей константы, характеристические функции, операции объединения и пересечения, произвольную функ цию из множества Рк можно представить канонической формой
/ Й = V («Л)'*(< W “ • • • K * j 4 |
(2-16) |
по всем
а
где ia — значение функции на наборе а. Доказательство. Рассмотрим выражение
K * i)'“ K * 2)'a • • • (<хпхп]1а.
Легко проверить, что
«iXj = |
а,- |
при |
Xj = |
а/, |
|
|
0 |
при |
Xj Ф а,-, |
( /= 1 ,2 , |
|||
|
||||||
|
(а/•*/)'“ = |
Iа |
при |
Xj = а„ |
||
|
0 |
при |
X j ^ a j . |
|||
|
|
|
||||
44
Следовательно, |
|
\ia |
при jfj - «I, *, = |
at, . . . , x n *= an, |
||
|
|
|
|
|||
( a . a:,) “ ( a 2x 2) “ . . . (a .,x „ ) “ = > , |
в остальных |
случаях. |
||||
1 |
' |
i ' |
" |
10 |
||
Так как аналогичные рассуждения справедливы для любого набо
ра а, то теорема доказана.
Следует отметить, что для получения канонической формы (2.16) представления &-значной функции вместо операции пересечения достаточно операции совпадения
\ х при х = у,
хсо у = \ а
{0 при X Ф у.
Реализация многозначных функций согласно рассмотренной кано нической форме слишком громоздка. Пользуясь приведенными ниже соотношениями, можно получить более простое представление пере ключательной функции. Непосредственно из (2.15) получаем
|
Х! V Y l = (X V Y j, |
(2.17) |
|||
|
(iX)‘ = |
iX, |
(2.18) |
||
|
х = i, |
где |
i £ E k. |
(2.19) |
|
Из (2.17) вытекает соотношение |
|
|
|
|
|
|
(.ХГ/' V (XW)1= (X {Y V |
(2 • 19а) |
|||
Из (2.18) и (2.19) следует |
|
|
|
|
|
|
(iX)1(jY)‘ = |
X (jY)‘. |
(2.196) |
||
Используя |
предыдущие соотношения, можн также показать, что |
||||
|
ЦХ)1 iJY)1= |
(iXY )', |
|
||
|
(ОХ/ V (1*)' V |
• • ■ V № - l)X)‘ = X1', |
(2.19в) |
||
|
(ОХ)° V О *)1 V |
••• |
V ((*— 1) Л')*_ ' = |
|
|
|
= ОХ У IX У |
••• |
у |
{k— 1)Х = Х. |
(2.19г) |
(Ах)1(By)1У (Вх)‘ (Ау)1= |
(А (х У у))‘ (В (х У у))1, |
(2.20) |
|||
где АВ = 0 |
и А, В £ М к. |
|
|
|
|
Действительно, раскрывая правую часть соотношения (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) принима ет нулевые значения
f(xlt |
х2) = |
(Охр0 (0х2)° V (1^)° (0х2)° V (2xj)° (0х2)° V (Зхх)° (0х2)° V |
||||||
|
V (0хР2(1х2)2 V |
|
V ( 2 ^ ( 1 x2f |
V (3xP2(1x2)2 V |
||||
V (0xp2(2x2)2 V (2xp2 (2 x 2)2 V (1хгП 2 х 2У V (Зхх)2(2х2)2 V (Ox,)3 (Зх2)3 V |
||||||||
|
|
V (1хР3(Зх2)3 V (2xp3(3x2)3 V (3xx)3 (3x2)3. |
|
|||||
Сгруппируем члены этого выражения следующим образом: |
|
|||||||
/ (х1( |
х2) = |
((Охр0 (0х2)° V (1хр° (0х2)° V (2хр° (0х2)° V (Зхр0 (0х2)° V |
||||||
|
|
V (0хр3(3х2)3 V (1х1)3(3х2)3 V (2xP3(3x2)3 V |
|
|||||
|
V (Зхр3(3х2)3 V (0хр°(0х2)° V (IxPMlxP1 V (2хР2(2х2)2 V |
|||||||
V (Зхр3(3х2)3) V ((0хР2(1х2)2 V (0хР 2(2х2)2 V (Зхр2 (1х2)2 V |
||||||||
V (ЗхР2 (2х2)2) V ((2xPJ (lx,)1 V (1хР1(2х2)1) = F, V Fa V Fa. |
||||||||
В первых |
скобках |
дважды |
встречаются |
члены (ОхР° |
(0х2)° и |
|||
(ЗхР3 |
(Зх2)3. Однако значения функции при этом не меняются, |
так как |
||||||
|
|
|
|
|
X V X — X. Рассмотрим каждое из |
|||
|
|
r2 |
Таблица 11 |
внугрискобочных выражений Flt F2 и |
||||
|
|
|
|
F3. Запишем Fx в следующем виде: |
||||
|
|
|
|
|
Fx = (0x2)°((0xp° V (1*Р° V |
|||
0 |
0 |
2 |
2 |
3 |
V (2хР° V (Зхр0) V (Зх2)3((0хр3 V |
|||
V (1хР3 V (2хР3 V (Зхр3) V |
||||||||
1 |
0 |
1 |
1 |
3 |
||||
V(0xp°(0x2)° V (lx P 1(lx2)1 V |
||||||||
2 |
0 |
1 |
2 |
3 |
||||
v (2хр2 (2х2)2 V (Зхр3(3х2)3. |
||||||||
3 |
0 |
2 |
2 |
3 |
||||
Отсюда видно, что объединения в |
||||||||
|
|
|
|
|
||||
|
|
|
|
|
скобках удовлетворяют соотношению |
|||
(2.196). Кроме |
того, |
к членам (ix)‘ применимо соотношение (2.18). |
||||||
Следовательно, |
|
|
|
|
|
|||
|
Fj = |
0x?x2 V Зх?х2 V 0хх0х2 V lxpXj \/ 2хх2х2 V 3Xi3x2. |
||||||
Применяя к первым двум членам этого выражения соотношение (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
