Unit 2: Boolean Algebra and Logic gates

1. Logic Gates and Truth Tables

Logic gates are the fundamental building blocks of digital circuits. They perform logical operations on one or more binary inputs and produce a single binary output.

Basic Gates

1. NOT Gate (Inverter)

• Function: Reverses the input state. If input is 1, output is 0, and vice versa.
• Expression: or
• Truth Table:

2. AND Gate

• Function: Output is High (1) only if all inputs are High.
• Expression:
• Truth Table:

3. OR Gate

• Function: Output is High (1) if at least one input is High.
• Expression:
• Truth Table:

Universal Gates

These gates can be combined to implement any other Boolean function or gate.

1. NAND Gate (NOT-AND)

• Function: Output is Low (0) only if all inputs are High. Equivalent to an AND gate followed by a NOT gate.
• Expression:
• Truth Table:

2. NOR Gate (NOT-OR)

• Function: Output is High (1) only if all inputs are Low. Equivalent to an OR gate followed by a NOT gate.
• Expression:
• Truth Table:

Special Purpose Gates

1. XOR Gate (Exclusive-OR)

• Function: Output is High (1) if inputs are different (odd number of 1s). Used in parity checkers and adders.
• Expression:
• Truth Table:

2. XNOR Gate (Exclusive-NOR)

• Function: Output is High (1) if inputs are the same. Also known as the "Coincidence Gate" or Equivalence gate.
• Expression:
• Truth Table:

2. Boolean Algebra

Boolean algebra is a system of mathematical logic used to analyze and simplify digital gates and circuits. It operates on binary variables (0 and 1).

Fundamental Postulates and Laws

Assuming variables :

1. Identity Law:
2. Null Law:
3. Idempotent Law:
4. Inverse (Complement) Law:
5. Double Complement:
6. Commutative Law:
7. Associative Law:
8. Distributive Law:
   • (Note: This is unique to Boolean Algebra)
9. Absorption Law:

De Morgan’s Theorems

These are crucial for converting between NAND and NOR logic and simplifying expressions.

Theorem 1: The complement of a product is equal to the sum of the complements.

• (NAND = Bubbled OR)

Theorem 2: The complement of a sum is equal to the product of the complements.

• (NOR = Bubbled AND)

Duality Principle

Every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged.

• Change OR () to AND ()
• Change AND () to OR ()
• Change 1 to 0
• Change 0 to 1
• Note: Variables remain unchanged.

3. Canonical and Standard Form Representation

Any Boolean function can be expressed in terms of Canonical (Standard) forms using Minterms and Maxterms.

Definitions

• Minterm (): A product term containing all variables of the function in either complemented or uncomplemented form. Corresponds to logic 1 in the truth table.
• Maxterm (): A sum term containing all variables of the function in either complemented or uncomplemented form. Corresponds to logic 0 in the truth table.

Example for 3 variables (A, B, C):

• Binary 011 -> Minterm: ()
• Binary 011 -> Maxterm: ()

Sum of Products (SOP)

• Canonical SOP: The logic function is represented as a sum of minterms.
• Notation:
• Expression:

Product of Sums (POS)

• Canonical POS: The logic function is represented as a product of maxterms.
• Notation:
• Expression:

Conversion between Canonical and Standard Forms

A Standard form is a simplified version where terms may not contain all variables (e.g., ). To convert Standard to Canonical:

1. SOP: Multiply missing variable terms by .
   • Ex: If term is and is missing: .
2. POS: Add missing variable terms as .
   • Ex: If term is and is missing: .

4. SOP and POS Simplification

Simplification reduces the number of gates and inputs required to implement a circuit.

Algebraic Simplification

Using the laws listed in Section 2 to reduce expressions.

• Example: Simplify
  1. Expand:
  2. Use :
  3. Use :
  4. Factor from last two:
  5. Use :
  6. Reorder:
  7. Factor :
  8. Result:

5. Implementation of Boolean Functions

Two-Level Implementation

1. AND-OR Logic: Standard SOP implementation. First level AND gates, second level OR gate.
2. OR-AND Logic: Standard POS implementation. First level OR gates, second level AND gate.

Universal Gate Implementation

Any digital circuit can be constructed using only NAND gates or only NOR gates.

NAND Implementation (SOP Focus)

• NOT: Join inputs of NAND.
• AND: NAND followed by NOT (NAND).
• OR: Invert inputs (NOT-NANDs) then feed to NAND.
• Rule for SOP: Simply replace all AND and OR gates with NAND gates in a standard two-level SOP circuit.

NOR Implementation (POS Focus)

• NOT: Join inputs of NOR.
• OR: NOR followed by NOT (NOR).
• AND: Invert inputs then feed to NOR.
• Rule for POS: Simply replace all OR and AND gates with NOR gates in a standard two-level POS circuit.

6. Karnaugh Map (K-Map)

The K-Map is a graphical method for minimizing Boolean functions suitable for up to 4-5 variables. It relies on the fact that terms differing by one bit ( and ) can be combined ().

Structure and Gray Codes

The axes of a K-Map are labeled using Gray Code (00, 01, 11, 10) so that adjacent cells differ by only one bit.

2-Variable K-Map (4 cells)

Variables A (rows), B (cols).
Cells: 0, 1, 2, 3.

3-Variable K-Map (8 cells)

Variables A (row), BC (cols).

• Row 0 (A=0): Cells 0, 1, 3, 2
• Row 1 (A=1): Cells 4, 5, 7, 6
• Note the column indices are 00, 01, 11, 10.

4-Variable K-Map (16 cells)

Variables AB (rows), CD (cols).

Grouping Rules

1. Group Size: Must be a power of 2 (1, 2, 4, 8, 16).
2. Direction: Horizontal or vertical only (no diagonals).
3. Wrapping: The map wraps around (top connects to bottom, left connects to right).
   • Example: Cell 0 can group with Cell 2; Cell 0 can group with Cell 8.
4. Priority: Make groups as large as possible.
5. Overlap: Groups may overlap to maximize size.

Steps for Simplification

1. Plot the 1s (for SOP) or 0s (for POS) on the map based on the minterms/maxterms.
2. Create the largest possible groups of 1s (SOP).
3. Write the simplified term for each group (keep variables that do not change state within the group).
4. OR the resulting terms together.

7. Don't Care Conditions

In specific digital systems, certain input combinations never occur, or the output for a specific input does not affect the system operation. These are called Don't Care conditions.

• Symbol: Represented by 'X', 'd', or ''.
• Usage in Simplification:
  • A Don't Care can be treated as a 1 if it helps form a larger group in a K-Map.
  • A Don't Care can be treated as a 0 if it is not needed to form a group.
  • You are not required to cover every 'X', only use them to optimize the coverage of actual 1s.

Example

Function

1. Plot 1s at positions 1, 3, 7, 11, 15.
2. Plot Xs at positions 0, 2, 5.
3. Grouping:
   • Without 'X', we might group (3, 7, 15, 11) for term .
   • With 'X' at position 5: We can group (1, 3, 5, 7) + (3, 7, 11, 15).
   • With 'X' at positions 0 and 2: We can form a group of (0, 1, 2, 3) .
4. Goal: Use 'X' to reduce the number of literals in the final equation.

Significance: Don't care conditions often result in significantly simpler hardware implementations by allowing "impossible" inputs to facilitate logic reduction.