A set L of linear polynomials in variables X-1, X-2,...,X-n with real coefficients is said to be an essential cover of the cube {0, 1}(n) if(E1) for each v is an element of {0, 1}(n), there is a p is an element of L such that p(v) = 0;(E2) no proper subset of L satisfies (E1), that is, for every P is an element of L, there is a v is an element of {0, 1}(n) such that p alone takes the value 0 on v;(E3) every variable appears (in some monomial with non-zero coefficient) in some polynomial of L.Let e (n) be the size of the smallest essential cover of {0, 1}(n). In the present note we show that1/2(root 4n + 1 + 1)<= e(n)<= [n/2] + 1(c) 2004 Elsevier Inc. All rights reserved.
展开▼
