1-2-3
.pdf
Нормальные формы Оптимизация ДНФ
Импликанты
I Элементарный конъюнкт
K = x |
1 & x |
2 & : : : & x |
k |
|
i1 |
i2 |
ik |
называется импликантом булевой функции f (x1; x2; : : : ; xn), если
K = 1 =) f (x1; x2; : : : ; xn) = 1
для всех x1; x2; : : : ; xn 2 B:
IЕсли K присутствует в ДНФ функции f , то K является импликантом f .
Нормальные формы Оптимизация ДНФ
Пример
|
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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нормальные формы Оптимизация ДНФ
Пример
|
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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нормальные формы Оптимизация ДНФ
Пример
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 |
I x & 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 |
Ix & y & z импликант,
Ix & 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 |
Ix & y & z импликант,
Ix & y & z импликант,
Ix & 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 |
Ix & y & z импликант,
Ix & y & z импликант,
Ix & y & z импликант,
Ix & 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 |
Ix & y & z импликант,
Ix & y & z импликант,
Ix & 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 импликант,
Ix & y & z импликант,
Ix & y & z импликант,
Ix & y & z импликант,
Ix & z импликант, так как если x = 0 и z = 1, то f = 1,
Нормальные формы Оптимизация ДНФ
Пример
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 импликант,
Ix & y & z импликант,
Ix & y & z импликант,
Ix & y & z импликант,
Ix & z импликант, так как если x = 0 и z = 1, то f = 1,
Iy & z импликант,