2015-05-20
280
Определение. Система функций {f1, f2,..., fs,...} 
P2 называется полной в Р2, если любая функция f(x1,..., xn) Î P2 может быть записана в виде формулы через функции этой системы.
Полными системами, например, являются само 
или множество 
, так как каждая функция может быть представлена в виде СДНФ или СКНФ, где используются только эти связки. Примерами неполных систем являются 
или 
.
Лемма (достаточное условие полноты).
Пусть система 
U = { f 1, f 2,..., fs,...} полна в Р 2, 
– диагностическая система. Пусть B = { g 1, g 2,..., gk,...} – некоторая система из Р 2, причем любая функция fi Î U может быть выражена формулой над B, тогда система B полна в Р 2.
Доказательство. Пусть h(x1,..., xn) Î P2; так как U полна в Р2, то h(x1,..., xn) =N[f1,..., fs,...] = N[L1[g1,..., gk,...],..., Ls[g1,..., gk,...],...] = = 
[g1,..., gk]. Здесь мы воспользовались тем, что для любого i 
n fi может быть выражена формулой над B, поэтому fi=Li[gi,..., gk,...].
С помощью леммы докажем полноту некоторых важных систем.
1. Система 
полна в .
Возьмем в качестве полной в Р 2 системы U ={ x 1Ú x 2, 
, x 1& x 2}, B ={ x 1Ú x 2, }. Надо показать, что x 1& x 2 представляется формулой над B. Действительно, по правилу Де Моргана получим x 1& x 2= 
.
2. Система { x 1& x 2, } – полна в Р 2. 
3. Система { x 1| x 2} полна в Р 2. Для доказательства возьмем в качестве полной в Р 2 системы U = { x 1& x 2, } и выразим х 1& х 2 и 
через х 1| x 2 :
= x 1 | x 1, x 1 & x 2 = 
= (x 1| x 2)|(x 1| x 2).
4. Система { x 1 
x 2} полна в Р 2. U = { x 1Ú x 2, 
}, = x 1 x 1, x 1Ú x 2 = = 
= (x 1 x 2) (x 1 x 2).
5. Система { x 1& x 2, x 1Å x 2, 0, 1}, U = { x 1& x 2, }, = x 1Å1.
