Boolean Algebra Fundamentals: SOP, POS, and K-Map Simplification

Boolean Algebra Fundamentals

Formulating Expressions: SOP and POS

Sum of Products (SOP) Formulation Steps

1. Circle rows in the truth table where the output $Y = 1$.
2. Identify the minterms corresponding to the circled rows.
3. Sum (OR) the selected minterms to form the final expression.

Product of Sums (POS) Formulation Steps

1. Circle rows in the truth table where the output $Y = 0$.
2. Identify the maxterms corresponding to the circled rows.
3. Multiply (AND) the selected maxterms to form the final expression.

Order of Evaluation in Boolean Algebra

Operations are evaluated in the following sequence:

1. Parentheses
2. NOT (Complementation)
3. AND (Multiplication)
4. OR (Addition)

Fundamental Boolean Laws and Theorems

• Identity Laws

  • $A + 0 = A$
  • $A \cdot 1 = A$

• Null Laws

  • $A + 1 = 1$
  • $A \cdot 0 = 0$

• Idempotent Laws

  • $A + A = A$
  • $A \cdot A = A$

• Complement Laws

  • $A + \bar{A} = 1$
  • $A \cdot \bar{A} = 0$

• Commutative Laws

  • $A + B = B + A$
  • $A \cdot B = B \cdot A$

• Associative Laws

  • $(A + B) + C = A + (B + C)$
  • $(A \cdot B) \cdot C = A \cdot (B \cdot C)$

• Distributive Laws

  • $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
  • $A + (B \cdot C) = (A + B) \cdot (A + C)$

• Absorption Laws

  • $A + (A \cdot B) = A$
  • $A \cdot (A + B) = A$

• De Morgan’s Theorems

  • $\overline{(A + B)} = \bar{A} \cdot \bar{B}$
  • $\overline{(A \cdot B)} = \bar{A} + \bar{B}$

Duality Principle

If a Boolean expression is true, replacing $0 \leftrightarrow 1$ and $AND \leftrightarrow OR$ yields another true expression.

Exclusive OR (XOR) Operation

XOR is a binary operation defined by the following results:

• $1 \oplus 1 = 0$
• $0 \oplus 1 = 1$
• $1 \oplus 0 = 1$ (Corrected from original text)
• $0 \oplus 0 = 0$

Karnaugh Maps (K-Maps) for Simplification

A K-map is a grid where each cell represents a minterm from a truth table. The number of cells depends on the number of variables:

• 2 variables (A, B): $2 \times 2$ grid (4 cells)
• 3 variables (A, B, C): $2 \times 4$ grid (8 cells)
• 4 variables (A, B, C, D): $4 \times 4$ grid (16 cells)

Sum of Products (SOP) Detailed Example

• SOP is a sum (OR) of product (AND) terms.
• A minterm is a product (AND) of literals, corresponding to rows where the output $Y=1$.
• Represented using Sigma notation ($\Sigma$).

2-Variable Truth Table and Minterms

Minterm Expression (SOP Form)

Based on $Y=1$ at $m_1, m_2, m_3$:

$Y = m_1 + m_2 + m_3 = \bar{A}B + A\bar{B} + AB$

Sigma Notation: $Y = \Sigma(1, 2, 3)$

Product of Sums (POS) Detailed Example

• POS is a product (AND) of sum (OR) terms.
• A maxterm is a sum (OR) of literals, corresponding to rows where the output $Y=0$.
• Represented using Pi notation ($\Pi$).

2-Variable Truth Table and Maxterms

Maxterm Expression (POS Form)

Based on $Y=0$ only at $M_0$ (using the same function as the SOP example):

$Y = M_0 = (A + B)$

Pi Notation: $Y = \Pi(0)$

Note: The original document incorrectly listed $Y = M_0 M_1 M_2$. This has been corrected to match the provided truth table where $Y=0$ only for $M_0$.

Converting a Truth Table to a Boolean Expression

3-Variable Truth Table (CBA)

We take all the minterms where the output $Y = 1$ (rows 001, 011, 110, 111) to form the SOP equation:

$Y = \bar{C}\bar{B}A + \bar{C}BA + CB\bar{A} + CBA$

Note: The original equation contained an error ($C\bar{B}\bar{A}$), which has been corrected to match the truth table.