Evaluation, strength, and relevance of variables of Boolean functions

Given a Boolean function f, we define the importance of a set S of variable s by an expression measuring to what extent the variables in S determine th e value of f. This "evaluation" uses a "constancy" measure which is assumed to be a real-valued convex function defined on [0, 1]. In spite of the gen erality of the constancy measure, it is shown that any such evaluation is i n strong agreement with the classical concept of the Winder-strength of var iables of a monotone Boolean function. Further, we study a special class of evaluations called relevances, characterize completely the cases of extrem e relevance value, relating the sets of maximum relevance to fictitious (du mmy) variables and support sets, and establish a lower bound on the relevan ce of sets "containing" implicants or implicates of a Boolean function.