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...
Given an n-ary k-valued function f, gap(f) denotes the essential arity gap of f which is the minimal number of essential variables in f
which become fictive when identifying any two distinct essential variables in f.
In the present paper we study the properties of the symmetric function
with non-trivial arity gap (2 ≤ gap(f)). We prove several results concerning
decomposition of the symmetric functions with non-trivial arity gap with
its minors or subfunctions. We show that all non-empty sets of...
Given an n-ary k-valued function f, gap(f) denotes the minimal number of essential variables in f which become fictive when identifying any two distinct essential variables in f.
We particularly solve a problem concerning the explicit determination of n-ary k-valued functions f with 2 ≤ gap(f) ≤ n ≤ k. Our methods yield new combinatorial results about the number of such functions.
Download Results (CSV)