As A Statement About Boolean Functions
Let be a set of vectors of booleans each. The ugly duckling is the vector which is least like the others. Given the booleans, this can be computed using Hamming distance.
However, the choice of boolean features to consider could have been somewhat arbitrary. Perhaps there were features derivable from the original features that were important for identifying the ugly duckling. The set of booleans in the vector can be extended with new features computed as boolean functions of the original features. The only canonical way to do this is to extend it with all possible Boolean functions. The resulting completed vectors have features. The Ugly Duckling Theorem states that there is no ugly duckling because any two completed vectors will either be equal or differ in exactly half of the features.
Proof. Let x and y be two vectors. If they are the same, then their completed vectors must also be the same because any Boolean function of x will agree with the same Boolean function of y. If x and y are different, then there exists a coordinate where the -th coordinate of differs from the -th coordinate of . Now the completed features contain every Boolean function on Boolean variables, with each one exactly once. Viewing these Boolean functions as polynomials in variables over GF(2), segregate the functions into pairs where contains the -th coordinate as a linear term and is without that linear term. Now, for every such pair, and will agree on exactly one of the two functions. If they agree on one, they must disagree on the other and vice versa. (This proof is believed to be due to Watanabe.)
Read more about this topic: Ugly Duckling Theorem
Famous quotes containing the words statement and/or functions:
“The force of truth that a statement imparts, then, its prominence among the hordes of recorded observations that I may optionally apply to my own life, depends, in addition to the sense that it is argumentatively defensible, on the sense that someone like me, and someone I like, whose voice is audible and who is at least notionally in the same room with me, does or can possibly hold it to be compellingly true.”
—Nicholson Baker (b. 1957)
“Let us stop being afraid. Of our own thoughts, our own minds. Of madness, our own or others’. Stop being afraid of the mind itself, its astonishing functions and fandangos, its complications and simplifications, the wonderful operation of its machinery—more wonderful because it is not machinery at all or predictable.”
—Kate Millett (b. 1934)