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:
“Eloquence must be grounded on the plainest narrative. Afterwards, it may warm itself until it exhales symbols of every kind and color, speaks only through the most poetic forms; but first and last, it must still be at bottom a biblical statement of fact.”
—Ralph Waldo Emerson (1803–1882)
“Adolescents, for all their self-involvement, are emerging from the self-centeredness of childhood. Their perception of other people has more depth. They are better equipped at appreciating others’ reasons for action, or the basis of others’ emotions. But this maturity functions in a piecemeal fashion. They show more understanding of their friends, but not of their teachers.”
—Terri Apter (20th century)