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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 10.07.2024

Просмотров: 153

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

каноническая

форма типа

СДНФ,

рассмотрим

систему, включаю­

щую все константы

и операции

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

х V У,

ху,

 

 

 

 

 

 

 

J, (х) =

а

при х = s,

 

 

 

 

 

 

 

 

 

b

при

х Ф s,

(s = 1,

2,

 

 

1) ,

 

где афЬ;

 

 

 

 

 

 

х,

у,

a,

b £ E k.

 

 

 

 

 

 

 

 

 

 

 

Теорема.

Если функции х V У и ху удовлетворяют условиям

 

 

 

 

 

x \ J b = b \ / x — х,

 

 

 

 

 

 

 

 

 

 

 

xb = bx — Ь,

 

 

 

 

 

 

(2.42)

 

 

 

 

 

ха = ах = х,

 

 

 

 

 

 

 

то любую функцию f (х) можно представить в виде

 

 

 

 

 

/ (х) —

V

/ (а) ^а, (*l) Ja, (Х2) • • ■ Jan (Х„).

 

(2.43)

 

 

 

по всем а

 

 

 

V

•••V хп означают соответственно

Выражения хгх2

... хп

и х1

\/

х2

 

 

 

*1*2

. . . хп =

{... ((*х*2) х3) .. .) хп,

 

 

 

 

Xi V *2 V

• •

•

V хп = ( . .

. ((* х v *а) V *з)

V

• •

•)

V *„•

Доказательство.

Пусть

х =

а.

Тогда

левая

часть

( \43)

равна

/ (а). Заметим, что

 

 

 

 

 

 

 

 

 

 

 

 

 

f (°0

 

(*1) Лх, (*2)

• • •

^а„ (

п) —

/ (а)

при х =

а,

 

 

,

при х Фа.

 

 

 

 

 

 

 

 

 

 

 

 

Ь

 

Следовательно, правую часть (2.43) можно представить в виде

N—1

 

-*

 

 

 

 

(as)

... ./«„ (a„) V

kn

 

b.

 

V ь V / (“) -Ах, (“1) Ja,

V

 

t= 1

 

 

 

 

 

 

 

 

 

 

/=ЛГ+1

 

 

Отсюда последовательно получаем

 

 

 

 

 

 

 

 

b v f(<x)Jat (ttJJa, (a2) . . .

Jan(an) \/ b = f(a)aa . . .

a =

/(a).

Так как

аналогичные

рассуждения

справедливы

для

любого

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

Рассмотренная система полна при любом доопределении функций х У у, ху и / , (х). Условиям (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 (х),

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

—¥ —►

щения транзитивно, то есть если fx (х) поглощает /2 (х), а /2 (х) погло-

—►

—►

—►

щает / з (х), то fx (х) поглощает /3 (х).

Функцию /

—►

поглощаемую данной функцией и накрывающую

(х),

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

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

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

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

57

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

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

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

/У 0(*) V-PAW V

••• V PJk-i (х) =

Р,

(2.44)

1 P J l (х) V 2P J 2 (х) V • • •

V (Ь — 1) PJk-i (х) = Рх,

(2.45)

где Р — произвольное выражение.

дизъюнктивную

Соотношения (2.44) и (2.45)

позволяют любую

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

Рассмотрим пример. Восстановим совершенную ДНФ функции, за­ данной в виде (к = 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

V 2У3(хх) У2(х2) V

1А (*1) J 1 (*2) V A (*i) А (*2) V A (*i) А (*2) V

V

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

Перейдем к алгоритму нахождения простых импликант. Любая

простая импликанта имеет вид

 

 

 

aRQ,

где а — константа; R

— xj,x/, . . .

x ir,

Q == Уа;1 (*/,) A /s (*/2)

• • A ^ (x;?), /" +

58

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

= 5Jb (х 3).

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

 

V o W V ^ A W V

•••

 

у Pak_Jk-i(x).

 

 

(2.46)

Среди всех

выберем наименьшее at

и запишем

 

 

 

 

 

 

 

V o w v v ^ v

 

 

•••

 

v v * - 'W

-

 

 

(2-47)

Выражение (2.47) поглощается выражением (2.46) и, согласно со­

отношению (2.44), равно Ра1- Поэтому

V Pak_ xJk-\ (х) =

 

 

 

 

V o ( x ) W

i W

V

 

•

•

•

 

 

 

 

= V o W

W i W

V

 

• •

•

 

У Рак_Ук—1 (х) У Раг

 

(2.48)

Аналогично, исходя из (2.45), получаем

 

 

 

 

 

 

 

QoA ix) У QaJ<i (х ) У

• • •

V

 

 

М =

 

 

 

 

— QaJi (х) У Qaji (х)

V

' ' •

 

V

 

Qak_ J k - 1(А) V 0 в/ ,

 

(2.49)

где at — наименьшее

из

at, коюрые

меньше

индекса

при

символе

J своего дизъюнктивного члена.

 

 

 

соотношениям

(2.48)

и

(2.49),

Операции,

выполняемые согласно

называют операциями склеивания по операторам и аргументам

[19].

Рассмотрим пример. Определим множество импликант переключа­

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

 

/

х2) — Jo (Ai) Jо(x2) У 'JJi (Xi) Jo (xz) V 1A (xi) J 1 (X2) V

 

 

V ^Jl (Xl)

(Хг)

V

(Xj) J3(x2) V U i

(Al) J l (X2) V

 

 

V %Jг (Al) J‘2 (Xi) V 2</2(Al) J3 iXi)

V

 

1J3 (Al) Jl (X‘l) V

JJ3“

(Al) J3 (X‘i)-

Из членов этой ДНФ составим все возможные выражения, удовлетво­

ряющие соотношения (2.48) и (2.49),

 

 

 

 

 

 

 

 

 

 

 

F i — 2 J i (хг) J0(х2) v

(Ai) Ji

(хг) У 1A (Ai) J%(x i ) V 2-/i (Xj)

J3(x2)

F-i =

Jo (xi) ^3 (Аг) V

(Xj) 73 (x2) у

 

2У2 (xx) У3 (x2) \J 2J3(Xj)

У3 (x

 

F3 =

\ J2(Xj) Ji (x2) V 2J2(Xj) J2(x2) V 2J2(xx) У3 (x2),

 

 

 

/Г4=

(Xj) J x (x2) V

l</2(Al) J l

i X2) V

^

(A'l) J l (X2)-

 

 

Обозначив в выражении для F\ функцию

(хх)

как Р,

получим

 

Fi = P2J0(х2) У P\Ji (х2) V F>\J2{x2) у P2J3(х2).

 

 

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

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

59

Смотрите также файлы