1-2-3
.pdf
Нормальные формы Оптимизация ДНФ
Пример
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 |
Ix & y & z не простой импликант, так как содержит импликанты x & z и y & z,
Ix & y & z содержит импликант x & z,
Ix & y & z содержит импликант y & z,
Ix & y & z простой импликант,
Ix & 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 |
Ix & y & z не простой импликант, так как содержит импликанты x & z и y & z,
Ix & y & z содержит импликант x & z,
Ix & y & z содержит импликант y & z,
Ix & y & z простой импликант,
Ix & z простой импликант,
Iy & z простой импликант.
Нормальные формы Оптимизация ДНФ
Простые импликанты и минимальная ДНФ
Теорема. Каждый элементарный конъюнкт в минимальной ДНФ для булевой функции f является простым импликантом.
Нормальные формы Оптимизация ДНФ
Простые импликанты и минимальная ДНФ
Теорема. Каждый элементарный конъюнкт в минимальной ДНФ для булевой функции f является простым
импликантом.
m
W
Доказательство. Пусть f = Ki является минимальной
i=1
ДНФ. Докажем, что K1 (например) является простым импликантом. Пусть не так: существует импликант K 0, являющийся собственной частью K1. Тогда
|
m |
|
m |
m |
f = K 0 _ f = K 0 |
i_1 |
Ki = (K 0 _ K1) _ |
i_2 |
i_2 |
_ |
Ki = K 0 _ |
Ki ; |
||
|
= |
|
= |
= |
то есть получили ДНФ, с меньшим весом чем минимальная. Противоречие.
Нормальные формы Оптимизация ДНФ
Сокращенная ДНФ
Теорема. Каждый элементарный конъюнкт в минимальной ДНФ для булевой функции f является простым импликантом.
Следствие. Пусть P множество всех простых импликантов
W
булевой функции f . Тогда f = |
K ; |
K 2P
Нормальные формы Оптимизация ДНФ
Сокращенная ДНФ
Теорема. Каждый элементарный конъюнкт в минимальной ДНФ для булевой функции f является простым импликантом.
Следствие. Пусть P множество всех простых импликантов
|
|
|
m |
W |
|
|
|
|
|
|
|
|
|
|
|
булевой функции f . Тогда f = |
K ; |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
iW1 |
K 2P |
|
|
|
|
|
|
|
|
|
|
|
Доказательство. Пусть f |
Ki минимальная ДНФ. |
||||||||||||||
= |
|||||||||||||||
Тогда Ki 2 P, i = |
|
, и |
= |
|
|
|
|
|
|
|
|
|
|
|
|
1; m |
|
|
|
|
|
|
|
|
|
|
|
|
|||
_ |
|
m |
_ |
_ |
|
|
|
|
|
|
|
|
|||
|
_ |
|
|
|
|
|
|
|
|
||||||
f = f _ K = Ki _ |
K = K : |
||||||||||||||
|
K 2P |
i=1 |
K 2P |
K 2P |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нормальные формы Оптимизация ДНФ
Сокращенная ДНФ
Теорема. Каждый элементарный конъюнкт в минимальной ДНФ для булевой функции f является простым импликантом.
Следствие. Пусть P множество всех простых импликантов булевой функции f . Тогда f = K ;
|
K 2P |
Определение. Дизъюнкция всехWпростых импликантов |
|
функции f |
_ |
f = |
K ; |
K 2P
называется сокращенной ДНФ.
Нормальные формы Оптимизация ДНФ
Пример
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; z) = x & y & z _ x & z _ y & z
Нормальные формы Оптимизация ДНФ
Тупиковая ДНФ
Определение. Пусть P множество всех простых |
|
|
|
|
|
|||||||
импликантов f . ДНФ вида f = |
K ; где S P, называется |
|||||||||||
|
K 2S |
|
|
|
|
W |
|
|
|
|
|
|
тупиковой ДНФ, если для всех SW0 |
6 |
K : ggg |
||||||||||
S имеем f = |
||||||||||||
|
|
|
|
|
K 2S0 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нормальные формы Оптимизация ДНФ
Тупиковая ДНФ
Определение. Пусть P множество всех простых |
|
||
импликантов f . ДНФ вида f = |
K ; где S P, называется |
||
K 2S |
W |
|
|
тупиковой ДНФ, если для всех SW0 |
K : ggg |
||
6 |
|||
S имеем f = |
|||
|
K 2S0 |
|
|
Теорема. Минимальная ДНФ является тупиковой.