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

Операции, определяемые соотношениями (4.36) — (4.38), назовем операциями неполного склеивания. Если в совершенной ДНФ функ­ ции произвести все операции неполного склеивания как над ее чле­ нами, так и над вновь полученными импликантами, то получим мно­ жество элементарных произведений, среди которых будут и все простые импликанты. Чтобы их выделить, необходимо произвести все операции поглощения согласно критериям поглощения.

Рассмотрим два элементарных произведения

В этих элементарных произведениях не может быть более двух

так как в противном случае или константа, или аргумент без знака

оператора отсутствует.

Теорема. Для того чтобы элементарное произведение U1 поглощало элементарное произведение U2, необходимо и достаточно:

axA m > a2As,.

Доказательство. Докажем вначале необходимость первого усло­ вия. Пусть U1 > U2n Jyz (Л(г) не входят в U2. В этом случае всегда

104

можно выбрать таким образом значения аргументов хс, чтобы для их симметричных аналогов выполнялись условия

и a2A S(. Но так как axAim < о2Л 5(, то в данном случае и Ux < U2,

что невозможно. Следовательно, второе условие также необходимо. Покажем достаточность приведенных условий. Рассмотрим значе­ ния Ux и U2 на тех наборах, на которых U2 Ф 0. Так как все опе­

раторы JVy (AiJ) входят в U2, то на этих наборах Ux = axAtm и U2 =

= a2A S(- Но в силу второго условия axAim > aAS/. Следовательно,

U\ > Uz на этих наборах. На всех остальных наборах U2 — 0. По­ этому на любых наборах Ux >• U2. Теорема доказана.

Таблица 20

Рассмотрим пример. Пусть симметричная функция / (х, у, г) за­ дана ДНФ (k = 4)

f(x, у, z) = J3(x)yJ0(z) V Ja(x) Jo (У) г У xJ3(y)J0(z) V

V xJ0(y)J3(z) V J0(x)Ja(y)z\/ J 0(x)yJ3(z) V 1Ja(x)J2{y)Jx{z) V V 1J2(x) J x{y) J2{z) V Mi(x)Ji(z) V 2Ji{x) J2{y) J 2{z).

Нетрудно проверить, что эта форма является минимальной ДНФ функции / (х, у, z). Совершенная ДНФ этой функции содержит 19

105

дизъюнктивных членов, в то время как ее симметричный аналог только пять членов:

f (x t У<z) = 1А (A) А (А ) A (A) V 2y3 (А ) А (А) А (А) V

V А (A) Jз (А) А (А) V JA (A) A (A) A (A*) V 2A (A) *A (A) A (A)-

Произведя всевозможные склеивания и поглощения (табл. 20), полу­ чим симметричный аналог минимальной ДНФ функции

/ (х, у I z) — A (A) А А (А) V А (А ) ^2 (А) А>

что значительно проще обычной минимальной ДНФ этой функции. Описанный метод упрощения симметричных функций не всегда

дает абсолютно минимальные выражения. Однако можно утверждать, что симметричные аналоги минимальных ДНФ, как правило, гораздо проще обычных минимальных ДНФ, а число операторов Js (х) в них всегда не больше, чем в обычных минимальных ДНФ. Это особенно важно при амплитудно-импульсном принципе представления инфор­ мации, так как в этом случае элементы, реализующие Js (х), значитель­ но сложнее других элементов (гл. 3). Такой метод можно применить для упрощения частично симметричных и обычных функций. Для

этого многозначную функцию / (х) необходимо представить как

f(x) = ф(х) V Ф(х),

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

§ 4.5. Особенности реализации многозначных симметричных функций в системе теоретико-множественных операций

Пусть х V У и ХУ— соответственно операции объединения и пере­ сечения, а Д — характеристическая функция (2.15). Как и в § 4.3,

символом {а} обозначим множество симметричных наборов, образо­

ванных набором а. Функцию S'(а, х), принимающую значение /' на

106

Теорема. Базовую симметричную функцию S' (а, х) можно пред­ ставить в виде

случае левая часть (4.41), согласно (4.39), равна /. Из определения

для множества симметричных наборов которой справедливы усло­ вия (4.40), можно реализовать на основе схемы, реализующей только функцию АпI.

Произвольный набор а, образующий множество {а}, можно пред­ ставить в виде

ГДе ССпг1-у—ССт2 Ф1 ... ifc ctn.

Теорема. Произвольную базовую симметричную функцию можно

Доказать эту теорему можно аналогично предыдущей.

Отметим, что определение базовой симметричной функции и ее реализация, согласно (4.42), не зависят от k. Имея все базовые симмет­ ричные функции (то есть базовый симметричный многополюсник),

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

по всем {а}

Для построения базового симметричного многополюсника необхо­

107

димо реализовать симметричные аналоги A ni аргументов, что можно

венно. Общее число двувходовых элементов, необходимых для реали­

Дальнейшее упрощение симметричных функций в системе теоре­ тико-множественных операций может основываться на использовании соотношений, аналогичных соотношениям (2.56) — (2.58), в которых аргументы заменены их симметричными аналогами. Однако использо­ вание таких соотношений не всегда приводит к отысканию всех сим­ метричных аналогов простых импликант. Примером тому может слу­ жить функция / (х, у, г), которая при k = 3 на наборах (0, 0 , 0), (0 , 0, 1 ) и (0, 0, 2 ) равна 1 , а на остальных наборах принимает произволь­ ные, но не равные единице значения. В этом случае выражения (О^зз)1 V (О^зг)1 AS1 V (О-Дд,) 1 (2А31У не могут быть подвергнуты даль­ нейшим упрощениям. С другой стороны, как легко проверить, спра­

Таким образом, в классе симметричных аналогов ДНФ многознач­

Предположим, что множество наборов {а,} состоит из всех тех наборов, в которых константы а1г а2, ..., аг встречаются соответствен­ но /ь /г» •••> !г и более раз. Пусть, кроме того, подлежащая минимиза­ ции функция принимает на этих наборах одно и то же значение р. В этом случае справедливо соотношение склеивания

т

где q = К SP (а;, х).

108