Local properties of Boolean functions I: injectivity

AbstractThis work inaugurates a cycle of papers based on the following common idea. Given a property P(f) which is defined for Boolean functions ƒ: Bn→B, introduce and study a suitable “local” property p(ƒ, X) depending both on the function ƒ and on a point X∈Bn in such a way that for every Boolean function ƒ, property P(ƒ) is true if and only if p(ƒ, X>) holds for every X∈Bn.The first article of the series deals with local injectivity, showing in particular that for n ≔ 1 local injectivity coincides with global injectivity, whereas for n > 1 there is no injective Boolean function (in the classical sense). Two forthcoming papers will study local isotony and applications to extremal solutions of Boolean equations