MODULE 1
BOOLEAN ALGEBRA
BOOLEAN ALGEBRA
Mathematician George Boole invented new kind of algebra –algebra of logic
in 1854 known as boolean algebra or switching algebra
Boolean algebra differ from conventional algebra and binary number system
In Boolean algebra, Eg: A+ A= A; A.A= A
Here variable A has only logical value, does not have any numerical
significance
In ordinary algebra, Eg. A+ A= 2A; A.A= A2, variable A has numerical
value.
Boolean algebra deals with rules by which logical operations are carried
out.
Used to simplify the design of logical circuits to reduce the hardware
required to design a specific system
BOOLEAN LOGIC EXPRESSIONS
• Three basic operations performed in Boolean algebra are
AND, OR and NOT
• In addition, NAND, NOR ,XOR and X-NOR are also
performed
LOCIGAL AND OPEARTION
• Two variables A and B, given as Y= A.B
• Common symbol for this operation is Multiplication sign (.)
Inputs Output
A B Y= A.B
0 0 0
0 1 0
1 0 0
1 1 1
LOCIGAL OR OPEARTION
•Two variables A and B, given as Y= A+B
•Common symbol for this operation is Addition sign (+)
Inputs Output
A B Y= A+B
0 0 0
0 1 1
1 0 1
1 1 1
LOCIGAL NOT OPEARTION
•The logical NOT operation convert logical 1 to logical 0 and
vice versa
•Represent NOT operation by A and
BASIC LAWS OF BOOLEAN ALGEBRA
AND LAWS
A.0 =0
A. 1= A
A.A=A
OR LAWS
A+0=A
A+1=A
A+A=A
COMMUTATIVE LAWS
Boolean addition is commutative, given by
Law 1: A + B = B+ A
Boolean multiplication is commutative, given by
Law 2 : A . B = B. A
ASSOCIATIVE LAWS
Associative law of addition is given by
law 1 : A+(B+C)= (A+B)+C
Associative law of multiplication is given by
Law 2 : A.(B.C) =(A.B).C
DISTRIBUTIVE LAWS
Boolean Addition is distributive over Boolean multiplication
Law 1:A+BC = (A+B)(A+C)
Boolean Multiplication is distributive over boolean addition
Law 2: A.(B+C)= A.B+A.C
List of postulates and theorems
Proof
DEMORGANS THEOREM
• Two important theorems which are part of Boolean
algebra were proposed by De Morgan.
• Theorem 5:
1. (x.y)’ = x’+y’
2. (x+y)’ = x’. y’
PROOF:
EXERCISE
Simplify the Boolean function using boolean laws and
theorems.
1. F= AB+BC+B’C
2. A+A’B
BOOLEAN FUNCTION
Binary variables has two values, 0 or 1.
Boolean function is an expression formed with binary
variables, two binary operators, one unary operator NOT,
parentheses and equal sign.
Function value may be 0 or 1 depending on values of
variables present in boolean function.
Consider Boolean function, F1=XYZ’
Function F1 =1 if x=1, y=1 and Z’=1, otherwise F1=0.
CONTD.
Boolean function can represented in truth table.
Number of rows in truth table: 2n combinations of 1’s and 0’s
of n variables.
Column represents function values according to different
combinations.
EXERCISE
Consider a Boolean Function:
F=X+Y’Z. Represent the boolean
function in form of truth table and
implement with basic gates.
CANONICAL AND STANDATRD FORM
MIN TERM AND MAX TERM
A binary variable may appear either in its normal form (x) or in its
complement form (x).
Now consider two binary variables x and y combined with an AND
operation.
four possible combinations: x’y’, xy’, x’y and xy.
Each of these four AND terms is called a minterm, or a standard product.
Each variable being primed if the corresponding bit of the
binary number is a 0 and unprimed if a 1.
In a similar manner, n variables can be combined to form 2n minterms
Similarly, n variables forming an OR term, provide 2n possible
combinations, called maxterms, or standard sums
Each variable being primed if the corresponding bit of the
binary number is a 1 and unprimed if a 0.
MINTERMS AND MAXTERMS FOR THREE
BINARY VARIABLES
MINTERM
MAXTERM
Any Boolean functions expressed as a sum of minterms or product of
maxterms are said to be in canonical form.
EXAMPLE PROBLEMS
EX: Express the Boolean function F=A+B’C in a sumof minterms
EX: Express the Boolean function F=xy+x’z in a product of maxterms
EXERCISE
CANONICAL SUM OF MIN TERMS(SOP)
1. Y=A+B
CANONICAL SUM OF MAX TERMS(POS)
1. Y= (A+B’)(B+C)(A+C’)