Minimal polynomials for the conjunction of functions on disjoint variables can be very simple
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).
- Boolesche Minimalpolynome und Überdeckungsprobleme
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- On covering a product of sets with products of their subsets
- On the complexity of 2-output Boolean networks
- On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
- Realizing Boolean functions on disjoint sets of variables
- Strong versions of Sperner's theorem
This page was built for publication: Minimal polynomials for the conjunction of functions on disjoint variables can be very simple
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823964)
