patternMinor
What is special about a canonical representation of Boolean functions?
Viewed 0 times
canonicalwhatbooleanspecialaboutfunctionsrepresentation
Problem
My textbook (Saurabh's Introduction to VLSI Design Flow) mentions while discussing formal verification that a representation of a Boolean function is said to be canonical if the following holds:
If a representation is canonical, then the two functionally equivalent functions are represented identically. Conversely, if a representation is canonical and if two functions have the same representation, they are functionally equivalent.
In short, he seems to be saying that a representation is canonical if there is a bijection between the set of Boolean functions (say, of $n$ Boolean variables) and the strings in the given representation.
My question is about what is unique about such representations: I would imagine that any (even noncanonical) representations of Boolean functions have the property that two functions with the same representation are functionally equivalent, so is it just the other (first) direction which is unique to (i.e. defines) canonical representations?
Any other sources on this notion of canonicity would also be greatly appreciated.
If a representation is canonical, then the two functionally equivalent functions are represented identically. Conversely, if a representation is canonical and if two functions have the same representation, they are functionally equivalent.
In short, he seems to be saying that a representation is canonical if there is a bijection between the set of Boolean functions (say, of $n$ Boolean variables) and the strings in the given representation.
My question is about what is unique about such representations: I would imagine that any (even noncanonical) representations of Boolean functions have the property that two functions with the same representation are functionally equivalent, so is it just the other (first) direction which is unique to (i.e. defines) canonical representations?
Any other sources on this notion of canonicity would also be greatly appreciated.
Solution
Yes. Two functions with the same representation will be functionally equivalent. The question is whether there can exist a function with two different representations (i.e., two different representations but they are functionally equivalent).
Consider $(x \lor x \lor x)$ vs $(x \lor x)$. Those are two different representations, but they are functionally equivalent. Therefore, CNF is not a canonical representation of a Boolean function.
Consider $(x \lor x \lor x)$ vs $(x \lor x)$. Those are two different representations, but they are functionally equivalent. Therefore, CNF is not a canonical representation of a Boolean function.
Context
StackExchange Computer Science Q#167195, answer score: 4
Revisions (0)
No revisions yet.