Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/386

 Title: Essential Arity Gap of Boolean Functions Authors: Shtrakov, Slavcho Keywords: Essential VariableIdentification MinorEssential 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. URI: http://hdl.handle.net/10525/386 ISSN: 1312-6555 Appears in Collections: Volume 2 Number 3

Files in This Item:

File Description SizeFormat