Minimal polynomials for the conjunction of functions on disjoint variables can be very simple (Q1823964): Difference between revisions

Let \(f_ i\) be Boolean functions in the variables \(x_{i1},...,x_{in_ i}\) \((i=1,...,r)\) and \(\circ \in \{\wedge,\vee \}\). Define \((f_ 1\circ...\circ f_ r)(x_{11},...,x_{\ln_ 1},...,x_{r1},...,x_{rn_ r})=f_ 1(x_{11},...,x_{1n_ 1})\circ...\circ f_ r(x_{r1},...,x_{rn_ r}).\)Let further the cost of a polynomial be either the number of monomials or the number of literals, and denote by MP(f) the minimal cost of a polynomial representing the Boolean function f. Then \(MP(f_ 1\vee...\vee f_ r)=MP(f_ 1)+...+MP(f_ r)\) if no \(f_ i\) is the constant 1 (Theorem 1), while \(MP(f_ 1\wedge...\wedge f_ r)=MP(f_ 1)\cdot...\cdot MP(f_ r)\) in the classes of monotone functions (Theorem 3) and symmetric functions (Theorem 5).