What heuristics are there (if any) to know how close a circuit is to a function?
You could base your "cost function" on DNF fault classes. For a start, you could consider the following set


ENF: expression negation fault (a -> !a)
TOF: term omission fault (a -> a | b)
TIF: term insertion fault (a | b -> a)
TNF: term negation fault (a | b -> a | !b)
LOF: literal omission fault (a -> ab)
LIF: literal insertion fault (ab -> a)
LNF: literal negation fault (ab -> a!b)


For example, the distance from AND (a&amp;b) to XOR (a&amp;!b | !a&amp;b) would be 1 LIF and 1 TOF, while a distance from AND to NAND would be 1 ENF. You'll have to experiment with weights you assign on different fault types in your cost function.

Another idea you may want to consider is to take the problem from the other end: instead of generating minimal functions and optimize for correctness, you could generate correct functions and optimize for minimalism. It's much easier to come up with a reasonable cost function in the latter case, and you don't have to actually reach the optimum in order to get an acceptable solution.