Дискретная математика
.pdf
|
|
|
(0000) |
(0001) |
(0011) |
(0111) |
(1000) |
(1100) |
(1101) |
(1110) |
(1111) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
K1 (000-) |
|
1 |
1 |
|
|
|
|
|
|
|
|
K2 (-000) |
|
1 |
|
|
|
1 |
|
|
|
|
|
K3 |
(00-1) |
|
|
1 |
1 |
|
|
|
|
|
|
K4 |
(1-00) |
|
|
|
|
|
1 |
1 |
|
|
|
K5 |
(0-11) |
|
|
|
1 |
1 |
|
|
|
|
|
K6 |
(-111) |
|
|
|
|
1 |
|
|
|
|
1 |
ЯK7 (11-) |
|
|
|
|
|
|
1 |
1k |
1k |
1 |
|
Обведенные метки расположены в строке, относящейся к импликанте K7 = (11−) = x1x2. Только эта импликанта является ядровой.
ДНФядр(f) = K7 = x1x2.
8.Составим функцию Патрика для заданной функции. Количество скобок в ней равно 9, так как | Nf |= 9.
P= (K1 K2)(K1 K3)(K3 K5)(K5 K6)·
·(K2 K4)(K4 K7)(K7)(K7)(K6 K7).
Все скобки, содержащие импликанту K7, вычеркиваем, применив закон поглощения A(A B) = A.
Первую и вторую, третью и четвертую скобки попарно перемножаем, также применяя закон поглощения. Получим
P= K7(K1 K2K3)(K3K6 K5)(K2 K4) =
=K7(K1K3K6 K2K3K6 K1K5 K2K3K5)(K2 K4) =
= |
|
7( |
1 |
2 |
3 |
|
|
6 |
2 |
3 |
|
6 |
1 |
2 |
|
5 |
z |
|
|
|
|
|
{5 |
|
|
|||||||||||||||
K |
K |
K |
K |
2 |
}|3 |
|
|
|
||||||||||||||||||||||||||||||||
|
|
|
K |
K |
K |
|
|
K |
K |
|
|
|
|
K |
|
K |
|
|
K K K |
|
|
|||||||||||||||||||
|
|
|
1 |
|
3 |
|
4 |
K |
6 |
2 |
|
3 |
|
4 |
K |
6 |
|
|
1 |
|
4 |
K |
5 z |
|
}|3 |
|
{5) |
. |
||||||||||||
|
|
|
|
|
|
|
|
2 |
4 |
|||||||||||||||||||||||||||||||
|
|
|
K |
K |
K |
|
|
K |
K |
K |
|
|
K |
K |
|
K K K K |
||||||||||||||||||||||||
Опять применим закон поглощения. Дважды подчеркнутая конъюнкция K2K3K6 поглощает конъюнкции K1K2K3K6 и K2K3K4K6, подчеркнутые одной линией; конъюнкция K2K3K5 поглощает K2K3K4K5.
P = K7(K2K3K6 K1K2K5 K2K3K5 K1K3K4K6 K1K4K5).
81
Выражение K7, стоящее перед скобками, соответствует ядровой ДНФ.
ДНФядр(f) = K7 = x1x2.
Мы подтвердили результат, полученный с помощью таблицы покрытия.
Раскроем скобки в функции Патрика.
P= K2K3K6K7 K1K2K5K7 K2K3K5K7
K1K3K4K6K7 K1K4K5K7.
Пять логических слагаемых определяют пять тупиковых ДНФ. Выписываем эти ДНФ, находим их ранг, определяем минимальные ДНФ.
ДНФтуп1 |
(f) = ДНФмин1 (f) = K2 K3 K6 K7 = |
||||||||||||||||||||
|
= |
|
2 |
|
3 |
|
4 |
|
1 |
|
2x4 x2x3x4 |
||||||||||
|
x |
x |
x |
x |
x |
||||||||||||||||
|
|
|
|
|
|
|
r1 = 11; |
||||||||||||||
ДНФтуп2 |
(f) = ДНФмин2 (f) = K1 K2 K5 K7 = |
||||||||||||||||||||
|
= |
|
1 |
|
2 |
|
3 |
|
2 |
|
3 |
|
4 |
|
1x3x4 |
||||||
|
x |
x |
x |
x |
x |
x |
x |
||||||||||||||
|
|
|
|
|
|
|
r2 = 11; |
||||||||||||||
ДНФтуп3 |
(f) = ДНФмин3 (f) = K2 K3 K5 K7 = |
||||||||||||||||||||
|
= |
|
2 |
|
3 |
|
4 |
|
1 |
|
2x4 |
|
1x3x4 |
||||||||
|
x |
x |
x |
x |
x |
x |
|||||||||||||||
|
|
|
|
|
|
|
r3 = 11; |
||||||||||||||
ДНФтуп4 |
(f) = K1 K3 K4 K6 K7 = |
||||||||||||||||||||
|
= |
|
1 |
|
2 |
|
3 |
|
1 |
|
2x4 x1 |
|
3 |
|
4 x2x3x4 |
||||||
|
x |
x |
x |
x |
x |
x |
x |
||||||||||||||
|
|
|
|
|
|
|
r4 = 14; |
||||||||||||||
ДНФтуп5 |
(f) = ДНФмин4 (f) = K1 K4 K5 K7 = |
||||||||||||||||||||
|
|
|
|
|
|
|
= |
|
1 |
|
2 |
|
3 x1 |
|
3 |
|
4 |
|
1x3x4 |
||
|
|
|
|
|
|
|
x |
x |
x |
x |
x |
x |
|||||||||
|
|
|
|
|
|
|
r5 = 11. |
||||||||||||||
x1x2;
x1x2;
x1x2;
x1x2;
x1x2;
82
Пример 5.3. Найти сокращенную, ядровую, все тупиковые и все минимальные ДНФ для булевой функции fe = (0010 0011 1100 1101) методом Квайна.
Решение.
1. Таблица истинности заданной функции
x1 |
x2 |
x3 |
x4 |
|
f |
|
|
|
|
|
|
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
|
0 |
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
|
1 |
Носитель данной функции
Nf =
={ (0010), (0110), (0111), (1000), (1001), (1100), (1101), (1111) }.
2.Применим операцию склейки ко всем наборам из соседних классов. Все наборы, которые участвуют в склейке, как и в предыдущих примерах, помечаем " ". Получается следующая таблица
83
S0 |
|
|
|
|
|
|
|
S1 |
(0010)* |
|
(0-10) |
|
|
(1-0-) |
|
|
(1000)* |
|
|
|
|
|
|
|
(100-)* |
(1-0-) |
|||||
|
|
(1-00)* |
|
|
|
||
|
(0110)* |
|
(011-) |
|
|
|
|
|
(1001) * |
|
|
|
|
|
|
S2 |
(1-01)* |
|
|
|
|
||
|
(1100)* |
(110-)* |
|
|
|
||
S3 |
(0111)* |
(-111) |
|
|
|
|
|
|
(1101)* |
|
|
|
|
|
|
|
(11-1) |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S4 |
(1111) * |
|
|
|
|
|
|
3. Выписываем простые импликанты и находим сокращенную ДНФ.
(0 − 10) ↔ K1 = x1x3x4 (011−) ↔ K2 = x1x2x3 (−111) ↔ K3 = x2x3x4 (11 − 1) ↔ K4 = x1x2x4 (1 − 0−) ↔ K5 = x1x3
ДНФсокр(f) = K1 K2 K3 K4 K5 =
=x1x3x4 x1x2x3 x2x3x4 x1x2x4 x1x3.
4.Составим таблицу покрытия. Обведем единственные в столбце метки.
|
|
|
|
|
(0010) |
|
(0110) |
(0111) |
ЯK1 |
(0-10) |
|
|
|
1k |
|
1 |
|
|
|
|
|
|||||
|
|
|
|
|
||||
K2 |
(011-) |
|
|
|
|
|
1 |
1 |
K3 |
(-111) |
|
|
|
|
|
|
1 |
K4 |
(11-1) |
|
|
|
|
|
|
|
ЯK5 |
(1-0-) |
|
|
|
|
|
|
|
Выпишем ядровую ДНФ.
(1000) |
(1001) |
(1100) |
(1101) |
(1111) |
|
|
|
|
|
|
|
|
|
1 |
1k |
1k |
1k |
1 |
1 |
1 |
|
ДНФядр(f) = K1 K5 = x1x3x4 x1x3.
84
5. По таблице покрытия составим функцию Патрика .
P = |
|
|
|
|
|
|
|
|
|
|
= (K1) (K1 |
K2) |
(K2 |
K3)(K5)(K5)(K5) (K4 |
K5)(K3 K4) = |
||||||
| |
|
{z |
|
} |
|
| |
|
{z |
|
} |
поглощается K1 |
поглощ.K5 |
|||||||||
=K1K5(K2 K3)(K3 K4) =
=K1K5(K2K3 K3K3 K2K4 K3K4) =
| {z }
K3
= K1K5 |
( K2K3 |
K3 |
K2K4 |
K3K4 |
) = |
||||||||
|
| |
|
{z |
|
} |
|
|
| |
|
{z |
|
} |
|
|
поглощается K3 |
|
|
поглощается K3 |
|||||||||
= K1K5(K3 K2K4).
Убедимся, что ядровая ДНФ , равная дизъюнкции импликант, стоящих перед скобками в упрощенной функции Патрика
ДНФядр(f) = K1 K5 = x1x3x4 x1x3,
совпадает с формулой, полученной с помощью таблицы покрытия.
Раскрывая скобки в функции Патрика, получаем 2 логических слагаемых, соответствующих двум тупиковым ДНФ.
P = K1K3K5 K1K2K4K5.
Выписываем полученные ДНФ, находим их ранг, определяем минимальную ДНФ.
ДНФтуп1 (f) = ДНФмин1 (f) = K1 K3 K5 =
= x1x3x4 x2x3x4 x1x3;
r1 = 8;
ДНФтуп2 (f) = K1 K2 K4 K5 =
= x1x3x4 x1x2x3 x1x2x4 x1x3;
r2 = 11.
85
5.3Задачи для самостоятельного решения
Методом Квайна найти сокращенную, ядровую, все тупиковые и минимальные ДНФ булевых функций.
1.fe1 = ( 0011 1101 );
2.fe2 = ( 0111 1110 );
3.fe3 = (1010 0111 1010 0000);
4.fe4 = (1011 1010 1110 1010);
5.fe5 = (1101 1011 1100 1010);
6.fe6 = (1110 0110 1110 0110);
7.fe7 = (0010 0010 0111 1110);
8.fe8 = (1010 1110 0011 0001);
9.fe9 = (1100 1010 1101 0010);
10.ff10 = (1110 0110 0100 0111).
Ответы к задачам для самостоятельного решения
1.ДНФсокр(f1) = x1x2 x1x2 x2x3 x1x3;
ДНФядр(f1) = x1x2 x1x2;
ДНФтуп1 (f1) = ДНФмин1 (f1) = x2x3 x1x2 x2x3; r(ДНФтуп1 ) = r(ДНФмин1 ) = 6;
ДНФтуп2 (f1) = ДНФмин2 (f1) = x2x3 x1x2 x1x3; r(ДНФтуп2 ) = r(ДНФмин2 ) = 6.
2.ДНФсокр(f2) = x1x3 x2x3 x1x2 x1x3 x2x3 x1x2;
ДНФядр(f2) − отсутствует;
ДНФтуп1 (f2) = x1x3 x1x2 x1x3 x1x2;
86
r(ДНФтуп1 ) = 8;
ДНФтуп2 (f2) = ДНФмин1 (f2) = x1x3 x1x2 x2x3; r(ДНФтуп2 ) = r(ДНФмин1 ) = 6;
ДНФтуп3 (f2) = x1x3 x2x3 x1x3 x2x3; r(ДНФтуп3 ) = 8;
ДНФтуп4 (f2) = x2x3 x1x2 x2x3 x1x2; r(ДНФтуп4 ) = 8;
ДНФтуп5 (f2) = x2x3 x1x3 x1x2; r(ДНФтуп5 ) = r(ДНФмин2 ) = 6.
3.ДНФсокр(f3) = x1x3x4 x1x2x4 x1x2x3 x2x4;
ДНФядр(f3) = x1x2x4 x2x4;
ДНФтуп1 (f3) = ДНФмин1 (f3) = x1x3x4 x1x2x4 x2x4; r(ДНФтуп1 ) = r(ДНФмин1 ) = 8;
ДНФтуп2 (f3) = ДНФмин2 (f3) = x1x2x4 x1x2x3 x2x4; r(ДНФтуп2 ) = r(ДНФмин2 ) = 8.
4. ДНФсокр(f4) = ДНФядр(f4) = ДНФтуп(f4) = ДНФмин(f4) = x1x2x3 x1x2x3 x4;
r(ДНФтуп) = r(ДНФмин) = 7.
5.ДНФсокр(f5) = x1x2x4 x1x3x4 x1x2x3 x2x3 x3x4 x2x4;
ДНФядр(f5) = x2x3 x2x4;
ДНФтуп1 (f5) = x1x2x4 x1x2x3 x2x3 x2x4; r(ДНФтуп1 ) = 10;
ДНФтуп2 (f5) = ДНФмин(f5) = x1x3x4 x2x3 x2x4; r(ДНФтуп2 ) = r(ДНФмин) = 7.
87
6.ДНФсокр(f6) = x2x3 x2x4 x3x4 x3x4;
ДНФядр(f6) = x3x4 x3x4;
ДНФтуп1 (f6) = ДНФмин1 (f6) = x2x3 x3x4 x3x4; r(ДНФтуп1 ) = r(ДНФмин1 ) = 6;
ДНФтуп2 (f6) = x2x4 x3x4 x3x4; r(ДНФтуп2 ) = r(ДНФмин2 ) = 6.
7. ДНФсокр(f7) = x1x2x4 x1x3x4 x1x2x3 x1x2x3 x1x2x4 x3x4;
ДНФядр(f7) = x3x4;
ДНФтуп1 (f7) = ДНФмин(f7) = x1x2x4 x1x2x3 x3x4; r(ДНФтуп1 ) = r(ДНФмин) = 8;
ДНФтуп2 (f7) = x1x2x4 x1x3x4 x1x2x4 x3x4; r(ДНФтуп2 ) = 11;
ДНФтуп3 (f7) = x1x3x4 x1x2x3 x1x2x3 x3x4; r(ДНФтуп3 ) = 11;
ДНФтуп4 (f7) = x1x3x4 x1x2x3 x1x2x4 x3x4; r(ДНФтуп4 ) = 11.
8.ДНФсокр(f8) = x2x3x4 x1x2x3 x1x2x3 x1x3x4 x1x4;
ДНФядр(f8) = x1x2x3 x1x3x4 x1x4;
ДНФтуп1 (f8) = ДНФмин1 (f8) = x2x3x4 x1x2x3 x1x3x4 x1x4; r(ДНФтуп1 ) = r(ДНФмин1 ) = 11;
ДНФтуп2 (f8) = ДНФмин2 (f8) = x1x2x3 x1x2x3 x1x3x4 x1x4; r(ДНФтуп2 ) = r(ДНФмин2 ) = 11.
88
9.ДНФсокр(f9) = x1x3x4 x1x2x4 x2x3x4 x1x2x4 x2x3;
|
|
|
|
|
|
|
|
ДНФядр(f9) = x2x3 |
|
|
|
|
4 x1 |
|
2x4 |
|
|
|
2 |
|
3; |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
x |
x |
x |
x |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ДНФтуп1 |
(f9) = ДНФмин1 (f9) = |
|
|
1 |
|
|
|
|
3 |
|
|
|
4 x2x3 |
|
|
4 x1 |
|
2x4 |
|
|
2 |
|
3; |
|||||||||||||||||||||||||||||||||||||||||||||||||
x |
x |
x |
x |
x |
x |
x |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
r(ДНФтуп1 ) = r(ДНФмин1 ) = 11; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ДНФтуп2 |
(f9) = ДНФмин2 (f9) = |
|
|
1x2 |
|
|
|
4 x2x3 |
|
|
4 x1 |
|
2x4 |
|
|
2 |
|
3; |
||||||||||||||||||||||||||||||||||||||||||||||||||||||
x |
x |
x |
x |
x |
x |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
r(ДНФтуп2 ) = r(ДНФмин2 ) = 11. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
10. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ДНФсокр(f10) = |
||||||||||||||||||||||||||||||||||||||||||||||||||||||
= |
|
1 |
|
2 |
|
3 |
|
1 |
|
2 |
|
4 |
|
|
1x3 |
|
4 x2x3 |
|
|
|
4 x1x2x4 x1x2x3 |
|
3x4; |
|||||||||||||||||||||||||||||||||||||||||||||||||
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ДНФядр(f10) = |
|
|
3x4; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ДНФтуп1 (f10) = |
|
1 |
|
2 |
|
3 |
|
1x3 |
|
|
4 x2x3 |
|
|
4 x1x2x4 |
|
3x4; |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x |
x |
x |
x |
x |
x |
x |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r(ДНФтуп1 ) = 14; |
||||||||||||||||||||||||||||||||||||||||||||||||||||||
ДНФтуп2 |
(f10) = ДНФмин1 (f10) = |
|
1 |
|
2 |
|
3 |
|
1x3 |
|
4 x1x2x3 |
|
3x4; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x |
x |
x |
x |
x |
x |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
r(ДНФтуп2 ) = r(ДНФмин1 ) = 11; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ДНФтуп3 |
(f10) = ДНФмин2 (f10) = |
|
1 |
|
2 |
|
4 |
|
1x3 |
|
4 x1x2x3 |
|
3x4; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x |
x |
x |
x |
x |
x |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
r(ДНФтуп3 ) = r(ДНФмин2 ) = 11; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ДНФтуп4 |
(f10) = ДНФмин3 (f10) = |
|
1 |
|
2 |
|
4 x2x3 |
|
4 x1x2x4 |
|
3x4; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x |
x |
x |
x |
x |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
r(ДНФтуп4 ) = r(ДНФмин3 ) = 11; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ДНФтуп5 |
(f10) = ДНФмин5 (f10) = |
|
1 |
|
2 |
|
4 x2x3 |
|
4 x1x2x3 |
|
3x4; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
x |
x |
x |
x |
x |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
r(ДНФтуп5 ) = r(ДНФмин4 ) = 11; |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
89
Глава 6
Метод Карно минимизации булевых функций
6.1Представление функции алгебры логики картой Карно
Любую булеву функцию можно представить картой Карно. Наиболее удобно и наглядно этим способом изображать функцию 4 переменных. Для этого рисуют прямоугольную таблицу 4 × 4. Строки обычно соответствуют переменным x1 и x2, а столбцыпеременным x3 и x4. Наборы, соответствующие переменным, следуют не в стандартном (лексикографическом) порядке, а следующим образом: 00, 01, 11, 10 (то есть два последних двоичных набора длины 2 меняют местами). Такое расположение наборов соответствует их размещению на координатной плоскости по направлению по часовой стрелке.
|
y |
|
|
|
|
|
x3x4 |
|
00 |
|
01 |
|
11 |
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
6 |
|
|
|
@ |
|
|
|
|
|
|
|
|
|
||
|
|
b |
|
|
|
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1x@2 |
|
|
|
|
|
|
|
|
|
|||||
(01) |
|
|
|
(11) |
|
00 |
|
|
|
|
|
|
|
|
|
||
|
|
b |
|
|
x |
|
01 |
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
(00) |
|
|
|
- |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
b(10) |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
||||
При таком порядке следования наборов соседние наборы оказываются расположенными рядом. Наборы 00 и 10 являются соседними, поэтому на карте Карно все соседние строки и столбцы, включая крайние, определяют соседние наборы. Отсюда еще одно название карты Карно- булев тор.
90