On the effect of variable identification on the essential arity of functions

Abstract

We show that every function of several variables on a finite set of k elements with n>k essential variables has a variable identification minor with at least n-k essential variables. This is a generalization of a theorem of Salomaa on the essential variables of Boolean functions. We also strengthen Salomaa's theorem by characterizing all the Boolean functions f having a variable identification minor that has just one essential variable less than f.

10 pages

Cited by in corpus (6)

• Generalizations of Swierczkowski's lemma and the arity gap of finite functions
• Decompositions of functions based on arity gap
• The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
• A complete classification of equational classes of threshold functions included in clones
• The arity gap of polynomial functions over bounded distributive lattices
• Additive decomposability of functions over abelian groups