3.

Solve Digital Logic Problems

A. Boolean Algebra Fundamentals

1. Definition

Boolean algebra is a mathematical system that deals with binary variables and logical operations.
Named after mathematician George Boole (1815-1864), it operates on variables that can have
only two possible values: TRUE (1) or FALSE (0). Unlike ordinary algebra that uses arithmetic
operations, Boolean algebra uses logical operations to manipulate these binary values.

Formal Definition: Boolean algebra is an algebraic structure consisting of a set B = {0, 1},
together with two binary operations (AND, OR) and one unary operation (NOT), satisfying
specific axioms and laws.

2. Uses of Boolean Algebra

Digital Circuit Design: Forms the foundation for designing logic gates, combinational circuits,
sequential circuits, and integrated circuits (ICs). Every digital device relies on Boolean logic.

Computer Programming: Used extensively in conditional statements (if-else), loops (while,

for), and decision-making logic in all programming languages.

Database Query Languages: SQL and other database languages use Boolean operators (AND,
OR, NOT) for filtering and retrieving data based on multiple conditions.

Search Engines: Boolean operators refine search queries to find more precise results by
combining or excluding search terms.

Digital Communication: Error detection and correction codes, data compression algorithms,
and encryption systems rely on Boolean operations.

Artificial Intelligence: Decision trees, expert systems, and logic-based AI systems use Boolean
algebra for reasoning and inference.

Control Systems: Industrial automation, robotics, and embedded systems use Boolean logic for
control decisions.

3. Key Terminologies

Boolean Variable: A variable that can assume only two values: 0 (FALSE, Low, Off) or 1
(TRUE, High, On). Examples: A, B, X, Y.

Boolean Constant: The fixed values 0 or 1.

Literal: A Boolean variable in its normal form (A) or complemented form (A').

Boolean Expression: A combination of Boolean variables, constants, and operators. Example: F

= A·B + C.

Boolean Function: A mapping from Boolean variables to a Boolean result. Example: F(A,B,C)
= AB + C.

Complement: The inverse of a Boolean value. If A = 0, then A' = 1, and vice versa.

Sum Term: OR operation of variables. Example: A + B + C.

Product Term: AND operation of variables. Example: A·B·C.

Minterm: A product term in which all variables appear exactly once, either in normal or
complemented form. Example: A·B·C'.

Maxterm: A sum term in which all variables appear exactly once. Example: A + B + C'.

Sum of Products (SOP): A Boolean expression expressed as OR of AND terms. Example: A·B
+ A·C.

Product of Sums (POS): A Boolean expression expressed as AND of OR terms. Example:

(A+B)·(A+C).

B. Boolean Operations
1. AND Operation (·, ∧)

Definition: The output is TRUE only when all inputs are TRUE.

Symbol: A·B or A∧B or AB

Truth Table:

A B | A·B
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1

Logic Gate: AND gate (D-shaped symbol)

2. OR Operation (+, ∨)
Definition: The output is TRUE when at least one input is TRUE.

Symbol: A+B or A∨B

Truth Table:

A B | A+B
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

Logic Gate: OR gate (shield-shaped symbol)

3. NOT Operation (', ¬, ‾)

Definition: The output is the inverse of the input. Also called complement or inversion.

Symbol: A', Ā, ¬A, or ~A

Truth Table:

A | A'
0 | 1
1 | 0

Logic Gate: NOT gate or Inverter (triangle with small circle)

4. NAND Operation (↑)

Definition: NOT-AND. The output is FALSE only when all inputs are TRUE. It's the
complement of AND.

Symbol: (A·B)' or A↑B

Truth Table:

A B | A NAND B
0 0 | 1
0 1 | 1
1 0 | 1
1 1 | 0

Logic Gate: AND gate with small circle at output

Significance: Universal gate - any Boolean function can be implemented using only NAND
gates.

5. NOR Operation (↓)

Definition: NOT-OR. The output is TRUE only when all inputs are FALSE. It's the complement
of OR.

Symbol: (A+B)' or A↓B

Truth Table:

A B | A NOR B
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 0

Logic Gate: OR gate with small circle at output

Significance: Universal gate - any Boolean function can be implemented using only NOR gates.

6. XOR (Exclusive-OR) Operation (⊕)

Definition: The output is TRUE when the inputs are different. Also called "difference" or
"inequality" function.

Symbol: A⊕B or A⊻B

Truth Table:

A B | A⊕B
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Logic Gate: Composite gate (requires multiple basic gates)

Expression: A⊕B = A'B + AB' = (A+B)·(A'+B')

Applications: Arithmetic circuits (adders), error detection, encryption, parity generators.

7. XNOR (Exclusive-NOR) Operation (⊙)

Definition: The output is TRUE when inputs are the same. Also called "equivalence" or
"equality" function. It's the complement of XOR.

Symbol: A⊙B or (A⊕B)'

Truth Table:

A B | A⊙B
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 1

Logic Gate: XOR gate with small circle at output

Applications: Comparators, error checking circuits, digital communication systems.

C. Expressing and Writing Boolean Expressions

1. Order of Basic Operations (Operator Precedence)

Priority from Highest to Lowest:

1st: Parentheses/Brackets - Operations inside parentheses are performed first Example:

(A+B)·C means perform OR first, then AND

2nd: NOT (') - Complement operation has highest precedence among operators Example: A'+B
means complement A first, then OR with B

3rd: AND (·) - Multiplication/conjunction operation Example: A·B+C means perform A·B first,
then OR with C

4th: OR (+) - Addition/disjunction operation (lowest precedence) Example: A+B·C means

perform B·C first, then OR with A

Complete Example: Expression: A + B'·C + (D+E)·F'

Evaluation order:

1. Parentheses: (D+E)
2. NOT operations: B', F'
3. AND operations: B'·C, (D+E)·F'
4. OR operations: A + [B'·C] + [(D+E)·F']

Important Note: When in doubt, use parentheses to make intentions clear and avoid ambiguity.
2. Symbols and Notation

Different Notation Systems:

AND Operation:

 A·B (dot notation - most common)

 A∧B (logical AND symbol)
 AB (implicit multiplication - common in mathematics)
 A AND B (verbal notation)

OR Operation:

 A+B (plus notation - most common)

 A∨B (logical OR symbol)
 A OR B (verbal notation)

NOT Operation:

 A' (prime notation - common in textbooks)

 Ā (overbar notation - common in engineering)
 ¬A (negation symbol - logic)
 ~A (tilde - programming)
 !A (exclamation - programming languages)

XOR Operation:

 A⊕B (circled plus)

 A⊻B (alternate symbol)
 A XOR B (verbal)

NAND:

 (AB)' or (A·B)'
 A↑B (Sheffer stroke)

NOR:

 (A+B)'
 A↓B (Peirce arrow)

XNOR:

 (A⊕B)' or A⊙B
 A XNOR B
Standard Conventions:

 Capital letters (A, B, C, ...) represent Boolean variables

 F, Y, or Z often represent output/function
 0 represents FALSE/LOW
 1 represents TRUE/HIGH
 Subscripts indicate multiple related variables: A₀, A₁, A₂

D. Methods of Simplifying Boolean Expressions

Boolean simplification reduces the number of gates and connections needed in circuits, leading
to cost reduction, improved reliability, and faster operation.

1. Using Algebraic Functions (Laws and Theorems)

Basic Laws:

Identity Laws:

 A+0=A
 A·1=A

Null (Annulment) Laws:

 A+1=1
 A·0=0

Idempotent Laws:

 A+A=A
 A·A=A

Inverse (Complement) Laws:

 A + A' = 1
 A · A' = 0

Double Negation (Involution) Law:

 (A')' = A

Commutative Laws:

 A+B=B+A
 A·B=B·A
Associative Laws:

 A + (B + C) = (A + B) + C
 A · (B · C) = (A · B) · C

Distributive Laws:

 A · (B + C) = A·B + A·C (AND over OR)

 A + (B · C) = (A + B) · (A + C) (OR over AND)

Absorption Laws:

 A + A·B = A
 A · (A + B) = A
 A + A'·B = A + B
 A · (A' + B) = A·B

De Morgan's Theorems (Critical for simplification):

 (A + B)' = A' · B'

 (A · B)' = A' + B'

General form: The complement of a function is obtained by changing AND to OR, OR to AND,
and complementing all variables.

Consensus Theorem:

 A·B + A'·C + B·C = A·B + A'·C

 (A+B)·(A'+C)·(B+C) = (A+B)·(A'+C)

2. Using Truth Tables

Method: Create a truth table showing all possible input combinations and their corresponding
outputs, then identify patterns or minimal expressions.

Steps:

1. List all possible input combinations (2ⁿ rows for n variables)

2. Calculate the output for each combination
3. Identify minterms (rows where output = 1)
4. Write Sum of Products (SOP) expression
5. Simplify if possible

Example: Simplify F = A'BC + AB'C + ABC' + ABC

Step 1: Create truth table

A B C | A'BC | AB'C | ABC' | ABC | F
0 0 0 | 0 | 0 | 0 | 0 |0
0 0 1 | 0 | 0 | 0 | 0 |0
0 1 0 | 0 | 0 | 0 | 0 |0
0 1 1 | 1 | 0 | 0 | 0 | 1 ← m₃
1 0 0 | 0 | 0 | 0 | 0 |0
1 0 1 | 0 | 1 | 0 | 0 | 1 ← m₅
1 1 0 | 0 | 0 | 1 | 0 | 1 ← m₆
1 1 1 | 0 | 0 | 0 | 1 | 1 ← m₇

Step 2: Identify minterms where F = 1 F = Σm(3, 5, 6, 7) F = A'BC + AB'C + ABC' + ABC

Step 3: Simplify by grouping

 m₆ and m₇: ABC' + ABC = AB(C' + C) = AB

 m₅ and m₇: AB'C + ABC = AC(B' + B) = AC
 m₃ and m₇: A'BC + ABC = BC(A' + A) = BC

Step 4: Look for minimal expression From the groupings: AB, AC, BC Check if any term is
redundant using absorption Since AB + AC + BC cannot be further simplified without losing
coverage:

Simplified F = AB + AC + BC

Alternative check:

 AB covers m₆, m₇
 AC covers m₅, m₇
 BC covers m₃, m₇ All minterms covered with only 2 terms: F = AB + AC (minimal
SOP)

Advantages of Truth Table Method:

 Systematic and straightforward

 Visual representation of function
 Easy to verify correctness
 Reveals all input-output relationships

Disadvantages:

 Becomes impractical for large number of variables (2ⁿ grows exponentially)

 Simplification not always obvious from table alone
 Requires additional analysis to find minimal form
3. Using Karnaugh Maps (K-Maps)

Definition: A K-map is a graphical method for simplifying Boolean expressions by arranging

truth table values in a grid where adjacent cells differ by only one variable. This allows visual
identification of terms that can be combined.

Gray Code Ordering: Adjacent cells use Gray code (only one bit changes between adjacent
cells), which is crucial for proper grouping.

K-Map Sizes:

 2 variables: 2×2 grid (4 cells)

 3 variables: 2×4 grid (8 cells)
 4 variables: 4×4 grid (16 cells)
 5-6 variables: Multiple 4×4 grids (complex, rarely hand-drawn)

K-Map for 2 Variables (A, B):

B
0 1
A0[][]
1[][]

K-Map for 3 Variables (A, B, C):

BC
00 01 11 10
A 0 [][][][]
1 [][][][]

K-Map for 4 Variables (A, B, C, D):

CD
00 01 11 10
AB 00 [ ] [ ] [ ] [ ]
01 [ ] [ ] [ ] [ ]
11 [ ] [ ] [ ] [ ]
10 [ ] [ ] [ ] [ ]

Steps for K-Map Simplification:

Step 1: Draw the appropriate K-map based on number of variables

Step 2: Fill the K-map with function values

  Place 1s in cells corresponding to minterms where F=1
 Place 0s (or leave blank) where F=0
 Mark don't cares with X if applicable

Step 3: Group adjacent 1s

 Groups must be rectangular and contain 2ⁿ cells (1, 2, 4, 8, 16...)

 Groups can wrap around edges (top-bottom, left-right)
 Groups can overlap
 Make groups as large as possible
 Use minimum number of groups to cover all 1s

Step 4: Write simplified expression

 For each group, identify variables that remain constant

 Combine all group expressions with OR