41. Минимизация логических выражений методом Куайна (Квайна).
Если лог-ая ф-ия имеет 4 и более перем-х то минимизация с помощью склеивания оказывается недостаточной(появляются лишние импликанты, которые можно исключить из окончательного результата минимизации с помощью склеивания).
Пусть дана функция 4-х переем-х, которая имеет единичное значение на следующих наборах:
ƒ(2,5,6,7,10,12,13,14)=1
Таблица истинности:
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
2 |
1 |
1 |
0 |
0 |
0 |
3 |
0 |
0 |
1 |
0 |
0 |
4 |
1 |
0 |
1 |
0 |
1 |
5 |
0 |
1 |
1 |
0 |
1 |
6 |
1 |
1 |
1 |
0 |
1 |
7 |
0 |
0 |
0 |
1 |
0 |
8 |
1 |
0 |
0 |
1 |
0 |
9 |
0 |
1 |
0 |
1 |
1 |
10 |
1 |
1 |
0 |
1 |
0 |
11 |
0 |
0 |
1 |
1 |
1 |
12 |
1 |
0 |
1 |
1 |
1 |
13 |
0 |
1 |
1 |
1 |
1 |
14 |
1 |
1 |
1 |
1 |
0 |
15 |
=(
/\
/\
)\/(
/\
/\
)\/
(
/\
/\
)\/
(
/\
/\
)\/(
/\
/\
)\/(
/\
/\
)\/
(
/\
/\
)\/
(
/\
/\
)\/
(
/\
/\
)=
( /\ )\/( /\ )\/( /\ /\ )\/( /\ /\ )\/ ( /\ /\ )\/ ( /\ /\ )\/ ( /\ /\ )=
( /\ )\/ ( /\ /\ )\/ ( /\ /\ )\/ ( /\ /\ )\/ ( /\ /\ )\/ ( /\ /\ ).
Метод Куайна: необходимо выбрать минимум строк, кот-е перекрывают все столбцы.
|
0010 |
0101 |
0110 |
0111 |
1010 |
1100 |
1101 |
1110 |
~ ~ 1 0 |
1 |
|
1 |
|
1 |
|
|
1 |
0 1 ~ 1 |
|
1 |
|
1 |
|
|
|
|
~ 1 0 1 |
|
1 |
|
|
|
|
1 |
|
0 1 1 ~ |
|
|
1 |
1 |
|
|
|
|
1 1 0 ~ |
|
|
|
|
|
1 |
1 |
|
1 1 ~ 0 |
|
|
|
|
|
1 |
|
1 |
=( /\ )\/ ( /\ /\ )\/ ( /\ /\ ).
Проверка:
(
/\
)
\/
(
/\
/\
)
\/
=
.
Проверка верна!
( /\ /\ )