Displaying similar documents to “A proof of the completeness theorem of Grödel”

Essential Arity Gap of Boolean Functions

Shtrakov, Slavcho (2008)

Serdica Journal of Computing

Similarity:

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...