Digital Logic & Programming Basics

Cheatsheet Content

1. Program Development Cycle Phases: Problem Definition: Understand the problem to be solved. Analysis: Gather requirements, analyze inputs, processes, and outputs. Design: Create a logical plan (algorithms, flowcharts, pseudocode). Coding: Translate the design into a specific programming language. Testing & Debugging: Find and fix errors, verify functionality. Implementation: Deploy the software for use. Maintenance: Update and improve the software over time. 2. Application Software Definition: Software designed to perform specific tasks for the user. Examples: Word Processors (e.g., MS Word): Create, edit, format text documents. Features include spell check, grammar check, formatting tools, templates. Image Editors (e.g., Photoshop, GIMP): Manipulate and enhance digital images. Features include layers, filters, color correction, drawing tools. 3. Factorial Algorithm Definition: For a non-negative integer $n$, $n!$ (n-factorial) is the product of all positive integers less than or equal to $n$. $0! = 1$. Algorithm (Iterative): FUNCTION Factorial(n): IF n 4. De Morgan's Theorems For two variables A and B: 1. $\overline{A \cdot B} = \overline{A} + \overline{B}$ 2. $\overline{A + B} = \overline{A} \cdot \overline{B}$ Proof (using Truth Table for $\overline{A \cdot B} = \overline{A} + \overline{B}$): A B $A \cdot B$ $\overline{A \cdot B}$ $\overline{A}$ $\overline{B}$ $\overline{A} + \overline{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 Since $\overline{A \cdot B}$ and $\overline{A} + \overline{B}$ columns are identical, the theorem is proven. 5. Binary Subtraction (1's & 2's Complement) 1's Complement: Invert all bits (0 to 1, 1 to 0). 2's Complement: 1's complement + 1. Method for $A - B$: Find the 2's complement of B. Add A to the 2's complement of B. If there is a carry-out, discard it (result is positive). If there is no carry-out, the result is negative and in 2's complement form. To get the magnitude, take the 2's complement of the result. Example: $(110101)_2 - (100101)_2$ $A = 110101_2$ ($53_{10}$) $B = 100101_2$ ($37_{10}$) 1's Complement of $B$: $011010_2$ 2's Complement of $B$: $011010_2 + 1_2 = 011011_2$ Add $A$ and 2's Compl. of $B$: 110101 + 011011 -------- 1 010000 Discard carry-out (1). Result: $010000_2 = 16_{10}$. ($53 - 37 = 16$) 6. Decimal Subtraction (9's & 10's Complement) 9's Complement: For each digit $d$, replace with $(9-d)$. 10's Complement: 9's complement + 1. Method for $A - B$: Find the 10's complement of B. Add A to the 10's complement of B. If there is a carry-out, discard it (result is positive). If there is no carry-out, the result is negative. To get the magnitude, take the 10's complement of the result. Example: $8056_{10} - 3250_{10}$ $A = 8056$ $B = 3250$ 9's Complement of $B$: $6749$ (9-3=6, 9-2=7, 9-5=4, 9-0=9) 10's Complement of $B$: $6749 + 1 = 6750$ Add $A$ and 10's Compl. of $B$: 8056 + 6750 ------- 1 4806 Discard carry-out (1). Result: $4806$. ($8056 - 3250 = 4806$) 7. Number Base Conversion Binary to Decimal: $(111011010.11)_2$ $(1 \cdot 2^8) + (1 \cdot 2^7) + (1 \cdot 2^6) + (0 \cdot 2^5) + (1 \cdot 2^4) + (1 \cdot 2^3) + (0 \cdot 2^2) + (1 \cdot 2^1) + (0 \cdot 2^0) + (1 \cdot 2^{-1}) + (1 \cdot 2^{-2})$ $256 + 128 + 64 + 0 + 16 + 8 + 0 + 2 + 0 + 0.5 + 0.25$ $= 474.75_{10}$ 8. Commutative Law (Truth Table) For Addition (OR): $A + B = B + A$ A B $A+B$ $B+A$ 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 For Multiplication (AND): $A \cdot B = B \cdot A$ A B $A \cdot B$ $B \cdot A$ 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 9. Venn Diagram for $x(y+z) = xy+xz$ x y z The shaded region represents $x(y+z)$ which is the union of the intersection of $x$ and $y$, and the intersection of $x$ and $z$. 10. Boolean Function Implementation & Truth Table Function: $F = x'y'z + yz'$ Basic Gates: NOT, AND, OR To implement $x'y'z + yz'$: Get $x'$ (NOT gate on $x$) Get $y'$ (NOT gate on $y$) Perform $x' \cdot y' \cdot z$ (3-input AND gate with $x'$, $y'$, $z$) Perform $y \cdot z'$ (2-input AND gate with $y$, $z'$) Perform OR operation on results of step 3 and 4 ($F = (x'y'z) + (yz')$) Truth Table for $F = x'y'z + yz'$: x y z $x'$ $y'$ $z'$ $x'y'z$ $yz'$ $F$ 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 11. K-Map Minimization (4 Variables) Function: $F(A,B,C,D)=\Sigma(0,1,2,5,7,8,9,10,13,15)$ K-Map Structure: CD\AB 00 01 11 10 00 1 (0) 1 (4) 1 (12) 1 (8) 01 1 (1) 1 (5) 1 (13) 1 (9) 11 1 (3) 1 (7) 1 (15) 1 (11) 10 1 (2) 1 (6) 1 (14) 1 (10) (The numbers in parentheses are the minterm indices) Let's fill the K-map with '1's for the given minterms: CD\AB 00 01 11 10 00 1 0 0 1 01 1 1 1 1 11 0 1 1 0 10 1 0 0 1 Grouping: Quad 1 (Horizontal - AB=X, CD=01): $A'B'C'D + A'BC'D + ABC'D + AB'C'D \rightarrow CD'$ (incorrect grouping for this example, must be $C'D$) Correct Octet (m(0,1,8,9) and m(2,3,10,11), etc. is not present) Let's re-evaluate the K-map and groupings. The minterms are: 0,1,2,5,7,8,9,10,13,15 CD\AB 00 01 11 10 00 1 (0) 0 (4) 0 (12) 1 (8) 01 1 (1) 1 (5) 1 (13) 1 (9) 11 0 (3) 1 (7) 1 (15) 0 (11) 10 1 (2) 0 (6) 0 (14) 1 (10) Groups: Quad 1 (corner group): $m(0,2,8,10) \rightarrow B'D'$ Quad 2 (middle row): $m(1,5,9,13) \rightarrow C'D$ (all are $D=1$, $C=0$, so $C'D$) Pair 1 (remaining): $m(7,15) \rightarrow ABD$ (from $111$, $1111$) or $m(7,15)$ is $BCD$ (from $0111$, $1111$) should be $A'BCD + ABCD = BCD$ No, this is $m(7) = A'BCD$ and $m(15) = ABCD$. So, $A'BCD + ABCD = (A'+A)BCD = BCD$. This can be grouped with another $m(5)$ or $m(13)$, so $m(5,7,13,15)$ forms a quad $BD$. Let's re-examine the map for $m(5,7,13,15)$: $A'BC'D (5)$ $A'BCD (7)$ $ABC'D (13)$ $ABCD (15)$ This quad is $BD$. Let's re-group from the K-map: Quad 1 (Corners): $m(0,2,8,10) \rightarrow D'$ (common $C=0$, $D=0$ and $B=0$, so $B'D'$) This is $A'B'C'D' + A'BC'D' + AB'C'D' + ABC'D'$ which reduces to $B'D'$. No, $m(0) = A'B'C'D'$, $m(2) = A'B'CD'$, $m(8) = AB'C'D'$, $m(10) = AB'CD'$. Common terms are $B'D'$. So this quad is $B'D'$. Quad 2 (Row 2): $m(1,5,13,9) \rightarrow C'D$ $m(1) = A'B'C'D$ $m(5) = A'BC'D$ $m(13) = ABC'D$ $m(9) = AB'C'D$ Common terms are $C'D$. So this quad is $C'D$. Pair 1 (Remaining 1s): $m(7)$ and $m(15)$. These form a pair $m(7,15)$ which is $BCD$. $m(7) = A'BCD$ $m(15) = ABCD$ This pair is $BCD$. Minimized Expression: $F = B'D' + C'D + BCD$ Further simplification: $C'D + BCD = D(C' + BC) = D(C' + B)$ (using absorption law $X+X'Y = X+Y$) So, $F = B'D' + D(C' + B) = B'D' + C'D + BD$ This is the minimized expression. Logic Diagram: (Requires drawing gates. Use AND, OR, NOT gates for $B'D'$, $C'D$, $BD$, then OR them together.) 12. Boolean Algebra Proof: $x + x'y = x + y$ Method 1: Algebraic Proof $x + x'y$ $= (x + x')(x + y)$ (Distributive Law: $A+BC = (A+B)(A+C)$) $= (1)(x + y)$ ($x + x' = 1$) $= x + y$ (Identity Law) Method 2: Truth Table Proof x y $x'$ $x'y$ $x+x'y$ $x+y$ 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 Since columns $x+x'y$ and $x+y$ are identical, the identity is proven. 13. Universal Gates Definition: A universal gate is a logic gate that can be used to construct all other logic gates (AND, OR, NOT). Examples: NAND gate, NOR gate. Proof that NAND is a Universal Gate: NOT gate from NAND: A --|D-- NOT | +-- A --|D-- Connect inputs of a NAND gate together: $\overline{A \cdot A} = \overline{A}$ AND gate from NAND: A --|D--|D-- AND B --|D-- Use a NAND gate followed by another NAND gate (used as a NOT gate): $\overline{\overline{A \cdot B}} = A \cdot B$ OR gate from NAND: A --|D--\ |D-- OR B --|D--/ Use NOT gates (NANDs with inputs tied) on inputs, then feed into another NAND: $\overline{\overline{A} \cdot \overline{B}} = \overline{\overline{A}} + \overline{\overline{B}} = A + B$ (De Morgan's) 14. Boolean Algebra Proof: $x'y'z + x'yz + xy' = x'z + xy'$ Algebraic Proof: LHS: $x'y'z + x'yz + xy'$ $= x'z(y' + y) + xy'$ (Distributive Law) $= x'z(1) + xy'$ ($y' + y = 1$) $= x'z + xy'$ (Identity Law) $=$ RHS Truth Table Proof: (This is for 3 variables x, y, z) x y z $x'$ $y'$ $x'y'z$ $x'yz$ $xy'$ LHS $x'z$ RHS 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 Since columns LHS and RHS are identical, the identity is proven.