Math 123 Boolean Algebra Chapter - 11 Boolean Algebra
253Math 123Boolean AlgebraChapter - 11Boolean Algebra11.1 Introduction:George Boole, a nineteenth-century English Mathematician,developed a system of logical algebra by which reasoning can beexpressed mathematically. In 1854, Boole published a classic book, “AnInvestigation of the Laws of thought” on which he founded theMathematical theories of Logic and Probabilities,Boole‟s system of logical algebra, now called Boolean algebra,was investigated as a tool for analyzing and designing relay switchingcircuits by Claude E. Shannon at the Massachusetts institute ofTechnology in 1938. Shannon, a research assistant in the ElectricalEngineering Department, wrote a thesis entitled “A” symbolic Analysis ofRelay and Switching Circuits. As a result of his work, Boolean algebra isnow, used extensively in the analysis and design of logical circuits. TodayBoolean algebra is the backbone of computer circuit analysis.11.2 Two Valued Logical Symbol:Aristotle made use of a two valued logical system in devising amethod for getting to the truth, given a set of true assumptions. Thesymbols that are used to represent the two levels of a two valued logicalsystem are 1 and 0. The symbol 1 may represent a closed switch, a truestatement, an “on” lamp, a correct action, a high voltage, or many otherthings. The symbol “O” may represent on open switch, a false statement,an “off” lamp, an incorrect action, a low voltage, or many other things.For the electronics circuits and signals a logic 1 will representclosed switch, a high voltage, or an “on” lamp, and a logic 0 will representan open switch, low voltage, or an “off” lamp. These describe the only twostates that exist in digital logic systems and will be used to represent the inand out conditions of logic gates.11.3 Fundamental Concepts of Boolean Algebra:Boolean algebra is a logical algebra in which symbols are used torepresent logic levels. Any symbol can be used, however, letters of thealphabet are generally used. Since the logic levels are generally associatedwith the symbols 1 and 0, whatever letters are used as variables that cantake the values of 1 or 0.
254Math 123Boolean AlgebraBoolean algebra has only two mathematical operations, additionand multiplication. These operations are associated with the OR gate andthe AND gate, respectively.11.4 Logical Addition:When the (the logical addition) symbol is placed between twovariables, say X and Y, since both X and Y can take only the role 0 and 1,we can define the Symbol by listing, all possible combinations for X andY and the resulting value of X Y.The possible input and out put combinations may arranged asfollows:0 0 00 1 11 0 11 1 1This table represents a standard binary addition, except for thelast entry. When both' X and Y represents 1‟s, the value of X Y is 1. Thesymbol therefore does not has the “Normal” meaning, but is a Logicaladdition symbol. The plus symbol ( ) read as "OR", therefore X Y isread as X or Y.This concept may be extended to any number of variables forexample A B C D E Even if A, B, C and D all had the values 1, thesum of the values i.e. is 1.11.5 Logical Multiplication:We can define the "." (logical multiplication) symbol or ANDoperator by listing all possible combinations for (input) variables X and Yand the resulting (output) value of X. Y as,0 .0 00 .1 01 .0 01 .1 1Note :Three of the basic laws of Boolean algebra are the same as inordinary algebra; the commutative law, the associative law and thedistributive law.
255Math 123Boolean AlgebraThe commutative law for addition and multiplication of twovariables is written as,A B B AAndA.B B.AThe associative law for addition and multiplication of threevariables is written as,(A B) C A (B C)And(A .B) . C A. (B. C)The distributive law for three variables involves, both addition andmultiplication and is written as,A (B C) A B ACNote that while either ' ' and „.‟ s can be used freely. The two cannotbe mixed without ambiguity in the absence of further rules.For example does A . B C means (A . B) C or A . (B C)? Thesetwo form different values for A O, B 1 and C 1, because we have(A . B) C (0.1) 1 1andA . (B C) 0 . (1 1) 0which are different. The rule which is used is that „.‟ is always performedbefore ' '. Thus X . Y Z is (X.Y) Z.11.6 Logic Gates:A logic gate is defined as a electronics circuit with two or moreinput signals and one output signal. The most basic logic Circuits are ORgates, AND gates, and invertors or NOT gates. Strictly speaking, invertorsare not logic gates since they have only one input signal; however Theyare best introduced at the same time as basic gates and will therefore bedealt in this section.
256Math 123Boolean AlgebraOR Gate:An OR gate is a logic circuit with two or more input signals andone output signal. The output signal will be high (logic 1) if any one inputsignal is high (logic 1). OR gate performs logical additionThe symbol for the logic OR gate isXX Y ZORYFig. 1A circuit that will functions as an OR gate can be implemented inseveral ways. A mechanical OR gate can be fabricated by connecting twoswitches in parallel as shown in figure 2.XYFig. 2V 5vZTruth Table for a switch circuit operation as an OR gate.Table – 1Switch XSwitch YOutput te that for the switch circuit were use diodes and resistors,Transistors and resistors and other techniques to control the voltage andresistance.
257Math 123Boolean AlgebraNote: If the switch is "on", it is represented by 1, and if, it is "off", itis represented by 0.Truth Table for a Two-input OR gate.Table - 2In PutOut PutXYZ000011101111Truth table for a three in put OR gate.Table – 3A0B0C0X00011010101111001101111011111No. of combinations 2 n, where n is number of variables.AND Gate:An AND gate is a logic circuit with two or more input signalsand one output signal. The output signal of an AND gate is high (logic 1)only if all inputs signals are high (Logic 1).
258Math 123Boolean AlgebraAn AND gate performs logical multiplication on inputs. Thesymbol for AND gate isXX.Y ZYFig.3A circuit that will functions as an AND gate can be implemented inseveral ways. A mechanical AND gate can be fabricated by connectingtwo switches in series as show in fig. 4XFig.4Truth Table for a switch circuit operation as an AND gate.Table – 4Switch XSwitch YOutput ZOpenOpen0OpenClosed0ClosedOpen0ClosedClosed5V
259Math 123Boolean AlgebraTruth Table for a Two-input AND gateTable - 5In PutOut PutXYZ000010100111Truth Table for a three input AND gate.Table omplementation:The logical operation of complementary or inverting a variable isperformed in the Boolean Algebra. The purpose of complementation is to
260Math 123Boolean Algebrainvert the, input signal, since there are only two values that variables canassume in two-value logic system, therefore if the input is 1, the output is0 and if the input is 0 the output is 1. The symbol used to representcomplementation of a variable is a bar (-) above the variable, for examplethe complementation of A is written as A and is read as “complement ofA” or “A not”.Since variables can only be equal to 0 or 1, we can say thatO 1Or 1 O O OAlsoOr 1Invertors Or NOT gate:An inventor is a gate with only one.inputsignal and one output signal; the output signal is always theopposite or complement of the input signal.An invertor is also called a NOT gate because the output not thesame as the input.Symbol of inverter or NOT gate isNXXFig.5 (i)NXX XXFig.5 (ii)Fig.5(ii) (Two invertors in series)Fig. 5The circle at the output or input indicates inversion. It alsodistinguish between the symbol for the NOT gate or the symbol for an
261Math 123Boolean Algebraoperational amplifier or certain types of buffers, because the symbol - can also be used for diode.Truth Table for a NOT circuitTable – 7In put01Out put10NOTE :A word is a group (or string) of binary bits that represents aclosed instruction or data,Example 1:How many input words in the Truth Table of an 6 input OR gate? Which, input word produce a highoutput?Solution:The total number of input word‟s 2n 26 32, where n isnumber of inputs. In an OR gate 1 or more-high inputs produce a highoutput. Therefore the word of 000000 results in low outputs all other inputwords produce a high output.11.7 Basic Duality in Boolean Algebra:We state the duality theorem without proof. Starting with aBoolean relation, we can derive another Boolean relation by1. Changing each OR ( ) sign to an AND (.) sign2. Changing each AND (.) sign to an OR ( ) sign.3. Complementary each 0 and 1For instanceA 0 AThe dual relation is A . 1 AAlso since A (B C) AB AC by distributive law. Its dualrelation is11.8A B C (A B) (A C)Fundamental Laws and Theorems of Boolean Algebra:1.X 0 X2.X 1 13.X X XX X 14.OR operations
262Math 123Boolean Algebra5.X . 0 06.X . 1 X7.X.X X8.X. X 09. X XDouble complement10.X Y Y XCommutative laws11.XY YX12.(X Y ) Z X (Y Z)13.(X . Y). Z X. (Y. Z)14.X (Y Z) XY XZ15.X Y .Z (X Y) . (X Z) Dual of Distributive Law16.X XZ X17.X (X Z) X18.X X Y X Y19.X ( X Y) X.Y20.21.X Y X . YX.Y X YAND operationsAssociative lawsDistribution LawLaws of absorptionIdentity TheoremsDe Morgan's TheoremsProof of Boolean Algebra Rules:Every rule can be proved by the application of rules and by perfectInduction.Rule 15:(i)This rule does not apply to normal algebra We follow:(X Y) (X Z) XX XZ YX YZ X XZ YX YZ,X.X X
263Math 123Boolean Algebra X (1 Z) YX YZ X YX YZ,1 Z 1– X (1 Y) Y Z X YZProof by Perfect induction Method:(ii)Truth Table-81 Y 1for the R.H.S. (X Y) (X Z)and for L.H.S. X YZXYZX YX ZYZ(X Y)(X Z)X 1101111111111111R.H.S. L.H.S.Rule .16Rule 17:X XZ XL.H.S. X XZ X(1 Z) X. 1 X,I Z 1 R.H.S.X(X Z) XL.H.S. X (X Z) X X XZBy distributive law X XZ,as X.X X X (1 Z),As 1 Z 1 X.1 XL.H.S. R.H.S.
264Math 123Boolean AlgebraRule 18:(i)X X YL.H.S. X X Y (X X ) . (X Y) X YBy rule 15 dualOf distributive law.as X X 1 1 . (X Y) X YL.H.S. R.H.S.(ii)Proof by perfect Induction Method:Truth Table 9for L.H.S. X X Y and for R.H.S. X YXYX YXXYX X Y001000011111100011110011L.H.S. R.H.S.Rule 19:(i)X.( X Y) X . YL.H.S. X ( X Y) X X X YBy distributive law 0 XYas X . X 0 X YL.H.S. R.H.S.(ii)Proof by Perfect Induction Method:for L.H.S. X. ( X Y) and for R.H.S. X.Y.Truth Table 10XYXX YX ( X Y)X.Y001100011100100000110111L.H.S. R.H.S.
265Math 123Boolean Algebra11.9 De Morgan’s Theorems:(i)Proof: (i)X Y X .YX.Y X Y(ii)By Perfect induction(i)Truth Table 11X0011Y0101for L.H.S. X Y and for R.H.S. X . YX1100Y1010X Y0111X Y1000X .Y1000L.H.S. R.H.S.(ii)Truth Table 12X0011Y0101X1100for L.H.S. X . Y and for R.H.S. X YX .YYX.YX Y1011001110110100L.H.S. R.H.S.Rules:3rd and 7th called idempotent. These shows that Boolean algebra isidempotent.i.e.A A AandA. A AProof:The variable A can have only the value 0 or 1.(3)(7)IfA 0,then0 0 0IfA 1,then1 1 1IfA 0,then0.0. 0IfA 1,then1 . 1 1Rule 2:X 1 1IfX 0 then0 1 1IfX 1, then1 1 1
266Math 123Boolean AlgebraRule 5:X.0 0IfX 0,Then0.0 1IfX 1,Then1 .0 1 X X,i.e., the Boolean algebra is involuted.X 0,ThenRule 9:IfSoIfO 1 and O 1 0Then 1 0 andX 1,So1 0O 1 1 O 1Similarly we can prove the remaining rules by setting the values ofvariables as 0 and 1 or by perfect inductionExample:2:Express the Boolean functionXY YZ Y Z XY ZSolution:L.H.S. XY YZ Y Z XY Z(Y Y ) XY Z.1 XY ZL.H.S Example 3:R.H.S.Find the complement of the expression: X YZ andverified the result by perfect induction.Solution:X YZ X . YZ X .( Y Z ) by DeMorgan‟s LawThis relation can be verified by perfect induction.
267Math 123Boolean Algebrafor L.H.S. X YZ and for R.H.S. X . ( Y Z )Truth Table 13XYZXYZYZX YZY ZX YZX (Y Z 101100101010011001100010110011100011000L.H.S. R.H.S.Example 4:Solution:(a)(b)Find the complement of A B C D , (b) AB CD 0A B C D (A B ) . ( C D ) (A B ) . ( C D )(A B ) . ( C D)AB CD 0Taking complement on both sides. AB CD O AB . CD 1(A B ) .(C D ) 1Example 5:Simplify the Boolean expressions:(i)(X Y) ( X Y ) ( X Z)(ii)XYZ X Y Z XY Z
268Math 123Boolean AlgebraSolution:First simplify (X Y ) ( X Y )(X Y) (X Y ) XX X Y YX Y Y X X Y YX O, as XX Xas Y Y 0 X X( Y Y),as Y Y 1 X X . 1,as X .1 X X X XNow(X Y) (X Y ) ( X Z) X( X Z) X X XZ, by distributive law(i)(ii) 0 XZ XZXYZ X Y Z XY Z XZ (Y Y ) XY Z XZ XY Z ,asY Y 1 X (Z Y Z ) X[(Z Y). (Z Z )], (By Rule 15 dual of distributive X [(Z Y). 1] X (Z Y) X (Y Z),by commutative law.
269Math 123Example 6:(a)(b)(c)(d)Solution:Boolean AlgebraMinimize the following expression by use of Booleanrules.X ABC A B AB CX A B C A B C A B C A B CAB A C B C AB A C(A B) ( A C) (B C) (A B) ( A C)(a)X(b)X ABC A B AB C ABC AB C A B AB (C C ) A B AB A BasC C 1 (A A ) B. 1. B B A BC A B C A B C A B C A B C A B C A B C as A A A A B C (A A ) B C A BC 1 . B C (A B B ) C [( A B ) . ( B B )] C by the dual ofdistribution, rules 15 ( A B ) . 1] C (A B ) C
270Math 123(c)Boolean AlgebraL.H.S. AB A C BC AB A C BC AB A C 1.BCas1 A A AB A C (A A ) BC AB A C ABC A BC , by distributive law AB ABC A C A BC, by commutative law AB (1 C) A C (1 B),AS 1 X 1 AB A CL.H.S. R.H.S.(d)L.H.S. (A B) ( A C)( B C) (A A AC B A BC) ( B C) (0 AC B A BC) ( B C) (AC B A BC ) (B C) [AC B( A C)] (B C) ABC ACC BB ( A C) BC ( A C) ABC AC B ( A C) BC ( A C) AC (B 1) B ( A C) (1 C) AC B( A C) A A AC B ( A C) asAA 0 A( A C) B( A C)or by rule 19.
271Math 123Boolean Algebra (A B) ( A C)L.H.S. R.H.S.11.10 Sum of Product (Minterm):The Sum of Product means that the products of the variablesthat are seperated by a plus sign. The variables can be complemented oruncomplemented, for-example,AB A B A B A B AB C A B C A B C11.11 Product of sum (Maxterm):The Product of Sum means that the sum of variables that areseperated by a multiplication sign. For example,(A B) ( A B) (A B ) ( A B ),(A B C)(A B C )( A B C)11.12 Fundamental Products:The products that produce a high (1) output are calledFundamental products. For example, for the two input variables A and B.We have four possible combination‟s, which are shown in the table belowand the fundamental product‟s corresponding to each:Truth Table 14 Two VariablesTable 14ABOutput Z0FundamentalProductA BABAB0001111AB1111
272Math 123Boolean AlgebraFor three input variables or signals a similar idea is applied.Whenever the input variable is 0, the same variable is complemented inthe fundamental product.Truth Table 15.A BCOutputZ00000010010101111000101011011110Three variablesFundamentalProductA B CA B CA BCA BCAB CAB CAB CABCOutput forproduct1111111Output forSumA B C1Sum of product(SOP)Sum terms0A B CA B CA B CA B C0000A B CA B CA B C000 A B C A B C A B CProduct of sum(POS) (A B C) (A B C ) ( A B C)(A B C ) (A B C )Note: See remarks for sum of product and product of sums.Remarks:(1)A sum of product (minterm) is obtained as follows: Foreach row of the truth table for which the out put is 1, theBoolean term is the product of variables that are equal to 1and the complement of variable that are equal to 0. Thesum of these products is the desired Boolean equation.(2)A product of sum expression is obtained as follows: eachrow of the truth table for which the output is 0, the Booleanterm is the sum of the variables that are equal 0 plus thecomplement of the variables that are equal to 1. The
273Math 123Example 7:Boolean Algebraproduct of these sum is the desired Boolean equation.Find the sum-of-products and product of sumsequations from the given truth Table - 16.Table 16ABCOutput Functional ct EquationX A B C A B C A B C AB CProduct-of-Sums Equation:Y (A B C)(A B C )( A B C )( A B C )NOTE:The Boolean expression from the truth table is the sum of product(minterms)terms for which the output is i.e.,X A B C A B C A B C AB C11.13 NAND and NOR gates:DeMorgan‟s theorems form two new gates NAND and NOR gates.These gates are the most popular and most widely used logic gates. Sinceany logic circuit can be constructed using only NAND and NOR gates,they are often referred to as the Universal building blocks.NAND gates:This NAND (or not AND) gate is an AND gate followed by aNOT circuit: The operation of the NAND gate is described by one ofDeMorgan‟s Theorem, which states that A.B A B . TheNAND gate has two or more input signals but only one output signal. Anyinput must be high to get a high output
274Math 123Boolean AlgebraAAA.BA.B A BBBA.B A BNANDGae (a) Standard Symbol(b) Logical meaning of NAND GateFig. 6(a) (b)NAND- Gate truth Table 17Table 17A0011B0101A.B.00011110NOR-Gate:The NOR (or not OR) gate is an OR-gate followed by a NOTcircuit. The operation of the NOR-gate is described by DeMorgan‟stheorem, which states that.A B A . BThe NOR gate has two or more input signals but only one outputsignal. All inputs must be low to get a high output.AAA BBBA B A . BA B A . BNAND Gate ( c) Standard Symbol(d) Logical meaning of NAND GateFig. 6(C)(d)Table 18ABA BA B0001011010101110
275Math 123Boolean AlgebraNAND and NOR Gates in Two level NetworkAA.B A BB(A.B) (C.D) AB CD)CDC.D C BFig. 7 (i) NAND Gates in Two - Level NetworksAA BB(A B) (C D) (A B)(C D)NORCDC.DFig. 7: NAND and NOR Gates in Two - Level NetworksFig. 711.14 Combination of Gates:The OR gate and AND gates and invertors can be interconnectedto form gatting or logic networks, in the switching theory, these are alsocalled combinational networks. The Boolean algebra expressioncorresponding to a given Network can be driven by systematicallyprogressing from input to output on the gates.A net work that forms(i) (X.Y) ( X . Y )and another net work that forms(ii) (X Y). ( X Y ) are shown as
276Math 123Boolean AlgebraX X YY(i)(i)ANDAGX.YORANDAGXX YYXYOr,XX.YYANDORXYANDX.Y X YX.YX(ii)YORX Y(X Y)(X Y)ANDXYORX YFig. 811.15Boolean Expression and Logic Diagrams:Boolean expressions are frequently written to describe mathematicallythe behavior of a logic circuit. Using a truth table and the Boolean expression,one can determine which combinations of input signals cause the output signal.
277Math 123Boolean AlgebraExample ally the behavior of logic circuit shown infig.10. Use a truth table to determine what inputconditions produce a logic 1 output.ABXCFig.10Solution:AAA. BBAB CX AB CCFig.11Fig.11 Circuit showing solution for example 9 8Solution:Truth Table 18 for the Circuit in Fig.11ABCAABA B C000011110011001101010101111100000111010101110101A B C10001010Thus the input conditions those produce a logic 1 output are : 0 0 0 , 100, 110
278Math 123Example 9:Boolean AlgebraGiven the Boolean expressionX AB ABC A B C A CSolution:(a)Draw the logic diagram for the expression.(b)Minimize the expression.(c)Draw the logic diagram for the reduced expression.(a)The logic diagram is shown in the Fig. 12.(b) X AB ABC A B C A C AB (1 C) A C ( B 1) AB. 1 A C .1 AB A C A(B C )(c)ABCFig.13X A(B C )Minimize diagram for example 9.
279Math 123Boolean Algebra11.16 Karnaugh Maps:Many engineers and technicians prefer to use Karnaugh Maps tominimize the Boolean expressions instead of Boolean Algebra. Thissection tells you how to construct. Here we use the Karnaugh maps tominimize expressions containing up to four Variables.A Karnaugh map is a graphical form of a truth table and consistsof a square or rectangular array of adjacent cells or blocks. The number ofcells in a particular map depends on the number of variables in theBoolean expression to be minimized. The number of cells for a particularmap is determined from expression.N 2nWhere N number of cells required for the Karnaugh map.n number of variables in the Boolean expression.The configuration of the Karnaugh map for two, three and fourvariable expression is shown in Fig. In the Karnaugh map, each variableand its complement are assigned half of the cells in the map. The assignedcells consists of adjacent rows or columns.(a)Two-variablesmap(b) Threevariables map(c)Four Variables mapThe sides of the map are labeled to show cell assignment asshown for the two variables map in Fig. 16. The two left hand cell beneathA are assigned to A and the two right hand cells or assigned to A .Moving horizontally, the top two cells are assigned to variable B and thebottom two cells are assigned to B . Each cell assigned a unique address,which is specified by the row column in which the cell resides. Fig. 17shows which variable share each cell in fig. 16.
280Math 123Boolean AlgebraAABBBABBAA BA BFig. 16Fig. 17The maps showing cell assignments for three and four variablesexpression are shown in Fig.18. The sides of the maps may be labeled inonly convenient way. Two cells of a map are considered to be adjacent aslong as their respective addressed differed by no more than one variable.For example, ABCD and ABC D are addresses of adjacent cells.Diagonal cells are not adjacent, even though they shore a common corner,because their addresses differe by more than one variable.BA BAB CB CA BABABC DC DCDBCC DB C(a)(b)Fig. 18After learning how to draw a Karnaugh map, the next step is toplot the given expression. The given expression must be in the sum-ofproducts form. The expression A B C ABC is the sum of two products,or, two minterms, and is therefore in the correct form; however, theexpression (A C) (B C) is not in the correct form and cannot be plotted inthis form.To plot an expression, we identify with a 1 each cell addressed bya minterm (product term). After placing a l in cells addressed by eachminterm, adjacent cells containing all are enclosed either singularly, inpairs, or in groups of 4, 8 or 16 (integral power of 2). We enclose thelargest number of adjacent cells containing a „l‟ as possible – as long asthe enclosed „l‟s equal 2 raised to an integral power. The enclosed, „l‟s arecollectively called a group or an implicant.
281Math 123Boolean AlgebraThe desired minimized Boolean expression is obtained from theKarnaugh map by applying the following two steps:1 . All 1‟s must be included in at least one group. It is permissible,and desirable, to enclosed a l more than once if it facilitatesenlarging another enclosure.2 . Each group represents a minterm. The sum of the minterms thatrepresent these groups is the minimized Boolean expression insum-of-products form corresponding to the given logic function.The use of these rules is illustrated in the following example:Example 10: Plot the Boolean express X AB A B BCand minimize expression from the Map.Solution:Since the expression contains three variables, we need a Karnaughmap containing cells equal toAAN 23 81BC1BCBCBC111Fig.19To plot the expression, we start by identifying all cells that arecommon to AB by placing 1 in these cells. If we repeat this procedure forthe terms A B and B C and placing a l in cells common to the minterms,we have plotted the function as shown in Fig. 19.To minimized Boolean expression, all 1,s must be enclosed at leastonce. Greatest minimization is achieved by enclosing the largest numberof adjacent l‟s possible, even if same have already enclosed.In Fig. 19, the 1‟s making up the larger group are common only to A,and the 1‟s making up the smaller group are common to B and C;therefore, the minimized expression isX A BC
282Math 123Boolean AlgebraAlgebraic Proof:The sum-of-products equation corresponding to larger group isY A B C A B C AB C ABC A ( B C B C B C BC) A{ B ( C C) B ( C C) A( B B) AThe sum-of-products equation corresponding to the smaller group isZ A BC ABC ( A A) BC BCExample 11:Minimize the following Boolean expression by use of theKarnaugh map.X B C B D AB AD AC C DSolution:The number of cells areN 24 16To plot the expression, place 1 in the cells common to each term inthe expression: Fig: 20A B AB AB ABCD11CD1111111CDCD11Fig.20
283Math 123Boolean AlgebraThe minimized expressions is:X B C AD C DNOTE: On four-variable maps, l‟s is cells on opposite sides of the mapmay be enclosed since the map is continuous, like a cylinder, inboth the horizontal and vertical planesExample 12: Minimize the following Boolean expression by use ofthe Karnaugh map:X A C D A B C D A B D A B CDSolution:Fig.21 shows the Karnaugh mapfor the expression.CDThe minimized expression isCDX B D C DA B AB AB A B11CD11CD11111Fig.2111.17 Non-Unique Group:Occasionally, we find a Karnaugh map for which more than one setof groups exists. This situation is illustrated in Fig.19. One can readily seethat both maps yield Boolean expression with three two-variableminterms. These equivalent expressions, described the same function;however, they differ in the way in which variables are combined. Booleanfunctions that can be described by two or more equivalent minimizedBoolean expressions are referred to as non-unique. On the other hand,functions that described by a single minimized Boolean expressions arereferred as unique.
284Math 123Boolean AlgebraWhen a non-unique Boolean function is to be implemented withlogic gates, it generally does not matter which of the possible minimizedexpressions is implemented. However, occasionally one expression maybe preferred because certain variables or minterms are more accessible ormay be available from an existing circuit.ABCBC11AA1BCBCABC1BC1BC1BC1111(a)11(b)Fig. 19:Boolean expressions from non-unique groups.(a) X1 AB A C B C , (b)X2 A C BC A BExample 12: Read out some of the possible Boolean expressions forthe Karnaugh map shown in Fig. 20.A B AB AB A BCD11CD11CD11CD1111Fig.20Solution:Fig.20 shows several possible combinations of enclosureand the resulting Boolean expression.
285Math 123Boolean AlgebraA B AB AB ABA B AB AB A BA B AB AB A CDCD1111111(c)(a)Fig.21 Various combinations of enclosures.(a) X B C A C B C C D(b) X B C B C A B C D(c) X B C A C B C B D11.18 Redundant Groups:After you finish encircling groups, there is one more thing to dobefore writing the simplified Boolean equation: eliminate any groupwhose l‟s are completely over lapped by other groups. (A group whose 1‟sare all overlapped by other groups is called redundant group).11.19 Dont’ Care States:Using the truth table, we, can list each combination of inputvariables that should cause a high output to exist. For some Booleanfunctions, the output corresponding to certain combinations of inputvariables does not matter. This usually occurs because certaincombinations of input variables cannot exist. Also, there are times that wedo not really care what value a function may take on. In both instances wecall such a term a don't care state. Don‟t-care states, means, that we do notcare whether the entry in a karnaugh map corresponding to a certaincombination of variables is a 1 or a 0. We shall use the symbol X for don‟tcare states.Don‟t-care states can be very important in the minimizationprocess. Since we can assign either a 1 or 0 to a don‟t-care condition, wecan choose which ever value will provide a larger enclosure andtherefore a simpler, more economical circuit.
286Math 123Boolean AlgebraExample 13: A logic circuit is to be constructed that will implementthe Boolean expression:X A B C A B C A B CPlot this expression on a Karnaugh map and reduce the expressionAAAAif the term A B C is a don't care.Solution:BCBCBCBCBCBCBCBC(a)(b)Fig.22 (a) Karnaugh map for given(b) Karnaugh map, illustratingexpressionthe use of don‟t care states.The expression corresponding to the map in Fig. 22 (b) is :X A B A C CTherefore, assigning a value of 1 to the don‟t care State allowed us toreduce the original expression significantly.11.20For the given truth table minimize the Booleanexpression using Karnaugh map.Consider the truth table. The Fundamental products for these 1 output are A B C , AB C and ABC. Enter these 1‟s on the Karnaugh 1Karanaugh mapfor theTruthTableBCBCBC111Fig.23
287Math 123Boolean AlgebraThe sum-of-product form for the Boolean expression from thetruth table isX A B C AB C ABCTo minimize this Boolean expression from the Karnaugh map, wefind thatX B C ABExercise 11Q.1:Q.2:Q.3:Q.4:Prepare a truth table for the following Boolean expression:(i)XYZ X Y Z(ii)ABC A B C A B C(iii)(A D) (B C)(iv)(A B) (A C)( A B )(v)AB A BSimplifying the following with the help of Boolean algebraRules:(i)AB AC ABC(ii)AB A( B C) AB C(iii)A BC A B C ABC AB C A B C(iv)AB C A B C A BC A B CMinimize the following expressions:(a)X W Z (W Y) WY( Z W )(b)X (A B) ( C )(c)X (A B C B C )(d)X (A B C ABC ) CConvert the following expression to sum-of-product form.
288Math 123Boolean Algebra(A B)( B C) ( A C)(ii)(A C) (A B AC)( A B C )Q.5: Convert the following expression to product-of-sum form:(i)A A B A C(ii)(AB C ) A C B B(iii)AB ABC A B C A C (iv)AB A BQ.6: Express the given function in the product of sums, also drawits circuit and truth table.X A B C A B C ABQ.7: Draw
Chapter - 11 . Boolean Algebra . 11.1 Introduction: George Boole, a nineteenth-century English Mathematician, developed a system of logical algebra by which reasoning can be expressed mathematically. In 1854, Boole published a classic book, “An Inve
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
123.1 3 RESCO (Ohio) Patronage 123.16 WPSC - Power Supply Development Fund 123.40 Wolverine Power Supply - Membership 123.42 NRUCFC -Membership 123.43 MECA - Membership 123.45 NRTC - Membership 123.64 MECA - Building 123,21822 NRUCFC - Capital Term Certificates 123.00 RESCO -Stock 123.1 5 NRTC 123.01 RESCO -Class 0 Stock
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
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
Intermediate Algebra 2nd Edition Ray Steege, Kelly Bailey McGraw Hill Math 120, 122, 123 1 Intermediate Algebra Charles McKeague XYZ Math 120, 122, 123 1 Intermediate Algebra for College Students Bernard Kolman, Arnold Shapiro BVT Math 120, 122, 123 1 Intermediate Algebra 4th Edition Jay Lehmann Prentice Hall Math 120, 122, 123 6
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
6. Boolean Algebra 3. Postulates, Laws and Theorems of Boolean algebra Boolean algebra is useful mathematical tool normally used to analyze a logic circuit and express its operation mathematically. It also plays an important role in designing digital system. The basic laws and theorems are normally utilized
Organist) and a fine choir, affiliated to the RSCM. Young singers train through the RSCM Voice for Life scheme, at which they have achieved much success in recent years. At present we have 17 trebles (both boys and girls) of school age and 19 adults. Funding is available for organ and choral scholars. The choir sings: at the 9:15 Parish Eucharist every Sunday during term time Choral .
