What could be a distance metric between boolean functions or a set of sets? Is it possible to defined a metric (with triangle inequality etc.) for boolean functions? Hence a real number which specifies how equal two boolean functions X and Y are (both mapping a set of boolean variables to a boolean outcome). Equivalently this would be a metric between a set of discrete sets.
 A: Will the Hamming distance work for you? The distance between two subsets of your set of variables is the cardinality of the symmetric difference: the number of elements in one but not both.
This is just the taxicab metric when you use the natural representation of subsets as bit vectors. It's well known: see https://en.wikipedia.org/wiki/Hamming_distance .
A: I know this is an old question, but I faced with a similar problem recently which took me to here. For my problem, I was trying to find an intuitive distance between two sets. As Ethan Bolker suggested, I first tried the size of the cardinality of the symmetric difference. But with this definition, the distance between the following sets are two:
$$A=\{a, b\}, B=\{b, c\}\implies |A \bigtriangleup B| = |\{a, c\}| = 2$$
But this was not what I was looking for. Because for my scenario, it would be more reasonable to have a distance of 1 between $A$ and $B$, since there is only one edit operation to convert $A$ into $B$ or vice versa, which is substituting $a$ with $c$. That is, I needed an edit distance allowing substitutions such as the Levenshtein distance but for discrete sets instead of strings.
After a literature search, I couldn't find any edit distance definition for discrete sets but I find this repository which implements a set edit distance function. I contact Benjamin Paasen who is the owner of the repository and discussed the metric I was looking for. According to his own experience, he also didn't know any research with that definition. The following is the distance formula he suggested for my case:
$$d(A, B) = \max\{|A|, |B|\} - |A \cap B| = \max\{|A \setminus B|, |B \setminus A|\}$$
Depending on your purpose this metric may be more suitable, and it satisfies all the axioms of a metric space.
A: On any set $A$ you can always define the discrete metric:
$$d: A \times A \rightarrow \mathbb{R^+_0}\\d(x,y)=\begin{cases}1, & x=y\\0,& x\neq y\end{cases}.$$
