canonical forms

[sulekha]

Hi all,

I was recently reading the book "Write Great code by ryndall Hyde" in
this in chapter 8 the following are given.

given n input variables there are two raised to two raised to n
unique Boolean functions ex:- for 2 i/p variables there are 16
different functions.

then he mentions about canonical forms. he says about sum of min terms
and sum of product form.

now my questions are as follows

1) what exactly is the purpose of canonical forms,especially sum of
min terms, where is it applied??

2)author says that for each different Boolean function, we can choose
a single canonical representation of that function.
I am not getting this point, can any one explain

pls note i am by no means an expert in these matters so please be
kind. only a beginner

[Alf P. Steinbach]

* sulekha:

> Hi all,
>
> I was recently reading the book "Write Great code by ryndall Hyde" in
> this in chapter 8 the following are given.
>
> given n input variables there are two raised to two raised to n
> unique Boolean functions ex:- for 2 i/p variables there are 16
> different functions.
>
> then he mentions about canonical forms. he says about sum of min terms
> and sum of product form.
>
> now my questions are as follows
>
> 1) what exactly is the purpose of canonical forms,especially sum of
> min terms, where is it applied??

A canonical form, whether it be of boolean functions or something else,
gives you a unique representation of each possibility. That makes it
possible to e.g. compare two functions f and g. To answer the question
"is f the same function as g?", represent f and g in canonical form and
compare the canonical forms.

For example, the statement about number of different boolean functions
would not be possible if you could not compare functions and say that
this function is different from that one, or equal to that other one.

Essentially the number of different functions is arrived at by counting
the ways to produce canonical forms. One way to do that: say that each
boolean function is of the form

f( a, b ) = ...

Here each argument can be 0 or 1, and so there are 2^2=4 different
combinations of argument values. For each such combination the function
can produce the result 0 or 1, represented by r[n] below:

Argument values: 11 10 01 00
Result: r[3] r[2] r[1] r[0]

Here the canonical form of the function can be chosen as the string of
four r-values (one for each possible argument value combination), e.g.
1000 defines the AND function and 1110 defines the OR function.

Since there are two possibilites for each symbol position in the
canonical form, and four positions, there are 2^4 = 16 possible functions.

> 2)author says that for each different Boolean function, we can choose
> a single canonical representation of that function.

Yes, that's the point of a canonical form, and luckily it is a property
of boolean functions that a canonical form is always possible.

> I am not getting this point, can any one explain

See above.

Cheers, & hth.,

- Alf

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[sulekha]

On Oct 11, 4:38 am, "Alf P. Steinbach" <al...@start.no> wrote:

e.g. compare two functions f and g. To answer the question
> "is f the same function as g?", represent f and g in canonical form and
> compare the canonical forms.

so what you mean is that canonical forms are basically used to compare
functions is n't it???

Can you give a working example other than boolean functions???

[Alf P. Steinbach]

* sulekha:

I thought I'd just send you to the Wikipedia article on canonical forms
(there had to be one), but it seems it's written by mathematicians with
a flair for expressing things in terms of impenetrable jargon.

So OK, a polynomial in x can be represented canonically like

A[n]*x^n + A[n-1]*x^(n-1) + ... + A[1]*x + A[0]

Now you can compare (2x+3)*(x-5) and (20-5x+2x^2) by representing both
in canonical form and comparing the A-values.

As another example, from programming, a stack can be represented
generally as a sequence of operations new, push and pop, like

push( pop( push( push( new, 1 ), 2 ) ), 3 )

with canonical form consisting only of new and push,

push( push( new, 1 ), 3 )