Canonical form (Boolean algebra) Guide, Meaning , Facts, Information and Description

In a Boolean algebra, a Boolean function that is composed of standard logical operators can be expressed in a canonical form using the dual concepts of a minterms and maxterms.

Table of contents

1 Minterms 1.1 Indexing minterms 2 Functional equivalence 3 Maxterms 3.2 Indexing maxterms 3.3 Dualization 3.4 Returning to functional equivalence 4 Summary of results 5 See also

Minterms

We firstly begin with defining a minterm as a logical expression of n variables consisting of only the logical and operator and complements.

For example, the following are examples of minterms:

a b'c

a' b c

There are 2ⁿ minterms of n variables - this is true since a variable in the minterm expression can either be in the form of itself or its complement - two choices per n variables.

Indexing minterms

In general, one assigns each minterm (ensuring the variables are written in the same order, usually alphabetic), an index based on the binary value of the minterm. A complemented term, like a' is considered a binary 0 and a noncomplemented term like a is considered a binary 1. For example, one would associate the number 6 with a b c'(110₂), and write the minterm expression as m₆. So m₀ of three variables is a'b'c'(000₂) and m₇ would be a b c(111₂).

Functional equivalence

It is apparent that minterm n gives a true value for the n+1 th unique function input for that logical function. For example, minterm 5, a b' c, is true only when a and c both are - the input where a = 1, b = 0, c = 1 results in 1.

If one is given a truth table of a logical function, it is possible to write the function as a "sum of products" (minterms AND'd in series). This is a special form of conjunctive normal form, qv. For example, if given the truth table

A B  f(A, B)
0 0  1
0 1  0
1 0  1
1 1  0

observing that the rows that have an output of 1 are the first and third, so we can write f as a sum of minterms m₀ and m₂.

If we wish to verify this:

g(a,b) = m₀ + m₂ = (a'b')+(ab')

then the truth table for this function, by direct computation, will be the same.

Maxterms

Maxterms are a dual of the minterm idea. Instead of using ANDs and complements, we use ORs and complements, and proceed similarly.

For example, the following are examples of minterms:

a+b'+c

a'+b+c

There are again 2ⁿ minterms of n variables - this is true since a variable in the maxterm expression also, can either be in the form of itself or its complement - two choices per n variables.

Indexing maxterms

Indexing maxterms however is done in the opposite way as with minterms. One assigns each maxterm (again, ensuring the variables are written in the same order, usually alphabetic), an index based on the order of its complements, for example, associating the number 6 with a'+b'+c, but writing M₆. So M₀ of three variables is now a b c and M₇ would be a'b'c'.

Dualization

It can be easily verified by using de Morgan's law, that the complement of a minterm is the respective maxterm. Observe, for example

m₂' = M₂

(a+b')'= a'b

Returning to functional equivalence

It is apparent that maxterm n now gives a false value for the n+1 th unique function input for that logical function. For example, maxterm 5, a'+b+c', is false only when a and c both are - the input where a = 1, b = 0, c = 1 results in 0.

If one is given a truth table of a logical function, it is possible to write the function as a "product of sums" (maxterms OR'd in series). This a special form of disjunctive normal form, q.v. For example, if given the truth table

A B  f(A, B)
0 0  1
0 1  0
1 0  1
1 1  0

observing that the rows that have an output of 0 are the second and fourth, so we can write f as a product of maxterms m₀ and m₂.

If we wish to verify this:

g(a,b) = M₀ M₂ = (a+b)(a'+b)

then the truth table for this function, by direct computation, will be the same.

Summary of results

All logical functions are expressible in a canonical form, either a "sum of minterms" or "product of maxterms" form. This, apart from being able to express complicated logical functions in a straightforward and simple algebraic form, allows for greater analysis into the simplification of these functions, which is of great importance in the minimization of digital circuits.

See also

• list of Boolean algebra topics

This is an Article on Canonical form (Boolean algebra). Page Contains Information, Facts Details or Explanation Guide About Canonical form (Boolean algebra)

	Web www.E-paranoids.com