Boolean Algebra and Logic Simplification

Discrete Mathematics
Boolean Algebra and Logic Simplification
Boolean Algebra is the mathematics of digital systems. In

Boolean algebra, a variable is a symbol used to represent an
action, a condition, or data. A single variable can only have a
value of 1 or 0. The complement represents the inverse of a
variable and is indicated with an overbar. Thus, the complement
of A is A. A literal is a variable or its complement
Addition is equivalent to the OR operation. The sum term is 1 if
one or more of the literals are 1. The sum term is 0 if all literals
are 0.
Multiplication is equivalent to the AND operation. The product
of literals forms a product term. The product term will be 1 only
if all of the literals are 1.
Lows of Boolean Algebra

Commutative Lows: The commutative laws are applied to
addition and multiplication. For addition, the commutative law
states: In terms of the result, the order in which variables are
ORed makes no difference.
A+B=B+A
For multiplication, the commutative law states: In terms of the

result, the order in which variables are ANDed makes no
difference.
AB = BA
Compiled by Mr. Kirui
Page 1
Associative Laws: The associative laws are also applied to

addition and multiplication. For addition, the associative law
states: When ORing more than two variables, the result is the
same regardless of the grouping of the variables.
A + (B +C) = (A + B) + C
For multiplication, the associative law states: When ANDing

more than two variables, the result is the same regardless of
the grouping of the variables.
A(BC) = (AB)C
Distributive Law: The distributive law is the factoring law. A

common variable can be factored from an expression just as in
ordinary algebra. That is:
AB + AC = A(B+ C)
Page 2
Rules of Boolean Algebra
Rule 1: A + 0 = A, a variable ORed with 0 is always equal to

the variable.
Rule 2: A + 1 = 1, a variable ORed with 1 is always equal to 1.
Rule 3: A . 0 = 0, a variable ANDed with 0 is always equal to 0.
Rule 4: A . 1 = A, a variable ANDed with 1 is always equal to

the variable.
Page 3
Rule 5: A + A = A, a variable ORed with itself is always equal

to the variable.
Rule 6: A + A = 1, a variable ORed with its complement is

always equal to 1.
Rule 7: A . A = A, a variable ANDed with itself is always equal

to the variable.
Rule 8: A . A = 0, a variable ANDed with its complement is

always equal to 0.
Page 4
Rule 9: A = A, the double complement of a variable is

always equal to the variable.
Rule 10: A + AB = A, this rule can be proved as follows:

A+AB= A (1+B)
Factoring (distributive low)

= A.1
Rule2: (1+B) = 1
=A
Rule4: A. 1 = A
Rule 11: A + AB = A + B, this rule can be proved as follows:

A + AB = (A +AB) + AB
Rule10 (A=A+AB)
= (AA+AB) + AB
Rule7:
= AA + AB +AA +AB
Rule8:
A = AA
adding AA = 0
= (A+A) (A+B)
Factoring
= 1. (A+B)
Rule6: A+A=1
= A+ B
Rule4: 1. X = X
Page 5
Rule 12: (A + B)(A + C) = A + BC, this rule can be proved as
follows:
(A + B)(A + C) = AA + AC + AB + BC
low
Distributive
= A + AC + AB + BC
Rule7: AA = A
= A (1+C) + AB + BC
Factoring
= A.1 + AB + BC
Rule2: 1+C = 1
= A (1 + B) + BC
Factoring
= A.1 +BC
Rule2: 1+B = 1
= A + BC
Rule4: A.1 = A
DeMorgans Theorems
1st Theorem: The complement of a product of variables is
equal to the sum of the complemented variables.
(XY)
= X + Y
2st Theorem: The complement of a sum of variables is equal to
the product of the complemented variables.
(X + Y)
= X. Y
Page 6
Example: Apply DeMorgans theorem to remove the overbar

covering both terms from the expression
X = (C + D)
Solution: To apply DeMorgans theorem to the expression, you
can break the overbar covering both terms and change the
sign between the terms.
This results in:
X = C . D
Deleting the double bar gives
X = C . D
Simplification Using Boolean Algebra

A simplified Boolean expression uses the fewest gates possible
to implement a given expression.
Example: Apply Boolean algebra to simplify this expression:
AB + A (B+C) + B (B+C)
Page 7
Solution:
1. Apply the distributive low to the 2nd and 3rd terms:
AB + AB + AC + BB + BC
2. Apply rule 7 (BB=B) to the 4th term:
AB + AB + AC + B + BC
3. Apply rule5 (AB+AB=AB) to the first two terms
AB + AC + B + BC
4. Apply rule10 (B+BC=B) to the last two terms
AB + AC + B
5. Apply rule10 (AB+B=B) to the 1st and 3rd terms
B + AC
Sum-of-Products and Product-of-Sums Forms

Boolean expressions can be written in the sum-of-products form
(SOP) or in the product-of-sums form (POS). These forms can
simplify the implementation of combinational logic, particularly
with PLDs. In both forms, an overbar cannot extend over more
than one variable.
Page 8
An expression is in SOP form when two or more product terms are
summed as in the following examples:
A B C + A B
A B C + C D
C D + E
An expression is in POS form when two or more sum terms are

multiplied as in the following examples:
(A + B)(A + C)
(A + B + C)(B + D)
(A + B)C
Example: Convert each of the following Boolean expressions to

SOP form:
(a) AB
+ B(CD + EF)
+ B) + C))
(b) (A + B)(B + C + D)
(c) ((A
Solution:
(a)
AB + B(CD + EF) = AB + BCD + BEF
(b)
(A + B)(B + C + D) = AB + AC + AD + BB + BC +
BD
(c)
((A + B) + C)) = (A + B) C
= (A + B) C
= AC + BC
The Standard SOP Form

In SOP standard form, every variable in the domain must
appear in each term. You can expand a nonstandard term to
Page 9
standard form by multiplying the term by a term consisting of
the sum of the missing variable and its complement.
Example: Convert X = A B + A B C to standard form.

Solution: The first term does not include the variable C.
Therefore, multiply it by the (C + C), which = 1:
X = A B ( C + C ) + A B C
= A B C + A B C + A B C
The Standard POS Form

In POS standard form, every variable in the domain must
appear in each sum term of the expression. You can expand a
nonstandard POS expression to standard form by adding the
product of the missing variable and its complement and
applying rule 12, which states that A + BC = (A + B)(A + C).
Example: Convert
form.
X = ( A + B )(A + B + C)
to standard
Solution: The first sum term does not include the variable C.
Therefore, add C C, which= 0, and expand the result by rule
12.
X = ( A + B + C C )(A + B + C)
= (A +B + C )( A + B +
C )(A + B + C)
Page 10
The Karnaugh Map
It is similar to a truth table because it represents all possible
values of input variables and the resulting output for each value.
Instead of being organized into columns and rows like truth table,
the K. map is an array of cells in which each cell represents a
binary value of the inputs variables. The cells are arranged in a
way so that simplification of a given expression is simply a matter
of properly grouping the cells.
The number of cells in K. maps, as well as the number of rows in
truth tables, is equal to the total number of possible
combinations. For 3 variables, the number of cells is 23 = 8. For 4
variables, the number of cells is 24 = 16. The K. maps can be
used for expressions up to 5 variables.
3- Variable K. Map
The 3-variable K. map is an array of 8 cells, as shown below:
Cells are usually labeled using 0s and 1s to represent the

variable and its complement. The numbers are entered in gray
code, to force adjacent cells to be different by only one variable.
Page 11
1s are read as the true variable and 0s are read as the
complemented variable.
The value of a given cell is the binary values of A and B combined
with the value of C, for each corresponding row and column.
4- Variable K. Map
The 4-variable K. map is an array of 16 cells, as shown below:
The cells in K. map are arranged so that there is only a singlevariable change between adjacent cells. Physically, each cell is
adjacent to the cells that are immediately next to it on any of its 4
sides.
The cells in the top row are adjacent to the corresponding cells in
the bottom row, and the cells in the outer left column are
adjacent to the corresponding cells in the outer right column, as
shown below:
Page 12
Mapping a standard SOP Expression

For an SOP expression in standard form, a 1 is placed on the K.
map for each product term in the expression. Each 1 is placed
in a cell corresponding to the value of a product term.
The figure below, illustrates mapping the expression: ABC +
ABC + ABC + ABC into the 3-variable K. map
Mapping a non-standard SOP Expression

Page 13
A Boolean expression must first be in standard form before you
use the K. map. If an expression is not in standard form, then it
must be converted to standard form.
Example: Map the following SOP expression on a K.map:
AB + ABC
A +
Solution:
First expand the terms numerically as follows:
A + AB + ABC
000 100
110
001 101
010
011
Thus the expression in standard SOP form will be as follows:
ABC + ABC + ABC+ ABC + ABC + ABC + ABC
Now you can map each of the product terms by placing a 1 in the
appropriate cell of the 3-variable K. map as shown below:
K. Map SOP Minimization

Page 14
K. map is used for simplifying Boolean expressions to their
minimum form. A minimized SOP expression contains the fewest
possible terms with the fewest possible variables per term.
Generally, a minimum SOP expression can be implemented with
fewer logic gates than the standard expression.
After an SOP expression has been mapped, a minimum SOP
expression is obtained by grouping the 1s and determining the
minimum SOP expression from the map.
You can group 1s on the K. map by enclosing those adjacent
cells containing 1s. The goal is to maximize the size of the
groups and minimize the number of groups according to the
following rules:
1. A group must contain either1, 2, 4, 8, or 16 cells, which
are all power of 2. In case of a 3-variable map, 23 = 8 cells,
is the maximum group.
2. Each cell in a group must be adjacent to one or more cells
in that same group, but all cells in the group do not have to
be adjacent to each other.
3. Always include the largest possible number of 1s in a group
(in accordance to rule 1).
4. Each 1 on the map must be included in at least one group.
Page 15
Example: Group the 1s in each of the following K. maps
Solution:
Determining the minimum SOP Expression from the Map

The following rules are applied to find the minimum product
terms and the minimum SOP expression.
1. Each group creates one product term composed of all
variables that occur in only one form (either uncomplemented or complemented) within the group.
2. Variables that occur both un-complemented and
complemented within the group are eliminated (these are
called contradictory variables).
Page 16
3. When all the minimum product terms are derived from the
K. map, they are summed to form the minimum SOP
expression
Notes: For a 3-variable map:

A 1-cell group yields a 3-variable product term
A 2-cell group yields a 2-variable product term
A 4-cell group yields a 1-variable term
An 8-cell group yields a value of 1 expression
Example: Use the K. map to minimize the following standard

SOP expression:
ABC + ABC + ABC + ABC + ABC
Solution:
The binary values of the expression are:
101 + 011 + 001+ 000+ 100
Map the standard SOP expression and group the cells as follows:
Page 17
Notice that:
The wrap around 4-cell group includes the top row and
the bottom row of 1s.
The remaining 1 is absorbed in an overlapping group of
two cells.
The group of four 1s produces a 1-variable term, B. This is
determined by observing that within the group, B is the
only variable that does not change from cell to cell.
The group of two 1s produces a 2-variable term, AC. This is
determined by observing that within the group, A and C do
not change from one cell to the next.
The resulting minimum SOP expression is : B + AC
Keep in mind that: this minimum expression
equivalent to the original standard SOP expression.
is
Page 18
Page 19

Boolean Algebra and Logic Simplification

Uploaded by

Copyright:

Available Formats

Boolean Algebra and Logic Simplification

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Boolean Algebra and Logic Simplification

Uploaded by

Copyright:

Available Formats

Discrete Mathematics

Boolean Algebra and Logic Simplification

Boolean Algebra is the mathematics of digital systems. In

Lows of Boolean Algebra

For multiplication, the commutative law states: In terms of the

Compiled by Mr. Kirui

Associative Laws: The associative laws are also applied to

For multiplication, the associative law states: When ANDing

Distributive Law: The distributive law is the factoring law. A

Compiled by Mr. Kirui

Rules of Boolean Algebra

Rule 1: A + 0 = A, a variable ORed with 0 is always equal to

Rule 2: A + 1 = 1, a variable ORed with 1 is always equal to 1.

Rule 3: A . 0 = 0, a variable ANDed with 0 is always equal to 0.

Rule 4: A . 1 = A, a variable ANDed with 1 is always equal to

Rule 5: A + A = A, a variable ORed with itself is always equal

Rule 6: A + A = 1, a variable ORed with its complement is

Rule 7: A . A = A, a variable ANDed with itself is always equal

Rule 8: A . A = 0, a variable ANDed with its complement is

Rule 9: A = A, the double complement of a variable is

Rule 10: A + AB = A, this rule can be proved as follows:

Factoring (distributive low)

Rule 11: A + AB = A + B, this rule can be proved as follows:

Compiled by Mr. Kirui

Compiled by Mr. Kirui

Example: Apply DeMorgans theorem to remove the overbar

Deleting the double bar gives

Simplification Using Boolean Algebra

Sum-of-Products and Product-of-Sums Forms

Compiled by Mr. Kirui

An expression is in POS form when two or more sum terms are

Example: Convert each of the following Boolean expressions to

AB + B(CD + EF) = AB + BCD + BEF

The Standard SOP Form

Compiled by Mr. Kirui

Example: Convert X = A B + A B C to standard form.

The Standard POS Form

Compiled by Mr. Kirui

Cells are usually labeled using 0s and 1s to represent the

Compiled by Mr. Kirui

Mapping a standard SOP Expression

Mapping a non-standard SOP Expression

K. Map SOP Minimization

Compiled by Mr. Kirui

Example: Group the 1s in each of the following K. maps

Determining the minimum SOP Expression from the Map

Notes: For a 3-variable map:

Example: Use the K. map to minimize the following standard

Compiled by Mr. Kirui

Compiled by Mr. Kirui

Compiled by Mr. Kirui

You might also like