Минимизация булевых функций с использованием диаграмм Вейча

МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

ТАБЛИЧНЫМИ МЕТОДАМИ

 

Методические указания по методам минимизации булевых функций

для студентов специальности 22.01 (Вычислительные машины,

системы, комплексы и сети)

 

Автор Асеева Т.В.

 

Тверь 1996

 

 

Теоретические предпосылки табличных методов минимизации

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

 

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

- Kx Ú K`x = K,

- K₁x ÚK₂`x = K<sub>1</sub>x Ú K<sub>2</sub>`x Ú K₁K₂,

- K₁K₂ Ú K₂ = K₂,

где К₁, К₂, К₃ - элементарные конъюнкции произвольного ранга.

Наиболее известные методы “ручной” минимизации связаны с использованием таблиц различных видов. Для n-местной булевой функции такая таблица должна содержать 2ⁿ клеток, в каждую из которых записывается значение функции на том наборе значений переменных, номер которого совпадает с номером клетки. Нумерация клеток производится таким образом, чтобы сделать возможным склеивание клеток, расположенных симметрично относительно некоторых осей симметрии таблицы. Например, склеиваются любые две соседние по вертикали или по горизонтали клетки, так как присвоенные им двоичные номера различаются ровно в одном символе. В склеивании могут участвовать 2^k клеток, в которых k каких-либо переменных принимают все возможные наборы значений. Эти к переменных называются свободными переменными образованного в результате склеивания интервала, который содержит к свободных и n-k связанных переменных. Интервалу соответствует множество, содержащее 2^n-k вершин единичного n-мерного куба Вⁿ

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

 

Минимизация булевых функций с использованием диаграмм Вейча

 

X1

При небольшом числе переменных (n=2,3,4) для минимизации булевых функций используют диаграммы Вейча [i]. Принцип построения диаграммы и нумерации клеток ясны из рисунков, Рис. 1,3, 5.

или в двоичной записи:

 

Рис.1. Нумерация клеток диаграммы Вейча при n=2.

 

Из рис.1 видно, что, если код номера каждой клетки диаграммы обозначить парой (х₁,х₂), то переменная х₁ принимает значение 1 в клетках с номерами 2 и 3, а переменная х₂ - в клетках с номерами 1 и 3, что и показано на отмеченой диаграмме Вейча линиями со стрелками. В приведенной диаграмме могут склеиваться клетки с номерами 0 и 1, а также клетки с номерами 2 и 3 по переменной х₂, а клетки с номерами 1 и 3, а также 0 и 2 по переменной х₁. Например, для функции двух переменных, заданной таблицей 1, диаграмма Вейча с указанием клеток, в которых связанная переменная принимает значение 1, и с обозначением склеиваемых клеток и соответствующих им интервалов приведена на рис.2.

 

 

x1	x2	f(x1,x2)

Таблица 1

1         x2

x1

 

 

Рис. 2. Пример минимизации булевой функции, заданной Табл.1.

f(x₁,x₂)=`x<sub>1</sub> Ú`x₂.

 

 

 

 

Интервалу (0-) соответствует элементарная конъюнкция `х<sub>1</sub>, являющаяся простым импликантом данной функции, а интервалу (-0) - также простой импликант данной функции `х₂.Таким образом минимальная дизъюнктивная нормальная форма данной функции имеет вид: f(x)=`x<sub>1</sub> Ú`x₂, так как связанная переменная интервала входит в соответствующий ему импликант с отрицанием, если ее значение в интервале равно 0, и без отрицания в противном случае.

X1

Для функции трех переменных диаграмма Вейча содержит 2³ =8 клеток. Нумерация клеток приведена на рис.3a,b с указанием групп по 2^n-1 клеток, в которых каждая из переменных принимает значение 1, n - число переменных функции, равное 3.

Рис.3,а. Десятичная нумерация клеток диаграммы Вейча при n=3.

X2 110

X3

 

Рис. 3.b. Двоичная нумерация клеток

отмеченной диаграммы Вейча при n=3.

 

Определим максимальные интервалы и соответствующую МДНФ для функции трех переменных, заданной вектором a_f=(0111 1011).Изображение этой функции на диаграмме Вейча показано на рис.4 в предположении, что нумерация переменных в последовательности, задающей номер клетки, производится слева направо.

Из рис.4 видно, что множество единиц данной функции покрывается тремя максимальными интервалами, которым соответсвует МДНФ = x₂ Ú x₁`x<sub>3</sub> Ú`x₁x₃.

 

 

х2 1
1

Х3

 

 

Рис.4. Пример минимизации трехместной булевой функции. Результат минимизации:

f (x₁,x₂,x₃)=x₁`x<sub>2</sub> Ú x<sub>2</sub> Ú`x₁x₃.

 

Для четырехместной булевой функции таблица содержит 2⁴=16 строк. Соответственно, диаграмма Вейча такой функции содержит 16 клеток, расположение которых показано на Рис.5.

 

 

Х2 Õ1 1100
Õ3 1110

Õ4

 

Рис.5. Нумерация клеток диаграммы Вейча и отмеченная диаграмма при n=4.

 

Примеры минимизации 4-х местных булевых функций приведены на рис. 6,7,8.

f (x⁴)=`x<sub>4</sub> f (x<sup>4</sup>)=`x₃`x₄ Ú x₃x₄

Рис.6. Определение МДНФ Рис.7. Определение МДНФ для функции

для функции, заданной вектором заданной вектором a(f)=(1001 1001 1001 1001).

a(f)=(1010 1010 1010 1010).

 

Для четырехместной функции диаграмма Вейча имеет 2⁴=16 клеток. Нумерация клеток и отмеченная диаграмма приведены на рис.5.

 

Рис.8. Определение МДНФ для функции, заданной вектором a(f)=(1101 110111001101).

 

При дальнейшем увеличении местности булевых функций их минимизация с использованием диаграмм Вейча становится затруднительной из-за громоздкости таблицы и уменьшения наглядности ее отметки. Поэтому при n>4 целесообразно использование метода симметричных таблиц.