Digital Electronics - Khulna University

Digital ElectronicsECE 2203Lecture 3Professor Dr. Md. Shamim AhsanElectronics and Communication Engineering DisciplineKhulna University.

OutlineLogic Gates & Boolean AlgebraBoolean TheoremsBasic PostulatesDualityFundamental Theorems of Boolean AlgebraUniversality of NAND and NOR GatesAlternate Logic Gate RepresentationLogic Symbol Interpretation

Logic Gates & Boolean Algebra Boolean Theorems: We have seen how Boolean algebra can be used to help analyze a logic circuitand express its operation mathematically.We will continue our study of Boolean algebra by investigating the variousBoolean theorems (rules) that can help us to simplify logic expressions andlogic circuits. Basic Postulates:

Logic Gates & Boolean Algebra Basic Postulates:

Logic Gates & Boolean Algebra Duality: The principle of duality is a very important concept in Boolean algebra.Briefly stated, the principle of duality pronounces that, if an expression is validin Boolean algebra, the dual of the expression is also valid.The expression is found by replacing all „ ‟ operators with „.‟, all „.‟ operatorswith „ ‟, all ones with zeros, and all zeros with ones.The principle of duality will be used extensively in proving Boolean algebratheorems. In fact, once we have employed the postulates and previouslyproven theorems to demonstrate the validity of one expression, duality can beused to prove the validity of the dual expressions.Example (1): Find the dual expression a (bc) (a b)(a c)Solution:a(b c) ab acWhen obtaining a dual, we must be careful not to alter the location ofparentheses, if they are present.

Logic Gates & Boolean Algebra Fundamental Theorems of Boolean Algebra:Table 1. Summary of the fundamental postulates & theorems of Boolean algebra.ExpressionDual

Logic Gates & Boolean AlgebraProof of 1(a):Proof of 1(b)a.a aa 0 aa aa a(a a) a.1 aProof of 2(a):Proof of 2(b)a.0 0 by duality[P-2(a)][P-6(b)][P-5(b)][P-6(a)][P-2(b)]

Logic Gates & Boolean AlgebraProof of 4(a):Proof of 4(b)a(a b) (a 0)(a b) a 0.b a 0 aExample (2):(i)(ii)(iii)[P-2(a)][P-5(a)][P-2(b)][P-2(a)]

Logic Gates & Boolean AlgebraProof of 5(a):Proof of 5(b)a(a b) aa ab 0 ab abExample (3):(i)(ii)(iii)(iv)[P-5(b)][P-6(b)][P-2(a)]

Logic Gates & Boolean AlgebraProof of 6(a):Proof of 6(b)(a b)(a b) a bb a 0 aExample (4):Example of Theorem 6(a):(i)Example of Theorem 6(b):(i)(ii)[P-5(a)][P-6(b)][P-2(a)]

Logic Gates & Boolean AlgebraProof of 7(a):Proof of 7(b)(a b)(a b c) a b(b c)Example (5):Example of Theorem 7(a):(i)(ii)Example of Theorem 7(b):(i)(ii) a bb bc a 0 bc a bc (a b)(a c)[P-5(a)][P-5(b)][P-2(a)][P-2(a)][P-5(a)]

Logic Gates & Boolean AlgebraProof of 8(a):

Logic Gates & Boolean AlgebraProof of 8(a) (Continued):

Logic Gates & Boolean AlgebraExample (6):Example of Theorem 8:-a(b z(x a)) a (b z(x a) a b . z(x a)[xy x y][T-8(b)][x y x.y] [T-8(a)] a b (z (x a)) [xy x y] a b (z x.a)[x y x.y] [T-8(a)] a b (z xa)[x x] a bz b xa[T-3][P-5(b)] a bx bz a b (x z)[T-8(b)][[x xy x y] [T-5(a)]x(y z) xy xz] [P-5(b)]

Logic Gates & Boolean AlgebraProof of 9(a):Example (7):Example of Theorem 9(a):(i)(ii)Example of Theorem 9(b):(i)

Logic Gates & Boolean AlgebraExample (8): ReduceSolution:AB ABC A(B AB).AB ABC A(B AB) A(B BC) A(B AB)[x(y z) xy xz] A(B C) A(B A)[x xy x y] A B AC AB AA[x(y z) xy xz] AB AC AB A[x.x x] AB AC A[x xy x y] AB AC A[x y x y] (A B) (A C) A[x y x y] (A B) (A C) A[x x] A BC A[(x y)(x z) x yz] 1 BC[x x 1] 1 0[1 x 1]

Logic Gates & Boolean Algebra Universality of NAND and NOR Gates: It is possible, however, to implement any logic expression using only NANDgates and no other type of gate. This is because NAND gates, in the propercombination, can be used to perform each of the Boolean operations OR,AND, and INVERT (NOT). This is demonstrated in Figure 1.Figure 1. NAND gates can be used to implement any Boolean function.

Logic Gates & Boolean Algebra Universality of NAND and NOR Gates: In a similar manner, it can be shown that NOR gates can be arranged toimplement any of the Boolean operations. This is illustrated in Figure 2.That’s why NAND and NOR gates are called Universal Gates.Figure 2. NOR gates can be used to implement any Boolean function.

Logic Gates & Boolean AlgebraProblem (Tocci-C 3-28):.Figure 3-53(b) Solution:The output expression of Figure 3-53(b) is The equivalent circuit of Figure 3-53(b) using only NAND gates is shown inFigure 3.

Logic Gates & Boolean AlgebraProblem (Tocci-C 3-28):Solution (Continued): Figure 3. Equivalent circuit of Figure 3-53(b).The NAND gates 7, 8, 9 and 10, 11, 12 can be eliminated from Figure 3 sincethey perform a double inversion of the signal outputs of NAND gates 4, 5, and6. The simplified circuit of Figure 3 is illustrated in Figure 4.The output expression of Figure 4 is .

Logic Gates & Boolean AlgebraProblem (Tocci-C 3-28):Solution (Continued):Figure 4. Simplified circuit of Figure 3. Using DeMorgan‟s Theorem we obtain x ABC ABC ABD x ABC ABC ABD So the simplified output expression is equal to the expression for the originalcircuit.

Logic Gates & Boolean Algebra Alternate Logic-gate Representation: Although you may find that some circuit diagrams still use these standardsymbols exclusively, it has become increasingly more common to find circuitdiagrams that utilize alternate logic symbols in addition to the standardsymbols shown in Figure 5.Figure 5. Standard and alternate symbols for various logic gates. .

Logic Gates & Boolean Algebra Logic Symbol Interpretation: When an input or output line on a logic circuit symbol has no bubble on ot,that line is said to be active-HIGH. When an input or output line does have abubble on it, that line is said to be active-LOW.To illustrate, Figure 6(a) shows the standard symbol for a NAND gate. It hasan active-LOW output and active-HIGH inputs. The logic operationrepresented by this symbol can therefore be interpreted as follows:“The output goes LOW only when all of the inputs are HIGH.”Figure 6. Interpretation of the two NAND gate symbols. .

Logic Gates & Boolean Algebra Logic Symbol Interpretation: The alternate symbol for a NAND gate shown in Figure 6(b) has an activeHIGH output and active-LOW inputs, and so its operation can be stated asfollows:“The out goes HIGH when any input is LOW.”For now, let us summarize the important points concerning the logic-gaterepresentations.(1) To obtain the alternate symbol for a logic gate, take the standard symboland change its operation symbol (OR to AND, or AND to OR), andchange the bubbles on both inputs and output (i.e. delete bubbles that arepresent, and add bubbles where there are none).(2) To interpret the logic-gate operation, first note which logic state, 0 or 1, isthe active state for the inputs and which is the active state for the output.Then realize that the output’s active state is produced by having all of theinputs in their active state (if an AND symbol is used) or by having anyof the inputs in its active state (if an OR symbol is used).Self Study: Tocci-3-14

Logic Gates & Boolean AlgebraProblem (Tocci-B 3-40):Figure 3-59 Solution:The active state of the output of Figure 3-59 is active-HIGH or 1. Inputs to theGate-3 is active LOW. So any one of the inputs to the OR gate is 0, the outputgoes to 1. So, D should be 0.So, E should be 1. When B and C are 0, the output of the Gate-2 will be 0.Again when B 1 and A 0, then the output of the Gate-1 will be 0.So, X will go HIGH when E 1, or D 0, or B C 0, or when B 1 and A 0.

Logic Gates & Boolean Algebra Homework: Problems-Tocci-Chapter 3:- 3.1, 3.6, 3.12 to 3.21, 3.24 to 3.31,3.38.

References[1] “Digital Systems: Principles and Applications,” Neal S. Widmer,Gregory L. Moss, and Ronald J. Tocci, 12th Ed., Pearson (2018).[2] “Digital Logic and Computer Design,” M. Morris Mano, 1st Ed.,Pearson (2016).[3] “Digital Logic Circuit Analysis and Design,” Victor P. Nelson, H.Troy Nagle, Bill D. Carroll, and David Irwin, 1st Ed., Pearson(1995).

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