Метод Квайна и импликантные матрицы

 

Метод получения сокращенной дизъюнктивной нормальной формы логической функции называется методом Квайна.

При минимизации по методу Квайна в базисе 1 предполагается, что исходная функция задана в СНДФ.

Напомним, что импликанта функции - это некоторая логическая функция, обращаемая в ноль при наборе переменных, на которых сама функция также равна нулю.

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

Первичная или простая импликанта функции - это импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой данной функции.

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

Задача минимизации по методу Квайна состоит в попарном сравнении всех импликант, входящих в СНДФ, с целью выявления возможности поглощения какой-то переменной:

Fxi Fxi= F

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

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

В этом методе используются операции неполного склеивания (полным склеиванием, как нам известно, будет:xy xy = x) и поглощения (x xy = x). Применяемая в методе Квайна операция неполного склеивания определяется формулой: xy xy = x xy xy. Заметим, что в правой части равенства, кроме члена ч, полученного в результате полного склеивания, остаются оба члена, участвующие в склеивании.

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

Метод Квайна выполняется в несколько этапов и сокращенную НДФ удобно находить в следующей последовательности.

Провести в СНДФ функции все возможные операции склеивания конституент единицы. В результате этого образуются произведения, содержащие (n - 1) букв. Подчеркнем, что склеиваться могут только произведения с одинаковым числом букв. Поэтому после этой процедуры производится операция поглощения, а затем выполняются все возможные склеивания членов с (n - 1) буквой.

После этого проводится поглощение членов с (n - 1) буквой и вновь выполняется операция склеивания членов с числом букв, равным (n - 2), и т.д.

Пример. Найти сокращенную дизъюнктивную нормальную форму логической функции, заданной таблично.

 

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

f(x, y, z) 0 0 0 1 1 1 0 0

 

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

f(x, y, z) =xyz xyz xyz.

В правой части полученного выражения можно выполнить только одно склеивание: второго члена с третьим по переменной z. При этом получим

f(x, y, z) = xy xyz xyz xyz.

Произведение xy поглощает члены xyz b xyz:

f(x, y, z) = xy xyz.

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

Теперь рассмотрим процедуру минимизации более сложной функции с использованием импликативных матриц.

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

f(A, B, C, D) =ABCD ABCD ABCD ABCD ABCD ABCD

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

Для нахождения простых импликант мы должны провести вначале процедуру неполного склеивания. Чтобы быстрее находить члены, которые склеиваются друг с другом, напомним, что склеиваться могут только соседние члены, т.е. такие члены, у которых число переменных с отрицаниями отличается на единицу. Проведем операции склеивания в следующем порядке:

- выполним все возможные склеивания 1-го члена с остальными;

- выполним все возможные склеивания 2-го члена с остальными, кроме 1-го;

- выполним все возможные склеивания 3-го члена с остальными, кроме 1-го и 2-го и т.д.

Запишем результат:

1* - 2* =ABCD ABCD = ACD(BB) =ACD (по B);

2 - 3* =BCD (по A);

3 - 4* = ABD (по C);

4 - 5* = ABC (по D);

5 - 6* = BCD (по A).

Получили простые импликанты. После процедуры неполного склеивания выражение примет следующий вид:

f(A, B, C, D) =ABCD* +ACD +ABCD* +BCD + ABCD* + ABD + ABCD* +ABC + ABCD* +BCD +ABCD*

Звездочками отмечены те члены, которые поглощаются произведениями, образовавшимися после склеивания. Теперь проведем операцию поглощения. Для каждой импликанты найдем конституенты единицы, т.е. минтермы, которые ею поглощаются, т.е. те конституенты, собственной частью которых является данная импликанта. Например, импликанта ACD поглощает конституенты ABCD, ABCD, импликанта BCD - конституенты ABCD, ABCD и т.д.

ABCD* +ACD = ACD(1 + B) =ACD;

ABCD* + ABCD* +BCD = BCD(1 + A +A) =BCD;

ABCD* +ABC = ABC(1 + D) =ABC;

ABCD* +ABCD* +BCD = BCD(1 + A +A) = BCD;

Теперь рассмотрим принцип построения и использования импликантной матрицы на примере матрицы, приведенной в Таблице 8.2.

Клетки импликантной матрицы, образованные пересечением строк с импликантами и колонок с поглощенными ими конституентами, отметим крестиками.

Т а б л и ц а 8.2. Импликантная матрица

 

Конституенты единицы

№ п/п\ Простые импликанты ABCD ABCD ABCD ABCD ABCD ABCD

1 2 3 4 5 6

1 ACD X X

2 BCD X X

3 ABD X X

4 ABC X X

5 BCD X X

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

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

Кроме того, импликанта ACD накрывает вторую, а импликантаBCD - пятую колонки. Поэтому остается накрыть только третью и четвертую колонки таблицы. Для этого можно выбрать пары импликант BCD и ABD; ABD и ABC или одну импликанту ABD. Если выбрать указанные выше пары импликант, члены BCD и ABC оказываются лишними, так как импликанта ABD одна накрывает третью и четвертую колонки таблицы. Таким образом, выбрав импликанту ABD, получим минимальную НДФ заданной функции:

f(A, B, C, D) =ACDABDBCD.

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

1. Логическую функцию представляют в совершенной НДФ, применяя либо запись "по единицам" функции, если функция задана таблично, либо применяя операции развертывания, правила де Морганаи и другие формулы алгебры логики, если функция задана в произвольной аналитической форме.

2. В полученной совершенной НДФ проводят все операции неполного склеивания и поглощения. В результате получается сокращенная НДФ заданной функции.

3. Находят минимальные НДФ по импликантной матрице. Если количество членов в сокращенной НДФ невелико, то можно найти тупиковые формы методом испытания членов и выбрать среди них минимальные.

Заметим, что в ряде случаев минимальная НДФ совпадает с сокращенной. Например, сокращенная НДФ любой логической функции двух аргументов совпадает с минимальной, в чем нетрудно убедиться, проведя испытание членов в сокращенной НДФ любой функции, приведенной в Таблице 7.2.

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

Один из алгоритмов получения МНКФ функции практически аналогичен описанному. В этом случае также вначале тем или иным способом формируется СНКФ функции. Далее находится сокращенная НКФ, по которой определяются тупиковые НКФ. Наконец, по ним находится МНКФ заданной функции. Только очевидно, что если функция задана таблично, то СНКФ формируется "по нулям" функции. Во всех же дальнейших процедурах минимизации учитывается, что в этом случае используются макстермы, т.е. элементарные суммы, а не элементарные призведения. Импликанта, в том числе и простая, - также элементарная сумма.

Операция неполного склеивания и поглощения для конъюнктивной формы определяется соответственно следующими соотношениями:

 

(x + y)(x +y) = x(x + y)(x +y),

x(x + y) = x,

 

а формулы развертывания имеют вид:

x = (x + y)(x +y),

(x + y) = (x + y + z)(x + y +z).

 

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

Но можно использовать и другой способ получения МНКФ. Предварительно находится МНДФ функции. Потом от полученной МНДФ берется отрицание и после преобразования по формулам де Моргана получают МНКФ заданной функции.

 

8.3. Метод Карно (диаграммы Вейча)

 

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

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

Напомним, что каждая строка таблицы истинности, для которой функция равна единице, соответствует конкретному минтерму функции, представленной в СНДФ. Строка, для которой функция равна нулю является определенным макстермом функции, представленной в СНКФ.

Карта Карно представляет собой прямоугольник, разбитый на квадраты, число которых равно общему числу наборов для данной функции n переменных, т.е. оно равно 2n. Так, для функции четырех переменных квадратов будет 16, для пяти переменных - 32 и т.д. Каждый квадрат соответствует определенному набору или терму, причем наборы располагаются так, чтобы соседние наборы или термы, как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одном квадрате она с инверсией, а в другом, соседнем - без. Функцию в СНДФ наносят на карту, отмечая, например, знаком 1 квадраты, соответствующие тем наборам, на которых функция равна единице, т.е. в СНДФ функции есть соответствующий минтерм. Остальные квадраты отмечаются знаком 0. Иногда в углу квадрата ставят номер набора. Такой способ используется, если функция задана числовым образом, но он неудо-бен для процедуры минимизации.

Рассмотрим примеры построения карт Карно по таблицам истинности для 2-х, 3-х и 4-х переменных.

1) Логическая функция двух переменных, где а) - таблица истинности; а б) - карта Карно.

 

x y f(x,y)

0 0 f(0,0)

0 1 f(0,1) y = 0 y = 1

1 0 f(1,0) x = 0 f(0,0) f(0,1)

1 1 f(1,1) x = 1 f(1,0) f(1,1)

а б

 

2) Логическая функция трех переменных.

 

x y z f(x,y,z)

0 0 0 f(0,0,0)

0 0 1 f(0,0,1)

0 1 0 f(0,1,0)

0 1 1 f(0,1,1)

1 0 0 f(1,0,0)

1 0 1 f(1,0,1) yz = 00 yz = 01 yz = 11 yz = 10

1 1 0 f(1,1,0) x = 0 f(0,0,0) f(0,0,1) f(0,1,1) f(0,1,0)

1 1 1 f(1,1,1) x = 1 f(1,0,0) f(1,0,1) f(1,1,1) f(1,1,0)

а б

 

3) Логическая функция четырех переменных.

 

w x y z f(w,x,y,z)

0 0 0 0 f(0,0,0,0)

0 0 0 1 f(0,0,0,1)

0 0 1 0 f(0,0,1,0)

0 0 1 1 f(0,0,1,1)

0 1 0 0 f(0,1,0,0)

0 1 0 1 f(0,1,0,1)

0 1 1 0 f(0,1,1,0)

0 1 1 1 f(0,1,1,1)

1 0 0 0 f(1,0,0,0)

1 0 0 1 f(1,0,0,1)

1 0 1 0 f(1,0,1,0)

1 0 1 1 f(1,0,1,1) yz = 00 yz = 01 yz = 11 yz = 10

1 1 0 0 f(1,1,0,0) wx = 00 f(0,0,0,0) f(0,0,0,1) f(0,0,1,1) f(0,0,1,0)

1 1 0 1 f(1,1,0,1,) wx = 01 f(0,1,0,0) f(0,1,0,1) f(0,1,1,1) f(0,1,1,0)

1 1 1 0 f(1,1,1,0) wx = 11 f(1,1,0,0) f(1,1,0,1) f(1,1,1,1) f(1,1,1,0)

1 1 1 1 f(1,1,1,1) wx = 10 f(1,0,0,0) f(1,0,0,1) f(1,0,1,1) f(1,0,1,0)

а б

 

Карту Карно для функции, например, четырех переменных A, B, C, D можно представить и таким образом:

 

AB

00 01 11 10

CD 01 @f@

 

Например, в клетке "а" записывается значение ЛФ на наборе 0101, т.е. на наборе FDCD\

В таком виде карту Карно для пяти аргументов A, B, C, D, E можно представить в следующем виде:

 

A=0 A=1

DE DE

00 01 11 10 10 11 01 00

BC 01 @f@

 

Например, в клетке "а" записывается значение ЛФ на наборе 00110, т.е. на наборе FDCDE\

Наконец, карта Карно для шести аргуменов A, B, C, D, E, F может выглядеть, например, следующим образом:

 

A=0 A=1

DE DE

00 01 11 10 10 11 11 00

F=0 BC 01

F=1 BC 11

01 @f@

00 01 11 10 10 11 01 00

DE DE

A=0 A=1

 

Например, в клетке "а" записывается значение ЛФ на наборе 001111, т.е. на наборе FDCDF\

Карту Карно для ЛФ, в частности пяти аргументов ABCDE, представляют и таким образом:

 

B B

E E E

A C

@f@ C

A @,@

C

D D D D D

 

Например, в клетке "а" записывается значение ЛФ на наборе ABCDE т.е. на наборе 11100, а в клетке "б" - на наборе ABCDE или 00111.

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

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

1) Исходная функция, подлежащая минимизации, должна быть представлена в НДФ. Затем ее надо представить в СНДФ. Или же составляется таблица истинности минимизируемой функции.

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

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

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

4) Каждой такой группе ставится в соответствие новый минтерм для изображения исходной функции в форме минимальной НДФ.

5) Изображение каждого нового минтерма формируется по следующему алгоритму:

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

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

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

Таким образом, карту Карно можно рассматривать как графическое представление совокупности всех (сушествующих и не существующих) минтермов функции в СНДФ данного числа логических переменных.

На основании закона дистрибутивности и теорем (F +A) = 1 и AA = 0= а также A + 0 = A и A0 = 0, два минтерма, находящиеся в соседних клетках, могут быть заменены одним новым минтермом, содержащим на одну переменную меньше. Если соседними являютя две пары минтермов, то такая группа из 4 минтермов может быть заменена новым минтермом, который содержит на две переменные меньше и т.д. В общем случае наличие единиц в 2n соседних клетках позволяет исключить n переменных.

При формировании на базе карты Карно новых минтермов для представления функции в минимальной НДФ, или же в минимальной НКФ, значения соответствующих переменных, равных 1, заменяются изображением переменных без отрицания, а при значениях равных 0 - с отрицанием.

Рассмотрим процесс минимизации на примере функции, заданной следующим логическим уравнением:

F(A,B,C,D) = BCD + ABD + BCD + ABC + ACD + BCD + ABC + ABC

Представим эту функцию в СДНФ:

F = BCD(A + A) + ABD(C + C) + BCD(A + A) + ABC(D + D) +ACD(B + B) +

+ BCD(A + A) + ABC(D + D) + ABC(D + D) = ABCD +ABCD + ABCD +

+ ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD.

 

Ниже изображена карта Карно, соответствующая рассматриваемой функции.

 

AB = 00 AB = 01 AB = 11 AB = 10

CD = 00 1 1 (ABC)

CD = 01 1 1 1 1

CD = 11 1 1 1 1 (D)

CD = 10 1

 

Минтермы функции образуют в карте четыре группы:

1) (ABC); 2) (ABC); 3) (D); 4) (ABC).

Следовательно

 

F = ABC + ABC + ABC + D = BC(A + A) + ABC + D = BC + ABC + D.

 

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

Хотя обычно карты Карно для функций 3-х и 4-х переменных изображаются на плоскости, но как отмечалось выше, с точки зрения формирования прямоугольных групп карту нужно считать трехмерной.

Для карт с тремя переменными карту следует рассматривать как цилиндр со склеенными правым и левым краями. Поскольку прямоугольные группы формируются на таком цилиндре, на плоском рисунке та или иная группа может оказаться разорванной. Например,

 

yz = 00 yz = 01 yz = 11 yz = 10

x = 0 1 1

x = 1

 

Минтерм, соответствующий этой группе получается xz.

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

 

yz yz

wx 00 01 11 10 wx 00 01 11 10

00 1 00 1 1

01 1 1 01

11 1 1 11

10 1 10 1 1

а) б)

Для варианта а): группа из 4-х ячеек соответствует минтерму xz, а группа из 2-х ячеек - минтерму xyz\

Для варианта б): ячейки в 4-х углах образуют одну группу, если поверхность считать тороидальной. Этой группе соответствует минтерм xz\

Рассмотрим ранее приведенный пример, но теперь представим карту в виде цилиндра. Тогда у нас получится три группы минтермов вместо четырех:

 

AB = 00 AB = 01 AB = 11 AB = 10

CD = 00 1 1

CD = 01 1 1 1 1

CD = 11 1 1 1 1 (D)

CD = 10 1

 

Минтермы функции образуют на карте три группы:

1) (BC) - минтерм, соответствующий группе из четырех верхних единиц;

2) (D); 3) (ABC).

Следовательно

F = BC + ABC + D.

 

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

Пример. Найти минимальные дизъюнктивные и конъюнктивные нормальные формы функции:

 

f(A, B, C) = ABC ABC ABC ABC ABC.

 

Карты Карно для данной функции выглядят следующим образом:

 

B B B B

A 1 1 1 0 A 1 1 1 0

A 0 0 1 1 A 0 0 1 1

C C C C C C

 

а) б)

 

Объединить единицы можно двумя вариантами (а и б). Этим вариантам соответствуют две минимальные дизъюнктивные формы:

 

f(A, B, C) = AB AC AB,

f(A, B, C) = AB BC AB.

 

Для получения минимальной конъюнктивной нормальной формы следует объединить нули логической функции. Две конституенты нуля, соответст-вующие клеткам, обведенным пунктирной линией (а), склеиваются по пере-менной С и представляются импликантой A B, а оставшийся ноль - конституентойABC. Поэтому минимальная НКФ заданной функции будет

 

f(A, B, C) = (A B) (A B C).

 

Заметим, что минимальная НКФ функции содержит меньше букв, чем минимальные НДФ.

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

При наличии уже сформированной минимальной НДФ функции минимальную НКФ можно также, в частности, найти следующим образом:

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

если МНДФ функции равна

 

f(A, B, C) =AB + AC,

 

то проведя отрицание и применив теорему де Моргана, получим МНКФ:

 

f(A, B, C) =AB + AC = (A +B)(A + C).

 

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

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

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

 

 

Глава 9.