HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is special about a canonical representation of Boolean functions?

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#167195, answer score: 4

Revisions (0)

No revisions yet.