2015-06-28
4227
Замыканием множества булевых функций N называется множество [ N ]всех суперпозиций функций из множества N. Свойства замыканий:
1) N Í [ N ];
2) [[ N ]] = [ N ];
3) N 1 Í N 2 Þ [ N 1 ] Í [ N 2];
4) [ N 1] È [ N 2] Í [ N 1 È N 2].
Доказательство. Свойство 1) имеет место при условии, что булевые функции из множества N мы рассматриваем как результат применения операции суперпозиции.
2) " f Î [[ N ]] Þ f = C (h 1 ,…,hn), hi Î[ N ],1£ i £ n Þ hi = Ci (g 1 ,…,gm), gj Î N, 1 £ j £ m Þ f =C (C 1(g 1 ,…,gm) ,…,Cn (g 1 ,…,gm)) Þ f Î[ N ] Þ [ [ N ] ] Í[ N ].Обратное включение следует из свойства 1.
3) " f Î [ N 1] Þ f =C (g1,…,gm), gi Î N 1Þ gi Î N 2, i = 
Þ f Î [ N 2] Þ [ N 1] Í [ N 2].
4) " f Î [ N 1] È [ N 2] Þ f = C (g 1, …,gn), gi Î N 1 Ú gi Î N 2, Þ
gi Î N 1È N 2 Þ f Î [ N 1 È N 2] Þ [ N 1] È [ N 2] Í [ N 1È N 2 ].■
Множество N называется замкнутым, если [ N ] = N. Для доказательства замкнутости множества, очевидно, достаточно доказать, что любая суперпозиция функции из множества вновь функция из этого же множества. Пять важнейших замкнутых классов: Т 0 = { f | f (0,…, 0) = 0}, Т 1 = { f | f (1,…, 1) = 1}, L = { f | f = e 0Å e 1 x 1 Å … Å enxn, ei = 0 Ú 1}, 
– класс монотонных булевых функций, S = { f | f = f *}. Обозначим через Р 2 множество всех булевых функций. Класс N булевых функций называется полным, если [ N ] = Р 2. Для доказательства полноты класса, очевидно,достаточно доказать, что любую булеву функцию можно представить в виде суперпозиции функций из этого класса. Множество булевых функций называется независимым, если ни одна из них не является суперпозицией остальных функций этого множества. Полная независимая система булевых функций называется базисом Р 2. Функции конъюнкция, дизъюнкция и отрицание образуют полный класс, но не базис, так как дизъюнкция – суперпозиция конъюнкции и отрицания. Система {0, 1, Ù, Å }полна, так как любую булеву функцию можно представить в виде полинома Жегалкина.
|
|
|
ТЕОРЕМА. Если каждая булева функция полного класса может быть представлена в виде суперпозиции булевых функций другого класса, то и этот класс полный.
Доказательство. Даны два класса булевых функций N 1 = { f 1, …}и N 2 = { g 1,…}.Первый класс полный, и каждая его функция – суперпозиция функции второго класса.
" f Î P 2 Þ f = C (f 1, …), fi = Ci(g1, …)Þ f Î [ N 2] Þ P 2 Í [ N 2] Þ P 2 = [ N 2].
