Shannon Expansion Theorem

The Shannon Expansion Theorem is used to expand a Boolean logic function (F) in terms of (or with respect to) a Boolean variable (X), as in the following forms.

space.gif

F = X . F (X = 1) + X' . F (X = 0)

space.gif

where F (X = 1) represents the function F evaluated with X set equal to 1; F (X = 0) represents the function F evaluated with X set equal to 0.

space.gif

Also the following function F can be expanded with respect to X,

space.gif

F = X' . Y + X . Y . Z' + X' . Y' . Z

space.gif

= X . (Y . Z') + X' . (Y + Y' . Z)

space.gif

Thus, the function F can be split into two smaller functions.

space.gif

F (X = '1') = Y . Z'

space.gif

This is known as the cofactor of F with respect to X in the previous logic equation. The cofactor of F with respect to X may also be represented as F X (the cofactor of F with respect to X' is F X' ). Using the Shannon Expansion Theorem, a Boolean function may be expanded with respect to any of its variables. For example, if we expand F with respect to Y instead of X,

space.gif

F = X' . Y + X . Y . Z' + X' . Y' . Z

space.gif

= Y . (X' + X . Z') + Y' . (X' . Z)

space.gif

A function may be expanded as many times as the number of variables it contains until the canonical form is reached. The canonical form is a unique representation for any Boolean function that uses only minterms. A minterm is a product term that contains all the variables of F such as X . Y' . Z).