Essential Variable Identification Minor Essential Arity Gap
Issue Date:
2008
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 2, No 3, (2008), 249p-266p
Abstract:
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 [3]. 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.
