Representing Boolean Functions

Introduction

Boolean functions can be represented in multiple ways, each with its own advantages. Understanding these representations is crucial for designing, analyzing, and optimizing digital circuits.

Methods of Representation

1. Truth Tables
2. Boolean Expressions
3. Logic Diagrams (Circuits)
4. Karnaugh Maps (K-maps)
5. Binary Decision Diagrams (BDDs)

1. Truth Table Representation

Definition

A truth table lists all possible combinations of input values and the corresponding output value.

Structure

For n variables:

• Number of rows = 2ⁿ
• First n columns: input variables
• Last column: output (function value)

Example 1: Two Variables

Function: f(x, y) = x ∧ y

Example 2: Three Variables

Function: f(x, y, z) = xy + z

Advantages of Truth Tables

• Complete specification of the function
• Easy to understand and verify
• Systematic approach to all input combinations
• Good for small functions (2-4 variables)

Disadvantages

• Size grows exponentially (2ⁿ rows)
• Impractical for many variables (10 variables = 1024 rows!)
• Doesn’t show structure or simplification opportunities

2. Boolean Expression Representation

Algebraic Form

Express the function using Boolean operators (∧, ∨, ¬).

Examples:

• f(x, y) = xy + x̄y
• g(x, y, z) = xyz + x̄ȳz̄
• h(a, b, c) = (a + b)(ā + c)

Types of Boolean Expressions

a) Canonical Forms

Standard, unique representations.

b) Minimized Forms

Simplified expressions with fewer terms/literals.

Standard Forms (Canonical Forms)

Sum of Products (SOP)

Definition: OR of AND terms (minterms)

Form: f = term₁ + term₂ + … + termₙ

Each term is a product (AND) of literals.

Minterms

A minterm is a product term where each variable appears exactly once (either complemented or uncomplemented).

For 2 variables (x, y):

For 3 variables (x, y, z):

Canonical SOP (Minterm Expansion)

Method: Sum the minterms where f = 1

Example: From truth table where f = 1 at rows 1, 3, 6, 7

f = m₁ + m₃ + m₆ + m₇ f = x̄ȳz + x̄yz + xyz̄ + xyz

Notation: f(x, y, z) = Σ(1, 3, 6, 7)

Example: Creating SOP from Truth Table

Given Truth Table:

| x | y | z | f | | --- | --- | --- | --- | ---- | | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | ← m₁ | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | ← m₃ | | 1 | 0 | 0 | 1 | ← m₄ | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 | ← m₆ | | 1 | 1 | 1 | 1 | ← m₇ |

Canonical SOP:

f = m₁ + m₃ + m₄ + m₆ + m₇

f = x̄ȳz + x̄yz + xȳz̄ + xyz̄ + xyz

f = Σ(1, 3, 4, 6, 7)

Product of Sums (POS)

Definition: AND of OR terms (maxterms)

Form: f = term₁ · term₂ · … · termₙ

Each term is a sum (OR) of literals.

Maxterms

A maxterm is a sum term where each variable appears exactly once.

For 2 variables:

Note: Maxterm Mᵢ is the complement of minterm mᵢ

Canonical POS (Maxterm Expansion)

Method: Product of maxterms where f = 0

Example: From truth table where f = 0 at rows 0, 2, 5

f = M₀ · M₂ · M₅ f = (x + y + z)(x + ȳ + z)(x̄ + y + ȳ)

Notation: f(x, y, z) = Π(0, 2, 5)

Converting Between SOP and POS

Rule: If f = Σ(minterms), then f = Π(other rows)

Example:

• If f = Σ(1, 3, 4, 6, 7) for 3 variables
• Then f = Π(0, 2, 5) (the rows where f = 0)

Example: Complete Conversion

Given: f(x, y, z) = Σ(1, 2, 4, 7)

SOP Form: f = m₁ + m₂ + m₄ + m₇ f = x̄ȳz + x̄yz̄ + xȳz̄ + xyz

POS Form: f = Π(0, 3, 5, 6) (complement of 1,2,4,7) f = M₀ · M₃ · M₅ · M₆ f = (x+y+z)(x+ȳ+z̄)(x̄+y+z̄)(x̄+ȳ+z)

Standard vs. Canonical Forms

Canonical Form

• Unique representation
• All minterms/maxterms explicitly listed
• Usually longer expression
• Good for verification

Example: f = x̄ȳz + x̄yz + xyz̄ + xyz

Standard (Non-Canonical) Form

• Not necessarily unique
• May have simplified terms
• Shorter, more efficient
• Good for implementation

Example: f = x̄z + xz + xy (simplified version)

Conversion: Truth Table ↔ Boolean Expression

Truth Table → SOP

Steps:

1. Identify rows where f = 1
2. Write minterm for each such row
3. OR all minterms together

Example:

| x | y | f | | --- | --- | --- | ---- | | 0 | 0 | 1 | ← x̄ȳ | | 0 | 1 | 0 | | 1 | 0 | 1 | ← xȳ | | 1 | 1 | 1 | ← xy |

f = x̄ȳ + xȳ + xy

Truth Table → POS

Steps:

1. Identify rows where f = 0
2. Write maxterm for each such row
3. AND all maxterms together

From same table above:

• f = 0 at row 1 (x=0, y=1)
• Maxterm: x + ȳ

f = x + ȳ

Boolean Expression → Truth Table

Steps:

1. List all input combinations
2. Evaluate expression for each combination
3. Fill in output column

Example: f = xy + z̄

Literal Count and Term Count

Literal

A literal is a variable or its complement appearing in an expression.

Example: In xy + x̄z + yz

• Literals: x, y, x̄, z, y, z
• Total: 6 literals

Term

A term is a product (in SOP) or sum (in POS).

Example: In xy + x̄z + yz

• Terms: xy, x̄z, yz
• Total: 3 terms

Cost Metrics

Implementation cost:

• Fewer literals → fewer gate inputs
• Fewer terms → fewer gates
• Goal: minimize both

Incomplete Specifications (Don’t Care Conditions)

Don’t Care Values

Symbol: X or d or - (dash)

Meaning: Output can be either 0 or 1 (doesn’t matter)

Uses:

• Impossible input combinations
• Unused combinations
• Optimization flexibility

Example with Don’t Cares

BCD to 7-segment decoder:

• Valid inputs: 0-9 (0000 to 1001)
• Invalid inputs: 10-15 (1010 to 1111)
• Invalid combinations are don’t cares

Truth Table:

| A | B | C | D | f | | --- | --- | --- | --- | --- | ------------ | | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 1 | 0 | | … | … | … | … | … | | 1 | 0 | 1 | 0 | X | ← don’t care | | 1 | 0 | 1 | 1 | X | | 1 | 1 | 0 | 0 | X | | 1 | 1 | 0 | 1 | X | | 1 | 1 | 1 | 0 | X | | 1 | 1 | 1 | 1 | X |

Notation: f = Σ(0, 3, 5, …) + d(10, 11, 12, 13, 14, 15)

Where d represents don’t care minterms.

Using Don’t Cares for Optimization

Strategy: Assign don’t cares to 0 or 1 to get simpler expression.

Example:

f = Σ(1, 3, 5) + d(0, 2)

Option 1: Treat d(0,2) as 0 f = Σ(1, 3, 5) = x̄ȳz + x̄yz + xȳz

Option 2: Treat d(0,2) as 1 f = Σ(0, 1, 2, 3, 5) This might simplify better!

Practical Examples

Example 1: Majority Function

Definition: Output is 1 if majority of inputs are 1

For 3 inputs:

| x | y | z | f | | --- | --- | --- | --- | -------- | | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | ← 2 ones | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | ← 2 ones | | 1 | 1 | 0 | 1 | ← 2 ones | | 1 | 1 | 1 | 1 | ← 3 ones |

SOP: f = Σ(3, 5, 6, 7) f = x̄yz + xȳz + xyz̄ + xyz

Simplified: f = xy + xz + yz

Example 2: Parity Function

Definition: Output is 1 if odd number of inputs are 1

For 3 inputs:

f = Σ(1, 2, 4, 7) = x ⊕ y ⊕ z

Example 3: Full Adder

Inputs: x, y, cin (carry in) Outputs: sum, cout (carry out)

Sum: s = x ⊕ y ⊕ cin = Σ(1, 2, 4, 7) Carry: cout = xy + xcin + ycin = Σ(3, 5, 6, 7)

Key Points for Exams

1. Truth table has 2ⁿ rows for n variables
2. Minterm: product where f=1, Maxterm: sum where f=0
3. SOP = OR of AND, POS = AND of OR
4. Σ notation for minterms, Π notation for maxterms
5. Canonical forms are unique, standard forms are not
6. Don’t cares (X) provide optimization flexibility
7. Minterm mᵢ and Maxterm Mᵢ are complements
8. If f = Σ(a,b,c), then f = Π(all others)
9. Count literals and terms for complexity
10. Convert between representations systematically

Practice Problems

1. Create truth table for f(x,y,z) = x̄y + yz̄

2. Express in canonical SOP: f = Σ(0, 2, 5, 7)

3. Express in canonical POS: f = Π(1, 3, 4, 6)

4. Convert f = xy + x̄z to POS form

5. From truth table with f=1 at rows 1,3,5,7, write SOP

6. How many minterms for 4 variables?

7. Express XOR of 2 variables in canonical SOP

8. Given f = Σ(1,3,5,7) + d(0,2), find optimal expression

9. Count literals in: f = abc + ābc̄ + ab̄c

10. Write maxterm M₅ for variables x,y,z