BOOLEAN ALGEBRA

&
LOGIC GATES
 What are Logic Gates?

i. Gate is a digital circuit having one or more input but only one output.
ii. Different combinations of gates can perform arithmetic and logical functions.
iii. Logic Gates act as electrical switches which allow the signal s to pass through
(Gate), and the output is determined only when certain logical conditions are
met. Hence, they are known as Logic gates.
iv. A logic gate acts as a building block for digital circuits .
v. They perform basic logical functions that are fundamental to digital circuits.
vi. Individual logic gates can be connected or cascaded together to form a logic gate
function with any desired number of inputs, or to form combinational and sequential
type circuits, or to produce different logic gate functions from standard gates.
 TRUTH TABLE
Truth Table is the tabular listing of all possible combinations given as input to a logic gate.

For Example:

TRUTH TABLE for AND Gate TRUTH TABLE

A B Q=A!B A B Q=A+B
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
Read As “ A AND B” = (A ! B) Read As “ A OR B”

1 + 1 = 2 This is normal addition

1+1=1 This is ‘OR’ operation

These two are very different things.

 Types of Logic Gates
Basic Logic Gates:

AND OR NOT

Other Gates:
NAND NOR XOR XNOR

Universal Logic Gate: Using which other gates can be made:

NAND and NOR Gate

AND GATE

• Operator is denoted by a dot between variables ( ! ).

• Expression: Q=A!B
• It is read as “Q is equal to A AND B.”
• If any input is LOW or “0” then the output is ”0” or LOW.
• For output to be HIGH or “1”, all the inputs must be HIGH or “1”.

Truth Table for two input AND Gate:

SYMBOL TRUTH TABLE
A B Q=A!B
0 0 0
0 1 0
1 0 0
1 1 1
Boolean Expression: Q = A ! B Read As “ A AND B”
 OR GATE

• Operator is denoted by a dot between variables ( + ).

• Expression: Q = A + B
• It is read as “Q is equal to A OR B.”
• For output to be HIGH or “1”, one of the inputs must be HIGH or
“1”.
• The output is ”0” or LOW when both the input are LOW or “0”.

SYMBOL TRUTH TABLE

A B Q=A+B
0 0 0
0 1 1
1 0 1
1 1 1
Boolean Expression: Q = A + B Read As “ A OR B”
NOT
¨ The Logic NOT Gate is the most basic of all the logical gates
¨ Referred to as an Inverting Buffer or simply an Inverter.
¨ It is SINGLE INPUT device.
¨ Converts HIGH to LOW and vice versa
 NAND
• Expression: Y="!#= $ + %

• It is read as “A AND B Bar or AB Bar.”

• For output to be HIGH or “1”, one of the inputs must be HIGH or “0”.

• The output is ”0” or LOW when both the input are HIGH or “1”.

SYMBOL TRUTH TABLE

A B Q= A ! B Y= & = " ! #
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
Boolean Expression: Y=!"# Read As “ A AND B Bar”
 NOR
• Expression: Q="+#== $ ! %

• It is read as “A OR B Bar.”

• For output to be HIGH or “1”, both the inputs must be LOW or “0”.

• The output is ”0” or LOW when one or both the inputs are HIGH or “1”.

SYMBOL TRUTH TABLE NOR

Output
A B Q=A+B Y="+#
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
Boolean Expression: Y = " + # Read As “ A OR B BAR”
 XOR
• Operator is denoted by a dot between variables (⊕). Q = A⊕B
• Expression: Q = A⊕B #
# +B%
Q=A$
• It is read as “Q is equal to A XOR B.”

• For output to be HIGH or “1”, one of the inputs must be HIGH or “1”.

• The output is ”0” or LOW when both the input are LOW or “0” or HIGH or “1”
.

SYMBOL TRUTH TABLE

A B Q = A ⊕B
0 0 0
0 1 1
1 0 1
1 1 0
Boolean Expression: Q = A ⊕ B Read As “ A XOR B”
 BOOLEAN ALGEBRA

• Algebra with Binary or Boolean variables and logic operation.

• Boolean Function is an algebraic expression or Boolean Expression consisting of Boolean variables, symbols 0 or 1 and
logic operation symbols like dot or + etc.

• Using Boolean Function, a logic diagram can be constructed using logic gates.

• De Morgan’s Theorem:

$+% =$ . %

$% = $ + %

• DUALITY THEOREM
• Starting with the Boolean expression, another relation can be obtained by doing the following:
• Change OR sign (+) to AND Sign (.)
• Change AND sign (.) to OR Sign (+)
• Change 0 to 1 And vice Versa appearing in the expression.
 Property
A+0 =A
Identities of Boolean Algebra A+1=1
OR Operations
A+A=A
A + A’ = 1
Reduce the Boolean Expression: $̿ = A Double Inversion Rule
A.A=A
A [ B + " ( AB + A " )] A.0 =0
AND Operations
A.1= A
A . A’ = 0
Reduce the following expressions:
1) ( $ . %* ) (A % + ABC ) A.B =B.A (Commutative Prop.)- Basic Law
A+B=B+A (Commutative Prop.)- Basic Law
2) AB + A % C + B * = AC + B *
A + (BC) = (A + B)( A + C) Distributive Prop.
A( B + C) = A . B + A . C Distributive Prop.
Find the complement of the following:
(A + B) + C = A + (B + C) Associative Law
1) AB + A (B + C) + % ( B + D) (A . B ) C = A ( B . C) Associative Law
A + AB = A Covering Rule
2) A + B + $ % C
A(A+B)=A

AB + A% = A Combining Rule
 CONSENSUS THEOREM

This theorem finds the redundant term which is the consensus of the two other terms.

AB + # C + BC = AB + # C -------------- (1)

(A + B) (# + C) ( B + C) = (A + B) (# + C) -----------------(2)

IN THE (1) BC is the consensus term and thus redundant because if

BC = 1 then both B = 1 and C = 1
And both other terms must be 1 as either A = 1 or # = 1

Similarly, in (2 ) (B + C) is consensus term and redundant because if

B + C = 0 then both B= 0 and C =0
Then one of the other two sum terms is 0 as A = 0 or # = 0
Problems:
Design the logic circuit for

1. Y = A $ C + ABC

2. Y = ( # + $ + ")( A + B + " )