LOGIC GATES & BOOLEAN ALGEBRA

Comprehensive Examination Notes

AND · OR · NOT · NAND · NOR · XOR · XNOR · Universal Gates · Parity

1. AND Gate

Definition
The AND gate is a digital logic gate with two or more inputs and one output. The output is HIGH (1)
only when ALL inputs are HIGH (1).
• Boolean Expression: Y = A · B (also written as Y = AB)
• Symbol: A flat-backed, curved-front shape (D-shape with flat back)
• The AND operation is equivalent to multiplication in Boolean algebra.

Truth Table (2-input AND)

Input A Input B Output Y = A·B
0 0 0
0 1 0
1 0 0
1 1 1

Realization Using Diodes (Diode AND Gate)

• Two diodes connected with anodes at inputs A and B; cathodes joined to output Y through a
resistor R to +V.
• If both inputs are HIGH (+V), both diodes are reverse biased; output = HIGH.
• If any input is LOW (0V), that diode conducts and pulls output LOW.
• Diode logic is passive — does not amplify; suffers from voltage drop (~0.7V per diode).

Realization Using Transistor (Transistor AND Gate)

• Two NPN transistors connected in SERIES (emitter of first to collector of second).
• Both transistors must be in saturation (base input HIGH) for output to be HIGH.
• If either transistor is cut off (base LOW), output is LOW.
• Transistor gates are active — provide amplification; overcome the voltage drop problem of
diodes.

2. OR Gate

Logic Gates & Boolean Algebra – Examination Notes

Definition
The OR gate outputs HIGH (1) if at least one input is HIGH (1). Output is LOW only when ALL inputs
are LOW (0).
• Boolean Expression: Y = A + B
• Symbol: Curved-back, pointed-front shape
• The OR operation is equivalent to addition (without carry) in Boolean algebra.

Truth Table (2-input OR)

Input A Input B Output Y = A+B
0 0 0
0 1 1
1 0 1
1 1 1

Realization Using Diodes (Diode OR Gate)

• Two diodes with anodes at inputs A and B; cathodes joined to output Y through resistor R to
ground.
• If any input is HIGH, that diode conducts and output goes HIGH.
• If all inputs are LOW, no diode conducts and output remains LOW.

Realization Using Transistor (Transistor OR Gate)

• Two NPN transistors connected in PARALLEL (collectors joined, emitters joined).
• If either transistor is saturated (base HIGH), output is HIGH.
• Output is LOW only when both transistors are cut off (both bases LOW).

3. NOT Gate (Inverter)

Definition
The NOT gate is a single-input gate that inverts or complements the input. It is also called an inverter.
• Boolean Expression: Y = A' (also written as Y = Ā or Y = ~A)
• Symbol: Triangle pointing right with a small circle (bubble) at the output

Truth Table
Input A Output Y = A'
0 1
1 0

Logic Gates & Boolean Algebra – Examination Notes

Realization Using Transistor
• A single NPN transistor in common-emitter configuration acts as an inverter.
• When base input is HIGH (1): transistor saturates → collector (output) goes LOW (0).
• When base input is LOW (0): transistor is cut off → output is pulled HIGH (1) through collector
resistor.
• This inversion is the fundamental action that makes the transistor useful in digital logic.

4. NAND Gate

Definition
NAND = NOT + AND. The NAND gate is an AND gate followed by a NOT gate. Output is LOW only
when ALL inputs are HIGH; otherwise output is HIGH.
• Boolean Expression: Y = (A·B)' i.e., complement of AND
• Symbol: AND gate symbol with a bubble at the output

Truth Table (2-input NAND)

Input A Input B Y = (A·B)'
0 0 1
0 1 1
1 0 1
1 1 0

4.1 NAND as Universal Gate

A gate is called a UNIVERSAL gate if any other logic gate (AND, OR, NOT) can be realized using only
that gate. NAND is a universal gate.

Gate to Realize Using NAND Gates Method

NOT 1-input NAND (both inputs tied) Y = (A·A)' = A'
AND NAND followed by NOT Y = ((A·B)')' = A·B
OR NOT each input, then NAND Y = (A'·B')' = A+B (De Morgan's)
NOR OR from NAND, then NOT Combine OR and NOT
implementations
XNOR Combination of NAND gates Requires 4 NAND gates

Importance: Using only NAND gates simplifies manufacturing — a single gate type can build any
circuit. NAND is preferred in TTL logic families.

Logic Gates & Boolean Algebra – Examination Notes

5. NOR Gate

Definition
NOR = NOT + OR. The NOR gate is an OR gate followed by a NOT gate. Output is HIGH only when
ALL inputs are LOW; otherwise output is LOW.
• Boolean Expression: Y = (A+B)' i.e., complement of OR
• Symbol: OR gate symbol with a bubble at the output

Truth Table (2-input NOR)

Input A Input B Y = (A+B)'
0 0 1
0 1 0
1 0 0
1 1 0

5.1 NOR as Universal Gate

NOR is also a universal gate. Every logic function can be built using only NOR gates.
Gate to Realize Using NOR Gates Method
NOT 1-input NOR (both inputs tied) Y = (A+A)' = A'
OR NOR followed by NOT (NOR on Y = ((A+B)')' = A+B
output)
AND NOT each input, then NOR Y = (A'+B')' = A·B (De Morgan's)
NAND AND from NOR, then NOT Combine AND and NOT
implementations

NOR gates are preferred in CMOS logic families. Both NAND and NOR are universal gates — either
one alone can implement any Boolean function.

6. XOR Gate (Exclusive OR)

Definition
The XOR gate outputs HIGH (1) when the inputs are DIFFERENT (one HIGH and one LOW). Output is
LOW when inputs are the same.
• Boolean Expression: Y = A ⊕ B = A'B + AB'
• Symbol: OR gate with an extra curved line at the input side
• Key rule: Output is 1 when inputs are NOT equal; output is 0 when inputs ARE equal.

Logic Gates & Boolean Algebra – Examination Notes

Truth Table (2-input XOR)
Input A Input B Y=A⊕B
0 0 0
0 1 1
1 0 1
1 1 0

Properties of XOR
• A ⊕ 0 = A (XOR with 0 gives the same value)
• A ⊕ 1 = A' (XOR with 1 inverts the value)
• A ⊕ A = 0 (XOR with itself gives 0)
• A ⊕ A' = 1 (XOR with its complement gives 1)
• Commutative: A ⊕ B = B ⊕ A
• Associative: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

7. XNOR Gate (Exclusive NOR)

Definition
The XNOR gate is the complement of XOR. Output is HIGH (1) when inputs are EQUAL (both 0 or both
1). Also called an Equivalence gate.
• Boolean Expression: Y = (A ⊕ B)' = A'B' + AB = A ⊙ B
• Symbol: XOR gate with a bubble at the output
• Key rule: Output is 1 when inputs ARE equal; output is 0 when inputs are NOT equal.

Truth Table (2-input XNOR)

Input A Input B Y = (A ⊕ B)'
0 0 1
0 1 0
1 0 0
1 1 1

XOR vs XNOR Comparison

Feature XOR XNOR
Output HIGH when Inputs are DIFFERENT Inputs are SAME

Logic Gates & Boolean Algebra – Examination Notes

 Output LOW when Inputs are SAME Inputs are DIFFERENT
Expression Y = A⊕B = A'B + AB' Y = A'B' + AB
Alternate name Exclusive OR Equivalence / Exclusive NOR
Relation — XNOR = complement of XOR

8. Application of XOR/XNOR as Parity

What is Parity?
Parity is a simple error-detection technique used in digital communication and data storage. A parity bit
is an extra bit added to a data word to make the total number of 1s either even or odd.

8.1 Types of Parity

Type Rule Example (data 1011)
Even Parity Total number of 1s in data + parity Data 1011 has three 1s (odd) →
bit must be EVEN parity bit = 1 → transmitted: 10111
Odd Parity Total number of 1s in data + parity Data 1011 has three 1s (odd) →
bit must be ODD parity bit = 0 → transmitted: 10110

8.2 XOR as Even Parity Generator

A cascade (chain) of XOR gates generates the even parity bit. The XOR of all data bits gives 1 when
there is an odd number of 1s — so XOR output is exactly the bit needed to make total 1s even.

• For 4-bit data A, B, C, D: Parity bit P = A ⊕ B ⊕ C ⊕ D

• If data = 1011: P = 1⊕0⊕1⊕1 = 1 → append P=1 → 10111 (even parity, four 1s total)
• If data = 1010: P = 1⊕1⊕0⊕1⊕0 = 0 → append P=0 → 10100 (even parity, two 1s total)

8.3 XNOR as Odd Parity Generator

An XNOR gate cascade generates the odd parity bit. XNOR output is 1 when input 1s count is even —
the bit needed to make total 1s odd.
• Odd Parity bit P = (A ⊕ B ⊕ C ⊕ D)' = A ⊙ B ⊙ C ⊙ D

8.4 Parity Checker

At the receiver side, a parity checker (built from XOR or XNOR gates) recomputes the parity over all
received bits (data + parity bit).
• Even parity check: XOR all received bits. Result = 0 means NO error; result = 1 means ERROR
detected.

Logic Gates & Boolean Algebra – Examination Notes

 • Odd parity check: XOR all received bits. Result = 1 means NO error; result = 0 means ERROR
detected.
• Limitation: Parity can only detect an ODD number of bit errors; it cannot detect an even number
of errors, and it cannot correct errors.

8.5 Summary Table — Parity

Parity Type Generator Gate Checker Condition (no Detects
error)
Even Parity XOR of all data bits XOR of all received bits = 0 Single-bit errors
(odd number of
flips)
Odd Parity XNOR of all data bits XOR of all received bits = 1 Single-bit errors
(odd number of
flips)

9. All Gates — Quick Summary

Gate Expression Output is 1 when… Universal?

AND Y = A·B ALL inputs are 1 No
OR Y = A+B At least ONE input is 1 No
NOT Y = A' Input is 0 (inverts) No
NAND Y = (A·B)' At least ONE input is 0 YES
NOR Y = (A+B)' ALL inputs are 0 YES
XOR Y = A⊕B Inputs are DIFFERENT No
XNOR Y = (A⊕B)' Inputs are SAME (equal) No

10. Quick Revision — Key Points

EXAM QUICK REVISION

1. AND: output 1 only if ALL inputs 1 (Y=A·B); OR: output 1 if ANY input 1 (Y=A+B)
2. NOT: single-input inverter; transistor in common-emitter = natural inverter
3. AND diodes = parallel pull-down; OR diodes = parallel pull-up to output
4. NAND = AND+NOT; NOR = OR+NOT; both are UNIVERSAL GATES
5. NAND universal: NOT=A NAND A; AND=NAND+NOT; OR=NOT inputs then NAND
6. NOR universal: NOT=A NOR A; OR=NOR+NOT; AND=NOT inputs then NOR
7. XOR: output 1 when inputs DIFFER (Y=A⊕B); XNOR: output 1 when inputs SAME

Logic Gates & Boolean Algebra – Examination Notes

8. XOR chain = Even Parity Generator; XNOR chain = Odd Parity Generator
9. Parity detects odd-number of bit errors only; cannot correct errors

Logic Gates & Boolean Algebra – Examination Notes