Essential Variable Identification Minor Essential Arity Gap
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Serdica Journal of Computing, Vol. 2, No 3, (2008), 249p-266p
In this paper we investigate the Boolean functions with maximum essential arity gap. Additionally we propose a simpler proof of an
important theorem proved by M. Couceiro and E. Lehtonen in . They use Zhegalkin’s polynomials as normal forms for Boolean functions and describe the functions with essential arity gap equals 2. We use to instead Full Conjunctive Normal Forms of these polynomials which allows us to simplify the
proofs and to obtain several combinatorial results concerning the Boolean
functions with a given arity gap. The Full Conjunctive Normal Forms are
also sum of conjunctions, in which all variables occur.