2

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.

Gere
  • 2,117

3 Answers3

4

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 .

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • It's also, basically, the most standard one in theoretical computer science. Equivalently, it corresponds to the probability two functions will differ on a point drawn uniformly at random from the Boolean hypercube. – Clement C. Apr 03 '17 at 19:38
  • Oh, so I basically order the boolean result by the input. This gives by a 2^N boolean vector for which I can use this distance or any other distance on vectors? That should work. – Gere Apr 04 '17 at 05:58
  • @Gerenuk Yes. See my edit. – Ethan Bolker Apr 04 '17 at 13:46
1

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.

Adnan Baysal
  • 21
0

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}.$$

Roland
  • 6,064
  • This won't tell you how similar or different two functions are though, just if they are or or are not. – A. Thomas Yerger Apr 03 '17 at 19:29
  • @AlfredYerger: That's correct. The discrete metric is a very generic metric and does not tell you a lot about the closeness of two elements. – Roland Apr 03 '17 at 19:31