Импликантная матрица

 

Простые импли-канты Конституенты единицы  
X X                
    X X            
        X X        
            X X    
                X X

 

 

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

 

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

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

Кроме того, имлликанта накрывает вторую, а импликанта — пятую колонки. Поэтому остается накрыть только третью и четвертую колонки. Для этого можно выбрать пары импликант: и ; и или одну импликанту . Если выбрать указанные выше пары импликант, то импликанты и оказываются лишними, так как импликанта одна накрывает третью и четвертую колонки таблицы. Таким образом, выбрав импликанту , получим ми­нимальную дизъюнк­тивную нормальную форму задан­ной функции.

 

,

 

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

 

,

 

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

 

Пример. Найти минимальные формы переключатель­ной функции

 

. (2.3.1)

 

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

 

(2.3.2)

 

. (2.3.3)

 

 

Составим импликаитную матрицу (табл. 2.3.2), выпи­сав из выражения (2.3.1) все конституенты единицы, а из выражения (2.3.3) - все простые импликанты. При заполнении импликантной матрицы удобно пользоваться формой записи (2.3.2): следует поставить крестики в тех колонках, номера которых совпадают с числами, стоящими в левой части формы (2.3.2).

 

Таблица 2.3.2

Импликантная матрица

 

Простые импли-канты Конституенты единицы  
X X                
X     X            
    X           X  
        X   X      
            X   X  
        X X

 

Для импликанты крестиками отмечаются первая и вторая колон­ки; для — первая и третья и т. д. Заметим, что каж­дая колонка табл. 2.3.2 отмечена двумя крестиками. По­этому из выражения (2.3.3) можно исключить любую импликанту. Минимальное количество импликант, накрывающих крестиками все колонки, равно трем:

накрывает первую и вторую колонки,

накрывает третью и четвертую колонки,

накрывает пятую и шестую колонки.

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

 

.

 

Можно накрыть все колонки табл. 3.9 и другими импликантами:

накрывает первую и третью колонки,

накрывает вторую и шестую колонки,

накрывает четвертую и пятую колонки.

Таким образом, данная функция имеет вторую минимальную форму

 

.

 

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

 

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

 

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

 

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

 

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

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

 

 

2.4. Метод испытания импликант

 

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

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

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

Это связано с тем, что дизъюнктивная форма обращается в нуль только в том случае, когда все ее логические слагаемые равны нулю. Однако, при исключении импликанты может оказаться, что на тех наборах, на которых исключенная импликанта равнялась единице (а следовательно, вместе с ней и вся дизъюнкция равнялась единице ввиду соотношения 1Úх1=1), оставшееся выражение не будет равно единице. Если же проверкой установить, что при исключении импликанты полученное выражение равно единице на этих наборах, то можно утверждать, что все нули и все единицы обоих выражений совпадают и, следовательно, исключенная импликанта является лишней.

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

Применение этого правила связано с некоторыми особенностями, которые можно рассмотреть на примерах.

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

 

.

 

1. Испытываем импликанту . Подставляем в значения х1 = 0 и х2 = 0, т.к. при этом = :

 

Следовательно, импликанту исключать нельзя, т.к. оставшееся выражение не равно тождественно единице.

2. Импликанту х1х3 исключать также нельзя, т.к. при х1= 1 и х3 = 1

 

 

3. Для импликанты :

 

 

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

 

Пример 2. Упростить переключательную функцию.

 

.

 

На основе теоремы Квайна получим

1¸2 ®

2¸3 ®

3¸4 ®

4¸5 ®

5¸6 ®

 

Тогда сокращенная ДНФ имеет вид

 

(2.4.1)

 

Найдем тупиковые формы.

1. Для : х1 = 0, х3 = 1, х4 = 1:

 

 

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

2. Для : х2 = 0, х3 = 1, х4 = 1.

 

 

т.е. импликанта является лишней.

3. Проверяем третью импликанту ; при этом вторую импликанту, которая оказалась лишней, вновь возвращаем в исследуемое выражение. Тогда, подставляя в выражение

 

ÚÚÚ

 

значения х1 = 1, х2 = 0, х4 = 1, получим

 

.

 

Следовательно, импликанта также лишняя и может быть исключена.

4. Аналогично можно показать, что и импликанту также может быть исключена.

Таким образом выражение (2.4.1) имеет три лишние импликанты и .

Однако исключать одновременно все лишние импликанты нельзя без дополнительной проверки. Вначале следует исключить одну импликанту полученного выражения. Исключим из выражения (24.1. импликанту , получим

 

Вновь проверяем наличие лишних импликант, проверяя только те, которые были лишними при первой проверке, т.е. импликанты и .

Подставляя в выражение

 

ÚÚ

 

значения х1 = 1, х2 = 0, х4 = 1 получаем

 

 

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

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

 

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

 

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

 

x2 х1 x2 x2 x2 x2 x2 x2
1     х1 х1 1,1 1,0 х1 х1 х1x2 х1x2 х1 х1 х1Úx2 х1Úx2
    0,1 0,0 х1x2 х1x2 х1Úx2 х1Úx2

 

(а) (б) (в) (г)

 

Рис. 2.5.1. Диаграмма Вейча для функции двух переменных.

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

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

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

 

x2 x2 x2 x2 x2 x2 x2 x2  
х1 х1 х1 х1 х1 х1 х1 х1

 

f2(х1; x2) = x1 f5(х1; x2) = x2 f12 = х1 f10 = х2

 

Это обстоятельство используют для получения минимальных ДНФ и КНФ.

Рассмотрим диаграммы Вейча переключательной функции f13(х1; x2) =

= х1® x2.

 

x2 x2 x2 x2   Пара единиц во второй строке соответствует х1, а пара единиц в  
х1 х1 х1 х1 х1x2   первой колонке – x2. f13(х1; x2) = х1Ú x2.
х1x2 х1x2

 

Это выражение, являющееся минимальной формой функции f13(x1;x2) получено путем склеивания конституент единиц, обведенных овалами.

 

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

x2
x1 x1x2x3 x1x2 x3 x1x2 x3 x1x2 x3
x1x2 x3 x1x2 x3 x1x2 x3 x1x2 x3

x3

 

x2
x1 x1Úx2Ú x3 x1Úx2Ú x3 x1Úx2Ú x3 x1Úx2Ú x3
x1Úx2Ú x3 x1Úx2Ú x3 x1Úx2Ú x3 x1Úx2Ú x3

x3

 

x2  
x1

x3

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

 

x2 x2 x2  
x1 x1 x1

 

x3 x3 x3

x1 x2 x3 x3

 

x2 x2 x2
x1 x1 x1

 

x3 x3 x3

x1 x1

 

Четыре единицы, расположенные в соседних клетках, выражаются одной буквой.

x2 x2 x2
x1 x1 x1

 

x3 x3 x3

x3

 

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

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

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