Sunday, December 11, 2011

Boolean Logic, Truth Tables and Karnaugh Maps





Simplification of Boolean Logic

Boundedness Law
X + 1 = 1
X . 0 = 0

Absorption Law
X + (X . Y) = X
X . (X + Y ) = X

Elimination Law
 X + (X' . Y) = X + Y
X.(X' + Y) = X.Y

Unique Complement theorem
If X + Y = 1 and X.Y = 0 then X = Y'

Involution theorem
 X'' = X
0' = 1

Associative Properties
X + (Y + Z) = (X + Y) + Z
X . ( Y . Z ) = ( X . Y ) . Z

Duality Principle
Interchanging AND and OR operators and replace 0's by 1's and 1's by 0's.
Duality of X.Y+Z' = (X'+Y').Z



Minterms and Maxterms
Any boolean expression may be expressed in terms of either minterms or maxterms.

Literal
A literal is a single variable within a term which may or may not be complemented.

A minterm is the product of N distinct literals where each literal occurs exactly once.

A maxterm is the sum of N distinct literals where each literal occurs exactly once.

The minterms and maxterms for a two-variable expression is
A  B   Minterm  Maxterm
0   0   A'.B'       A+B
0   1   A'.B        A+B'
1   0   A.B'        A'+B
1   1   A.B         A'+B'

The minterms and maxterms for a three variable expression is
A B C Minterm  Maxterm
0  0 0 A'.B'.C'    A+B+C
0  0 1 A'.B'.C     A+B+C'
0  1 0 A'.B.C'     A+B'+C
0  1 1  A'.B.C    A+B'+C'
1   0 0 A.B'.C'   A'+B+C
1   0 1 A.B'.C   A'+B+C'
1   1  0 A.B.C'  A'+B'+C
1   1 1  A.B.C   A'+B'+C'


2 comments: