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

Набор одноместных операций J s (х), х1, (х)‘ и двухместных J (х\,

х2), J ((лу)', х2) назовем набором D, а указанные операции — символа­ ми из набора D. Конечное число символов из набора D, объединенных знаками конъюнкции, назовем произведением.

Элементарным произведением называется произведение конечного числа попарно различных символов из набора D и константы, причем: 1) среди всех членов произведения может встречаться только один какой-нибудь символ одноместной операции над данным аргументом

из набора D; 2) если в произведении есть символ J ((ху/, х2) либо сим­

вол J ((лу/, х2), то среди символов операций над аргументами хх и х2 в элементарном произведении может быть лишь один из 4-х символов:

х\, (хiY, где / = 1,2.

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

Нетрудно проверить справедливость следующих тождественных соотношений:

(k— l)J 0(x )\/(k — 2)J1(x)V ••• У \Jk- 2 {x) = ~x,

Js (х) ~ Js+i (х ).

J s (x) = J 7 (х).

В рассматриваемой системе помимо операций склеивания по опе­ раторам и аргументам, согласно соотношениям (2.48) и (2.49), справе­ дливы также операции склеивания, согласно следующим соотношениям

1201:

Это утверждение очевидно, ибо любая простая импликанта как эле­ ментарное произведение может включать в себя в качестве сомножите­ лей лишь символы из набора D, получение которых обеспечивается приведенными соотношениями. Однако при больших k и п выбор ми­ нимальной ДНФ затруднителен, так как необходимо перебрать боль­ шое количество простых импликант.

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

а в Р 2 входит функция Js (х), где s + / > С2 в первом случае и h —

— s — 1 >• С2 — во втором;

Таким образом, использование избыточной базисной системы приводит к усложнению алгоритма минимизации и к возрастанию пе­ ребора при выборе минимальной ДНФ в связи с увеличением количе­

71

ства простых импликант. Между тем, при построении соотношений (2.51)—(2.55) учитывались далеко не все возможные суперпозиции даже среди одноместных функций [20]. Поэтому для некоторого упро­ щения алгоритма минимизации введены ограничения в определение элементарного произведения. Дополнительные трудности возникают также из-за необходимости сравнения сложности реализации простых импликант и элементарных произведений, которые ими накрываются.

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

§ 2.10. Минимизация многозначных функций в системе со всеми одноместными операциями

Рассмотрим избыточную базисную систему, в которую включены все й-значные функции одного переменного и для которой характерно каноническое представление типа СДНФ (§ 2.6). В этом случае соот­ ношение склеивания для любой одноместной функции получают из ее

СДНФ [21 ]. Например, СДНФ функции х — k — 1 — х (mod k) имеет вид

X = V {k— \ — i) Ji (х),

( = 0

а соотношение склеивания для той же функции

Р V (& — 1— i)Ji(x) = Рх.

i = 0

В рассматриваемой системе таких соотношений будет kk, и любое из них можно легко использовать. Алгоритм отыскания простых им­

вует следующий простой пример.

Пусть есть заданная таблицей истинности £-значная функция, зависящая от двух аргументов. Выполняя операции склеивания над произведениями, соответствующими всем местам любого столбца (или строки) таблицы, получим одну простую импликанту.

Если же в систему функций (например Россера — Тьюкетта) вклю­ чить только одноместные функции х‘ = х + i (mod As), t = 1, 2, ...

..., k — 1,' о в результате такой же операции (если столбец или строка не содержат 0) получается k + 1 простая импликанта [20]. Очевидно^

72

что перебор при выборе минимальной ДНФ данной функции в первом случае значительно меньше.

Выбрать нужное из kk соотношений склеивания легко, сгруп­ пировав склеиваемые произведения. Например, пусть для функции, заданной табл. 18, выполняется операция склеивания над произведе­ ниями, соответствующими строке с лу = 2,

3J2 (Хх) J0 (Х2) V 2</2 (-^l) J l (X2) V 1*^2 (Xl) (-^2) V 2«/jj (xy) J3 (x2).

Вынеся функции J2 (xx) за скобки, внутри скобок получаем СДНФ

какой-то одноместной функции, то есть одно из kk соотношений склеи­ вания. В данном случае

V ' рш)*= pr.

1=0

Для произвольной одноместной функции соотношение склеивания

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

к- 1 (xi) ?/?—I —i

V р

где Р, R £ М к, а М к — множество всех подмножеств множества Е'к.

§ 2.11. Минимизация многозначных функций в других полных системах

Минимизация многозначных функций во многих других полных системах операций основывается на использовании соотношений, подобных соотношениям склеивания (2.48), (2.49) и поглощения (2.50).

73