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

Теорема. Операции склеивания по операторам и аргументам дают возможность найти все простые импликанты многозначной функции

/ (х), то есть получить сокращенную ДНФ этой функции. Доказательство. Импликанта, которая не зависит от Js (х), принима­

ет одно и то же значение А при s = 1, 2, .... k — 1. Поскольку А Ф О,

то среди элементарных произведений, составляющих СДНФ функции

—у

f (х), должны быть и те, которые обеспечивают выполнение соотношения (2.48). Рассуждения относительно аргумента xt и соотношения (2.49) аналогичны, следовательно, теорема доказана.

Дальнейшие упрощения, если они возможны, должны быть про­ ведены с вновь полученными импликантами аналогичным способом. Необходимо провести все возможные склеивания по одному разу.

Рх \J Р = Р (х \J (k — 1)) = Р.

Следовательно, любая собственная часть какого-либо элементар­ ного произведения поглощает его.

Собственной частью называют произведение, полученное путем исключения из данного произведения одного или нескольких сомно­ жителей. Например, элементарное произведение aJr (хх) Jq (х2) имеет такие собственные части: aJr (хг), aJq (x2), Jr {xi)Jq(x2), a, /Д х ^ ,

Jq(x2).

Приведенное условие является достаточным, но не необходимым для поглощения одного элементарного произведения другим. Дей­ ствительно, элементарное произведение 5х поглощает элементарное произведение 3J6{x) и при этом не является его собственной частью.

Теорема. Для того чтобы элементарное произведение Рг погло­ щало элементарное произведение Р2, необходимо и достаточно, чтобы соблюдались следующие условия:

60

1) Ci > C2, где Ci и C2 — константы элементарных произведений

иР 2;

2)все функции У, (х), входящие в состав произведения Р 1( должны быть и в Р2;

3)если в состав Рг входит аргумент х{, не содержащийся в Р2,

то в состав Р 2 должна входить функция J, (хс) этого аргумента, причем

С2.

Доказательство. Необходимость первого условия очевидна. Не­ обходимым является и второе условие, так как элементарное произве-

—у

дение Pi должно накрывать функцию f (х) на тех наборах, которые накрыты элементарным произведением Р2. Следовательно, если Р1зави­ сит от какой-либо функции J s(x), то Р2тоже должно от нее зависеть.

которые сведут разницу между элементарными произведениями Рх и Р2 к случаю, предусмотренному условием 3. Согласно (2.50), элемен­ тарное произведение Рг будет поглощать вновь полученное произве­

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

тарные произведения — суть импликанты функции / (х)). Приведенные условия позволяют выделить простые импликанты.

Дальнейший процесс отыскивания минимальной (тупиковой) ДНФ не зависит от k [19] и может идти известными в булевой алгебре пу­ тями, поскольку возможны всего два варианта: или простая импликанта поглощает данное произведение, или нет.

Рассмотрим пример. Определим все простые импликанты для функ­ ции из предыдущего примера. Для этого к каждой импликанте спра­ ва припишем все импликанты, которые поглощаются этой импликан-

61

в рассматриваемом случае произвести нельзя.

Сравнивая приведенный перечень поглощенных импликант с СДНФ

Минимальную Д//Ф этой функции найдем с помощью импликантной матрицы. Матрица представляет собой таблицу, строки которой обозначены простыми импликантами, а столбцы — членами совершен­ ной ДНФ. Для упрощения записи каждую простую импликанту обо­ значим буквой J с индексом, равным ее порядковому номеру в сокра­ щенной ДНФ (например, У4 = 1 x1Jl (х2)), а каждый член совершенной ДНФ — буквой К с индексом, также равным его порядковому номеру (например, Кь — 2J 1 (х4) J 3 (х2)). Клетки такой импликантной матрицы (табл. 15), образованные пересечением строк с простыми импликанта­ ми и столбцов с поглощаемыми ими членами СДНФ, отметим крестиками.

62

Как и в булевой алгебре, для получения минимальной ДНФ за­ данной функции достаточно найти минимальное число простых импликант, которые совместно накрывают крестиками все столбцы импликантной матрицы. Из табл. 15 видно, что все простые импликанты должны войти в ее минимальную форму, так как только в этом случае все столбцы импликантной матрицы накрываются крестиками. Сле­ довательно, минимальная ДНФ рассматриваемой функции совпадает

сее сокращенной ДНФ.

§2.8. Критерии и методы получения минимальных Д Н Ф многозначных функций

Рассмотрим более подробно критерии, по которым выбирают ми­ нимальную ДНФ. Как известно, в булевой алгебре минимальная ДНФ выбирается по минимальному числу букв, то есть по минимальному числу двухместных операций. В любой многозначной полной системе, для которой характерна каноническая форма типа СДИФ, целесообпазно пользоваться следующими критериями выбора минимальной

ДНФ:

1)минимальное число двухместных операций;

2)минимальное число функций J s (х);

3)минимальное число суперпозиций.

Можно привести примеры, когда минимальная ДНФ, выбираемая по первому или второму критерию, не является минимальной по третье­ му критерию. В то же время именно третий критерий наиболее соот­ ветствует практическим целям. Однако при kn > ЮО (если не фикси­

руется k , то kn будет более удобной характеристикой функции, чем просто га) число одноместных функций в общем случае пренебрежимо мало по сравнению с числом двухместных.

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

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

Рассмотрим пример. Требуется найти минимальную форму функ­ ции хх + х2 (mod 3), заданной в виде

хх + х2 (mod 3) = J0(хх) х2 V 1A (*i) А (*2) V V A (*1) A (*2) V A (•'t) A (-*2) V 1 A (xi) А (*г)«

63

Применяя к первому дизъюнктивному члену соотношение (2.45), восстановим СДНФ этой функции

x i х 2(mod3 ) = U 0 (хх) Ji (х2) V А (Xj) J2 (х2) V

V 1 A (^l) А С*а) V A Wl) A W2) V ^ i ( Xl) ^о(Х2) V lA C*i) A C^a)*

Из членов этой СДНФ составим все возможные выражения, удовле­ творяющие соотношениям (2.48) и (2.49),

и 0 (Х1) А (*а) V А (*i) А (•’‘-г) = 1 А (x i) А (-'-г) V V A Wi) А (^г) V A Wi) *2*

1 A Wi) А Аг) V A Ai) А (^а) = 1A Wi) А (^а) V V A Wi) А (*а) V V o (Л'г)-

Таким образом, импликантами функции х2 + х2 (mod3) помимо членов ее СДНФ будут также элементарные произведения J0 (хг) х2 и х Д 0 (х2). Выполнив все возможные операции поглощения согласно приве­ денным в § 2.7 условиям, получим сокращенную ДНФ этой функции

хх + х2 (mod 3) = J0 (Xj) х2 V V o W V A W A W V 1A W A W -

Как и ранее, обозначим каждую импликанту буквой J, а каждый член совершенной ДНФ,— буквой К. Индексы при J и К указывают их порядковые номера в сокращенной и совершенной ДНФ. Построив для функции xl + х2 (mod 3) импликантную матрицу (табл. 16), убе­ димся, что ее минимальная ДНФ совпадает с сокращенной ДНФ.

Таблица 16

Нетрудно проверить, что найденная минимальная форма функции

xi+ х 2 (mod 3) минимальна по всем приведенным ранее критериям. Описанная методика связана с громоздкими вычислениями при

большом числе элементарных произведений. Рассмотрим другой более наглядный метод, аналогичный методу Карно.

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

с односимвольных (констант, переменных х{, функций J s. (х(-)), дву­

64