# Introduction to Digital Logic Digital logic is the fundamental concept used in creating electronic devices such as calculators, computers, and digital watches. It involves the use of digital circuits. * **Digital Circuits**: Composed of a large number of logic gates and operate based on discrete (digital) values, typically 0 (LOW) and 1 (HIGH). * **Logic Gates**: The building blocks of digital circuits. Each gate performs a particular logical function by taking two or more logic inputs (LOW or HIGH) and producing a single output (LOW or HIGH) determined by the input logic levels. ## Types of Logic Gates Commonly used logic gates include AND, OR, NAND, NOR, NOT, Exclusive-OR (XOR), and Exclusive-NOR. ### 1. AND Gate * **Function**: Output is HIGH (1) *only when all inputs are HIGH (1)*. * **Mathematical Expression**: For two inputs (x, y), $F = xy$. For three inputs, $F = xyz$. * **Symbol, Expression, and Truth Table:** ### 2. OR Gate * **Function**: Output is HIGH (1) *when any input is HIGH (1)*. * **Mathematical Expression**: For two inputs (x, y), $F = x + y$ (where '+' stands for the OR operation). For three inputs, $F = x + y + z$. * **Symbol, Expression, and Truth Table:** ### 3. NAND Gate * **Function**: Combines an AND gate and a NOT gate. Output is LOW (0) *only when all inputs are HIGH (1)*. It produces the inverse of an AND gate's output. * **Mathematical Expression**: For two inputs (x, y), $F = \overline{xy}$. The bar indicates inversion. * **Symbol, Expression, and Truth Table:** ### 4. NOR Gate * **Function**: Combines an OR gate and a NOT gate. Output is LOW (0) *when any input is HIGH (1)*. It produces the inverse of an OR gate's output. * **Mathematical Expression**: For two inputs (x, y), $F = \overline{x+y}$. The bar indicates inversion. * **Symbol, Expression, and Truth Table:** ### 5. NOT Gate (Inverter) * **Function**: A single-input gate that converts LOW to HIGH and vice versa. It *inverts* the input. * **Mathematical Expression**: For input x, $F = \overline{x}$. The bar indicates inversion. * **Symbol, Expression, and Truth Table:** ### 6. Exclusive-OR (XOR) Gate * **Function**: Produces a HIGH (1) output *only when the two inputs are at different logic levels*. * **Mathematical Expression**: For two inputs (x, y), $F = x\overline{y} + \overline{x}y$. * **Symbol, Expression, and Truth Table:** ## Truth Tables * **Definition**: A table that represents a Boolean function or digital logic circuit by showing how the circuit's output responds to all possible combinations of inputs using logic '1' for true (HIGH) and '0' for false (LOW). * **Properties**: * Consists of rows and columns. * Shows the relationship between inputs and output. * Lists all possible input combinations in columns on the left. * The output is shown in the rightmost column. * Input columns are constructed in binary counting order. **Example Truth Table** (for Boolean function $F=(x \cdot y \cdot \overline{z}) + (x \cdot y \cdot z) + (\overline{x} \cdot y)$): | **x** | **y** | **z** | **$\overline{x}$** | **$\overline{z}$** | **$(x \cdot y \cdot \overline{z})$** | **$(x \cdot y \cdot z)$** | **$(\overline{x} \cdot y)$** | **$F = (x \cdot y \cdot \overline{z}) + (x \cdot y \cdot z) + (\overline{x} \cdot y)$** | | :---: | :---: | :---: | :---: | :---: | :----------: | :---------: | :--------: | :--------------------------------: | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | ## Boolean Algebra ### 1. Boolean Identities Boolean identities are mathematical expressions or equations that are always true regardless of the values of the binary variables (0 or 1). They are fundamental for simplifying and analyzing logical expressions and digital circuits. | Identity Type | Boolean Identity | | :--- | :--- | | Identity Law (OR) | $A + 0 = A$ | | Identity Law (AND) | $A \cdot 1 = A$ | | Domination Law (OR) | $A + 1 = 1$ | | Domination Law (AND) | $A \cdot 0 = 0$ | | Complement Law (OR) | $A + \overline{A} = 1$ | | Complement Law (AND) | $A \cdot \overline{A} = 0$ | | Double Negation Law | $\overline{\overline{A}} = A$ | | Idempotent Law (OR) | $A + A = A$ | | Idempotent Law (AND) | $A \cdot A = A$ | | Associative Law (OR) | $(A + B) + C = A + (B + C)$ | | Associative Law (AND) | $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ | | Distributive Law (AND over OR) | $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$ | | Distributive Law (OR over AND) | $A + (B \cdot C) = (A + B) \cdot (A + C)$ | | Absorption Law (OR) | $A + (A \cdot B) = A$ | | Absorption Law (AND) | $A \cdot (A + B) = A$ | | De Morgan's Theorem 1 | $\overline{A+B} = \overline{A} \cdot \overline{B}$ | | De Morgan's Theorem 2 | $\overline{A \cdot B} = \overline{A} + \overline{B}$ | ### 2. Boolean Function and its Conversion to Logic Circuit * **Boolean Function**: An expression formed with binary variables, logical operators (OR, AND, NOT), parentheses, and an equal sign. * **Conversion Process**: A Boolean function can be directly transformed from its algebraic expression into a logic circuit using AND, OR, and NOT gates. **Example 1**: $F1 = xy\overline{z}$ **Example 2**: $F2 = x + \overline{y}z$ **Example 3**: $F3 = \overline{x}\overline{y}z + \overline{x}yz + x\overline{y}$ ### 3. Simplification of Boolean Function using Karnaugh Map (K-Map) Introduced by Maurice Karnaugh in 1953, it provides a simple, pictorial method for simplifying Boolean functions. A simplified function requires fewer logic gates, reducing cost and complexity. #### a. Simplification of Two-Variable Boolean Function Using K-Map A two-variable K-map (e.g., for variables A and B) has two rows and two columns. **Simplification Rules**: 1. **Plot terms**: Place a '1' in the corresponding cell for each term. 2. **Group cells**: Make groups of two adjacent cells containing '1's. Groups can be horizontal or vertical, but *not diagonal*. 3. **Eliminate variables**: Within a group, eliminate variables that appear in both normal and complemented form. 4. **Write simplified function**: Express the result as the sum of the remaining variables. #### b. Simplification of Three-Variable Boolean Function Using K-Map A three-variable K-map has eight cells. Columns are labeled using Gray code (e.g., $\overline{B}\overline{C}, \overline{B}C, BC, B\overline{C}$) to ensure adjacency between columns that wrap around. | | $\overline{B}\overline{C}$ | $\overline{B}C$ | $BC$ | $B\overline{C}$ | | :--- | :---: | :---: | :---: | :---: | | $\overline{A}$ | $\overline{A}\overline{B}\overline{C}$ | $\overline{A}\overline{B}C$ | $\overline{A}BC$ | $\overline{A}B\overline{C}$ | | $A$ | $A\overline{B}\overline{C}$ | $A\overline{B}C$ | $ABC$ | $AB\overline{C}$ | ## Principle of Duality in Boolean Algebra The Principle of Duality states that for any given Boolean expression, a dual expression can be obtained by: 1. Interchanging the AND ($\cdot$) and OR ($+$) operators. 2. Interchanging 0s and 1s. | Expression | Dual | | :--- | :--- | | $1 \cdot 0 = 0$ | $0 + 1 = 1$ | | $A \cdot 0 = 0$ | $A + 1 = 1$ | | $A \cdot 1 = A$ | $A + 0 = A$ | | $A \cdot B = B \cdot A$ | $A + B = B + A$ | | $A \cdot (A + B) = A$ | $A + (A \cdot B) = A$ | ## Applications of Logic Gates Logic gates are essential components in digital electronics: * **Memory Circuits**: Used to build flip-flops and latches. * **Data Encoding/Decoding**: Used in communication systems. * **Arithmetic Operations**: Multiplication and division in CPUs. * **Security Systems**: Control access and alarms. * **Automotive Electronics**: Engine control and ABS. ## Practical Implementation: NOT Gate on a Breadboard Hands-on experiment to build and test a NOT gate using basic electronic components. **Procedure Overview**: Involves placing components, connecting the power supply, then wiring the resistor, switch, NPN transistor, and LED. **Expected Result**: The LED should light up when the input switch is *not pressed* (logic 0), and turn off when the switch *is pressed* (logic 1).

1.3 Digital Logic And Logic Gates | Computer Systems | Computer 11