ВУЗ:
Составители:
31
карты указаны значения входных переменных, которые для соответствующих строк и
столбцов остаются постоянными. Набор переменных для заданной клетки таблицы
определяется как совокупность аргументов, постоянных для строк и столбцов, на
пересечении которых она расположена.
1
x
1
x
0
x
(
)
01
, xxf
()
01
, xxf
0
x
(
)
01
, xxf
()
01
, xxf
Рис. 4.3. Карта Вейча функции двух переменных
Карта Вейча функции трех переменных приведена на рис. 4.4. Она содержит
восемь клеток. Наборы входных переменных, соответствующие крайним левому и
правому столбцам, являются соседними. Поэтому данную карту удобно представить
как поверхность цилиндра и она, в отличие от карты двух переменных, является
объемной фигурой.
1
x
1
x
1
x
1
x
0
x
()
012
,, xxxf
(
)
012
,, xxxf
()
012
,, xxxf
(
)
012
,, xxxf
0
x
()
012
,, xxxf
()
012
,, xxxf
()
012
,, xxxf
(
)
012
,, xxxf
2
x
2
x
2
x
2
x
Рис. 4.4. Карта Вейча функции трех переменных
Карта Вейча функции четырех переменных приведена рис. 4.5. Она содержит
16 клеток. Очевидно, что наборы входных переменных, соответствующие крайним
левому и правому столбцам, как и в карте для трех переменных, являются соседними.
Кроме этого соседние коды содержатся в нижней и верхней строках карты. Поэтому
данная карта тоже является объемной фигурой и может быть представлена как
поверхность тора.
1
x
1
x
1
x
1
x
0
x
(
)
0123
,,, xxxxf
(
)
0123
,,, xxxxf
()
0123
,,, xxxxf
(
)
0123
,,, xxxxf
2
x
0
x
()
0123
,,, xxxxf
(
)
0123
,,, xxxxf
()
0123
,,, xxxxf
(
)
0123
,,, xxxxf
2
x
0
x
(
)
0123
,,, xxxxf
(
)
0123
,,, xxxxf
()
0123
,,, xxxxf
(
)
0123
,,, xxxxf
2
x
0
x
()
0123
,,, xxxxf
(
)
0123
,,, xxxxf
()
0123
,,, xxxxf
(
)
0123
,,, xxxxf
2
x
3
x
3
x
3
x
3
x
Рис. 4.5. Карта Вейча функции четырех переменных
Еще более сложную форму имеет карта Вейча функции пяти переменных. Ее
можно представить как две карты Вейча функции четырех переменных,
расположенные одна над другой и отличающиеся лишь значением одной переменной.
32
Геометрически это можно представить как два тора, один из которых расположен в
другом. Соседним кодам тут дополнительно соответствуют клетки, расположенные
на разных торах одна под другой. Ввиду сложности работы с такими картами, данный
способ редко используется при минимизации ФАЛ пяти переменных.
4.2.1. Минимизация полностью определенной функции алгебры логики
При минимизации ФАЛ используют либо ее нулевые, либо единичные значения. В
обоих случаях получают равносильные выражения, которые, однако, могут
отличаться по числу членов
(т. е. цене) и выполняемым логическим операциям.
Алгоритм минимизации ФАЛ сводится к следующему.
1. На карте Вейча ФАЛ n-переменных выделяют прямоугольные области,
объединяющие выбранные значения функции (лог. 0 или лог. 1). Каждая область
должна содержать 2
k
клеток, где k – целое число. Выделенные области могут
пересекаться, т.е. одна или несколько клеток могут включаться в различные
области.
2. Каждой из выделенных областей соответствует
k-куб исходной ФАЛ, который
представляется самостоятельным логическим произведением переменных,
значения которых в рамках выделенной области остаются постоянными. Каждое
произведение содержит
n-k переменных и носит название импликанты.
3. Из полученного множества выбирают минимальное число максимально больших
областей, включающих все выбранные значения ФАЛ.
4. Логически суммируют импликанты, соответствующие выбранным областям.
Полученная сумма образует МДНФ, т.е. является покрытием ФАЛ минимальной
стоимости (покрытием Квайна).
При объединении клеток с единичными значениями ФАЛ получают МДНФ
самой функции, а при объединении клеток
с нулевыми значениями ФАЛ - МДНФ
функции, инверсной заданной. Последнее легко объясняется при помощи тождества
(2.4).
Очевидно, что если полностью определенная ФАЛ
n-переменных принимает
значение 1 на
m наборах переменных, то на остальных 2
n
-m входных наборах ее
значение равно нулю. Следовательно, объединение 0 значений согласно правилам
записи ДНФ приведет к получению функции, инверсной заданной.
Применяя к полученной инверсной минимальной форме теоремы Де-Моргана
(2.9), получаем минимальную функцию, записанную в виде КНФ.
Пример. 4.2. Минимизировать ФАЛ
012012012012
)( xxxxxxxxxxxxxz
+
+
+
=
.
Решение. 1. По заданной ФАЛ составим карту Вейча.
1
x
1
x
1
x
1
x
0
x 0 1 1 0
0
x 0 1 1 0
2
x
2
x
2
x
2
x
карты указаны значения входных переменных, которые для соответствующих строк и Геометрически это можно представить как два тора, один из которых расположен в
столбцов остаются постоянными. Набор переменных для заданной клетки таблицы другом. Соседним кодам тут дополнительно соответствуют клетки, расположенные
определяется как совокупность аргументов, постоянных для строк и столбцов, на на разных торах одна под другой. Ввиду сложности работы с такими картами, данный
пересечении которых она расположена. способ редко используется при минимизации ФАЛ пяти переменных.
x1 x1 4.2.1. Минимизация полностью определенной функции алгебры логики
При минимизации ФАЛ используют либо ее нулевые, либо единичные значения. В
x0 f (x1 , x0 ) f ( x1 , x0 ) обоих случаях получают равносильные выражения, которые, однако, могут
x0 f (x1 , x0 ) f ( x1 , x0 ) отличаться по числу членов (т. е. цене) и выполняемым логическим операциям.
Алгоритм минимизации ФАЛ сводится к следующему.
Рис. 4.3. Карта Вейча функции двух переменных 1. На карте Вейча ФАЛ n-переменных выделяют прямоугольные области,
Карта Вейча функции трех переменных приведена на рис. 4.4. Она содержит объединяющие выбранные значения функции (лог. 0 или лог. 1). Каждая область
восемь клеток. Наборы входных переменных, соответствующие крайним левому и должна содержать 2k клеток, где k – целое число. Выделенные области могут
правому столбцам, являются соседними. Поэтому данную карту удобно представить пересекаться, т.е. одна или несколько клеток могут включаться в различные
как поверхность цилиндра и она, в отличие от карты двух переменных, является области.
объемной фигурой. 2. Каждой из выделенных областей соответствует k-куб исходной ФАЛ, который
представляется самостоятельным логическим произведением переменных,
x1 x1 x1 x1 значения которых в рамках выделенной области остаются постоянными. Каждое
произведение содержит n-k переменных и носит название импликанты.
x0 f ( x2 , x1 , x0 ) f ( x2 , x1 , x0 ) f (x2 , x1 , x0 ) f ( x2 , x1 , x0 ) 3. Из полученного множества выбирают минимальное число максимально больших
x0 f ( x2 , x1 , x0 ) f ( x2 , x1 , x0 ) f (x2 , x1 , x0 ) f ( x2 , x1 , x0 ) областей, включающих все выбранные значения ФАЛ.
4. Логически суммируют импликанты, соответствующие выбранным областям.
x2 x2 x2 x2 Полученная сумма образует МДНФ, т.е. является покрытием ФАЛ минимальной
стоимости (покрытием Квайна).
Рис. 4.4. Карта Вейча функции трех переменных При объединении клеток с единичными значениями ФАЛ получают МДНФ
Карта Вейча функции четырех переменных приведена рис. 4.5. Она содержит самой функции, а при объединении клеток с нулевыми значениями ФАЛ - МДНФ
16 клеток. Очевидно, что наборы входных переменных, соответствующие крайним функции, инверсной заданной. Последнее легко объясняется при помощи тождества
левому и правому столбцам, как и в карте для трех переменных, являются соседними. (2.4).
Кроме этого соседние коды содержатся в нижней и верхней строках карты. Поэтому Очевидно, что если полностью определенная ФАЛ n-переменных принимает
данная карта тоже является объемной фигурой и может быть представлена как значение 1 на m наборах переменных, то на остальных 2n-m входных наборах ее
поверхность тора. значение равно нулю. Следовательно, объединение 0 значений согласно правилам
записи ДНФ приведет к получению функции, инверсной заданной.
x1 x1 x1 x1 Применяя к полученной инверсной минимальной форме теоремы Де-Моргана
(2.9), получаем минимальную функцию, записанную в виде КНФ.
x0 f (x3 , x2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) x2 Пример. 4.2. Минимизировать ФАЛ
z ( x) = x2 x1 x0 + x2 x1 x0 + x2 x1 x0 + x2 x1 x0 .
x0 f (x3 , x2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) x2
Решение. 1. По заданной ФАЛ составим карту Вейча.
x0 f (x3 , x2 , x1 , x0 ) f (x3 , x 2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) x2 x1 x1 x1 x1
x0 0 1 1 0
x0 f ( x3 , x2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) f ( x3 , x 2 , x1 , x0 ) f ( x3 , x2 , x1 , x0 ) x2
x0 0 1 1 0
x3 x3 x3 x3
x2 x2 x2 x2
Рис. 4.5. Карта Вейча функции четырех переменных
Еще более сложную форму имеет карта Вейча функции пяти переменных. Ее
можно представить как две карты Вейча функции четырех переменных,
расположенные одна над другой и отличающиеся лишь значением одной переменной.
31 32
Страницы
- « первая
- ‹ предыдущая
- …
- 14
- 15
- 16
- 17
- 18
- …
- следующая ›
- последняя »
