LECTURE (2)
BOOLEAN ALGEBRA AND
LOGIC SIMPLIFICATION
Dr. Mohamed El-Ghoboushi
Boolean Operations and Expressions
Boolean algebra is the mathematics
of digital logic.
A basic knowledge of Boolean
algebra is indispensable to the study
and analysis of logic circuits.
.
Variable and complement definitions
A variable is a symbol (usually an italic uppercase
letter or word) used to represent an action, a
condition, or data. )
.
(
( ).
1 0 .
Any single variable can have only a 1 or a 0 value.
The complement is the inverse of a variable and is
indicated by a bar over the variable (over bar).
For example, the complement of the variable A is
A. If A = 1, then A¯ = 0. If A = 0, then A¯ = 1.
The complement of the variable A is read as “not A”
or “A bar.”
Definition of Literal
Sometimes a prime symbol rather than an over bar
is used to denote the complement of a variable;
for example, B’ indicates the complement of B.
A literal is a variable or the complement of a
variable.
Boolean Addition
Boolean addition is equivalent to the OR
operation.
The basic rules are illustrated with their relation to
the OR gate in Figure
Boolean Addition
Boolean Multiplication
Boolean multiplication is equivalent to the AND
operation.
The basic rules are illustrated with their relation to
the AND gate in Figure
Boolean Multiplication
Laws and Rules of Boolean Algebra
After completing this section, you should be
able to:
Apply the commutative laws of addition and
multiplication
Apply the associative laws of addition and
multiplication
Apply the distributive law
Apply twelve basic rules of Boolean algebra
Commutative Law of addition
Commutative Law of Multiplication
The commutative law of multiplication for two variables is:
AB = BA
This law states that the order in which the variables are
ANDed makes no difference.
Following Figure illustrates this law as applied to the AND
gate.
Remember, in Boolean algebra as applied to logic circuits,
multiplication and the AND function are the same.
Associative Law of addition
The associative law of addition is written as follows
for three variables:
A + (B + C) = (A + B) + C
This law states that when ORing more than two
variables, the result is the same regardless of the
grouping of the variables. Figure illustrates this law
as applied to 2-input OR gates.
Associative Law of multiplication
The associative law of multiplication is written as follows
for three variables:
A(BC) = (AB)C
This law states that it makes no difference in what order
the variables are grouped when ANDing more than two
variables.
Following Figure illustrates this law as applied to 2-
input AND gates.
Distributive Law
The distributive law is written for three variables as follows:
A(B + C) = AB + AC
This law states that ORing two or more variables and then
ANDing the result with a single variable is equivalent to
ANDing the single variable with each of the two or more
variables and then ORing the products.
The distributive law also expresses the process of factoring
in which the common variable A is factored out of the
product terms, for example, AB + AC = A(B + C).
The Figure illustrates the distributive law in terms of gate
implementation.
Application of distributive law
Rules of Boolean Algebra
Rules 1 through 9 will be viewed in terms of their application to logic
gates.
Rules 10 through 12 will be derived in terms of the simpler rules and
the laws previously discussed.
Proof
Rule 11
Rule 11 proof using Truth Table
Rule 12
Rule 12 proof using Truth Table
DeMorgan’s first Theorem
DeMorgan’s first theorem is stated as follows:
“ The complement of a product of variables is
equal to the sum of the complements of the
variables”.
Stated another way,
“The complement of two or more ANDed
variables is equivalent to the OR of the
complements of the individual variables”.
DeMorgan’s second Theorem
DeMorgan’s second theorem is stated as follows:
“The complement of a sum of variables is equal
to the product of the complements of the
variables”.
Stated another way,
“The complement of two or more ORed variables
is equivalent to the AND of the complements of
the individual variables”.
The formula for expressing this theorem for two
variables is
Example
Example
Notes:
Applying DeMorgan’s Theorems
Example Cont.
Thank You
