Полнота систем булевых функций
Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Полные системы булевых функций.
Линейная булева функция f ( x1 , x2 ,...,xn ) c0 c1x1 c2 x2 ... cn xn
c0 c1 f (1,0,...,0)
a 0 0, a 0 a
с0 , с1,...,сn 0,1
a 1 a,
c0 f (0,0,...,0)
aa 0
c1 c0 f (1,0,...,0)
c0 c2 f (0,1,...,0)
…
c0 cn f (0,0,...,1)
c2 c0 f (0,1,...,0)
…
cn c0 f (0,0,...,1)
Метод неопределенных коэффициентов
c0 f (0,0,...,0)
f ( x, y) x y
c0 0 0 0, c1 0 (1 0) 0 1 1, c2 0 (0 1) 0 1 1
c0 c1x c2 y 0 1 x 1 y x y
Теорема Жегалкина. Всякая булева функция представима в виде
полинома Жегалкина: f ( x1, x2 ,..., xn )
(i ,i ,...,i )
xi1 xi2 ...xik c
1 2
k
1. Приводим формулу в СДНФ.
2. Заменяем знаки дизъюнкции на кольцевые суммы.
x y x y xy
3. Избавляемся от отрицаний x 1 x.
4. Используем дистрибутивность конъюнкции относительно кольцевой суммы
x( y z ) xy xz.
5. Сокращаем парные конъюнкты x x 0, x 0 x.
( x, y, z ) x yz x yz x y z x yz x yz x y z ( x 1)( y 1) z ( x 1) yz x( y 1)( z 1)=
xyz xz yz z xyz yz xyz xy xz x z xyz xy x
Полная система булевых функций
,,, ,,1
Классы Поста:
1) T0 f ( x1, x2 ,...,xn ) | f (0,...,0) 0
2) T1 f ( x1, x2 ,...,xn ) | f (1,...,1) 1
3) T* f ( x1, x2 ,..., xn ) | f f *
4) TM f ( x1, x2 ,..., xn ) | f ( ) f ( )
5) TL f ( x1, x2 ,..., xn ) | f c0 c1x1 ... cn xn
Теорема. Классы Поста
попарно различны, не пусты
и не совпадают с P2
T0
T1 T* TM TL
+
+
+
1
+
+
+
x
+
+
+
+
x y +
Теорема. Классы Поста замкнуты.
1) f ( x1, x2 ,..., xn ), f1( x1, x2 ,..., xn ), f 2 ( x1, x2 ,..., xn ),..., f n ( x1, x2 ,..., xn ) T0
( x1, x2 ,..., xn ) f ( f1( x1, x2 ,...,xn ), f 2 ( x1, x2 ,..., xn ),..., f n ( x1, x2 ,..., xn ))
(0,0,...,0) f ( f1(0,0,...,0), f 2 (0,0,...,0),..., f n (0,0,...,0)) f (0,0,...,0) 0
Далее самостоятельно.
T0
Теорема (критерий Поста). Система булевых функций полна тогда и только
тогда, когда она не содержится целиком ни в одном из классов Поста.
, - дизъюнктивный базис Буля. ,,1 - базис Жегалкина
Теорема о четырех функциях. Каждый базис содержит не более четырех
булевых функций.
f0 T0 , f1 T1, f L TL , f M TM , f* T*
{ f0 , f1, f L , f M , f*}
f0 : f (0,0,...,0) 1
f0 (1,1,...,1) 0 f0 T1, f0 TM
{ f0 , f L , f*} - полная система
f0 (1,1,...,1) 1 f0 T*
{ f0 , f1, f L , f M } - полная система
