Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf

§ 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