Boolean Algebra PDF

Boolean Algebra  Overview Boolean Operations and Expressions Laws and rules of Boolean Algebra DeMorgan’s Theorems Boolean Analysis of Logic Circuits Simplification Using Boolean Algebra Karnaugh Map (K-Map) This type of circuit could be part of: A digital computation system. Boole...

Boolean Algebra  Overview Boolean Operations and Expressions Laws and rules of Boolean Algebra DeMorgan’s Theorems Boolean Analysis of Logic Circuits Simplification Using Boolean Algebra Karnaugh Map (K-Map) This type of circuit could be part of: A digital computation system. Boolean function implementation. Complex logic operations in microprocessors or programmable logic devices. IKB 20803 Computer Organization 2 Boolean Operations and Expressions Boolean Algebra is the mathematics of digital systems. A variable is a symbol used to represent a logical quantity Any single variable can have 0 or 1 values. A complement is the inverse of a variable and is indicated by a bar over the variable (overbar). IKB 20803 Computer Organization 3 Table 2 Boolean Addition and Multiplication Addition Rules Multiplication Rules 0+0=0. 0 0=0 0+1=1. 0 1=0 1+0=1. 1 0=0 1+1=1 IKB 20803 Computer Organization. 4 Boolean Multiplication Boolean Multiplication is equivalent to the AND operation 0. 0 = 0 0. 1 = 0 1. 0 = 0 1. 1 = 1 A product term is the product of literals. Examples of product terms are AB, AB, ABC, ABCD A product term is equal to 1 only of the literals in the term is 1. A product term is equal to 0 when one or more of the literals are 0 IKB 20803 Computer Organization 5 If both inputs are 0, the output is 0.If at least one input is 1, the output is 1. The arithmetic and logic unit (ALU) is the part of the CPU that performs logical operations. What is Logical operation? Identity Law Idempotent Law Dominance Law ***Involution / Double Negation Law** Negation / Complement Law Rules of Boolean Algebra (1/2) Rule Number Boolean Expression 1 (Identify Law) A+0=A 2 (Dominance/Null Law) A+1=1 3 (Dominance/Null Law) A.0=0 4 (Identify Law) A.1=A 5 (Idempotent Law) A+A=A 6 (Inverse Law) A + A’ = 1 8  Rules of Boolean Algebra (2/2) Rule Number Boolean Expression 7 (Idempotent Law) A.A=A 8 (Inverse Law) A. A’ = 0 9 (Double Complement Law) A’’ = A 10 (Absorption Law) A + AB = A 11 (Absorption Law) A + A’B = A + B 12 (Distributive Law) (A + B)(A + C) = A + BC 9 These rules are the building blocks of Boolean algebra and are crucial in simplifying logic circuits and expressions:  The Identity Law explains how adding or multiplying with constants does not affect the variable.  The Dominance Law shows how certain operations with constants override the variable.  The Idempotent Law states that combining a variable with itself yields the same variable.  The Inverse Law highlights the relationship between a variable and its complement. 1. Identity Law A+0=A A 1=A This law states that a variable would remain unchanged when it is ANDed with ‘1’ or ORed with ‘0’, i.e., X.1 = X X+0=X 2. Idempotent Law A+A=A A A=A This law states that a variable would remain unchanged when it is AND or OR with itself, i.e., X + X = X X.X = X Examples of Idempotent Laws One of the most well-known examples of an idempotent operation is the square function. If we square a number, and then square the result, we will get the same answer as if we had only squared the original number once. For example, (3^2)^2 = 3^(2*2) = 3^4 = 81, and 3^2 = 9. 34 =3×3×3×3=81 3. Dominance Law A+1=1 A 0=0 4. Involution / Double Negation Law A'' = A double prime” 5. Negation / Complement Law A + A' = A A' = 0 1 A represents a variable or input. A.A ′ (or sometimes A‾A ) represents the complement or NOT of AA, meaning it is the opposite of AA. The ⋅ indicates the AND operation in Boolean algebra. 0 is the result of the operation, indicating a false or off state. 6. Commutative Law A B=B A A+B=B+A The order of the variable or two different terms does not matter according to this law. X + Y = Y + X X.Y = Y.X 7. Associative Law A + (B + A (B C) = (A + C) = (A B) + C B) C According to this law, the order of an operation does not matter when the priority of the given variables are similar, such as ‘*’ and ‘/’, i.e., X + (Y + Z) = (X + Y) + Z X.(Y.Z) = (X.Y).Z (matrix multiplication) 8. Distributive Law A + (B C) A (B + C) = (A + B) = (A B) + (A + C) (A C) 9. Absorption Law A + (A B) = A A (A + B) = A we absorb similar variables, i.e., X.(X + Y) = X X + XY = X 10. De Morgan's Theorem (A + B)' = A' B' (A B)' = A' + B' This law states that the operation of an OR or an AND logic circuit stays unchanged whenever all inputs are inverted, while the operator actually changes from AND to OR whenever the outputs are inverted, i.e., (X.Y)’ = X’ + Y’ (X + Y)’ = X’.Y’ (X prime plus Y prime) Not X and Y is equivalent to not X or not Y  LOGIC GATE Logic gates are the basic building blocks of any digital system. It is an electronic circuit having one or more than one input and only one output. The relationship between the input and the output is based on a certain logic. Based on this, logic gates are named as AND gate, OR gate, NOT gate, etc.  Basic Logic Gates - OR | AND | NOT | XOR gates | Boolean Algebra An X-NOR Gate (Exclusive-NOR Gate) is a digital logic gate that outputs TRUE (1) when its two inputs are equal, and FALSE (0) when its two inputs are different. It is essentially the inverse (complement) of an XOR gate. 1.Inputs: 1. A and B are the two inputs to the gate. 2.EX-OR Gate: 1. The first part of the diagram is an XOR gate, which computes the logical exclusive OR of A and B. 2. Output of XOR: Y=A⊕BY = A \oplus BY=A⊕B 1.A⊕B=1A \oplus B = 1A⊕B=1 when A ≠ B (inputs are different). 2.A⊕B=0A \oplus B = 0A⊕B=0 when A = B (inputs are the same). 3.NOT Gate: 1. The output of the XOR gate is passed through a NOT gate, which inverts the XOR output. 2. Output after NOT gate: Y=A⊕B‾Y = \overline{A \oplus B}Y=A⊕B​. 1.A⊕B‾=1\overline{A \oplus B} = 1A⊕B​=1 when inputs are the same. 2.A⊕B‾=0\overline{A \oplus B} = 0A⊕B​=0 when inputs are different. The X-NOR Gate gives the output 𝑌=𝐴⊕𝐵‾Y= A⊕B​, meaning it is 1 (True) when both inputs are equal and 0 (False) when the inputs are different. DeMorgan’s Theorem One of DeMorgan’s Theorem is stated as follows: The complement of a product of variables is equal to the sum of the complements of the variables Stated another way The complement of two or more ANDed variables is equivalent to the OR of the complements of the individual variables The formula for expressing this theorem for two variables is XY = X + Y IKB 20803 Computer Organization 44 DeMorgan’s Theorem DeMorgan’s second theorem is stated as follows: The complement of a sum of variables is equal to the product of the complements of the variables. Stated another way, The complement of two or more ORed variables is equivalent to the AND of the complements of the individual variables. The formula for expressing this theorem for two variables is X + Y = X Y IKB 20803 Computer Organization 45 DeMorgan’s Truth Tables X Y XY X+Y X Y X+Y XY 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 IKB 20803 Computer Organization 46 Standard Forms of Boolean Expressions All Boolean expressions, regardless of their form, can be converted into either two standard forms: The sum-of-products The product-of-sum Standardization makes the evaluation, simplification, and implementation of Boolean expressions much more systematic and easier 50  The sum-of-products (SOP) The sum-of-products (SOP) A product term is defined as a term consisting of the product (Boolean multiplication) of literals (variables or their complements). When two or more product terms are summed by Boolean addition, the resulting expression is a sum-of-products (SOP). Some examples are: AB + ABC ABC + CDE + BCD AB + ABC + AC 51  The sum-of-products (SOP) The sum-of-products (SOP) An SOP expression can contain a single-variable term, as in A + ABC + BCD. In an SOP expression, a single overbar cannot extend more than one variable; however, more than one variable in a term can have an overbar. For example, an SOP expression can have the term A B C but not ABC 52  The sum-of-products (SOP) Domain of a Boolean Expression The domain of a general Boolean Expression is the set of variables contained in the expression in either complemented or uncomplemented form. For example, the domain of the expression AB + ABC is the set of variables A, B, C and the domain of the expression ABC + CDE + BCD is the set of variables A, B, C, D, E. 53 Karnaugh map (K-map) Karnaugh map is similar to a truth table because it presents all of the possible values of input variables and the resulting output for each value. The size of the Karnaugh map with n boolean variables is determined by 2n. For three variable, the number of cells is 23 = 8 54 Karnaugh map (K-map) The procedure for simplifying an SOP expression using a K-map: Place a 1 in each cell that corresponds to a minterm that evaluates to 1 in the expression. Combine cells with 1s in them and that share edges into the largest possible groups. The number of cells in a group must be a power of 2. The edges of the K-map are considered to wrap around to the other side, both vertically and horizontally. Groups may overlap. The result is the sum of the product terms that represent each group. 55 Karnaugh map (K-map) 2 variable k-map 3 variable k-map 4 variable k-map 56 Mapping a Standard SOP Expression ABC + ABC + ABC + ABC AB C 0 1 000 001 110 100 00 1 1 01 11 1 1 10 57 58 Mapping a Nonstandard SOP Expression A Boolean expression must first be in standard form before using Karnaugh map. If an expression is not in standard form, then it must be converted by numerical expression. 59  E.g. SOP expression is A B. Step 1: Write the binary value of the two variables and attach a 0 for the missing variable C: 100 Step 2: Write the binary value of the two variables and attach a 1 for the missing variable C: 101 The two resulting binary are the values of the standard SOP term A B C and A B C 60