2.4.3. Приведение формулы к днф, кнф, сднф, скнф, полиному Жегалкина.
Упрощение:
F = (⌐(x↔y)→⌐z)│y = <штрих Шеффера> =
= ⌐(⌐(x↔y)→⌐z)V⌐y = <эквивалентность> =
= ⌐(⌐(xyV⌐x⌐y)→⌐z)V⌐y = <импликация>=
= ⌐(⌐⌐(xyV⌐x⌐y)V⌐z)V⌐y = ⌐(xyV⌐x⌐yV⌐z)V⌐y =
= <закон де Моргана> = (⌐(xy)⌐(⌐x⌐y)⌐(⌐z))V⌐y =
= <закон де Моргана> = (⌐xV⌐y)(⌐⌐xV⌐⌐y)zV⌐y =
= (⌐xV⌐y)(xVy)zV⌐y = (⌐xV⌐y)(xzVyz)V⌐y =
= (⌐xxzV⌐yxzV⌐xyzV⌐yyz)V⌐y = x⌐yzV⌐xyzV⌐y =
= <поглощение> = ⌐xyzV⌐y.
ДНФ: F=⌐xyzV⌐y, (табл. 2.5).
KНФ: F = ⌐xyzV⌐y = (⌐x)(y)(z)V⌐y = (⌐xV⌐y)(yV⌐y)(zV⌐y) =
= <поглощение> = (⌐xV⌐y)(⌐yVz).
СДНФ: F = ⌐xyzV⌐y = ⌐xyzV⌐y(xV⌐x) = ⌐xyzV⌐yxV⌐y⌐x =
= ⌐xyzVx⌐y(zV⌐z)V⌐x⌐y(zV⌐z) =
= ⌐xyzVx⌐yzVx⌐y⌐zV⌐x⌐yzV⌐x⌐y⌐z.
СKНФ: F = (⌐xV⌐y)(zV⌐y) = ((⌐xV⌐y)Vz⌐z)((⌐yVz)Vx⌐x) =
= (⌐xV⌐yVz)(⌐xV⌐yV⌐z)(xV⌐yVz)(⌐xV⌐yVz) = <поглощение> =
= (⌐xV⌐yVz)(⌐xV⌐yV⌐z)(xV⌐yVz).
Таблица 2.5
|
x |
y |
z |
f1= ⌐x |
F2= ⌐y |
f3= f1yz |
F= f2Vf3 |
|
Л |
Л |
Л |
И |
И |
Л |
И |
|
Л |
Л |
И |
И |
И |
Л |
И |
|
Л |
И |
Л |
Л |
И |
Л |
Л |
|
Л |
И |
И |
Л |
И |
И |
И |
|
И |
Л |
Л |
И |
Л |
Л |
И |
|
И |
Л |
И |
И |
Л |
Л |
И |
|
И |
И |
Л |
Л |
Л |
Л |
Л |
|
И |
И |
И |
Л |
Л |
Л |
Л |
Полином Жегалкина в общем виде:
F = c0+c1x+c2y+c3z+c4xy+c5xz+c6yz+c7xyz.
F(0,0,0) = 1 =
= c0+c1∙0+c2∙0+c3∙0+c4∙0∙0+c5∙0∙0+c6∙0∙0+c7∙0∙0∙0 =
=c0+0+0+0+0+0+0+0, => c0 = 1,
F(0,0,1) = 1 =
= 1+c1∙0+c2∙0+c3∙1+c4∙0∙0+c5∙0∙1+c6∙0∙0+c7∙0∙0∙1 =
= 1+0+0+c3+0+0+0+0, => c3 = 0,
F(0,1,0) = 0 =
= 1+c1∙0+c2∙1+0∙0+c4∙0∙1+c5∙0∙0+c6∙1∙0+c7∙0∙1∙0 =
= 1+0+c2+0+0+0+0+0, => c2 = 1,
F(1,0,0) = 1 =
= 1+c1∙1+1∙0+0∙0+c4∙1∙0+c5∙1∙0+c6∙0∙0+c7∙1∙0∙0 =
= 1+c1+0+0+0+0+0+0, => c1 = 0,
F(0,1,1) = 1 =
= 1+0∙0+1∙1+0∙1+c4∙0∙1+c5∙0∙1+c6∙1∙1+c7∙0∙1∙1 =
= 1+0+1+0+0+0+c6+0, => c6 = 1,
F(1,0,1) = 1 =
= 1+0∙1+1∙0+0∙1+c4∙1∙0+c5∙1∙1+1∙0∙1+c7∙1∙0∙1 =
= 1+0+0+0+0+c5+0+0, => c5 = 0,
F(1,1,0) = 0 =
= 1+0∙1+1∙1+0∙0+c4∙1∙1+0∙1∙0+1∙1∙0+c7∙1∙1∙0 =
= 1+0+1+0+c4+0+0+0, => c4 = 0,
F(1,1,1) = 0 =
= 1+0∙1+1∙1+0∙1+0∙1∙1+0∙1∙1+1∙1∙1+c7∙1∙1∙1 =
= 1+0+1+0+0+0+1+c7, => c7 = 1.
Полином Жегалкина для данной функции: F = 1+y+yz+xyz.
2.4.4.Нахождение сокращенной, тупиковых и минимальных днф булевой функции.
f(x,y,z):
f(0,1,1) = f(0,1,0) = f(1,0,1) = f(1,1,1) = 1.
а) Метод Квайна.
Сокращенная ДНФ (СокрДНФ):
f(x,y,z) = ⌐xyzV⌐xy⌐zVx⌐yzVxyz = <неполное склеивание> =
= ⌐xyzV⌐xy⌐zVx⌐yzVxyzV⌐xyVyzVxz = <поглощение> =
= ⌐xyVyzVxz.
б) Карта Карно (рис. 2.1).
СокрДНФ: f(x,y,z) = ⌐xyVyzVxz.
Рис. 2.1
в) Метод Квайна-МакКлоски (табл. 2.6). Плюсом помечены импликанты, вступившие в операцию склеивания.
СокрДНФ: f(x,y,z) = ⌐xyVyzVxz.
Матрица Квайна (табл. 2.7). Плюсом помечены вхождения исходных векторов в склейки (импликанты), а скобками помечен выбор склеек в состав МНДФ.
Минимальная ДНФ (МДНФ): f(x,y,z)=⌐xyVxz.
Принадлежность функции к классам Поста:
P0 (сохранение 0): f(0,0,0) = 0, => P0=1,
P1 (сохранение 1): f(1,1,1) = 1, => P1=1,
PS (самодвойственность): f(x,y,z) = ⌐f(⌐x,⌐y,⌐z),
f(0,0,0) = 0 = ⌐f(⌐0,⌐0,⌐0) = ⌐f(1,1,1) = ⌐1 = 0,
f(0,0,1) = 0 <> ⌐f(⌐0,⌐0,⌐1) = ⌐f(1,1,0) = ⌐0 = 1,
=> PS = 0,
PM (монотонность): f(0,1,0) = 1, f(1,1,0) = 0, => PM = 0,
PL (линейность): f(x,y,z) = ⌐xyVxz = (x+1)yVxz = y+xy+xz,
=> PL = 0.
P0 = 1, P1 = 1, PS = 0, PM = 0, PL = 0.
Таблица 2.6
|
|
3 |
2 |
1 |
|
011 |
010 + |
01* |
|
|
010 |
011 + |
*11 |
|
|
101 |
101 + |
1*1 |
|
|
111 |
111 + |
|
|
Таблица 2.7
|
|
01* |
*11 |
1*1 |
|
011 |
(+) |
+ |
|
|
010 |
(+) |
|
|
|
101 |
|
|
(+) |
|
111 |
|
+ |
(+) |