Unit 4-Part 1 : Boolean Algebra
Unit 4-Part 1 : Boolean AlgebraTable of Contents3.1Introduction .33.1.1 Advantages of Boolean Algebra.33.2Boolean Algebra Terminology .33.3Logic Operators.43.4Axioms or Postulates .43.5Boolean Algebra’s Laws and Theorems .43.5.1Reduction of Boolean Expression . 103.5.1.1 De-Morganized the following functions . 103.5.1.2 Reduce the following functions using Boolean Algebra’s Laws and Theorems . 103.6Different forms of Boolean Algebra . 123.6.1Standard Form . 123.6.1.1 Standard Sum of Product (SOP) . 123.6.1.2 Standard Product of Sum (POS) . 123.6.2Canonical Form . 123.6.2.1 Sum of Product (SOP) . 123.6.2.2 Product of Sum (POS) . 133.6.2MINTERMS & MAXTERMS for 3 Variables . 143.6.3Conversion between Canonical Forms . 143.6.3.1 Convert to MINTERMS . 143.6.3.2 Convert to MAXTERMS . 153.7Karnaugh Map (K-Map) . 173.7.12 Variable K-Map . 173.7.1.1 Mapping of SOP Expression . 173.7.1.2 Mapping of POS Expression . 173.7.1.3 Reduce Sum of Product (SOP) Expression using K-Map . 183.7.1.4 Reduce Product of Sum (POS) Expression using K-Map . 183.7.23 Variable K-Map . 183.7.2.1 Mapping of SOP Expression . 18 EE & EC Department 3130907 – Analog and Digital Electronics1
Unit 4-Part 1 : Boolean Algebra3.7.2.2 Mapping of POS Expression . 183.7.2.3 Reduce Sum of Product (SOP) Expression using K-Map . 193.7.2.4 Reduce Product of Sum (POS) Expression using K-Map . 193.7.34 Variable K-Map . 203.7.3.1 Mapping of SOP Expression . 203.7.3.2 Mapping of POS Expression . 203.7.3.3 Looping of POS Expression . 213.7.3.4 Reduce Sum of Product (SOP) Expression using K-Map . 233.7.3.5 Reduce Product of Sum (POS) Expression using K-Map . 243.7.3.6 Reduce SOP & POS Expression with Don’t Care Combination using K-Map . 243.7.45 Variable K-Map . 253.7.4.1 Mapping of SOP Expression . 253.7.4.2 Reduce Sum of Product (SOP) Expression using K-Map . 253.7.4.3 Reduce Product of Sum (POS) Expression using K-Map . 263.8Converting Boolean Expression to Logic Circuit and Vice-Versa. 263.9NAND and NOR Realization/Implementation . 283.10Tabulation / Quine-McCluskey Method . 293.11GTU Questions . 33 EE & EC Department 3130907 – Analog and Digital Electronics2
Unit 4-Part 1 : Boolean Algebra3.1Introduction Inventor of Boolean algebra was George Boole (1815 - 1864). Designing of any digital system there are three main objectives;1) Build a system which operates within given specifications2) Build a reliable system3) Minimize resources Boolean algebra is a system of mathematical logic.Any complex logic can be expressed by Boolean function.Boolean algebra is governed by certain rules and laws.Boolean algebra is different from ordinary algebra & binary number system.In ordinary algebra; A A 2A and AA A2, here A is numeric value.In Boolean algebra;A A A and AA A, here A has logical significance, but no numeric significance. Table: Difference between Binary, Ordinary and Boolean systemBinary number system1 1 10 Ordinary no. system1 1 2A A 2A and AA A2Boolean algebra1 1 1A A A and AA AIn Boolean algebra, nothing like subtracting or division, no negative or fractional numbers.Boolean algebra represent logical operation only. Logical multiplication is same as ANDoperation and logical addition is same as OR operation.Boolean algebra has only two values 0 & 1.In Boolean algebra; If A 0 then A 1. & If A 1 then A 0. 3.1.1 Advantages of Boolean Algebra1.2.3.4.5.6.7.3.2Minimize the no. of gates used in circuit.Decrease the cost of circuit.Minimize the resources.Less fabrication area is required to design a circuit.Minimize the designer’s time.Reducing to a simple form. Simpler the expression more simple will be hardware.Reduce the complexity.Boolean Algebra Terminology1. Variable EE & EC Department: The symbol which represent an arbitrary elements of a Booleanalgebra is known as variable.e.g. F A BC, here A, B and C are variable and it can have value either1 or 0. 3130907 – Analog and Digital Electronics3
Unit 4-Part 1 : Boolean Algebra2. Constant3. Complement4. Literal5. Boolean Function3.3: In expression F A 1, the first term A is variable and second term 1is known as constant. Constant may be 1 or 0.: A complement of any variable is represented by a “ ” (BAR) over anyvariable.e.g. Complement of A is 𝐴.: Each occurrence of a variable in Boolean function either in a noncomplemented or complemented form is called literal.: Boolean expressions are constructed by connecting the Booleanconstants and variable with the Boolean operations. This Booleanexpressions are also known as Boolean Formula.e.g. F(A, B, C) (𝐴 𝐵) C OR F (𝐴 𝐵) CLogic Operators1. AND: Denoted by (e.g. A AND B A B)2. OR: Denoted by (e.g. A OR B A B)3. NOT OR Complement : Denoted by “ ” (BAR) or ( )′ (e.g. 𝐴 or (𝐴)′ )3.4Axioms or PostulatesAxioms 1Axioms 2Axioms 3Axioms 43.5::::0·0 00·1 01·0 01·1 1Axioms 5Axioms 6Axioms 7Axioms 8: 0 0 0: 0 1 1: 1 0 1: 1·1 1Axioms 9 :Axioms 10 :1’ 00’ 1Boolean Algebra’s Laws and Theorems1. Complementation Laws: The term complement simply means to invert, i.e. to change 0’s to 1’s and 1’s to 0’s.Law 1: 0’ 1Law 4: If A 1 then A’ 0Law 2: 1’ 0Law 5: A’’ ALaw 3: If A 0 then A’ 12. AND Laws:Law 1: A · 0 0Law 2: A · 1 ALaw 3: A · A ALaw 4: A · A’ 03. OR Laws:Law 1: A 0 ALaw 2: A 1 1Law 3: A A ALaw 4: A A’ 1 EE & EC Department 3130907 – Analog and Digital Electronics4
Unit 4-Part 1 : Boolean Algebra4. Commutative Laws: Commutative laws allow change in position of AND or OR variables.Law 1: A B B AProof: This law can be extended to any numbers of variables for e.g.A B C B A C C B A C A BLaw 2: A · B B · AProof: This law can be extended to any numbers of variables for e.g.A·B·C B·A·C C·B·A C·A·B5. Associative Laws: The associative laws allow grouping of variables.Law 1: (A B) C A (B C)Proof: This law can be extended to any no. of variables for e.g.A (B C D) (A B C) D (A B) (C D) EE & EC Department 3130907 – Analog and Digital Electronics5
Unit 4-Part 1 : Boolean AlgebraLaw 2: (A · B) · C A · (B · C)Proof: This law can be extended to any no. of variables for e.g.A · (B · C · D) (A · B · C) · D (A · B) · (C · D)6. Distributive Laws: The distributive laws allow factoring or multiplying out of expressions.Law 1: A (B C) AB ACProof:Law 2: A BC (A B) (A C)Proof: R.H.S. (A B) (A C) AA AC BA BC A AC BA BC A BC ( A(1 C B) A) L.H.S.Law 3: A A’B A BProof: L.H.S. A A’B (A A’) (A B) A B R.H.S.7. Idempotence Laws: Idempotence means the same value.Law 1: A · A AProof:Case 1: If A 0 A · A 0 · 0 0 ACase 2: If A 1 A · A 1 · 1 1 A EE & EC DepartmentLaw 2: A A AProof:Case 1: If A 0 A A 0 0 0 ACase 2: If A 1 A A 1 1 1 A 3130907 – Analog and Digital Electronics6
Unit 4-Part 1 : Boolean Algebra8. Complementation Law / Negation Law:Law 1: A · A’ 0Proof:Case 1: If A 0 A · A’ 0 · 1 0Case 2: If A 1 A · A’ 1 · 0 0Law 2: A A’ 1Proof:Case 1: If A 0 A A’ 0 1 1Case 2: If A 1 A A’ 1 0 19. Double Negation / Involution Law: This law states that double negation of a variables is equal to the variable itself.Law: A’’ AProof:Case 1: If A 0 A’’ 0’’ 0 ACase 2: If A 1 A’’ 1’’ 1 A Any odd no. of inversion is equivalent to single inversion.Any even no. of inversion is equivalent to no inversion at all.10. Identity Law:Law 1: A · 1 AProof:Case 1: If A 1 A · 1 1 · 1 1 ACase 2: If A 0 A · 0 0 · 0 0 ALaw 2: A 1 1Proof:Case 1: If A 1 A 1 1 1 1 ACase 2: If A 0 A 0 0 0 0 A11. Null Law:Law 1: A · 0 0Proof:Case 1: If A 1 A · 0 1 · 0 0 0Case 2: If A 0 A · 0 0 · 0 0 0Law 2: A 0 AProof:Case 1: If A 1 A 0 1 0 1 ACase 2: If A 0 A 0 0 0 0 A12. Absorption Law:Law 1: A AB AProof: L.H.S. A AB A (1 B) A (1) A R.H.S. EE & EC DepartmentLaw 2: A (A B) AProof: L.H.S. A (A B) A · A AB A AB A (1 B) A R.H.S. 3130907 – Analog and Digital Electronics7
Unit 4-Part 1 : Boolean Algebra13. Consensus Theorem:Theorem 1:A · B A’C BC AB A’C (0 AC A’B BC) (B C) ACB ACC A’BB A’BC BCB BCC ABC AC A’B A’BC BC BC ABC AC A’B A’BC BC AC (1 B) A’B (1 C) BC AC A’B BC AC A’B . (1)Proof: L.H.S. AB A’C BC AB A’C BC (A A’) AB A’C BCA BCA’ AB (1 C) A’C (1 B) AB A’C R.H.S. R.H.S. (A B) (A’ C) AA’ AC BA’ BC 0 AC BA’ BC AC A’B BC AC A’B (2)Eq. (1) Eq. (2); So, L.H.S R.H.S.This theorem can be extended as,AB A’C BCD AB A’CTheorem 2:(A B) (A’ C) (B C) (A B) (A’ C)Proof:L.H.S. (A B) (A’ C) (B C) (AA’ AC A’B BC) (B C)14. Transposition theorem:Theorem: AB A’C (A C) (A’ B)Proof: R.H.S. (A C) (A’ B) AA’ AB CA’ CB 0 AB CA’ CB AB CA’ CB AB A’C L.H.S.15. De Morgan’s Theorem:Law 1: (A B)’ A’ · B’Proof: EE & EC DepartmentOR This theorem can be extended to any no. ofvariables.(A B) (A’ C) (B C D) (A B) (A’ C)( AB A’C BC AB A’C)(A B C)’ A’ · B’ · C’ 3130907 – Analog and Digital Electronics8
Unit 4-Part 1 : Boolean AlgebraLaw 2: (A· B)’ A’ B’Proof:OR(A · B · C)’ A’ B’ C’LHSABAB(AB)’A (AB)’BNAND GateRHSA’AAA’ B’ B’BA0010B0101AB0001(AB)’1110A’ B’BBubbled OR A0010B0101A’1100B’1010A’ B’111016. Duality Theorem: Duality theorem arises as a result of presence of two logic system i.e. positive & negativelogic system. This theorem helps to convert from one logic system to another. From changing one logic system to another following steps are taken:1) 0 becomes 1, 1 becomes 0.2) AND becomes OR, OR becomes AND.3) ‘ ’ becomes ‘·’, ‘·’ becomes ‘ ’.4) Variables are not complemented in the process. EE & EC Department 3130907 – Analog and Digital Electronics9
Unit 4-Part 1 : Boolean Algebra3.5.1Reduction of Boolean Expression3.5.1.1 De-Morganized the following functions(1)F [(A B’) (C D’)]’(3)FFFF [(A B’) (C D’)]’(A B’)’ (C D’)’A’ B’’ C’D’’A’B C’DF [(AB)’ A’ AB]’FFFFF [(AB)’ A’ AB]’(AB)’’ · A’’ · (AB)’ABA (A’ B’)AB (A’ B’)ABA’ ABB’F [P (Q R)]’Sol: (5)F [(AB)’ (CD E’F) ((AB)’ (CD)’)]’ FFFF [(AB)’ (CD E’F) ((AB)’ (CD)’)]’(AB)’’ (CD E’F)’ ((AB)’ (CD)’)’AB [(CD)’ (E’F)’] [(AB)’’ (CD)’’]AB (C’ D’) (E F’) ABCD(4)F [(P Q’) (R’ S)]’ FFFF [(P Q’) (R’ S)]’(P Q’)’ (R’ S)’P’Q’’ R’’S’P’Q RS’(6)F [[(A B)’ (C D)’]’ [(E F)’ (G H)’]’]’FFFF [[(A B)’ (C D)’]’ [(E F)’ (G H)’]’]’[(A B)’ (C D)’]’’ [(E F)’ (G H)’]’’[(A B)’ (C D)’] [(E F)’ (G H)’]A’B’C’D’ E’F’G’H’Sol:Sol: (2)Sol:Sol:Sol:FFF [P (Q R)]’P’ (Q R)’P’ Q’ R’ 3.5.1.2 Reduce the following functions using Boolean Algebra’s Laws and Theorems(1)F A B [ AC (B C’)D ]F A [ B C’ (AB AC’)’ ]FFFFFFFFF A [ B C’ (AB AC’)’ ]A [ B C’ (AB)’ (AC’)’ ]A [ B C’ (A’ B’) (A’ C) ]A [ B (A’ C’ B’ C’) (A’ C) ]A [ B (A’ C’A’ B’ C’A’) (A’ C’ C B’ C’ C) ]A [ B (A’C’ B’ C’A’) (0 0) ]A [ B A’C’ ( 1 B’) ]AB A’AC’ABSol:Sol: (2)FFFFFFF A B [ AC (B C’)D ]A B [ AC (BD C’D) ]A ABC BBD BC’DA ABC BD BC’DA (1 BC) BD (1 C’)A (1) BD (1)A BD EE & EC Department 3130907 – Analog and Digital Electronics10
Unit 4-Part 1 : Boolean Algebra(3)Sol:F (A (BC)’)’ (AB’ ABC)FFFFFF (A (BC)’)’ (AB’ ABC)(A’ (BC)’’) (AB’ ABC)(A’BC) (AB’ ABC)A’BCAB’ A’BCABC0 00F [(A B’) (A’ B’)] [(A’ B’) (A’ B’)] FF FFFF [(A B’) (A’ B’)] [(A’ B’) (A’ B’)][AA’ AB’ B’A’ B’B’] [A’A’ A’B’ B’A’ B’B’][0 AB’ A’B’ B’] [A’ A’B’ B’][B’ (A A’ 1)] [A’ B’(1)]B’ A’ B’A’ B’(7)Sol:F (B BC) (B B’C) (B D)(8)FFFFFF (B BC) (B B’C) (B D)(BB BB’C BBC BCB’C) (B D)(B 0 BC 0) (B D)B (B D)( B BC B(1 C) B)B BD( B (B D) BB BD)B( B BD B (1 D))Sol:F AB AB’C BC’FFFFFF AB AB’C BC’A (B B’C) BC’A (B B’) (B C) BC’AB AC BC’{ B B’ 1}CA C’B ABCA C’B { 𝑐𝑜𝑛𝑠𝑒𝑛𝑠𝑢𝑠 𝑡ℎ𝑒𝑜𝑟𝑒𝑚 } (5)Sol: (9)Sol: EE & EC Department(4)Sol:F [(A B) (A’ B)] [(A B) (A B’)]FFFFFF [(A B) (A’ B)] [(A B) (A B’)][AA’ AB BA’ BB] [AA AB’ BA BB”][0 AB A’B B] [A AB’ AB 0][B (A A’ 1)] [A (1 B’ B)]B AA BF (A B) (A B’) (A’ B) (A’ B’) FF FFFF (A B) (A B’) (A’ B) (A’ B’)(AA AB’ BA BB’) (A’A’ A’B’ BA’ BB’)[A (1 B’ B)] [A’ (1 B’ B)][A(1)] [A’(1)]AA’0 (6)Sol:F AB’C B BD’ ABD’ A’CReduce the function to minimum no. of literals.F AB’C B BD’ ABD’ A’C F AB’C B (1 D’ AD’) A’C F AB’C B A’C F C (A’ AB’) B F C (A’ A) (A’ B’) B F C (1) (A’ B’) B F C (A’ B’) B F A’C CB’ B F A’C (C B) (B’ B) F A’C (B C) (1) F A’C B C F C (1 A’) B F B CHere, 2 literals are present B & C. 3130907 – Analog and Digital Electronics11
Unit 4-Part 1 : Boolean Algebra3.6Different forms of Boolean Algebra 3.6.1 There are two types of Boolean form1) Standard form2) Canonical formStandard FormDefinition: The terms that form the function may contain one, two, or any number of literals.i.e. each term need not to contain all literals. So standard form is simplified form of canonicalform.A Boolean expression function may be expressed in a nonstandard form. For example thefunction:F (A C) (AB’ D’)Above function is neither sum of product nor in product of sums. It can be changed to astandard form by using distributive law as below;F AB’ AD’ AB’C CD’There are two types of standard forms: (i) Sum of Product (SOP) (ii) Product of Sum (POS).3.6.1.1 Standard Sum of Product (SOP) 3.6.2SOP is a Boolean expression containingAND terms, called product terms, of oneor more literals each. The sum denote theORing of these terms.An example of a function expressed insum of product is:F Y’ XY X’YZ’3.6.1.2 Standard Product of Sum (POS) The OPS is a Boolean expression containingOR terms, called sum terms. Each termsmay have any no. of literals. The productdenotes ANDing of these terms.An example of a function expressed inproduct of sum is:F X (Y’ Z) (X’ Y Z’ W)Canonical Form Definition: The terms that form the function contain all literals. i.e. each term need to containall literals. There are two types of canonical forms: (i) Sum of Product (SOP) (ii) Product of Sum (POS).3.6.2.1 Sum of Product (SOP) A canonical SOP form is one in which a no. of product terms, each one of which contains all thevariables of the function either in complemented or non-complemented form, summedtogether. Each of the product term is called “MINTERM” and denoted as lower case ‘m’ or ‘Ʃ’. For minterms, Each non-complemented variable 1 & Each complemented variable 0 For example,1. XYZ 111 m73. P’Q’R’ 000 m02. A’BC 011 m34. T’S’ 00 m0 EE & EC Department 3130907 – Analog and Digital Electronics12
Unit 4-Part 1 : Boolean Algebra3.6.2.1.1 Convert to MINTERM(1)F P’Q’ PQ(2)F X’Y’Z XY’Z’ XYZFFF 001 100 111m1 m4 m7Σm(1,4,7)Sol:Sol: (3)FFF 00 11m0 m3Σm(0,3)F XY’ZW XYZ’W’ X’Y’Z’W’FFF 1011 1100 0000m11 m12 m0Σm(0,11,12) Sol: 3.6.2.2 Product of Sum (POS) A canonical POS form is one in which a no. of sum terms, each one of which contains all thevariables of the function either in complemented or non-complemented form, are multipliedtogether.Each of the product term is called “MAXTERM” and denoted as upper case ‘M’ or ‘Π’.For maxterms, Each non-complemented variable 0 & Each complemented variable 1For example,1. X’ Y’ Z 110 M62. A’ B C’ D 1010 M10 3.6.2.2.1 Convert to MAXTERM(1)F (P’ Q)(P Q’)(3)F (A’ B C)(A B’ C)(A B C’)FFF (100) (010) (001)M 4 M2 M1ΠM(1,2,4)Sol:Sol: (2)FFF (10)(01)M2·M1ΠM(1,2)F (X’ Y’ Z’ W)(X’ Y Z W’)(X Y’ Z W’)FFF (1110)(1001)(0101)M14·M9·M5ΠM(5,9,14) Sol: EE & EC Department 3130907 – Analog and Digital Electronics13
Unit 4-Part 1 : Boolean Algebra3.6.2MINTERMS & MAXTERMS for 3 VariablesTable: Representation of Minterms and Maxterms for 3 variables3.6.3Conversion between Canonical Forms3.6.3.1 Convert to MINTERMS1.F(A,B,C,D) ΠM(0,3,7,10,14,15)Solution:Take complement of the given function; F’(A,B,C,D) ΠM(1,2,4,5,6,8,9,11,12,13) F’(A,B,C,D) (M1 M2 M4 M5 M6 M8 M9 M11 M12 M13)’Put value of MAXTERM in form of variables; F’(A,B,C,D) [(A B C D’)(A B C’ D)(A B’ C D)(A B’ C D’)(A B’ C’ D)(A’ B C D)(A’ B C D’)(A’ B C’ D’)(A’ B’ C D)(A’ B’ C D’)]’ F’(A,B,C,D) (A’B’C’D) (A’B’CD’) (A’BC’D’) (A’BC’D) (A’BCD’) (AB’C’D’) (AB’C’D) (AB’CD) (ABC’D’) (ABC’D) F’(A,B,C,D) m1 m2 m4 m5 m6 m8 m9 m11 m12 m13 F’(A,B,C,D) Σm(1,2,4,5,6,8,9,11,12,13)In general, Mj’ mj EE & EC Department 3130907 – Analog and Digital Electronics14
Unit 4-Part 1 : Boolean Algebra2.F A B’CSolution:A B & C is missing. So multiply with (B B’) & (C C’)B’C A is missing. So multiply with (A A’). A A (B B’) (C C’) A (AB AB’) (C C’) A ABC AB’C ABC’ AB’C’And, So, B’CB’C B’C (A A’)AB’C A’B’CFFFFF ABC AB’C ABC’ AB’C’ AB’C A’B’CABC AB’C ABC’ AB’C’ A’B’C111 101 110 100 001m7 m6 m5 m4 m1Σm(1,4,5,6,7)3.6.3.2 Convert to MAXTERMS1.F Σ(1,4,5,6,7)Solution:Take complement of the given function; F’(A,B,C) Σ(0,2,3) F’(A,B,C) (m0 m2 m3)Put value of MINTERM in form of variables; F’(A,B,C) (A’B’C’ A’BC’ A’BC)’ F’(A,B,C) (A B C)(A B’ C)(A B’ C’) F’(A,B,C) M0·M2·M3 F’(A,B,C) ΠM(0,2,3)In general, mj’ Mj2.F A (B C’)Solution:A B & C is missing. So add BB’ & CC’B C’ A is missing. So add AA’ A A BB’ CC’ EE & EC Department 3130907 – Analog and Digital Electronics15
Unit 4-Part 1 : Boolean Algebra AA (A B CC’) (A B’ CC’)(A B C) (A B C’) (A B’ C) (A B’ C’) B C’B C’ B C’ AA’(A B C’) (A’ B C’)FFFF (A B C) (A B C’) (A B’ C) (A B’ C’) (A B C’) (A’ B C’)(A B C) (A B C’) (A B’ C) (A B’ C’) (A’ B C’)(000) (001) (010) (011) (101)ΠM(0,1,2,3,5)3.Solution:F XY X’Z FFFF XY X’Z(XY X’) (XY Z)(X X’) (Y X’) (X Z) (Y Z)(X’ Y) (X Z) (Y Z)And,So, X’ Y Z is missing. So add ZZ’X Z Y is missing. So add YY’Y Z X is missing. So add XX’ X’ YX’ Y X’ Y ZZ’(X’ Y Z) (X’ Y Z’) X ZX Z X’ Z YY’(X Y Z) (X Y’ Z) Y ZY Z Y Z XX’(X Y Z) (X’ Y Z)FFFF (X’ Y Z) (X’ Y Z’) (X Y Z) (X Y’ Z) (X Y Z) (X’ Y Z)(100) (101) (000) (010)M4 M5 M0 M 2ΠM(0,2,4,5)And,And,So, EE & EC Department 3130907 – Analog and Digital Electronics16
Unit 4-Part 1 : Boolean Algebra3.7Karnaugh Map (K-Map) A Boolean expression may have many different forms.With the use of K-map, the complexity of reducing expression becomes easy and Booleanexpression obtained is simplified.K-map is a pictorial form of truth table and it is alternative way of simplifying Boolean function.Instead of using Boolean algebra simplification techniques, you can transfer logic values froma Boolean statement or a truth table into a Karnaugh map (k-map)Tool for representing Boolean functions of up to six variables then after it becomes complex.K-maps are tables of rows and columns with entries represent 1’s or 0’s of SOP and POSrepresentations.K-map cells are arranged such that adjacent cells correspond to truth table rows that differ inonly one bit position (logical adjacency)K-Map are often used to simplify logic problems with up to 6 variablesNo. of Cells 2 n, where n is a number of variables. 3.7.1The Karnaugh map is completed by entering a ‘1’ (or ‘0’) in each of the appropriate cells.Within the map, adjacent cells containing 1's (or 0’s) are grouped together in twos, fours, oreights and so on.2 Variable K-Map For 2 variable k-map, there are 22 4 cells. If A & B are two variables then;SOP Minterms A’B’ (m0, 00) ; A’B (m1, 01) ; AB’ (m2, 10) ; AB (m3, 11)POS Maxterms A B (M0, 00) ; A B’ (M1, 01) ; A’ B (M2, 10) ; A’ B’ (M3, 11)3.7.1.1 Mapping of SOP Expression 1 in a cell indicates that the minterm isincluded in Boolean expression.For e.g. if F m(0,2,3), then 1 is put incell no. 0,2,3 as shown below.BA1A 11 EE & EC Department 0 in a cell indicates that the maxterm isincluded in Boolean expression.For e.g. if F ΠM(0,2,3), then 0 is put incell no. 0,2,3 as shown below.BB’0A’ 03.7.1.2 Mapping of POS ExpressionB1A00A’ 003A 10B110112B’01023 3130907 – Analog and Digital Electronics17
Unit 4-Part 1 : Boolean Algebra3.7.1.3 Reduce Sum of Product (SOP) Expression using K-Map(1)F m0 m1Sol:B(2)B’0AA’ 01A 10B1BA’ 01A 1102(5)B’0AA’ 00A 11A’ 00A 100B1001A’ 01A 11012B’0A3F A11123F B(6)BB103 m(0,1,3)Sol:B’01F B’F m2 m3BBA023F Σ(1,3)Sol:B101F A’(4)Sol:(3)B’0A10F A’B’ AB’Sol:B1112BA10 m(0,1,2,3)Sol:3B’0A’ 01A 11B110F A’ AB1123F 13.7.1.4 Reduce Product of Sum (POS) Expression using K-Map(1)F ΠM(0,2,3,1)(2)BSol:Sol:B’1B0A0100A’ 123F 03.7.2B00A’ 1F ABBAA 0A’ 1B’1B0010112F M3·M1·M2Sol:00A 0(3)B’1B0A00A 0F (A B) (A’ B) (A B’)002313F A’ B’3 Variable K-Map For 3 variable k-map, there are 23 8 cells.3.7.2.1 Mapping of SOP Expression EE & EC Department3.7.2.2 Mapping of POS Expression 3130907 – Analog and Digital Electronics18
Unit 4-Part 1 : Boolean Algebra3.7.2.3 Reduce Sum of Product (SOP) Expression using K-Map(1)Sol:F A’B’C ABC A’BC’(2)Sol:F Σ(1,6,7)F A’B’C ABC A’BC’(3)Sol:F A’B’C’ ABC’ AB’C’ A’BCF A’B’C AB(4)Sol:F Σm(0,1,2,4,5,6)F B’C’ AC’ A’BC(5)Sol:F m3 m4 m6 m7F B’ C’(6)Sol:F Σm(3,7,1,6,0,2,5,4)F BC AC’F 13.7.2.4 Reduce Product of Sum (POS) Expression using K-Map(1)Sol:F (A’ B’ C’) (A’ B C’)F (A’ C’) EE & EC Department(2)Sol:F M0·M3·M7F (A B C) (B’ C’) 3130907 – Analog and Digital Electronics19
Unit 4-Part 1 : Boolean Algebra(3)Sol:F ΠM(1,2,5)(4)Sol:F (B C’) (A B C)(5)Sol:F (A B C)(A B’ C’)(A’ B C)F (B) (C’)(6)Sol:F (B C) (A B’ C’)3.7.3F ΠM(0,4,1,5,7,3)ΠM(5,7,0,3,2,4,6,1)F 04 Variable K-Map For 4 variable k-map, there are 24 16 cells.3.7.3.1 Mapping of SOP Expression EE & EC Department3.7.3.2 Mapping of POS Expression 3130907 – Analog and Digital Electronics20
Unit 4-Part 1 : Boolean Algebra3.7.3.3 Looping of POS Expression Looping Groups of Two: Looping Groups of Four: EE & EC Department 3130907 – Analog and Digital Electronics21
Unit 4-Part 1 : Boolean Algebra Looping Groups of Eight: Examples EE & EC Department 3130907 – Analog and Digital Electronics22
Unit 4-Part 1 : Boolean Algebra3.7.3.4 Reduce Sum of Product (SOP) Expression using K-Map(1)Sol:F (0,1,2,4,5,6,8,9,12,13,14)(2)Sol:F C’ A’D’ BD’(3)Sol:F (0,1,2,3,5,7,8,9,12,13)F A’B’ AC’ A’D EE & EC DepartmentF A’B’C’ B’CD’ A’BCD’ AB’C’F B’C’ B’D’ A’CD’(4)Sol:F (0,1,3,4,5,6,7,13,15)F A’C’ A’D BD A’B 3130907 – Analog and Digital Electronics23
Unit 4-Part 1 : Boolean Algebra(5)Sol:F m (5,6,7,9,10,11,13,14,15)F BD BC AD AC3.7.3.5 Reduce Product of Sum (POS) Expression using K-Map(1)Sol:F ΠM (0,1,2,5,7,8,9,10,14,15)(2)Sol:F (B D) (B C) (A B’ D’) (A’ B’ C’)F M1 M3 M4 M7 M6 M9 M11 M12 M14 M15F (B’ D) (C’ B’) (D’ B)3.7.3.6 Reduce SOP & POS Expression with Don’t Care Combination using K-Map(1)Sol:F m (1,5,6,12,13,14) d (2,4)F BC’ BD’ A’C’D EE & EC Department(2)Sol:F ΠM (4,7,10,11,12,15) · d (6,8)F (B’ C D) (B’ C’ D’) (A’ B C’) 3130907 – Analog and Digital Electronics24
Unit 4-Part 1 : Boolean Algebra3.7.45 Variable K-Map For 5 variable k-map, there are 25 32 cells.3.7.4.1 Mapping of SOP Expression3.7.4.2 Reduce Sum of Product (SOP) Expression using K-Map(1) F m (0,2,3,10,11,12,13,16,17,18,19,20,21,26,27)Sol:F C’D B’C’E’ AB’D’ A’BCD’(2) F m (0,2,4,6,9,11,13,15,17,21,25,27,29,31)Sol:F BE AD’E A’B’E’ EE & EC Department 3130907 – Analog and Digital Electronics25
Unit 4-Part 1 : Boolean Algebra3.7.4.3 Reduce Product of Sum (POS) Expression using K-Map(1) F ΠM (1,4,5,6,7,8,9,14,15,22,23,24,25,28,29,30,31)Sol:F (B’ C D) (C’ D’) (A B C’) (A’ B’ D) (A C D E’)3.8(1)Sol: Converting Boolean Expression to Logic Circuit and Vice-VersaFor the logic circuit shown fig., find the (2)Boolean expression and the truth table.Identify the gate that given circuit realizes.Here,Output of OR gate will be (A B)Output of NAND gate will be (AB)’So, C will be AND of these two outputs C (A B) · (A·B)’For the logic circuit shown fig., find theBoolean expression and the truth table.Identify the gate that given circuit realizes.Sol: Truth table for the same can be given below;InputOutputA B A B A·B (A·B)’ (A B)·(A·B)’0 000100 110111 010111 11100 From the truth table it is clear that the circuitrealizes Ex-OR gate. EE & EC DepartmentHere, bubble indicates inversion.Hence input of top OR gate is A’ and B’ andhence its output will be A’ B’Output of bottom OR gate will be A B Y (A’ B’)(A
Boolean algebra is a system of mathematical logic. Any complex logic can be expressed by Boolean function. Boolean algebra is governed by certain rules and laws. Boolean algebra is different from ordinary algebra & binary number system. In ordinary algebra; A A 2A and AA A2, here
Boolean Expressions & Logic Circuits A Boolean expression (logic circuit) gives a unique Boolean function The converse is not true, that is, a Boolean function can be represented by different Boolean expressions (logic circuits) A truth table gives a unique Boolean function, and vice
Basic theorem of Boolean algebra Basic postulates of Boolean algebra are used to define basic theorems of Boolean algebra that provides all the tools necessary for manipulating Boolean expressi
Boolean topological algebras We call a topological algebra of some algebraic type Boolean provided the underlying topological space is Boolean Theorem: Let X be a Boolean space, f : Xn!X any function, and R Xn X its graph. The the following are equivalent: IR is a dual relation with i as the output coordinate for some (and then for all) 1 6i 6n
Logic Gates & Boolean Algebra Boolean Theorems: We have seen how Boolean algebra can be used to help analyze a logic circuit and express its operation mathematically. We will continue our study of Boolean algebra by investigating the various Boolean theorems (rules) that can
3 Boolean rings, their ideals and varieties Boolean ring consists of idempotent elements, which satisfy the equality a2 a. Boolean ring has characteristic 2 due to the equalities a a (a a)2 a2 2a a2 a 2a a, hence 2a 0. This ring is commutative due to the equalities (a b) (a b)2
varieties they form, were termed semi-Boolean-like in the same paper. Although double-pointed discriminator varieties are prime examples of semi-Boolean-like va-rieties, a generic semi-Boolean-like variety need not be c-subtractive or c-regular (c2f0;1g). A better approximation to double-pointed discriminator varieties is
BOOLEAN ANALYSIS OF LOGIC CIRCUITS Boolean algebra provides a concise way to express the operation of a logic circuit formed by a combination of logic gates so that the output can be determined for various combinations of input values. Boolean Expression for a Logic Circuit To derive the B
Std. 12th Economics Smart Notes, Commerce and Arts (MH Board) Author: Target Publications Subject: Economics Keywords: economics notes class 12, 12th commerce, 12th economics book , 12th commerce books, class 12 economics book, maharashtra state board books for 12th, smart notes, 12th std economics book , 12th economics book maharashtra board, 12th economics guide , maharashtra hsc board .
