книги из ГПНТБ / Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие

§ 2. УПРОЩЕНИЕ НОРМАЛЬНЫХ ФОРМ БУЛЕВЫХ ФУНКЦИЙ

В настоящем параграфе рассматриваются примеры упрощения нормальных форм булевых функций с помощью следующих прие­ мов: 1 ) перегруппировка членов, 2 ) сложение соседних членов, 3) добавление членов.

Перегруппировка членов

Перегруппировка членов возможна всякий раз, когда эти члены входят в одно из трех основных выражений, которые приводятся ниже и для которых указаны эквивалентные им упрощенные вы­ ражения:

= (xy + xz) (xt -f z) = xyxt + xxzt + xyz + XZ2 =

f = ( x + yz) + xyz = z (y + yx) + X = zy + (zx 4 - x) =

= zy + (x + z) = (z + z y )i- x = z + x.

Сложение соседних членов

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

132

Пусть, например, дана функция

f — xyz + xyz + xyz 4 - xyz + xyz + xyz\

группируя попарно четвертый и пятый, второй и четвертый, чет­ вертый и шестой и, наконец, первый и третий члены, можно напи­ сать:

f = (xyz + xyz) + (xyz + xyz) -f {xyz + xyz) + {xyz + xyz) =

= xy {z + 2) + xy (2 + 2) + X2 {у + у) + xz {y + y) =

= xy- 1 + xy- 1 + X2- 1 -f-XZ- 1 = xyA~xy + xz+ xz.

Можно получить и другое выражение, содержащее только три члена, группируя в разложении данной функции второй и третий, первый и пятый и, наконец, четвертый и шестой члены:

f = {xyz + xyz) + {xyz + xyz) + {xyz + xyz) = xy{z + z) + yz {x -f x) +

-\-zx{y + y) —x y -l-\-y z -l-\-z x -l= x y + yz-\-zx.

Посредством другой группировки членов первоначальной функ­ ции можно было бы получить еще одно выражение, также состоя­ щее из трех членов:

f = xy + yz + zx.

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

Чтобы найти эти эквивалентные формы, удобно умножать каж­

дый из членов данной функции на выражение вида {А + Л), что позволяет выявить все члены ее совершенной нормальной формы, которые затем могут быть сгруппированы попарно всеми возмож­ ными способами.

Пусть, например, дана функция

f = xy 4 - xyz 4- xzt.

Чтобы выявить члены совершенной дизъюнктивной нормальной формы, каждый из которых содержит четыре переменных, напишем

f = xy{z 4-z) {t + 1) 4-xyz {t+~t) + xzt {у + y) =

= {xyzt + xyzt -f xyzt 4- xyzt) + {xyzt 4- xyzt 4- xyzt 4- xyzt).

Тогда СДНФ будет иметь вид:

f = xyzt + xyzt 4- xyzt 4 - xyzt 4- xyzt -f xyzt -f- xyzt.

Группируя члены, состоящие из четырех переменных, всеми возможными способами попарно, мы получим члены из трех пере-

менных:

xyz = xyzt + xyzt,

xyz —xyzt -f- xyzt,

xyt = xyzt -f- xyzt,

xyz = x y z t x y z t ,

xyt = xyzt + xyzt,

xzt = xyzt + xyzt,

yzt = xyzt + xyzt.

Тогда можно написать

/ = xyz + xyz + xyt + xyz + xyt + xzt + yzt —

= (xyz + xyz) + (xyt + xyt) -f- (xyt + xzt + yzt) =

= xy + xy + (xyz -f xzt + yzt) = xy + xyz + xzt + yzt.

Мы видим, что полученное выражение содержит три основных члена исходной функции, но появился еще четвертый член, который раньше отсутствовал.

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

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

xy + xyz, а последний, xyzt, может быть представлен либо третьим основным членом xzt первоначальной формы, либо новым основным членом yzt. Таким образом, хотя никакого упрощения функции и йе было получено, указанный метод позволил найти выражение, эквивалентное исходной функции. Этому новому выражению бу­ дет соответствовать иная цепь, которая может оказаться предпоч­ тительней, чем первая, если, например, переменную у основного члена yzt реализовать легче, чем переменную х основного члена xzt.

134

О п р е д е л е н и е . Дизъюнкция P i V P 2 V - - - V P a элемен­

тарных конъюнкций pj поглощает элементарную конъюнкцию ру, если формула p^PiVP2V---VPft выражает функцию, тож­

1.у р ;= 1 , t=i

2 . р ->р ; - р 2 . . . p; = i.

Здесь через р^ обозначены конъюнкции всех членов, общих для р. и р, а через p"t — конъюнкции оставшихся членов из рг

Пример 1. Пусть дана функция в дизюънктивной форме

F = Х гХ 2Х3 V *1*2*3 V Х]Х3Х4 V * 2 * 3 * 4 •

Представим данную функцию в виде дизъюнкции

PiVР2 VРз= *1*2*3 V*1*2*3V*1*3*4

и конъюнкции

р = *2Х3Х4.

Представим элементарные конъюнкции в р 4 V Р 2 V Рз в следующем виде:

p1 = p ;p i'= * 3 (*i*2)>

Р2 = P2P2= (Л'2Хз) ‘ *1’

Ръ ~ Р3Р2,= (*3*4) 'Х1‘

При этом

3 __

V Р"= *j*2V*!V*1~ 1,

1=1

Р[Р'2РЗ= Х2Х3Х4

136

F= хгх2х3V хгх2х3V ххх2х3.

§4. МЕТОДЫ МИНИМИЗАЦИИ СДНФ БУЛЕВОЙ ФУНКЦИИ

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

Конъюнкции ргс и р ' ранга г называются соседними, если су­ ществует такая переменная xk, что

P ir = P r~ Xxl и р ' = р г~ 1 - х 0к .

Конъюнкция р ранга г называется изолированной по отноше­ нию к данному множеству конъюнкций r-го ранга, если в нем не существует ни одной конъюнкции, соседней с р.

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

рг2, . . . рг Оставшиеся конъюнкции не являются изолированными.

Для каждой из них выберем соседние с ней конъюнкции, и к каждой паре соседних конъюнкций применим операцию склеивания:

Pt Vрги= Рг~ 'х?VРг~ 'х? = Рг~ 1•

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

Для полученной таким образом дизъюнктивной формы повто­ рим описанный процесс упрощения и получим множество изоли­ рованных конъюнкций ранга г—1 и дизъюнктивную форму, обра­ зуемую конъюнкциями ранга г—2 и т. д. Этот процесс завершится после s повторений. В результате получим упрощенную дизъюнк­ тивную нормальную форму функции в виде

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

137

Пример 2. Минимизировать булеву функцию f (хъ х 2, х 3), заданную следующей совершенной нормальной формой:

* 1 * 2 * 3 V * 1 * 2 * 3 V * 1 * 2 * 3 V * 1 * 2 * 3 -

Образуем три пары соседних конъюнкций

(* 1 * 2 * 3 > *1*2*з) >

(* 1 * 2 * 3 . * 1* 2* з ) ,

( X ^ X g , * х * 2* з ) .

Применяя к ним операции склеивания, получим конъюнкции

второго ранга: х хх 2, х хх 3, х 2х 3. Строим из них дизъюнктивную нор­ мальную форму

* 1 * 2 V * 1 * 3 V * 2 * 3 •

Применяя к ней критерий поглощения, получим тупиковую форму, являющуюся в данном случае минимальной:

* 1 * 2 V * 1 * 3 -

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

Пример 3. Минимизировать функцию А, заданную в конъюнк­ тивной нормальной форме

А= ( * l V * 2 V * 3 ) A ( * l V * 2 V * 3 ) -

Раскроем скобки и получим дизъюнктивную нормальную форму

А = *]*2 V * 1 * 3 V * 2 * 3 V * 2 * 3 V * 1 * 2 V * 1 * 3 •

Применим к ней критерий поглощения и получим минимальную дизъюнктивную форму

S ^ X ^ V * 2*3 V * 1* з -

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

Метод Куайна

При минимизации по методу Куайна исходной является СДНФ функции. Если функция задана одной из своих ДНФ, то с помощью развертывания (5.10) нетрудно перейти к СДНФ.

В соответствии с методом Куайна сначала производятся склеи­ вания каждой конституенты единицы со всеми соседними. Для того, чтобы какая-либо конституента единицы, как и любая элементар­

138

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

В результате этой процедуры, которую назовем «1-м шагом», получим формулу, дизъюнктивно объединяющую элементарные конъюнкции ранга п—1 и оставшиеся несклеенными, ввиду отсутст­ вия соседних, конституенты единицы. Когда ни одна из конституент единицы не имеет соседних, тогда СДНФ является минимальной' формой функции.

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

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

Пример 4. Рассмотрим минимизацию по Куайну СДНФ. Пусть

139

\