I'm studying discrete mathematics now.
And a slide said "If a normal form leads to a unique representation for every Boolean function, we call it canonical. One canonical form("xor normal form") presents the function in a sum-of-products form, using exclusive or and conjunction."
Can anyone make me understand this sentence? What is the unique representation? Does that means there is only one expression for the form?
Thanks
Here is an example. Take the statement $A \lor (\neg A \land B)$. Let's put it on a truh-table, using the convention that we put the reference columns in alphabetical order, and that we fill out the truth-values in those columns in the following way: start with the right-most column, and alternate between $T$ and $F$. For the second-most right column, alternate between two $T$'s and two $F$'s, etc. So, we get:
\begin{array}{cc|c} A&B&A\lor (\neg A \land B)\\ \hline T&T&T\\ T&F&T\\ F&T&T\\ F&F&F\\ \end{array}
OK, now let's generate a term for each row in the table where the statement is true. Each term is a conjunction of literals, where each variable occurs once, and in the same order as the reference columns. We then disjunct together all these terms from top to bottom. So, you get:
$$(A \land B) \lor (A \land \neg B) \lor (\neg A \land B)$$
Ok, this is a 'sum' (disjunction) or products (conjunctions) that is equivalent to the original expression. As such it is in 'disjunctive normal form' (DNF)
Now, a statement can have many equivalent DNF's. In fact, the very original statement is in DNF, and another DNF for this statement is $A \lor B$. But note, in the latter case, the disjuncts $A$ and $B$ can be true at the same time ... so these are not exclusive disjuncts ... and so $A \lor B$ is not in 'XOR normal form'. The original statement, as well as the statement we generated with the truth-table are in 'XOR normal form' ... which also means that there can be multiple equivalent XOR normal forms for the same statement.
However, because we followed a very specific convention and procedure when using the truth-table, the outcome was completely determined, and therefore it is a 'canonical' normal form: there is exactly one such expression for each statement. And, note, since each disjunct reflects a different row in the truth-table, it will always be a XOR normal form. So, this method is a way to get a canonical XOR normal form for any statement.