Информатика и вычислительная техника


Преобразование и минимизация логических выражений - часть 4


Значение функции трех аргументов

x1 x2 x3 F(x1, x2, x3) x1 x2 x3 F(x1, x2, x3)
0 0 0 0 1 0 0 1
0 0 1 0 1 0 1 1
0 1 0 0 1 1 0 0
0 1 1 1 1 1 1 1

На рис. 5.6 приведена карта Карно, соответствующая этой функции.

Рис. 5.6. Карты Карно для функции трех аргументов

В правом крайнем столбце этой карты соседним единицам соответствуют конъюнкции х1 & х2 & х3 и х1 & x2 & х3 которые заменяются одной конъюнкцией на ранг меньше с одинаковыми показателями инверсии переменных, т.е. х1 & х2. Две оставшиеся единицы находятся в соседних клетках второй строки, поэтому соответствующие им конъюнкции х1 & х2 & х3 и х1 & х2 & x3. заменяются одной х2 & x3 В результате минимизированная ДСНФ исходной функции примет вид:

F(x1, х2, х3) = х1 & х2 ? х2 & х3,

116

который значительно проще первоначальной ДСНФ, имеющий в соответствии с табл. 5.4 вид:

F(x1, x2, x3) = x1 & x2 & x3 ? x1 & x2 & x3 ? x1 & x2 & x3 ? x1 & x2 & x3.

Рассмотрим теперь пример минимизации функции четырех аргументов, ДСНФ которой задана в виде:

F(x1, x2, x3, x4) = x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4 ? x1 & x2 & x3 & x4.

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

Рис. 5.7. Карты Карно для функции четырех аргументов

В результате получим:

F(x1, x2, x3, x4) = x1 & x2 ? x2 & x3 & x4 ? x1 & x2 & x3 & x4.

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

117

113 :: 114 :: 115 :: 116 :: 117 :: Содержание




Начало  Назад  Вперед