IMI-BAS BAS
 

BulDML at Institute of Mathematics and Informatics >
IMI >
IMI Periodicals >
Serdica Journal of Computing >
2008 >
Volume 2 Number 3 >

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 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.
URI: http://hdl.handle.net/10525/386
ISSN: 1312-6555
Appears in Collections:Volume 2 Number 3

Files in This Item:

File Description SizeFormat
sjc062-vol2-num3-2008.pdf159.39 kBAdobe PDFView/Open

 



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0!   Creative Commons License DSpace Software Copyright © 2002-2009  The DSpace Foundation - Feedback