Boolean Algebra and Digital Logic Circuits

Fundamentals of Boolean Algebra

• Boolean algebra deals with arithmetical and logical operations executed on digital signals that take values of $0$ and $1$.

• Boolean Expression & Logic Function:

  • A Boolean expression equates a logical function of variables to a binary output (for example, $x + x \cdot y = 1$).
  • Logical functions use operators such as OR ($+$) and AND ($\cdot$).
  • Variables are denoted by letters such as $x, y$.
  • Complements of variables are represented as $\bar{x}$ or $x'$.
  • Boolean constants consist exclusively of $0$ and $1$.
  • Literals refer to any occurrence of a variable or its complement within an expression.

• Postulates of Boolean Algebra:

  • Let $B = \{0, 1\}$ be the set of Boolean constants.
  • Closure: For every $x, y \in B$:
  • The OR operation $x + y \in B$ is closed.
  • The AND operation $x \cdot y \in B$ is closed.
  • Identity Elements: There exist unique identity elements in $B$ denoted relative to OR ($+$) and AND ($\cdot$):
  • OR Identity ($0$): $0 + x = x + 0 = x$ for every $x \in B$
  • AND Identity ($1$): $1 \cdot x = x \cdot 1 = x$ for every $x \in B$
  • Commutative Law: For all $x, y \in B$:
  • $x + y = y + x$
  • $x \cdot y = y \cdot x$
  • Distributive Law: Each operation ($\cdot$) and ($+$) is distributive over the other for all $x, y, z \in B$:
  • $x + (y \cdot z) = (x + y) \cdot (x + z)$
  • $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$
  • Complement: For every element $x \in B$, there exists an element $\bar{x} \in B$ called the complement of $x$ such that:
  • $x \cdot \bar{x} = 0$
  • $x + \bar{x} = 1$
  • Distinct Elements: There exist at least two elements $x, y \in B$ such that $x \neq y$

Boolean Laws, Theorems, and Proofs

• Basic OR Laws:

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

• Basic AND Laws:

  • $A \cdot 0 = 0$
  • $A \cdot 1 = A$
  • $A \cdot A = A$ (Idempotence Law)
  • $A \cdot \bar{A} = 0$

• Involution (Double Inversion) Law:

  • $\bar{\bar{A}} = A$

• Key Theorems:

  • Commutative Law:
  • $A + B = B + A$
  • $A \cdot B = B \cdot A$
  • Associative Law:
  • $A + (B + C) = (A + B) + C$
  • $A \cdot (B \cdot C) = (A \cdot B) \cdot C$
  • Distributive Law:
  • $A \cdot (B + C) = A \cdot B + A \cdot C$
  • $A + (B \cdot C) = (A + B) \cdot (A + C)$
  • Absorption Law:
  • $A + A \cdot B = A$
  • $A \cdot (A + B) = A$
  • $A + \bar{A} \cdot B = A + B$

• Verification and Proofs by Exhaustive Substitution:

  • OR Laws:
  • Proof of $A + 0 = A$: For $A = 1 \implies 1 + 0 = 1$; for $A = 0 \implies 0 + 0 = 0$.
  • Proof of $A + 1 = 1$: For $A = 1 \implies 1 + 1 = 1$; for $A = 0 \implies 0 + 1 = 1$.
  • Proof of $A + A = A$: For $A = 1 \implies 1 + 1 = 1$; for $A = 0 \implies 0 + 0 = 0$.
  • Proof of $A + \bar{A} = 1$: For $A = 0 \implies 0 + 1 = 1$; for $A = 1 \implies 1 + 0 = 1$.
  • AND Laws:
  • Proof of $A \cdot 0 = 0$: For $A = 1 \implies 1 \cdot 0 = 0$; for $A = 0 \implies 0 \cdot 0 = 0$.
  • Proof of $A \cdot 1 = A$: For $A = 1 \implies 1 \cdot 1 = 1$; for $A = 0 \implies 0 \cdot 1 = 0$.
  • Proof of $A \cdot A = A$: For $A = 1 \implies 1 \cdot 1 = 1$; for $A = 0 \implies 0 \cdot 0 = 0$.
  • Proof of $A \cdot \bar{A} = 0$: For $A = 1 \implies 1 \cdot 0 = 0$; for $A = 0 \implies 0 \cdot 1 = 0$.

• Algebraic Proofs of Complex Simplifications:

  • Proof of $A + A \cdot B = A$:
  • $A + A \cdot B = A \cdot 1 + A \cdot B$
  • $= A \cdot (1 + B)$
  • $= A \cdot 1$
  • $= A$
  • Proof of $(A + B)(A + C) = A + B \cdot C$:
  • $(A + B)(A + C) = A \cdot A + A \cdot C + B \cdot A + B \cdot C$
  • $= A + A \cdot C + A \cdot B + B \cdot C$
  • $= A(1 + C + B) + B \cdot C$
  • $= A(1) + B \cdot C$
  • $= A + B \cdot C$
  • Proof of $A + \bar{A} \cdot B = A + B$:
  • $A + \bar{A} \cdot B = (A + \bar{A}) \cdot (A + B)$
  • $= 1 \cdot (A + B)$
  • $= A + B$

Principle of Duality

• Definition: The dual of any Boolean expression or identity is obtained by performing the following conversions:

  • Change all OR operators ($+$) to AND operators ($\cdot$).
  • Change all AND operators ($\cdot$) to OR operators ($+$).n * Interchange binary constants $0$ and $1$ (change all $0$'s to $1$'s and $1$'s to $0$'s).
  • All variables and their complements remain completely unchanged.

• Examples of Dual Pairs:

  • Expression: $A + 1 = 1$ $\implies$ Dual: $A \cdot 0 = 0$
  • Expression: $\bar{1} = 0$ $\implies$ Dual: $\bar{0} = 1$
  • Expression: $A \cdot B = B \cdot A$ $\implies$ Dual: $A + B = B + A$
  • Expression: $A \cdot \bar{A} = 0$ $\implies$ Dual: $A + \bar{A} = 1$
  • Expression: $\overline{A \cdot B} = \bar{A} + \bar{B}$ $\implies$ Dual: $\overline{A + B} = \bar{A} \cdot \bar{B}$

De Morgan's Theorems

• Law 1: $\overline{A + B} = \bar{A} \cdot \bar{B}$

  • Statement: The complement of a sum of variables is equal to the product of the individual complements of those variables.
  • Logic Gate Equivalence: A NOR gate is equivalent to a Bubbled AND gate (also called a negative AND gate).
  • Truth Table Verification:     | $A$ | $B$ | $A+B$ | $\overline{A+B}$ | $\bar{A}$ | $\bar{B}$ | $\bar{A} \cdot \bar{B}$ |     | :---: | :---: | :---: | :---: | :---: | :---: | :---: |     | 0 | 0 | 0 | 1 | 1 | 1 | 1 |     | 0 | 1 | 1 | 0 | 1 | 0 | 0 |     | 1 | 0 | 1 | 0 | 0 | 1 | 0 |     | 1 | 1 | 1 | 0 | 0 | 0 | 0 |

• Law 2: $\overline{A \cdot B} = \bar{A} + \bar{B}$

  • Statement: The complement of a product of variables is equal to the sum of the individual complements of those variables.
  • Logic Gate Equivalence: A NAND gate is equivalent to a Bubbled OR gate (also called a negative OR gate).
  • Truth Table Verification:     | $A$ | $B$ | $A \cdot B$ | $\overline{A \cdot B}$ | $\bar{A}$ | $\bar{B}$ | $\bar{A} + \bar{B}$ |     | :---: | :---: | :---: | :---: | :---: | :---: | :---: |     | 0 | 0 | 0 | 1 | 1 | 1 | 1 |     | 0 | 1 | 0 | 1 | 1 | 0 | 1 |     | 1 | 0 | 0 | 1 | 0 | 1 | 1 |     | 1 | 1 | 1 | 0 | 0 | 0 | 0 |

• Simplification Examples using De Morgan's Law:

  • Problem 1: Simplify $Y(A, B, C, D) = \overline{(A + C) \cdot (B + \bar{D})}$
  • Step 1: Apply Law 2 $\implies Y = \overline{(A + C)} + \overline{(B + \bar{D})}$
  • Step 2: Apply Law 1 $\implies Y = (\bar{A} \cdot \bar{C}) + (\bar{B} \cdot \bar{\bar{D}})$
  • Step 3: Apply double negation rule $\implies Y = \bar{A}\bar{C} + \bar{B}D$
  • Problem 2: Simplify $\overline{\overline{AB + CD + EF} + \overline{AB + CD}}$
  • Step 1: Apply Law 1 $\implies (\overline{\overline{AB + CD + EF}}) \cdot (\overline{\overline{AB + CD}})$
  • Step 2: Cancel double overlines $\implies (AB + CD + EF) \cdot (AB + CD)$
  • Step 3: Apply absorption $\implies AB + CD$

Basic and Universal Logic Gates

• Logic Gate Definition: A physical digital circuit that performs a specific logical operation on one or more binary inputs to produce a single binary output.

• NOT Gate (Inverter):

  • Logic Operation: Performs inversion or complementing ($Y = \bar{A}$).
  • Truth Table:     | Input ($A$) | Output ($Y$) |     | :---: | :---: |     | 0 | 1 |     | 1 | 0 |

• AND Gate:

  • Logic Operation: Output is high ($1$) if and only if all inputs are high ($Y = A \cdot B$).
  • 2-Input Truth Table:     | $A$ | $B$ | $Y = A \cdot B$ |     | :---: | :---: | :---: |     | 0 | 0 | 0 |     | 0 | 1 | 0 |     | 1 | 0 | 0 |     | 1 | 1 | 1 |
  • 3-Input Truth Table:     | $A$ | $B$ | $C$ | $Y = A \cdot B \cdot C$ |     | :---: | :---: | :---: | :---: |     | 0 | 0 | 0 | 0 |     | 0 | 0 | 1 | 0 |     | 0 | 1 | 0 | 0 |     | 0 | 1 | 1 | 0 |     | 1 | 0 | 0 | 0 |     | 1 | 0 | 1 | 0 |     | 1 | 1 | 0 | 0 |     | 1 | 1 | 1 | 1 |

• OR Gate:

  • Logic Operation: Output is high ($1$) if at least one input is high ($Y = A + B$).
  • 2-Input Truth Table:     | $A$ | $B$ | $Y = A + B$ |     | :---: | :---: | :---: |     | 0 | 0 | 0 |     | 0 | 1 | 1 |     | 1 | 0 | 1 |     | 1 | 1 | 1 |
  • 3-Input Truth Table:     | $A$ | $B$ | $C$ | $Y = A + B + C$ |     | :---: | :---: | :---: | :---: |     | 0 | 0 | 0 | 0 |     | 0 | 0 | 1 | 1 |     | 0 | 1 | 0 | 1 |     | 0 | 1 | 1 | 1 |     | 1 | 0 | 0 | 1 |     | 1 | 0 | 1 | 1 |     | 1 | 1 | 0 | 1 |     | 1 | 1 | 1 | 1 |

• Universal Gates (NAND and NOR):

  • A universal gate can implement any Boolean function without requiring any other gate type.
  • NAND Gate:
  • Expression: $Y = \overline{A \cdot B} = \bar{A} + \bar{B}$ (Equivalent to Bubbled OR gate).
  • Truth Table:       | $A$ | $B$ | $Y = \overline{A \cdot B}$ |       | :---: | :---: | :---: |       | 0 | 0 | 1 |       | 0 | 1 | 1 |       | 1 | 0 | 1 |       | 1 | 1 | 0 |
  • NOR Gate:
  • Expression: $Y = \overline{A + B} = \bar{A} \cdot \bar{B}$ (Equivalent to Bubbled AND gate).
  • Truth Table:       | $A$ | $B$ | $Y = \overline{A + B}$ |       | :---: | :---: | :---: |       | 0 | 0 | 1 |       | 0 | 1 | 0 |       | 1 | 0 | 0 |       | 1 | 1 | 0 |

• Exclusive Gates:

  • XOR Gate (Exclusive-OR):
  • Expression: $Y = A \oplus B = A\bar{B} + \bar{A}B$
  • Operation: Produces high output ($1$) when inputs are different.
  • Truth Table:       | $A$ | $B$ | $Y = A \oplus B$ |       | :---: | :---: | :---: |       | 0 | 0 | 0 |       | 0 | 1 | 1 |       | 1 | 0 | 1 |       | 1 | 1 | 0 |
  • XNOR Gate (Exclusive-NOR):
  • Expression: $Y = A \odot B = \overline{A \oplus B} = AB + \bar{A}\bar{B}$
  • Derivation: $(A + B)(\bar{A} + \bar{B}) = A\bar{A} + A\bar{B} + \bar{A}B + B\bar{B}$ complement… yields $AB + \bar{A}\bar{B}$.
  • Operation: Produces high output ($1$) when inputs are identical.
  • Truth Table:       | $A$ | $B$ | $Y = A \odot B$ |       | :---: | :---: | :---: |       | 0 | 0 | 1 |       | 0 | 1 | 0 |       | 1 | 0 | 0 |       | 1 | 1 | 1 |

• Finding Expression from Circuit Diagram:

  • For a multi-stage circuit with inputs $A, B, C, D, E, F$ where $A, B$ enter an AND gate, $C, D$ enter an AND gate, their outputs enter an OR gate, and the result is OR-ed with $E \cdot F$:
  • Output Expression: $Y(A, B, C, D, E, F) = (A \cdot B + C \cdot D) + E \cdot F$

Canonical and Standard Forms of Logical Expressions

• Standard Representations:

  • Sum of Products (SOP): Logic expression formed by OR-ing individual product terms.
  • Example: $Y(A, B, C) = AB\bar{C} + A\bar{B}C + BC$
  • Product of Sums (POS): Logic expression formed by AND-ing individual sum terms.
  • Example: $Y(A, B, C) = (A + B)(B + C)(C + A)$

• Minterms ($m_i$):

  • A product term containing all variables of the function in either complemented or uncomplemented form.
  • For a minterm, a variable is represented uncomplemented if its binary value is $1$, and complemented if its binary value is $0$
  • A minterm evaluates to $1$ for its specific variable combination.
  • 3-Variable Minterm Table:     | $A$ | $B$ | $C$ | Minterm Expression | Designation |     | :---: | :---: | :---: | :---: | :---: |     | 0 | 0 | 0 | $\bar{A}\bar{B}\bar{C}$ | $m_0$ |     | 0 | 0 | 1 | $\bar{A}\bar{B}C$ | $m_1$ |     | 0 | 1 | 0 | $\bar{A}B\bar{C}$ | $m_2$ |     | 0 | 1 | 1 | $\bar{A}BC$ | $m_3$ |     | 1 | 0 | 0 | $A\bar{B}\bar{C}$ | $m_4$ |     | 1 | 0 | 1 | $A\bar{B}C$ | $m_5$ |     | 1 | 1 | 0 | $AB\bar{C}$ | $m_6$ |     | 1 | 1 | 1 | $ABC$ | $m_7$ |

• Maxterms ($M_i$):

  • A sum term containing all variables of the function in either complemented or uncomplemented form.
  • For a maxterm, a variable is represented complemented if its binary value is $1$, and uncomplemented if its binary value is $0$
  • A maxterm evaluates to $0$ for its specific variable combination.
  • 3-Variable Maxterm Table:     | $A$ | $B$ | $C$ | Maxterm Expression | Designation |     | :---: | :---: | :---: | :---: | :---: |     | 0 | 0 | 0 | $A + B + C$ | $M_0$ |     | 0 | 0 | 1 | $A + B + \bar{C}$ | $M_1$ |     | 0 | 1 | 0 | $A + \bar{B} + C$ | $M_2$ |     | 0 | 1 | 1 | $A + \bar{B} + \bar{C}$ | $M_3$ |     | 1 | 0 | 0 | $\bar{A} + B + C$ | $M_4$ |     | 1 | 0 | 1 | $\bar{A} + B + \bar{C}$ | $M_5$ |     | 1 | 1 | 0 | $\bar{A} + \bar{B} + C$ | $M_6$ |     | 1 | 1 | 1 | $\bar{A} + \bar{B} + \bar{C}$ | $M_7$ |

• Expansion to Canonical Standard Form:

  • Canonical SOP Conversion: Multiply missing variables in a term by $(x + \bar{x}) = 1$
  • Example: Convert $Y(A, B, C) = AB + C$ to standard SOP form:
  • $AB = AB(C + \bar{C}) = ABC + AB\bar{C}$
  • $C = (A + \bar{A})(B + \bar{B})C = (AB + A\bar{B} + \bar{A}B + \bar{A}\bar{B})C = ABC + A\bar{B}C + \bar{A}BC + \bar{A}\bar{B}C$
  • Combining unique terms: $Y = \bar{A}\bar{B}C + \bar{A}BC + A\bar{B}C + AB\bar{C} + ABC$
  • Numeric Notation: $Y(A, B, C) = \sum m(1, 3, 5, 6, 7)$
  • Canonical POS Conversion: Add missing variable products $x \cdot \bar{x} = 0$ to incomplete sum terms and apply distributivity.
  • Example: Convert $Y(A, B, C) = (A + B)(B + C)(A + C)$ to standard POS form:
  • $(A + B) = A + B + C\bar{C} = (A + B + C)(A + B + \bar{C})$
  • $(B + C) = A\bar{A} + B + C = (A + B + C)(\bar{A} + B + C)$
  • $(A + C) = A + B\bar{B} + C = (A + B + C)(A + \bar{B} + C)$
  • Combining unique terms: $Y = (A + B + C)(A + B + \bar{C})(A + \bar{B} + C)(\bar{A} + B + C)$
  • Numeric Notation: $Y(A, B, C) = \prod M(0, 1, 2, 4)$

• Conversion between SOP and POS:

  • The POS representation of a function consists of maxterms whose indices are missing from the SOP minterm list.
  • Example: If $Y(A, B, C) = \sum m(0, 2, 4, 5, 6)$, the missing indices are $1, 3, 7$.
  • Therefore, the POS equivalent is $Y(A, B, C) = \prod M(1, 3, 7) = (A + B + \bar{C})(A + \bar{B} + \bar{C})(\bar{A} + \bar{B} + \bar{C})$.

Karnaugh Map (K-map) Simplification

• Overview:

  • The Karnaugh map is a graphical technique used to minimize Boolean functions for 2, 3, 4, 5, and 6 variables.
  • Number of cells in K-map equals $2^n$ where $n$ is the number of variables:
  • 2 variables: $2^2 = 4$ cells
  • 3 variables: $2^3 = 8$ cells
  • 4 variables: $2^4 = 16$ cells
  • 5 variables: $2^5 = 32$ cells (two 16-cell maps for $A=0$ and $A=1$)
  • Cell Labeling Rule: Uses Gray Code ordering ($00, 01, 11, 10$) where adjacent cells differ by only one bit.

• Step-by-Step Rules for SOP Simplification:

  1. Place $1$'s in cells corresponding to the minterms in the expression.
  2. Enclose adjacent cells containing $1$'s into groups.
  3. Group sizes must be powers of 2 ($1, 2, 4, 8, 16, 32$).
  4. Maximize group size and minimize the total number of groups.
  5. Every $1$ on the map must be included in at least one group.
  6. Groupings can wrap around boundaries (opposite edges top-bottom and left-right are adjacent).
  7. Groups must be rectangular or square blocks oriented horizontally or vertically; diagonal groupings are strictly prohibited.

• SOP Simplification Example:

  • Given $Y(A, B, C, D) = \sum m(0, 2, 4, 7, 8, 10, 12, 13)$
  • Map grid layout (4-variable 16 cells):
  • $m_0(0000)=1, m_2(0010)=1, m_4(0100)=1, m_7(0111)=1, m_8(1000)=1, m_{10}(1010)=1, m_{12}(1100)=1, m_{13}(1101)=1$
  • Grouping:
  • Corner Quad $(m_0, m_2, m_8, m_{10}) \implies \bar{B}\bar{D}$
  • Quad $(m_0, m_4, m_8, m_{12}) \implies \bar{C}\bar{D}$
  • Pair $(m_{12}, m_{13}) \implies AB\bar{C}$
  • Single/Pair $(m_7) \implies \bar{A}BCD$
  • Simplified Expression: $Y = \bar{B}\bar{D} + \bar{C}\bar{D} + AB\bar{C} + \bar{A}BCD$

• Implementation of Simplified Expressions:

  • AOI Logic (AND-OR-INVERT): Standard logic diagram built with AND gates feeding into an OR gate.
  • Conversion from AOI to Universal NAND Logic:
  • Draw the original circuit in AOI logic.
  • Place a circle (bubble) at the output of every AND gate and at every input of the final OR gate (since Bubbled OR = NAND).
  • Add an inverter on any input line that received a circle to preserve original signal polarity.
  • Conversion from AOI to Universal NOR Logic:
  • Draw POS circuit with OR gates feeding into an AND gate.
  • Place a bubble at the output of every OR gate and at every input of the AND gate (Bubbled AND = NOR).

• POS Simplification using K-map:

  • Place $0$'s in cells corresponding to maxterm numbers.
  • Group adjacent $0$'s in powers of 2 following standard grouping rules.
  • Combine terms as sums to write the reduced POS expression.
  • Example: $f(A, B, C, D) = \prod M(2, 8, 9, 10, 11, 12, 14)$
  • Grouping $0$'s yields simplified POS expression: $Y = (A + B)(B + C)(\bar{A} + \bar{B} + \bar{D})$

• Don't Care Conditions ($d$ or $X$):

  • In certain logic circuits, specific input combinations never occur or their output levels are unassigned.
  • These combinations are marked as $X$ (or $d$) on the K-map.
  • An $X$ can be treated as $1$ if it aids in forming a larger group size, or as $0$ if it does not help simplify the expression. It is not required to enclose all $X$'s.
  • Example: $Y(A, B, C, D) = \sum m(0, 1, 2, 4, 8, 10) + d(5, 7)$
  • Including don't care conditions at $m_5, m_7$ allows quad creation $(m_0, m_1, m_4, m_5) \implies \bar{A}\bar{C}$ and $(m_4, m_5, m_6, m_7) \implies \bar{A}B$
  • Reduced SOP expression: $Y = \bar{B}\bar{D} + \bar{A}\bar{C}$

Quine-McCluskey (Tabulation) Method

• Purpose: An algorithmic tabular method used to minimize Boolean functions, ideal when variable count exceeds 4 or 5 variables.

• Step-by-Step Procedure:

  • Step 1: List all minterms in their binary representation.
  • Step 2: Group binary minterms into index groups based on the count of $1$'s present in their representation (Index 0, Index 1, Index 2, etc.).
  • Step 3: Compare each minterm in Index group $k$ with every minterm in Index group $k+1$. If two terms differ by exactly one bit position, combine them into a pair, replacing the differing bit position with a dash (-).
  • Step 4: Repeat the comparison process between combined pairs to form quads (2 dashes), octets (3 dashes), etc., until no further combinations can be made.
  • Step 5: Mark all uncombined terms; these represent the Prime Implicants (PIs).
  • Step 6: Construct a Prime Implicant Chart listing Prime Implicants along rows and original minterms along columns.
  • Step 7: Place checks (X) where a PI covers a minterm. Identify Essential Prime Implicants (EPIs) (any column containing only one X makes its corresponding row PI essential).
  • Step 8: Select minimum additional PIs required to cover any remaining minterms.

• Solved Tabulation Example:

  • Function: f(A, B, C, D) = \sum m(1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 15)$\n * **Column 1 (Binary Index Groups)**:\n * Index 1: m_1(0001), m_2(0010), m_8(1000)\n * Index 2: m_3(0011), m_5(0101), m_6(0110), m_9(1001), m_{12}(1100)\n * Index 3: m_7(0111), m_{13}(1101)\n * Index 4: m_{15}(1111)\n * **Column 2 (Pairs)**:\n * (1,3): 00-1\n * (1,5): 0-01\n * (1,9): -001\n * (2,3): 001-\n * (2,6): 0-10\n * (8,9): 100-\n * (8,12): 1-00\n * (3,7): 0-11\n * (5,7): 01-1\n * (5,13): -101\n * (6,7): 011-\n * (9,13): 1-01\n * (12,13): 110-\n * (7,15): -111\n * (13,15): 11-1\n * **Column 3 (Quads / Combinations)**:\n * P = (1,3,5,7): 0--1 \implies \bar{A}D\n * Q = (1,9,5,13): --01 \implies \bar{C}D\n * R = (2,3,6,7): 0-1- \implies \bar{A}C\n * S = (8,9,12,13): 1-0- \implies A\bar{C}\n * T = (5,7,13,15): -1-1 \implies BD\n * **Prime Implicant Chart Evaluation**:\n * Minterms: 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 15\n * Essential Prime Implicants: R (\bar{A}C)$covers$2,3,6,7$;$S (A\bar{C})$covers$8,9,12,13$;$T (BD)$covers$5,7,13,15.\n * Remaining uncovered minterm: m_1\n * Minterm m_1$can be covered by either$P (\bar{A}D)$or$Q (\bar{C}D).\n * Final Minimal Logic Expressions:\n * Y = R + S + T + P = \bar{A}C + A\bar{C} + BD + \bar{A}D\n * OR\n * Y = R + S + T + Q = \bar{A}C + A\bar{C} + BD + \bar{C}D\n\n# Combinational Logic Circuits\n\n* Definition: A logic circuit in which the output at any instant depends strictly on the present combination of inputs, with no reliance on past inputs or past states. Contains zero memory elements.\n\n* Comparison with Sequential Circuits:\n * Combinational Circuits: Memoryless, outputs rely only on present inputs.\n * Sequential Circuits: Contain memory elements (flip-flops/latches), outputs depend on present inputs and stored past state.\n\n* General Design Steps for Combinational Logic:\n 1. Determine the required number of input and output variables from problem specification.\n 2. Construct the truth table defining output values for all input combinations.\n 3. Obtain simplified Boolean functions for each output using K-maps or algebraic reduction.\n 4. Draw the logic circuit diagram implementing the simplified expressions.\n\n* Design Example — Even Parity Generator (4 Inputs):\n * Problem: Design a circuit with 4 input variables (A, B, C, D$) that outputs logic$1$when the number of$1's in the input is even.\n * Output Y = 1$for minterms with an even number of set bits:$m_0(0000), m_3(0011), m_5(0101), m_6(0110), m_9(1001), m_{10}(1010), m_{12}(1100), m_{15}(1111).\n * Expression: Y = \sum m(0, 3, 5, 6, 9, 10, 12, 15)\n * Simplified Function using Exclusive-NOR equivalences:\n * Y = \overline{A \oplus B \oplus C \oplus D}\n\n# Arithmetic and Comparison Circuits\n\n* **1-Bit Digital Comparator**:\n * Inputs: A, B (1 bit each)\n * Outputs: A > B$,$A = B$,$A < B\n * Truth Table:\n    | A$|$B$|$A > B$|$A = B$|$A < B |\n    | :---: | :---: | :---: | :---: | :---: |\n    | 0 | 0 | 0 | 1 | 0 |\n    | 0 | 1 | 0 | 0 | 1 |\n    | 1 | 0 | 1 | 0 | 0 |\n    | 1 | 1 | 0 | 1 | 0 |\n * Derived Equations:\n * A > B = A\bar{B}\n * A = B = AB + \bar{A}\bar{B} = \overline{A \oplus B}\n * A < B = \bar{A}B\n\n* **Half Adder**:\n * Adds two single-bit inputs A$and$B\n * Outputs:\n * Sum (S) = A \oplus B = A\bar{B} + \bar{A}B\n * Carry (C_{out}) = AB\n\n* **Full Adder**:\n * Adds three single-bit inputs A, B,$and$C_{in}\n * Derived Equations:\n * Sum = A \oplus B \oplus C_{in}\n * C_{out} = AB + B C_{in} + A C_{in}\n * Implementation using Two Half Adders and One OR Gate:\n * Half Adder 1 outputs: S_1 = A \oplus B$,$C_1 = AB\n * Half Adder 2 takes inputs S_1$and$C_{in}, yielding:\n * Sum = S_1 \oplus C_{in} = (A \oplus B) \oplus C_{in}\n * C_2 = S_1 \cdot C_{in} = (A \oplus B) C_{in}\n * Final Carry Output:\n * C_{out} = C_1 + C_2 = AB + (A \oplus B) C_{in}\n * = AB + (A\bar{B} + \bar{A}B) C_{in} = AB + A\bar{B}C_{in} + \bar{A}BC_{in}\n * = AB(1 + C_{in}) + A\bar{B}C_{in} + \bar{A}BC_{in} = AB + ABC_{in} + A\bar{B}C_{in} + \bar{A}BC_{in}\n * = AB + AC_{in}(B + \bar{B}) + BC_{in} = AB + B C_{in} + A C_{in}\n\n* **Half Subtractor**:\n * Subtracts input bit B$from input bit$A\n * Outputs:\n * Difference (D) = A \oplus B = A\bar{B} + \bar{A}B\n * Borrow (B_{out}) = \bar{A}B\n\n* **Full Subtractor**:\n * Subtracts bits B$and$B_{in}$from input bit$A\n * Outputs:\n * Difference = A \oplus B \oplus B_{in}\n * B_{out} = \bar{A}B + \bar{A}B_{in} + BB_{in}\n * Implementation using Two Half Subtractors and One OR Gate:\n * Half Subtractor 1 outputs: D_1 = A \oplus B$,$B_1 = \bar{A}B\n * Half Subtractor 2 takes inputs D_1$and$B_{in}, yielding:\n * Diff = D_1 \oplus B_{in} = (A \oplus B) \oplus B_{in}\n * B_2 = \overline{D_1} \cdot B_{in} = \overline{(A \oplus B)} B_{in}\n * Final Borrow Output:\n * B_{out} = B_1 + B_2 = \bar{A}B + \overline{(A \oplus B)} B_{in} = \bar{A}B + (AB + \bar{A}\bar{B}) B_{in}\n * = \bar{A}B + \bar{A}B_{in} + BB_{in}\n\n# Data Selection and Decoding Circuits\n\n* **Multiplexer (MUX) / Data Selector**:\n * Function: Routes binary data from one of N = 2^n$input lines to a single output line based on$n select control inputs.\n * Enable Line (E$): Active High ($E=1$enables device) or Active Low ($\bar{E}=0 enables device).\n * Common Configurations:\n * **2:1 MUX**: 2 data inputs (I_0, I_1$), 1 select line ($S_0$). Output$Y = \bar{S}0 I_0 + S_0 I_1\n * **4:1 MUX**: 4 data inputs (I_0, I_1, I_2, I_3$), 2 select lines ($S_1, S_0).\n * Output Equation: Y = E [\bar{S}_1 \bar{S}_0 I_0 + \bar{S}_1 S_0 I_1 + S_1 \bar{S}_0 I_2 + S_1 S_0 I_3]\n * **8:1 MUX**: 8 data inputs (I_0$to$I_7$), 3 select lines ($S_2, S_1, S_0).\n * **16:1 MUX**: 16 data inputs (I_0$to$I{15}$), 4 select lines ($S_3, S_2, S_1, S_0).\n\n* **Demultiplexer (DEMUX)**:\n * Function: Performs reverse operation of MUX; routes a single input line D$to one of$N = 2^n$output lines determined by$n select control lines.\n * **1:4 DEMUX**:\n * Inputs: Data D$, Select lines$S_1, S_0$, Enable$E\n * Outputs:\n * Y_0 = \bar{S}_1 \bar{S}_0 D E\n * Y_1 = \bar{S}_1 S_0 D E\n * Y_2 = S_1 \bar{S}_0 D E\n * Y_3 = S_1 S_0 D E\n\n* **Decoder**:\n * Function: Converts an n$-bit binary coded input to a maximum of$2^n distinct output lines.\n * **3-to-8 Line Decoder (Decimal to Octal Decoder)**:\n * Inputs: X_2, X_1, X_0 (3 bits)\n * Outputs: Y_0$to$Y_7 (8 lines)\n * Logic Equations: Each output corresponds to a unique minterm derived using AND gates (Y_0 = \bar{X}_2\bar{X}_1\bar{X}_0$,$Y_1 = \bar{X}_2\bar{X}_1X_0$, ...,$Y_7 = X_2X_1X_0).\n\n* **Encoder**:\n * Function: Performs reverse operation of decoder; converts an active input signal on one of 2^n$input lines into an$n-bit coded output.\n * **8-to-3 Octal to Binary Encoder**:\n * Inputs: 8 lines (X_0$through$X_7)\n * Outputs: 3 binary bits (Y_2, Y_1, Y_0)\n * **10-to-4 Decimal to BCD Encoder**:\n * Inputs: 10 lines (X_0$to$X_9)\n * Outputs: 4 BCD output bits (Y_3, Y_2, Y_1, Y_0)\n * Output Equations:\n * Y_0 = X_1 + X_3 + X_5 + X_7 + X_9\n * Y_1 = X_2 + X_3 + X_6 + X_7\n * Y_2 = X_4 + X_5 + X_6 + X_7\n * Y_3 = X_8 + X_9\n\n# Sequential Logic Circuits Overview\n\n* Definition: A digital logic circuit whose output signal depends on both current input signals and the present state stored in memory elements.\n\n* Block Diagram Structure:\n * Consists of a Combinational Logic Circuit paired with Memory Storage Elements (Latches or Flip-Flops) forming a continuous feedback loop.\n\n* Concept of State:\n * The binary contents retained inside memory elements at any given point in time represent the present state of the sequential circuit.\n\n* Classification:\n * **Synchronous Sequential Circuits**:\n * State updates and operations across all memory elements are governed synchronously by a centralized periodic timing signal called a clock (CLK$$).
  • Asynchronous Sequential Circuits:
  • Circuit behavior and state changes occur immediately in response to changes in input signals without relying on a clock signal.