Minimal polynomials for the conjunction of functions on disjoint variables can be very simple (Q1823964)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimal polynomials for the conjunction of functions on disjoint variables can be very simple |
scientific article |
Statements
Minimal polynomials for the conjunction of functions on disjoint variables can be very simple (English)
0 references
1989
0 references
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).
0 references
Boolean functions
0 references
number of monomials
0 references
number of literals
0 references
minimal cost of a polynomial
0 references
monotone functions
0 references
symmetric functions
0 references