1 Множества. Логика Буля - лекции
.pdfЕсли в СДНФ сделать замены
x1 x2 x1 x2 x1 x2 , x1 1 x1 ,
то получим совершенную полиномиальную нормальную форму (СПНФ)
представления булевых функций. Запишем еѐ, учитывая, что конституенты
не пересекаются ( CiC j |
): x1 |
x2 |
|
x1 x2 |
|
|
x1 x2 |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
y |
(x1 x2 |
f (0,0)) |
(x1 x2 f (1,0)) |
( x1 |
x2 f (0,0)x1 x2 |
f (1,0)) |
||||||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
C |
0 |
|
|
C |
0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
0 |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
(x1 x2 f (0,1)) |
(x1 x2 f (1,1)) |
(x1 x2 f (0,1) x1 x2 f (1,1)) |
|||||||||||||||||||||
((1 |
x1 )(1 |
x2 ) f (0,0)) |
(x1 (1 x2 ) f (1,0)) |
((1 |
|
x1 )x2 f (0,1)) |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
(x1 x2 f (1,1)) |
|
|
|
|
|
|
|
|
|
|
|
|
|||
(1 |
x1 x2 |
|
x1 x2 ) f (0,0) |
|
(x1 x1 x2 ) f (1,0) |
(x2 |
x1 x2 ) f (0,1) |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
(x1 x2 f (1,1)) |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
f (0,0) |
x1 ( f (0,0) |
|
f (1,0)) |
|
|
x2 ( f (0,0) |
f (0,1)) |
|||||||||||||||
|
|
|
|
|
|
|
|
x1 x2 ( f (0,0) |
|
f (1,0) |
|
f (0,1) |
f (1,1)) . |
|
В таблице 1 записаны все три совершенные формы всех элементарных функций двух переменных.
Табл. 1
y f (x1 , x2 ) |
|
|
|
|
|
|
|
СДНФ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
СКНФ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
СПНФ |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
f1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x |
|
x |
2 |
) (x |
|
x |
2 |
) (x |
|
|
|
x |
2 |
) (x |
|
|
|
x |
2 |
) |
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
||||||||||||||
f2 |
x1 |
x2 |
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x x |
2 |
) (x |
|
|
x |
2 |
) (x x |
2 |
) |
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
f3 |
x2 \ x1 |
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
x1 x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x1 |
x2 ) (x1 |
|
|
x2 ) (x1 |
|
|
x2 ) |
|
|||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
f4 |
|
x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
|
|
(x |
|
|
x |
2 |
) (x |
x |
2 |
) |
|
|
|
|
|
|
|
|
|
(x |
|
x |
2 |
) (x |
|
|
|
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
f5 |
x1 \ x2 |
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x1 x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
(x |
|
x |
2 |
) (x |
|
|
|
|
x |
2 |
|
) (x |
|
|
x |
2 |
) |
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
f6 |
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
|
|
|
(x |
|
|
|
x |
2 |
) (x |
x |
2 |
) |
|
|
|
|
|
|
|
|
|
(x |
|
x |
2 |
) (x |
|
|
|
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
f7 |
x1 |
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
|
(x |
|
|
|
x |
2 |
) (x |
x |
2 |
) |
|
|
|
|
|
|
|
|
|
(x |
x |
2 |
) (x |
|
|
|
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
f8 |
x1 |
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
x1 x2 |
||||||
(x x |
2 |
) (x x |
2 |
) (x |
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
35
f |
|
|
x |
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 x1 x2 |
x1x2 |
||||||
9 |
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
(x |
x |
2 |
) (x |
x |
2 |
) (x |
|
x |
2 |
) |
|||||||||||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
||||||||||||||
f10 |
|
x1 |
|
|
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 x1 |
x2 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x |
|
|
|
x |
2 |
|
) (x |
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x1 |
|
|
x2 ) (x1 |
|
|
x2 ) |
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 x1 |
|
|
f |
11 |
|
x |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x |
|
|
|
x |
2 |
|
) (x |
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x |
|
|
x |
2 |
) (x |
|
|
x |
2 |
) |
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
f12 |
|
x2 |
|
|
|
x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
1 x1 |
x1 x2 |
|||||
|
|
|
|
|
|
|
(x |
|
|
|
|
x |
2 |
) (x |
|
|
|
x |
2 |
) (x |
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 x2 |
|
|
f |
13 |
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
(x |
|
|
|
x |
2 |
|
) (x |
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x1 |
|
|
x2 ) (x1 |
|
|
x2 ) |
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
f14 |
|
x1 |
|
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
1 x2 |
x1 x2 |
||||||
|
|
|
(x |
|
|
|
x |
2 |
) |
|
|
|
|
(x |
|
|
|
|
x |
2 |
) |
|
|
(x |
|
|
|
|
x |
2 |
) x x |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
f15 |
x1 | x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
1 x1 x2 |
|||||||||||
|
|
|
(x |
|
|
|
|
|
x |
2 |
) |
(x |
|
|
|
x |
2 |
) |
(x |
|
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
f16 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|||||||
|
|
|
(x |
|
|
|
x |
2 |
) |
|
|
|
(x |
|
x |
2 |
) |
|
(x |
|
|
|
x |
2 |
) |
|
|
(x |
|
|
|
|
x |
2 |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Совершенные формы представления позволяют записать булеву
функцию аналитически по еѐ известной таблице истинности.
►Пример. Записать СДНФ, СКНФ, СПНФ функции трѐх переменных, заданной таблицей истинности (табл. 2).
|
|
|
Табл. 2 |
|
|
|
|
x1 |
x2 |
x3 |
f1 (x1 , x2 , x3 ) |
|
|
|
|
0 |
0 |
0 |
0 |
|
|
|
|
0 |
0 |
1 |
1 |
|
|
|
|
0 |
1 |
0 |
0 |
|
|
|
|
0 |
1 |
1 |
1 |
|
|
|
|
1 |
0 |
0 |
1 |
|
|
|
|
1 |
0 |
1 |
0 |
|
|
|
|
1 |
1 |
0 |
0 |
|
|
|
|
1 |
1 |
1 |
1 |
|
|
|
|
Решение. Выписывая соответствующие конъюнкты против единичных значений f, мы получим СДНФ:
fСДНФ x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 .
Если выпишем дизъюнкты против нулевых значений f, то получим СКНФ:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 ) . |
|
fСКНФ |
(x1 |
x2 |
x3 ) (x1 |
|
x2 |
x3 ) (x1 |
x2 x3 ) (x1 x2 |
||||||||||
|
|
|
|
x »: |
|||||||||||||
СПНФ образуем заменой в СДНФ « » на « |
» и « x » на «1 |
||||||||||||||||
fСПНФ |
(1 |
x1 )(1 |
x2 )x3 |
(1 |
x1 )x2 x3 |
x1 (1 |
x2 )(1 x3 ) |
x1 x2 x3 . |
В последнем выражении раскроем скобки и взаимно уничтожим все одинаковые слагаемые, входящие в формулу чѐтное число раз:
36
fСПНФ x1 x3 x1 x2 . ◄
Полиномиальные представления. Булевы функции с операциями сложения по модулю 2 и конъюнкцией изучал русский математик Жегалкин11. Поэтому многочлен, являющийся суммой по модулю 2 константы и различных одночленов, в которые каждая из переменных входит не выше чем в первой степени, называется многочленом Жегалкина.
Многочлен Жегалкина константы равен самой константе; многочлен Жегалкина булевой функции одной переменной имеет вид
f (x) a0 a1 x ;
многочлен Жегалкина булевой функции двух переменных имеет вид
f (x1 ; x2 ) |
a0 |
a1 x1 |
a2 x2 a12 x1 x2 ; |
|
многочлен Жегалкина булевой функции трѐх переменных имеет вид |
||||
f (x1 ; x2 ; x3 ) a0 a1 x1 |
a2 x2 |
a3 x3 |
a12 x1 x2 |
a13 x1 x3 a23 x2 x3 |
|
|
a123x1 x2 x3 |
|
|
и так далее. |
|
|
|
|
Коэффициенты a1, 2, ..., i |
и свободный член a0 |
принимают значения 0 |
или 1, а число слагаемых в формуле равно 2n , где n – число переменных. Используя следующие соотношения
x1 |
|
x2 |
|
x2 |
x1 , |
|
x1 (x2 |
|
x3 ) |
|
x1 x2 |
x1 x3 , |
|
|
x |
x |
0 , |
|
||
|
x |
0 |
x , |
|
||
|
|
|
|
|
x , |
|
|
|
x |
1 |
|
можно записать булеву функцию в виде многочлена Жегалкина и затем упростить эту запись.
►Пример. Известно, что f (0,0,0) f (0,1,1) f (1,0,1) f (1,1,0) 1.
Найти fСПНФ .
Решение. СДНФ данной функции имеет вид:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
fСДНФ (x1; x2 ; x3 ) |
|
x1 x2 x3 |
|
x1 x2 x3 |
x1 x2 x3 |
x1 x2 x3 . |
|||||||||||||||||
Тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
fСПНФ (x1 ; x2 ; x3 ) |
x1 x2 x3 |
x1 x2 x3 |
x1 x2 x3 |
x1 x2 x3 |
|||||||||||||||||||
(1 x1 )(1 x2 )(1 x3 ) |
(1 |
|
|
|
x1 )x2 x3 x1 (1 x2 )x3 |
x1 x2 (1 x3 ) |
|||||||||||||||||
1 x1 |
|
|
|
x2 |
|
|
|
|
x3 |
|
|
|
x1 x2 |
x1 x2 x3 . |
|
|
|
11 Иван Иванович Жегалкин (1869, Российская империя – 1947, СССР) – российский и советский математик, логик. Самое известное его открытие – полином Жегалкина. Получил алгоритмическое решение проблемы разрешимости в некоторых важных случаях.
37
Теорема Жегалкина. Любую булеву функцию f (x1 , x2 , ..., xn ) можно представить в виде многочлена Жегалкина.
Сформулируем два алгоритма построения многочлена Жегалкина. Любую функцию, отличную от константы 0, можно представить в
виде СДНФ. Таблицы истинности дизъюнкции и суммы по модулю 2 отличаются только последней строкой, то есть на наборе 11. Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю 2. Кроме того, известно, что
x x 1. На этом и основан
первый алгоритм построения многочлена Жегалкина:
1.Находим множество тех двоичных наборов, на которых функция принимает значение 1.
2.Составляем СДНФ.
3.В СДНФ каждый знак дизъюнкции меняем на знак суммы по
модулю 2
4.Упрощаем, если можно, полученное выражение, используя тож-
дество xi xi 1.
5. В полученной формуле каждое отрицание xi заменяем на xi 1.
6.Раскрываем скобки в полученной формуле, содержащей только
функции |
и и константу 1. |
|
|
7. |
Приводим подобные члены, используя тождество xi |
xi |
0 . |
Используя метод неопределѐнных коэффициентов, получаем |
|
||
|
второй алгоритм определения многочлена Жегалкина: |
|
|
Составляем систему линейных уравнений относительно |
2n |
неиз- |
вестных коэффициентов, содержащую 2n уравнений, решением которой
являются коэффициенты a0 , a1 , ..., a1, 2, ..., n |
многочлена Жегалкина. |
|
||||||||||||||||||||||||||||||||||||
►Пример. Для данной булевой функции трѐх переменных |
|
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f (x1; x2 ; x3 ) |
|
x2 |
(x1 x3 ) | (x2 | x3 ) |
|
|
|
|
|
|
|
|
||||||||||||||||||||
а) построить таблицу истинности, найти двоичную форму F булевой |
||||||||||||||||||||||||||||||||||||||
функции и привести функцию к СДНФ и СКНФ; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
б) найти двумя способами многочлен Жегалкина. |
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
Решение. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
а) |
Обозначим |
x1 x3 |
1 , |
|
x2 | x3 |
2 , |
|
|
|
|
(x2 | x3 ) 2 |
3 , |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(x1 x3 ) | (x2 | x3 ) 4 |
1 | 3 , x2 |
(x1 |
x3 ) | (x2 | x3 ) |
|
|
x2 |
4 . |
|
|
|
|
|
38
|
x1 |
x2 |
x3 |
|
|
|
|
|
x |
|
|
f1 |
f 2 |
|
f3 |
f 4 |
f5 |
|
|
x |
2 |
|
|
3 |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
0 |
0 |
0 |
|
1 |
|
1 |
|
0 |
0 |
|
1 |
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
0 |
0 |
1 |
|
1 |
|
0 |
|
1 |
1 |
|
0 |
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
0 |
1 |
0 |
|
0 |
|
1 |
|
0 |
1 |
|
0 |
1 |
0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
0 |
1 |
1 |
|
0 |
|
0 |
|
1 |
1 |
|
0 |
1 |
0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
1 |
0 |
0 |
|
1 |
|
1 |
|
1 |
0 |
|
1 |
0 |
0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
1 |
0 |
1 |
|
1 |
|
0 |
|
1 |
1 |
|
0 |
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
1 |
1 |
0 |
|
0 |
|
1 |
|
1 |
1 |
|
0 |
1 |
0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
1 |
1 |
1 |
|
0 |
|
0 |
|
1 |
1 |
|
0 |
1 |
0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Двоичная форма имеет вид: |
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
F=11000100. |
|
|
|
|||||
Наборы, на которых f (x1 ; x2 ; x3 ) |
1, следующие: |
|
|
||||||||||||||
|
|
|
|
|
|
|
(0;0;0), (0;0;1) , (1;0;1) . |
|
|
|
Значит, СДНФ функции имеет вид:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 ) . |
|
|
|
|
f (x1; x2 ; x3 ) (x1 |
|
|
|
|
x2 |
|
|
x3 ) (x1 |
|
|
|
x2 |
|
x3 ) (x1 |
|
x2 |
|||||||||||||||||||||||||||
Наборы, на которых f (x1 ; x2 ; x3 ) |
|
0 , следующие: |
|
|
|
||||||||||||||||||||||||||||||||||||||||||
(0;1;0) , (0;1;1) , (1;0;0) , (1;1;0) , (1;1;1) . |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
СКНФ функции имеет вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
f (x1 ; x2 ; x3 ) |
|
|
|
(x1 |
|
|
x2 |
|
x3 ) (x1 |
|
|
x2 |
|
x3 ) (x1 |
|
x2 |
x3 ) |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
(x1 |
|
x2 |
x3 ) (x1 |
|
x2 |
x3 ) . |
|
|
|
|||||||||||||||||||||||||||
б) Построим многочлен Жегалкина первым способом: |
|
||||||||||||||||||||||||||||||||||||||||||||||
в СДНФ функции |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
(x1 |
|
x2 |
x3 ) (x1 |
x2 |
x3 ) (x1 x2 |
x3 ) |
|
||||||||||||||||||||||||||||||||||
заменяем знак дизъюнкции знаком суммы Жегалкина: |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 ) , |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
(x1 x2 x3 ) (x1 |
|
|
x2 |
|
x3 ) |
(x1 |
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
из первой и второй конъюнкции выносим за скобки выражение x1 x2 :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 ) ; |
|
(x1 x2 ) (x3 |
x3 ) |
(x1 |
|
x2 |
x3 ) |
(x1 |
|
|
x2 ) |
(x1 |
|
x2 |
|||||||||||||||||
делаем замены: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
1, |
|
|
|
|
|
|
1. |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
x1 |
x1 |
|
|
x2 |
|
x2 |
|
|
|
|
||||||||||
Тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
(( x1 |
1) |
|
(x2 |
1)) |
(( x1 |
|
|
|
(x2 |
1) |
x3 ) . |
|
||||||||||
Далее раскрываем скобки: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
x1 |
x2 |
|
|
x2 |
|
x1 |
1 x1 |
x2 |
|
x3 |
x1 |
|
x3 |
|
|||||||||
|
|
|
|
|
|
x1 x2 x3 x1 x2 |
|
x1 |
|
|
|
x3 |
x1 |
x2 |
1. |
||||||||||||||
39 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Многочлен Жегалкина имеет вид:
|
|
f (x1 ; x2 ; x3 ) x1 x2 x3 |
x1 x2 x1 x3 |
x1 |
x2 |
1. |
||||||
Построим многочлен Жегалкина методом неопределѐнных коэффи- |
||||||||||||
циентов. Составляем восемь уравнений: |
|
|
|
|
|
|
||||||
f (0;0;0) |
a0 |
1, |
|
|
|
|
|
|
|
|
a0 |
1. |
f (0;0;1) |
a0 |
a3 |
1, |
|
|
1 |
a3 |
1, |
|
|
a3 |
0 . |
f (0;1;0) |
a0 |
a2 |
0 , |
|
|
1 |
a2 |
0 , |
|
a2 |
1. |
|
f (0;1;1) |
a0 |
a2 |
a3 |
a23 |
0, |
1 |
1 |
0 |
a23 |
0 , a23 |
0 . |
|
f (1;0;0) |
a0 |
a1 |
0 , |
|
|
1 |
a1 |
0 , |
|
|
a1 |
1. |
f (1;0;1) |
a0 |
a1 |
a3 |
a13 |
1, |
1 |
1 |
0 |
a13 |
1, |
a13 |
1. |
f (1;1;0) |
a0 |
a1 |
a2 |
a12 |
0 , |
1 |
1 |
1 |
a12 |
0 , |
a12 |
1. |
f (1;1;1) |
a0 |
a1 |
a2 |
a3 |
a12 |
a13 |
a23 |
a123 |
0 , |
|
|
|
|
1 1 1 0 1 1 0 |
a123 |
0 , |
|
|
|
a123 |
1. |
||||
Многочлен Жегалкина имеет вид: |
|
|
|
|
|
|
||||||
f (x1 ; x2 ; x3 ) x1 |
x2 |
x3 |
x1 |
x2 |
x1 |
x3 |
x1 |
x2 |
1.◄ |
|||
Линейные и |
нелинейные |
булевы функции. |
Многочлен |
Жегалкина |
называется нелинейным, если он содержит конъюнкции переменных, а если он не содержит конъюнкции переменных, то он называется линейным.
Функция f (x1 , x2 , ..., xn ) называется |
линейной, если еѐ многочлен |
|||
Жегалкина имеет вид |
|
|
|
|
f (x1 ; x2 ;...; xn ) |
a0 |
a1 x1 |
... an xn , |
|
и нелинейной в противном случае. |
|
|
|
|
Из определения многочлена Жегалкина следует, что для любой бу- |
||||
левой функции коэффициенты при переменных |
x1 , x2 , ..., xn и свободный |
|||
член вычисляются по формулам: |
|
|
|
|
|
a0 |
f (0;0;...;0) , |
|
|
a1 |
f (0;0;...;0) |
f (1;0;...;0) , |
||
a2 |
f (0;0;...;0) |
f (0;1;0;...;0) , |
||
|
|
… |
|
|
an |
f (0;0;...;0) |
f (0;0;...;0;1) . |
На этом основан
алгоритм определения линейности (или нелинейности) булевой функции.
1. По таблицам истинности функции f (x1 , x2 , ..., xn ) и выше указанным формулам находим коэффициенты a0 , a1 , ..., an .
40
2. Выписываем многочлен (x1 ; x2 ;...; xn ) a0 a1 x1 ... an xn и проверяем, задаѐт ли он эту функцию. Для этого строим таблицу истинности многочлена (x1; x2 ;...; xn ) и сравниваем еѐ с таблицей истинности
функции f (x1 , x2 , ..., xn ) .
Если таблицы истинности совпадают, то функция f (x1 , x2 , ..., xn ) линейная и (x1; x2 ;...; xn ) – еѐ многочлен Жегалкина. Иначе функция не-
линейная.
►Пример. Проверить на линейность функцию f (x1 ; x2 ; x3 ) с двоичным набором
F=11100001.
Решение.
Применяем к функции f (x1 ; x2 ; x3 ) алгоритм проверки на линей-
ность. |
|
|
|
|
|
Вычислим коэффициенты a0 , a1 , a2 , a3 |
многочлена Жегалкина для |
||||
данной функции: |
|
|
|
|
|
|
a0 |
f (0;0;0) |
1, |
|
|
a1 |
f (0;0;0) |
f (1;0;0) |
1 |
0 |
1, |
a2 |
f (0;0;0) |
f (0;1;0) |
1 |
1 |
0 , |
a3 |
f (0;0;0) |
f (0;0;1) |
1 |
1 |
0 . |
Вычисляем многочлен
|
(x1; x2 ; x3 ) a0 |
a1 x1 a2 x2 |
a3 x3 x1 |
1. |
Очевидно, |
что двоичный |
набор |
F=11110000 |
многочлена |
(x1 ; x2 ; x3 ) x1 |
1 не совпадает с двоичным набором булевой функции |
F=11100001, следовательно, функция f (x1 ; x2 ; x3 ) не линейна. ◄
41
ЛЕКЦИЯ 6. КЛАССЫ БУЛЕВЫХ ФУНКЦИЙ
Классы булевых функций. Представление функций в СДНФ и СКНФ образовано тремя операциями – дизъюнкцией, конъюнкцией, отрицанием, а в СПНФ – сложением по модулю два, конъюнкцией и единицей как операцией. Возникает вопрос: через какие ещѐ системы логических операций можно выразить произвольную булеву функцию? Чтобы ответить на него, определим пять классов функций.
Булева функция f (x1 , x2 , ..., xn ) сохраняет константу 0, если
|
|
|
|
|
|
|
f (0, 0, ..., 0) |
0 . |
|
|
|
|
|
|
|
||||||||
Множество всех таких функций образует 0-класс (в частности, |
|||||||||||||||||||||||
функции f1 ( x1 , x2 ) , …, |
f8 ( x1 , x2 ) из табл. 2 лекции 2). |
|
|
|
|
|
|
||||||||||||||||
►Пример. Определить, принадлежит ли функция |
f |
x |
y |
0- |
|||||||||||||||||||
классу. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Решение. Так как |
f (0, 0) |
0 |
|
0 |
|
0 , |
|
то функция |
f |
x |
y принад- |
||||||||||||
лежит 0-классу. ◄ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Булева функция |
f |
сохраняет константу 1, если |
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
f (1, 1, ...,1) |
1. |
|
|
|
|
|
|
|
||||||||
Множество всех таких функций образует 1-класс (в частности, |
|||||||||||||||||||||||
функции с чѐтным индексом |
f2 ( x1 , x2 ) , |
f4 ( x1 , x2 ) , … из табл. 2 лекции 2). |
|||||||||||||||||||||
►Пример. Определить, принадлежит ли функция |
f |
x |
y |
1- |
|||||||||||||||||||
классу. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Решение. |
Так как |
f (1, 1) |
1 1 |
1, то функция |
f |
x |
y |
принадле- |
|||||||||||||||
жит 1-классу. ◄ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Булева функция |
f |
называется линейной, |
если еѐ можно записать в |
||||||||||||||||||||
следующем виде: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
f (x1 , x2 , ..., xn ) a0 |
|
|
a1 x1 |
|
|
a2 x2 ... |
an xn , |
|
|
|
||||||||||
где ai |
{0, 1}, i |
0, 1, 2, ..., n . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Множество всех линейных булевых функций образует 2-класс (в |
|||||||||||||||||||||||
частности, |
функция |
эквивалентность |
f10 ( x1 , x2 ) |
линейная, |
так |
|
как |
||||||||||||||||
f10 ( x1 , x2 ) x1 |
x2 1 |
x1 |
x2 , а стрелка Пирса за счѐт нелинейного сла- |
||||||||||||||||||||
гаемого |
x1 |
x2 |
нелинейная: |
f9 ( x1 , x2 ) |
x1 |
x2 |
1 x1 |
x2 |
x1 |
x2 ). |
|
||||||||||||
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Функция g(x1 , x2 , ..., xn ) |
f (x1 , x2 , ..., xn ) называется двойственной к |
||||||||||||||||||||||
функции f |
и обозначается f * . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
42
Например, |
(x |
x |
2 |
)* |
x |
|
x |
2 |
x |
x |
2 |
. То есть, функция |
x |
x |
2 |
– |
|
1 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
||||
двойственная к x1 |
x2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблицы истинности этих двойственных функций имеют вид:
x1 |
x2 |
x1 x2 |
|
|
|
0 |
0 |
0 |
|
|
|
0 |
1 |
0 |
|
|
|
1 |
0 |
0 |
|
|
|
1 |
1 |
1 |
|
|
|
x1 |
x2 |
|
x |
|
x |
2 |
|
|
|
|
1 |
|
|
|
|
0 |
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
|
|
|
|
|
x1 |
|
x2 x1 x2 |
||||
|
|
|
|
|||
|
|
|
|
|
||
0 |
0 |
|
|
0 |
||
|
|
|
|
|
||
0 |
1 |
|
|
1 |
||
|
|
|
|
|
||
1 |
0 |
|
|
1 |
||
|
|
|
|
|
||
1 |
1 |
|
|
1 |
||
|
|
|
|
|
|
|
Легко заметить, что для получения значений двойственной функции нужно «перевернуть» столбец значений исходной функции, а затем заменить в нѐм 0 на 1, а 1 – на 0.
|
►Пример. Найти двоичный набор функции f * |
двойственной |
f , ес- |
|||||||
ли двоичный набор f имеет вид: |
F |
0010. |
|
|
|
|||||
|
|
|
|
|
то двоичный набор функции f * |
|
||||
|
Решение. Так как F |
1101 , |
имеет |
|||||||
вид: F * |
1011 . ◄ |
|
|
|
|
|
|
|||
|
Булева функция f называется самодвойственной, если она совпада- |
|||||||||
ет с двойственной себе функцией |
f * , то есть |
f f * . |
|
|
||||||
|
Множество всех таких функций образует 3-класс (например, функ- |
|||||||||
ции |
f3 ( x1 , x2 ) , f4 ( x1 , x2 ) |
из |
табл. 2 |
лекции |
2, функции |
f x , |
||||
f |
xy |
xz yz ). |
|
|
|
|
|
|
Для самодвойственных функций необходимо и достаточно, чтобы на любых двух противоположных наборах значений переменных функция принимала разные значения.
►Пример. Определить, является ли функция f , имеющая двоичный
набор
а) F 10101110,
б) F 01110001
самодвойственной.
43
Решение. а) Так как значения на третьем месте в начале строки и на третьем месте в конце строки одинаковые (1), то функция f – не самодвойственная.
б) На первых местах в начале и в конце строки находятся противоположные числа (0 и 1), на вторых – противоположные числа (1 и 0), на третьих – противоположные числа (1 и 0), на четвѐртых – противополож-
ные числа (1 и 0). Поэтому функция |
f – самодвойственная. ◄ |
|
|
|
||||||||||||||||||||||||||||
|
|
Булева функция |
f |
называется монотонной, если она удовлетворяет |
||||||||||||||||||||||||||||
неравенству |
f (x1 , x2 , ..., xn ) |
|
f (x1 , x2 , ..., xn |
) при |
x1 |
|
x1 , |
x2 |
x2 , |
…, |
||||||||||||||||||||||
xn |
xn . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
Например, пусть x1 |
0 , x1 |
|
0 , x2 |
1, |
x2 |
1, тогда для дизъюнкции |
||||||||||||||||||||||||
имеем: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
(x1 |
x2 |
1) (x1 |
x2 |
1) . |
|
|
|
|
|
|
|
|
|||||||||
|
|
Какие бы наборы x1 , x1 , x2 , |
|
x2 |
мы не брали, |
если выполняются |
||||||||||||||||||||||||||
условия x1 |
x1 , |
x2 |
x2 , |
то для дизъюнкции всегда |
f |
|
f |
. Значит, дизъ- |
||||||||||||||||||||||||
юнкция – функция монотонная. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
Множество всех монотонных функций образует 4-класс. |
|
|
|
|
||||||||||||||||||||||||||
|
|
►Пример. Определить, является ли монотонной функция, заданная |
||||||||||||||||||||||||||||||
двоичным набором F |
01011001. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
Решение. |
Так |
как |
(1, 0, 0) |
(1, 0, 1) , |
а |
f (1, 0, 0) |
1 |
|
f (1, 0, 1) |
0 , |
||||||||||||||||||||
функция не является монотонной. ◄ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
Принадлежность элементарной функции к тому или иному классу |
||||||||||||||||||||||||||||||
отмечена единицей в табл. 1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Табл. 1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
f1 |
|
f 2 |
|
f3 |
|
f 4 |
f5 |
|
f6 |
|
f7 |
|
f8 |
|
f9 |
|
f10 |
|
f11 |
|
f12 |
|
f13 |
|
f14 |
f15 |
|
f16 |
|||
0 |
1 |
|
1 |
|
1 |
|
1 |
1 |
|
|
1 |
|
1 |
|
1 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
1 |
|
0 |
|
1 |
0 |
|
|
1 |
|
0 |
|
1 |
|
0 |
|
1 |
|
0 |
|
1 |
|
0 |
|
|
1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
1 |
|
0 |
|
0 |
|
1 |
0 |
|
|
1 |
|
1 |
|
0 |
|
0 |
|
1 |
|
1 |
|
0 |
|
1 |
|
|
0 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
0 |
|
0 |
|
0 |
|
1 |
0 |
|
|
1 |
|
0 |
|
0 |
|
0 |
|
0 |
|
1 |
|
0 |
|
1 |
|
|
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
1 |
|
1 |
|
0 |
|
1 |
0 |
|
|
1 |
|
0 |
|
1 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
0 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Базисные системы булевых функций. В логике Буля действует прин-
цип суперпозиции: вместо аргументов любой булевой функции можно подставить другие булевы функции, в частности, аргументы.
44