8.6. Минимизация неполностью определенных логических функций с помощью карты Карно
Среди устройств дискретного действия встречаются схемы, закон функционирования которых определен не полностью. В таких схемах некоторые комбинации сигналов на входы никогда не подаются. Эти комбинации называются запрещенными.
Логическая функция
называется неполностью определенной,
если ее значения определены лишь на
наборах аргументов.
На тех наборах, на которых функция не определена, ее можно доопределить произвольно таким образом, чтобы соответствующая функции схема была наиболее простой, то есть так, чтобы МДНФ доопределенной функции содержала наименьшее число букв.
На карте Карно недоопределенное условие обозначается прочерком в соответствующей ячейке. Любую из таких ячеек можно включать как в группу единичных, так и в группу нулевых ячеек.
Пример. Функция задана таблицей
-
x
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
y
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
z
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
t
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
f
1
–
0
–
1
1
0
0
0
0
0
0
0
–
–
1
8.7. Минимизация неполностью определенных логических функций без использования карты Карно
Общий метод доопределения логических функций, обеспечивающий минимальное представление в классе дизъюнктивных форм, состоит в следующем.
Неполностью
определенную функцию
приравнивают единице на всех тех наборах,
на которых она не определена. Полученную
таким путем функцию обозначим
и найдем все ее простые импликанты.
Затем приравняем функцию
нулю на всех тех наборах, на которых она
не определена. Полученную таким образом
функцию обозначим
.
Для нахождения МДНФ исходной функции
составим импликантную матрицу, в столбцах
которой будут располагаться конституенты
функции
,
а в строках – простые импликанты функции
.
Пример. Функция задана таблицей
x |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
z |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
t |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
f |
1 |
– |
– |
– |
0 |
1 |
0 |
0 |
1 |
0 |
– |
– |
1 |
– |
– |
1 |
=
0000 + 0001 + 0010 + 0011 + 0101 + 1000 + 1010 +
+ 1011 + 1100 + 1101 + 1110 + 1111
0 группа: 0000 *
1: 0001 * 0010 * 1000 *
2: 0011 * 0101 * 1010 * 1100 *
3: 1011 * 1101 * 1110 *
4: 1111 *
0 группа: 000- * 00-0 * -000 *
1: 00-1 * 001- * 0-01 -010 * 10-0 * 1-00 *
2: -011 * 101- * -101 110- * 1-10 * 11-0 *
3: 1-11 * 11-1 * 111- *
0 группа: 00-- 00-- -0-0 -0-0
1: -01- -01- 1--0 1--0 0-01
2: 1-1- 11-- 1-1- 11-- -101
|
|
||||
0000 |
0101 |
1000 |
1100 |
1111 |
|
00-- |
|
|
|
|
|
-0-0 |
|
|
|
|
|
-01- |
|
|
|
|
|
1--0 |
|
|
|
|
|
0-01 |
|
|
|
|
|
1-1- |
|
|
|
|
|
11-- |
|
|
|
|
|
-101 |
|
|
|
|
|
=
-0-0 + 11-- + 0-01 =
