1-2-3
.pdf
Нормальные формы Оптимизация ДНФ
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
i1 |
i2 |
ik |
||||
|
|
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
xi1 = 1; xi2 = 2; : : : ; xik = k |
|||||||
Полные конъюнкты вершины: |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
z |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
x |
yz |
|
xyz |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
xyz |
|
|
|
|
|
|
|
xyz |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xyz |
|
|||||
|
|
|
|
x |
|
|
y |
|
z |
|
|
|
y |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
xy z
xxyz
Нормальные формы Оптимизация ДНФ
Элементарные конъюнкты
|
I В частности, f = x 1 x |
2 : : : x |
k отождествляем с |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i1 |
i2 |
ik |
|
|
|
|
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xi1 = 1; : : : xi2 = 2; : : : ; xik = k |
||||||
Конъюнкты длины n 1 ребра: |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
z |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xz |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
yz |
x |
y |
|
yz |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
xz |
|
|
xy |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
xy |
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xy |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
x z |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
yz |
|
|
|
|
|
|||||||
|
|
|
|
|
y |
z |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
xxz
Нормальные формы Оптимизация ДНФ
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
|||
xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Конъюнкты длины n 2 грани: 
z
z
y
z
x
Нормальные формы Оптимизация ДНФ
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
|||
xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Конъюнкты длины n 2 грани: 
z
xx
y
x
Нормальные формы Оптимизация ДНФ
Элементарные конъюнкты
I В частности, f = x |
1 x |
2 : : : x |
k отождествляем с |
|
i1 |
i2 |
ik |
множеством (x1; x2; : : : ; xn) 2 Bn таких, что |
|||
xi1 = 1; : : : xi2 = 2; : : : ; xik = k
Конъюнкты длины n 2 грани: 
z
yy
y
x
Нормальные формы Оптимизация ДНФ
Метод получения сокращенной ДНФ
1. Выписываем все грани, содержащиеся в f .
Нормальные формы Оптимизация ДНФ
Метод получения сокращенной ДНФ
1.Выписываем все грани, содержащиеся в f .
2.Выписываем все ребра, содержащиеся в f , но не содержащиеся в 1.
Нормальные формы Оптимизация ДНФ
Метод получения сокращенной ДНФ
1.Выписываем все грани, содержащиеся в f .
2.Выписываем все ребра, содержащиеся в f , но не содержащиеся в 1.
3.Выписываем все вершины, содержащиеся в f , но не содержащиеся в 1 и 2.
Нормальные формы Оптимизация ДНФ
Пример построения сокращенной ДНФ
z
xz
yz
xy
xy
yz y
xxz
Нормальные формы Оптимизация ДНФ
Тупиковая ДНФ № 1
z
xz
yz
yz y
xxz