Раздел: Документация
0 ... 3 4 5 6 7 8 9 ... 119 сти получим: 2"-12"-1 2"-1 t=01=0t=0 Из определения макстермов следует, что 2"-1 /М= nv-Mb(1-73) t=0 Данная форма представления функции га переменных называется СКНФ. Так как значения функции а, = 0 или 1, то ai V Mi(v) = Mi(v), если щ = 0, и а, V М{(у) = 1, если а, = 1. Поэтому СКНФ можно представить в виде «о где го - номера тех точек, в которых функция f(v) равна 0, т. е. /("«о) = а«о = 0- Таким образом, СКНФ функции га переменных представляет собою конъюнкцию некоторого числа к < 2П макстермов. В качестве примера рассмотрим функцию трех переменных, заданную табл. 1.5. Так как только значения функции а0 = а3 = а4 = а6 = 0, то на основании (1.74) f(u) = М0 М3 М4 М6 - = (х3 V х2 V xi)(x3 V х2 Vii)(x3 V х2 V x-i)(x3 V х2 V хг). Это и есть СКНФ функции, заданной табл. 1.5. Совокупность элементарных функций, с помощью которых можно записать любую функцию f(v), называется функционально полной системой функций, или базисом. Из (1.72) и (1.74) следует, что для представления любой функции f(v) в виде СДНФ или СКНФ достаточно использовать только функции (операции) И, ИЛИ и НЕ (операция НЕ необходима для получения первичных термов хр, входящих в минтермы и макстермы), т.е. эти три функции составляют базис. Преобразуем СДНФ функции (1.72) с помощью закона двойного отрицания и закона двойственности: 2"-12"-1 /И = V= П «.*«(")•(1-75) j=0i-0 Данная форма представления функций называется совершенной нормальной формой (СНФ) в базисе И-НЕ, так как она требует использования только функций (операций) И-НЕ. Преобразуем теперь СКНФ функции (1.73) с помощью закона двойного отрицания и закона двойственности: 2--12"-1 f(v) = n«.V М.-И = V«.V M{(u).(1.76) 1=01=0 Данная форма представления функций называется совершенной нормальной формой в базисе ИЛИ-НЕ, так как она требует использования только функций (операций) ИЛИ-НЕ. На основании (1.75) и (1.76) из СДНФ и СКНФ функции, заданной табл. 1.5, можно получить СНФ этой функции в базисах И-НЕ и ИЛИ-НЕ: f{v) = X3X2Xl • Х3Х2Х1 • X3X2Xl • Х3Х2Х1, f(v) = х3 V х2 V xi V х3 V х2 V xi V х3 V х2 V xi V х3 V х2 Vij. На основании свойства минтермов (1.68) справедливо соотношение Ki(u) V Kj(v) = Ai(i/) ф Kj(v), поэтому 2"-12"-1 /(1/)= V «.•А,-М= £ ax-Kt{u). » = 0г=0 Такое представление функции позволяет записать ее в виде полинома п-й степени. Пусть, например, задана СДНФ функции трех переменных f(u) = K0(v) V Аз(«/) V A7(i/). Тогда /(«/) = x3x2xi ф x3x2xi ф X3X2Xl = = (1 Ф Х3)(1 ф Х2)(1 ф Xl) ф (1 ф Х3)Х2Х! ф Х3Х2Х! = = 1 ф Xl ф Х2 ф Х3 ф Х3Х1 ф Х3Х2 ф Х3Х2Х1 . Такой же результат можно получить и с помощью-разложения Рида (1.36) функции трех переменных. Полученная форма представления функции называется разложением Рида - Маллера [8]. 1.9. Конъюнктивные и дизъюнктивные термы Конъюнктивным термом (контермом, элементарной конъюнкцией) называется конъюнкция любого числа первичных термов хРр, если каждый первичный терм с индексом р входит в нее не более одного раза. Любой контерм представляет собой функцию п переменных A,-j(j/), которую можно записать в виде Ki3{v)= f[(zpVzP),(1.77) где v - (хп,..., xi), ер = О или 1, ер = О или 1; ер < ер - для исключения неоднозначности нумерации контермов; i = еп...е\, j = еп ... е\ - двоичные числа. Действительно, в соответствии с (1.64) Xе" V х*р = { ХрР еСЛИ еР = ер * р \ 1, если ер ф ер (ер = ер), поэтому функция Kij(v) будет представлять собой конъюнкцию г < га первичных термов хрр. Запишем, например, в явном виде контерм Ii\j(i>) трех переменных. Для этого воспользуемся символической схемой:
(операция дизъюнкции выполняется поразрядно). Если значения ер = ер для всех р, то i = j и херр V херр = херр для всех р = 1,2,..., п , поэтому, как следует из (1.77), п Кц(и) = Ки{и) = П *рр = А». p=i т.е. контерм К\г(и) является минтермом K{(v). Если же значения ер ф ер для всех р (ер < ер, т.е. ер = О, ер = 1), то е с г = 0» j = 2n-1 и хррУхр = 1 для всехр, поэтому A0)2"-i(f) = 1. Таким образом, функция константа единица является конъюнктивным термом. Из определения (1.77) и рассмотренных частных примеров следует, что все контермы, за исключением Ka{v) = Ki(v), являются вырожденными функциями п переменных. Всего имеется Зп различных контермов га переменных. Действительно, так как хрр Vxpp = хр, хр или 1 (дизъюнкция первичных термов может принимать любое из этих трех значений), то каждой функции h\j(v) можно поставить в соответствие одно из га-разрядных чисел с основанием системы счисления q = 3, а поскольку на основании (1.23) имеется Зп различных га-разрядных чисел при q - 3, то и число различных контермов равно Зп. Дизъюнктивным термом (дизтермом, элементарной дизъюнкцией) называется функция га переменных Мц(и) = ЪуУ) = f[(xPp У хрр) = V 4" (1-78) Дизтермы представляют собой дизъюнкцию любого числа г < га первичных термов хрр, причем каждый первичный терм с индексом р входит в нее только один раз. Всего имеется 3" различных дизтермов, так как имеется Зп различных контермов. Запишем, например, в явном виде дизъюнктивный терм М\уз(и) трех переменных. Для этого воспользуемся символической схемой: Mli3(i/) (операция конъюнкции выполняется поразрядно). Поскольку функция M0,2"-i(/) = Ao,2"-i(f) = 0, то константа нуль является дизъюнктивным термом (понятно, что дизъюнктивным термом является и макстерм). 1.10. Минимизация переключательных функций Физическое устройство, реализующее одну из основных операций алгебры логики или простейшую переключательную функцию, называется логическим элементом (ЛЭ). Схема, составленная из конечного числа ЛЭ по определенным правилам (см. § 2.3), называется логической схемой (ЛС). Если ЛС полностью описывается переключательными функциями (одной или несколькими), то она называется комбинационной схемой (КС). Одной из основных задач, "возникающих при синтезе КС, является минимизация переключательных функций, которые она реализует. Чем проще логические выражения, описывающие функции, тем проще и дешевле реализующая их КС. х°3 V z% V х\ ~,=1 xl Ух\ Vx[~=3 xi V О V х? = хз V X! = В качестве критерия сложности логического выражения, описывающего функцию, целесообразно принять количество первичных термов хрр, в него входящих. Очевидно, что любой метод минимизации может основываться только на тождественных преобразованиях логических выражений. Общие правила минимизации можно установить только для случаев, когда в результате минимизации получаются так называемые минимальные нормальные формы функций (термин "нормальные формы" означает, что в логическом выражении, определяющем функцию f(v), последовательно выполняется не более двух операций из совокупности операций И, ИЛИ, И-НЕ и ИЛИ-НЕ). Два минтерма K{(v) и Kj(v) будем называть соседними, если они различаются только одним первичным термом хрр, т.е., если для одного из минтермов ер = О, а для другого ер = 1 (все же остальные первичные термы одинаковые). Так, например, если га = 3, то минтермы Аз(г) = х3х2х\ и Kr(i>) = x3x2xi являются соседними, так как они различаются только одним первичным термом х33. Для минтерма K3(v) соседними будут также минтермы Ai(i/) = x3x2xx и K2(i>) = x3x2xv Понятно, что каждый минтерм га переменных A,(i/) имеет по га соседних из общего числа 2П минтермов. Рассмотрим контерм п переменных KtJ(i/), не зависящий от одной переменной хр, т. е. случай, когда контерм является конъюнкцией п - 1-го первичного терма. Данный контерм можно представить в СДНФ: К1}(и) = (хр V хр)К{](и) = xpKtj(v) V xpKxj(u) - Ki(v) V Kj(v), где и - (xn,... ,хр,... ,xi). Очевидно, что полученные минтермы Ki(v) и Kj(v) являются соседними, так как они различаются только одним первичным термом хрр (хр и хр). Отсюда следует правило минимизации: дизъюнкцию двух соседних минтермов можно заменить одним контермом, не зависящим от одной переменной. Пусть контерм га переменных не зависит от двух переменных хр и xq (га > 2, р > q). Выполним тождественные преобразования контерма для его представления в СДНФ: KiAv) = (хР V xp)(xq V xq)Kij(u) = = xpxqKij(v) V xpxqKij(v) V xpxqKij(u) V xpxqK~ij(y) = = Ki(v) V Кт(и) V K.(u) V Kj(v), где v = (xn,..., xp,..., x?,..., x]), г < r < s < j. Из этих соотношений видно, что каждый из четырех полученных минтермов имеет среди остальных по два соседних. Отсюда следует правило минимизации: дизъюнкцию четырех минтермов, каждый из которых имеет среди остальных по два соседних, можно заменить одним контермом, не зависящим от двух переменных, причем исключаются те переменные, которые входят в минтермы как с инверсией, так и без инверсии. Рассмотрим пример. В § 1.9 было показано, что контерм трех переменных Aij = х\, т. е. данный контерм является вырожденной функцией, независящей от двух переменных х3 и х2. Тогда легко показать, что AVH = (х3 V х3)(х2 V x2)KXj(v) = - Х3Х2ХХ V x3x2xi V х3х2х!V Х3Х2Х\ = = Кх(и) V K3(v) V Къ(и) V K7{v), где каждый минтерм имеет по два соседних. Продолжив вышеприведенные рассуждения дальше, можно установить общее правило минимизации: одним контермом га переменных Kij(v), не зависящим от m переменных (тп < га), можно заменить дизъюнкцию 2т минтермов, если каждый из них имеет по тп соседних среди остальных 2m - 1 минтермов. Если контерм A,j() не зависит от m переменных, то принято говорить, что он покрывает 2т минтермов. На этом свойстве контермов и основывается минимизация функций /(), заданных в СДНФ, которая в соответствии с выражением (1.72) представляет собой дизъюнкцию некоторого числа минтермов А*: «1 Заменив в данном выражении дизъюнкцию 2т (т = 0,1,..., га) минтермов (2° = 1 в случаях, когда какие-либо минтермы не имеют ни одного соседнего) соответствующими контермами Kij(y), функцию можно представить в виде дизъюнкции некоторого числа контермов, покрывающих все минтермы A,j, входящие в СДНФ функции:. Такая форма представления функций называется дизъюнктивной нормальной формой (ДНФ). Если ДНФ содержит минимально возможное число первичных термов хрр, то она называется минимальной дизъюнктивной нормальной формой (МДНФ). Следует отметить, что любые правила минимизации 0 ... 3 4 5 6 7 8 9 ... 119
|
