1-2-3
.pdf
Нормальные формы Оптимизация ДНФ
Тупиковая ДНФ
Определение. Пусть P множество всех простых |
|
|
|
|
|
|
||||||
импликантов f . ДНФ вида f = |
K 2S |
K ; где S P, называется |
||||||||||
|
|
|
|
|
|
W |
||||||
тупиковой ДНФ, если для всех SW0 |
6 |
|||||||||||
S имеем f = |
|
K : ggg |
||||||||||
|
|
|
|
|
|
K 2S0 |
||||||
Теорема. Минимальная ДНФ является тупиковой. |
|
|
|
|
|
|
||||||
|
W |
K минимальная ДНФ для |
||||||||||
Доказательство. Пусть f = |
||||||||||||
= |
K 2S |
|
|
|
|
|
|
|
|
|
|
|
W: |
|
|
|
|
|
S. |
||||||
f . Ясно, что вес |
K будет еще меньше при S0 |
|||||||||||
K 2S0 |
|
|
|
|
|
|
|
|
|
|
|
|
W |
K |
|
|
|
|
|
|
|
|
|
|
|
Поэтому, f 6 |
|
|
|
|
|
|
|
|
|
|
|
|
K 2S0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нормальные формы Оптимизация ДНФ
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
Сокращенная ДНФ для f :
f (x; y; x) = x & y & z _ x & z _ y & z
является тупиковой
Нормальные формы Оптимизация ДНФ
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
Сокращенная ДНФ для f :
f (x; y; x) = x & y & z _ x & z _ y & z
является тупиковой и, следовательно, минимальной.
Нормальные формы Оптимизация ДНФ
Нахождение минимальной ДНФ
Нормальные формы Оптимизация ДНФ
Нахождение минимальной ДНФ
1. Строим сокращенную ДНФ.
Нормальные формы Оптимизация ДНФ
Нахождение минимальной ДНФ
1.Строим сокращенную ДНФ.
2.Последовательно удаляем лишние конъюнкты из сокращенной ДНФ, находим все тупиковые ДНФ.
Нормальные формы Оптимизация ДНФ
Нахождение минимальной ДНФ
1.Строим сокращенную ДНФ.
2.Последовательно удаляем лишние конъюнкты из сокращенной ДНФ, находим все тупиковые ДНФ.
3.Находим минимальную ДНФ, выбирая тупиковую ДНФ с наименьшим весом.
Нормальные формы Оптимизация ДНФ
Пример–домашнее задание
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1.Сокращенная ДНФ = ?
2.Тупиковые ДНФ = ?
3.Минимальная ДНФ = ?
Нормальные формы Оптимизация ДНФ
Метод получения сокращенной ДНФ функции f
0 (Выписываем все возможные импликанты длины 0).
Нормальные формы Оптимизация ДНФ
Метод получения сокращенной ДНФ функции f
0 (Выписываем все возможные импликанты длины 0).
1Выписываем все возможные импликанты длины 1, не содержащие импликанты, выписанные в 0.