Дискретная математика
.pdf
zI1
|
6 |
|
iu |
|
|
|
@ |
|
|
|
|
|
|
@ |
|
|
|
(001)*@ |
? @*(011) |
||||
|
iu |
||||
|
|
|
- |
y |
|
iu |
|
iu |
|||
@ @ |
|
|
|||
(101)* |
|
|
(111) |
|
|
@ |
|
@ |
|
|
|
|
(000)e |
e(010) |
|||
e |
|
|
|
|
I2 |
|
|
iu |
|
|
|
|
|
|
|
|
|
(100) |
|
|
@ *(110) |
||
|
|
|
@ |
|
|
х
Вершина (110) покрыта только интервалом I2. Согласно определению, этот интервал и соответствующая импликанта K2 = x1x2 - ядровые.
Вершина (111) содержится в двух интервалах и "*" не отмечена. Остальные вершины входят только в ядровый интервал I1, импли-
канта K1 = x3 - ядровая.
ДНФмин(f2) = ДНФтуп(f2) = ДНФядр(f2) = ДНФсокр(f2) =
= x1x2 x3;
r(ДНФмин(f2)) = 3.
в) f3(xe) = (0110 1110)
z
|
|
|
6 |
|
|
|
|
|
|
@ |
|
|
|
|
|
(001)* |
|
|
||
I |
|
|
@ |
|
e(011) |
|
1 |
- ui |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
@ |
|
|
|
|
(101) |
(111) |
|
||||
|
|
@ |
e@*- |
y |
||
|
|
ui |
||||
I2 |
- |
(000)e |
|
@ |
|
|
|
ui(010) |
|||||
|
|
u |
|
|
I4 |
|
|
|
|
ui |
|
||
|
|
|
|
|
|
|
(100) |
|
@ (110) |
|
|||
|
|
х |
|
@ |
|
|
|
|
|
|
|
|
|
|
|
I3 |
|
|
|
|
Каждый из ядровых интервалов I1 и I4 покрывает по 2 вершины. В результате их вычеркивания остается одна вершина (100). Она содержится в двух интервалах I2 и I3. Для того, чтобы покрыть вершину, достаточно одного из них. Значит, тупиковые ДНФ будут содержать
61
ядро и одну из импликант - K2 или K3 (эти импликанты избыточны для функции f3). Других тупиковых ДНФ у данной функции нет.
ДНФтуп1 (f3) = ДНФядр(f3) K2 = x2x3 x2x3 x1x2; r(ДНФтуп1 ) = 6.
ДНФтуп2 (f3) = ДНФядр(f3) K3 = x2x3 x2x3 x1x3; r(ДНФтуп2 ) = 6.
Так как ранг обеих тупиковых ДНФ одинаков, обе формулы являются минимальными ДНФ функции f3.
ДНФмин1 (f3) = ДНФтуп1 (f3) = x2x3 x2x3 x1x2; r(ДНФмин1 ) = 6.
ДНФмин2 (f3) = ДНФтуп2 (f3) = x2x3 x2x3 x1x3; r(ДНФмин2 ) = 6.
4.2.6Функция Патрика
Находить тупиковые ДНФ также можно, применяя вспомогательную функцию - функцию Патрика.
Функция Патрика представляет собой КНФ, в которой каждому набору из носителя взаимно однозначно соответствует элементарная дизъюнкция (количество сомножителей в функции Патрика равно | Nf |). Каждый логический сомножитель представляет собой перечисление через знак дизъюнкции всех импликант, покрывающих данную вершину.
Упрощаем функцию Патрика, применяя логические тождества
A · A = A
A AB = A
A(A B) = A
По функции, полученной в результате преобразований, выписываем ядровую и тупиковые ДНФ. Ядро образует логическая сумма импликант, стоящих перед скобками. Тупиковые ДНФ получим, раскрыв скобки. Теперь функция Патрика имеет вид ДНФ. Каждой тупиковой ДНФ соответствует логическое слагаемое в преобразованной функции Патрика.
62
Пример 4.9. Найти все тупиковые и минимальные ДНФ для функций a) f1(xe) = (1001 0001)
б) f2(xe) = (0101 0111) из примера 4.4, используя функцию Патрика. в) f3(xe) = (0110 1110)
Решение.
а) f1(xe) = (1001 0001)
z
|
|
|
6 |
|
*(011) |
||||
|
(001)e |
|
|||||||
|
|
|
|
|
u |
|
|
I1 |
|
|
|
ku |
(111) |
||||||
(101) |
|
|
e |
|
|
||||
|
|
* |
|
|
|
|
|||
I2 |
-e |
|
|
u |
|
|
|
- |
y |
|
|
|
|
|
(010) |
||||
|
e |
*(000) |
e |
|
|
||||
|
|
|
|
|
|
|
|
||
(100) |
|
|
(110) |
|
|||||
х
Носитель функции f1 содержит 3 вершины, каждая покрыта только одним интервалом. Значит, каждый из трех сомножителей в искомой КНФ содержит одну импликанту, покрывающую данную вершину. Перечисляя наборы в порядке их следования в таблице истинности, получаем функцию Патрика Pf1 = (K2)(K1)(K1) = K1K2. Последнее тождество получили, применяя закон идемпотентности K1 · K1 = K1. Так как полученная ДНФ содержит одно слагаемое K1K2, соответствующее и ядровой, и тупиковой ДНФ, то
ДНФмин(f1) = ДНФтуп(f1) = K1 K2 = x2x3 x1x2x3;
r(ДНФмин(f1)) = 5.
б) f2(xe) = (0101 0111)
zI1
|
6 |
|
|
|
u |
|
(001)*u |
? |
|
|
|
||
|
|
*(011) |
||||
|
|
|
|
|||
|
|
|
(111) |
y |
||
(101)*u |
(000)e |
u |
|
- |
||
|
e(010) |
|||||
e |
|
|
u |
|
|
I2 |
|
|
|
|
|
|
|
63 |
|
|
*(110) |
|||
(100) |
|
|
|
|||
х
Соответствующие наборам носителя сомножители в функции Патрика опять зададим в порядке возрастания их номеров. Вершина (111) покрыта двумя интервалами I1 и I2 (ей соответствует последняя скобка в КНФ), остальные наборы носителя покрываются одним интервалом.
Pf2 = (K1)(K1)(K1)(K2)(K1 K2) = K1K2.
Упрощая формулу, сначала применили тождество A · A = A, затем закон поглощения A(A B) = A.
Аналогично предыдущему примеру,
ДНФмин(f2) = ДНФтуп(f2) = K1 K2 = x1x2 x3;
r(ДНФмин(f2)) = 3.
в) f3(xe) = (0110 1110)
z
|
|
|
6 |
|
|
|
I |
|
(001)*u |
|
(011) |
||
1 |
- |
|
e |
|
||
|
u |
|
e |
*- |
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(101) |
(000)e |
(111) |
|
|||
I2 |
- |
|
u(010) |
|||
|
|
u |
|
|
I4 |
|
|
|
|
u |
|
|
|
|
|
|
|
|
|
|
(100) |
|
|
|
|
||
|
(110) |
|
||||
|
|
х |
|
|
|
|
|
|
I3 |
|
|
|
|
Каждый из наборов носителя (001) и (010) покрывается только одним интервалом . Этим вершинам соответствуют в функции Патрика сомножители (K1) и (K4). Вершина (100) покрыта интервалами I2 и I3, соответствующий ей сомножитель - (K2 K3). Аналогично, вершинам (101) и (110) сопоставлены дизъюнкции (K1 K2) и (K3 K4). Задавая вершины в стандартном порядке, получаем
Pf3 = (K1)(K4)(K2 K3)(K1 K2)(K3 K4) = K1K4(K2 K3).
В этой формуле импликанта K1 поглотила скобку (K1 K2), а K4 -
(K3 K4).
Выражение K1K4 перед скобками задает ядровую ДНФ ДНФядр(f3) = K1 K4 = x2x3 x2x3.
64
Раскроем скобки в функции Патрика. Получаем 2 логических слагаемых K1K2K4 и K1K3K4, которым соответствуют две тупиковые ДНФ
ДНФтуп1 (f3) = K1 K2 K4 = x2x3 x2x3 x1x2;
ДНФтуп2 (f3) = K1 K3 K4 = x2x3 x2x3 x1x3.
Вычислив их ранг, определяем, что обе тупиковые ДНФ являются минимальными.
ДНФмин1 (f3) = x2x3 x2x3 x1x2; ДНФмин2 (f3) = x2x3 x2x3 x1x3.
Пример 4.10. Найти сокращенную, ядровую, все тупиковые и все минимальные ДНФ для функции f(xe) = x1 x2 x3 x1x2 x1x3 x2x3.
Решение.
Построим таблицу истинности заданной функции. Сначала вычислим все конъюнкции, затем просуммируем все столбцы по модулю 2, учитывая, что сумма пар одинаковых слагаемых равна нулю.
x1 x2 x3 |
|
x1x2 x1x3 x2x3 |
f |
||||
|
|
|
|
|
|
|
|
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
0 |
Носитель функции
Nf = { (001), (010), (011), (100), (101), (110) }.
Изобразим функцию на булевом кубе.
z
|
6 |
u |
|
|
(001)u |
|
|||
|
(011) |
|||
|
|
|
|
|
|
|
(111) |
y |
|
(101)u |
|
e |
- |
|
(000)e |
u(010) |
|||
|
65 |
|
|
|
u |
|
u |
|
|
(100) |
|
(110) |
|
|
х
Объединим вершины носителя в максимальные интервалы. Максимальных интервалов, покрывающих все 8 вершин (весь куб) или 4 вершины (грань куба), нет. Все максимальные интервалы соединяют пары соседних вершин и являютcя ребрами куба (1-мерными гранями булевого куба). Таких интервалов шесть - I1, I2, I3, I4, I5, I6.
|
|
|
|
zI6 |
|
|
|
|
|
|
|
6 |
|
|
|
I |
|
(001)u |
? |
(011) |
|||
1 |
- |
|
|
|
u |
I5 |
|
|
|
|
|
|
|||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
|
(111) |
y |
|
(101)u |
(000)e |
e |
- |
||||
I2 |
- |
|
|
u(010) |
|||
|
|
u |
|
|
I4 |
||
|
|
|
u |
|
|
||
|
|
|
|
|
|
||
(100) |
|
|
|
|
|
||
|
|
(110) |
|
||||
|
|
х |
|
|
|
|
|
|
|
I3 |
|
|
|
||
Выпишем наборы, покрытые этими интервалами, и найдем соответствующие данным ребрам простые импликанты.
I1 = { (001), (101) } |
↔ |
K1 = |
|
2x3 |
||||
x |
||||||||
I2 = { (101), (100) } |
↔ |
K2 = x1 |
|
2 |
||||
x |
||||||||
I3 |
= { (100), (110) } |
↔ |
K3 |
= x1 |
|
3 |
||
x |
||||||||
I4 |
= { (110), (010) } |
↔ |
K4 |
= x2 |
|
3 |
||
x |
||||||||
I5 |
= { (010), (011) } |
↔ |
K5 |
= |
|
1x2 |
||
x |
||||||||
I6 |
= { (011), (001) } |
↔ |
K6 |
= |
|
1x3 |
||
x |
||||||||
Дизъюнкция всех простых импликант образует сокращенную ДНФ.
ДНФсокр(f) = K1 K2 K3 K4 K5 K6 =
= x2x3 x1x2 x1x3 x2x3 x1x2 x1x3.
Каждая вершина носителя покрыта ровно двумя интервалами. Вершин, покрытых только одним интервалом, нет. Значит, нет и ядровых интервалов и импликант. Ядровой ДНФ также нет.
Для нахождения всех тупиковых ДНФ воспользуемся функцией Патрика. Так как носитель состоит из 6 наборов, функция Патрика содержит 6 сомножителей. Каждая вершина покрыта дву-
66
мя интервалами, поэтому каждый сомножитель представляет собой дизъюнкцию двух импликант. Для удобства упрощения функции, наборы в функции Патрика перечислим в следующем порядке: (001),(101),(100),(110),(010),(011).
P = (K1 K2)(K2 K3)(K3 K4)(K4 K5)(K5 K6)(K6 K1)
Рассмотрим любые две соседние скобки. В общем виде их произведение имеет вид (A B)(B C) = AB BB AC BC. Так как BB = B, и AB B = B, то (A B)(B C) = B AC.
Перемножив пары соседних скобок и, упорядочив простые импликанты в порядке возрастания номеров (в силу коммутативности конъюнкции), получим
P= (K1 K2)(K2 K3)(K3 K4)(K4 K5)(K5 K6)(K6 K1) =
=(K1K3 K2)(K3K5 K4)(K1K5 K6) =
=(K1K3K5 K2K3K5 K1K3K4 K2K4)(K1K5 K6) =
=K1K3K5 K1K2K3K5 K1K3K4K5 K1K2K4K5
K1K3K5K6 K2K3K5K6 K1K3K4K6 K2K4K6
Эту функцию можно упростить, применив закон поглощения к подчеркнутым слагаемым:
K1K3K5 K1K3K5 K1K3K5
K1K2K3K5 = K1K3K5
K1K3K4K5 = K1K3K5
K1K3K5K6 = K1K3K5.
P = K1K3K5 K1K2K4K5 K2K3K5K6 K1K3K4K6 K2K4K6.
Остается еще 5 логических слагаемых, соответствующих пяти тупиковым ДНФ
ДНФтуп1 (f) = K1 K3 K5 = x2x3 x1x3 x1x2; r1 = 6;
ДНФтуп2 (f) = K1 K2 K4 K5 = x2x3 x1x2 x2x3 x1x2; r2 = 8;
ДНФтуп3 (f) = K2 K3 K5 K6 = x1x2 x1x3 x1x2 x1x3; r3 = 8;
67
ДНФтуп4 (f) = K1 K3 K4 K6 = x2x3 x1x3 x2x3 x1x3; r4 = 8;
ДНФтуп5 (f) = K2 K4 K6 = x1x2 x2x3 x1x3; r5 = 6.
Две тупиковые ДНФ (ДНФтуп1 и ДНФтуп5 ) имеют наименьший ранг, равный 6, и являются минимальными.
ДНФмин1 (f) = ДНФтуп1 (f) = x2x3 x1x3 x1x2; r(ДНФмин1 ) = 6 ДНФмин2 (f) = ДНФтуп5 (f) = x1x2 x2x3 x1x3; r(ДНФмин2 ) = 6.
4.3Задачи для самостоятельного решения
Геометрическим методом найти сокращенную, ядровую, все тупиковые
иминимальные ДНФ булевых функций:
1.fe1 = ( 1001 1100 );
2.fe2 = ( 1011 0101 );
3.fe3 = ( 1011 1101 );
4.fe4 = ( 1111 1100 );
5.fe5 = ( 1001 1110 );
6.fe6 = ( 0011 1110 );
7.fe7 = ( 0101 1111 ).
Ответы к задачам для самостоятельного решения
1.ДНФсокр(f1) = ДНФядр(f1) = ДНФтуп(f1) = ДНФмин(f1) =
=x1x2x3 x2x3 x1x2;
r(ДНФтуп) = r(ДНФмин) = 7.
68
2.ДНФсокр(f2) = x1x3 x1x2 x2x3 x1x3;
ДНФядр(f2) = x1x3 x1x3;
ДНФтуп1 (f2) = ДНФмин1 (f2) = x1x3 x1x2 x1x3; r(ДНФтуп1 ) = r(ДНФмин1 ) = 6;
ДНФтуп2 (f2) = ДНФмин2 (f2) = x1x3 x2x3 x1x3; r(ДНФтуп2 ) = r(ДНФмин2 ) = 6.
3.ДНФсокр(f3) = x1x3 x2x3 x1x2 x1x3 x2x3 x1x2;
ДНФядр(f3) − отсутствует;
ДНФтуп1 (f3) = x1x3 x1x2 x1x3 x1x2; r(ДНФтуп1 ) = 8;
ДНФтуп2 (f3) = x1x3 x2x3 x1x3 x2x3; r(ДНФтуп2 ) = 8;
ДНФтуп3 (f3) = ДНФмин1 (f3) = x1x3 x1x2 x2x3; r(ДНФтуп3 ) = r(ДНФмин1 ) = 6;
ДНФтуп4 (f3) = x2x3 x1x2 x2x3 x1x2; r(ДНФтуп4 ) = 8;
ДНФтуп5 (f3) = ДНФмин2 (f3) = x2x3 x1x3 x1x2; r(ДНФтуп5 ) = r(ДНФмин2 ) = 6.
4. ДНФсокр(f4) = ДНФядр(f4) = ДНФтуп(f4) = ДНФмин(f4) = x1 x2;
r(ДНФтуп) = r(ДНФмин) = 2.
5. ДНФсокр(f5) = ДНФядр(f5) = ДНФтуп(f5) = ДНФмин(f5) = x1x2x3 x2x3 x1x2 x1x3;
r(ДНФтуп) = r(ДНФмин) = 9.
69
6. ДНФсокр(f6) = x1x2 x2x3 x1x3 x1x2;
ДНФядр(f6) = x1x2 x1x2;
ДНФтуп1 (f6) = ДНФмин1 (f6) = x1x2 x2x3 x1x2; r(ДНФтуп1 ) = r(ДНФмин1 ) = 6;
ДНФтуп2 (f6) = ДНФмин2 (f6) = x1x2 x1x3 x1x2; r(ДНФтуп2 ) = r(ДНФмин2 ) = 6.
7.ДНФсокр(f7) = ДНФядр(f7) = ДНФтуп(f7) = ДНФмин(f7) =
=x1 x3;
r(ДНФтуп) = r(ДНФмин) = 2.
70