BCA 111 DCLD

Number System 43 4. Convert (49.25)10 into its equivalent binary number   (a) (111.11)2 (b) (111.00)2 (c) (1111.000)2 (d) (110001.01)2 5. Convert (10110)2 into its hexadecimal equivalent (a) (16)16 (b) (44)16 (c) (45)16 (d) (22)16 Answers 1. (a), 2. (b), 3. (c), 4. (d), 5. (a) 2.8 References 1. https://www.geeksforgeeks.org/number-system-and-base-conversions/ 2. https://www.robotroom.com/NumberSystems2.html 3. https://circuitglobe.com/number-system-in-digital-electronics.html CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 3 LOGIC GATES 1 Structure: 3.0 Learning Objectives 3.1 Introduction 3.2 Positive and Negative Logic 3.3 Basic Gates 3.4 Not Gate 3.5 OR Gate 3.6 NOR Gate 3.7 AND Gate 3.8 NAND Gate 3.9 X-OR Gate 3.10 X-NOR Gate 3.11 Summary 3.12 Key Words/Abbreviations 3.13 Learning Activity 3.14 Unit End Questions (MCQ and Descriptive) 3.15 References CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 1 45 3.0 Learning Objectives After studying this unit, you will be able to:  Discuss logic gates  Draw the block diagram of various logic gates  Explain the operation of logic gates 3.1 Introduction A logic gate is an electronic component that can be used to conduct electricity based on a rule. The output of the gate is the result of applying this rule to one or more “inputs”. These inputs may be two wires or the output of other logic gates. A logic gate is an electronic component that can be used to conduct electricity based on a rule. The output of the gate is the result of applying this rule to one or more “inputs”. These inputs may be two wires or the output of other logic gates. Logic gates are digital components. They normally work at only two levels of voltage, a positive level and zero level. Commonly they work based on two states: On and Off. In the On state, voltage is present. In the Off state, the voltage is at zero. The On state usually uses a voltage in the range of 3.5 to 5 volts. This range can be lower for some uses. Logic gates compare the state at their inputs to decide what the state at their output should be. A logic gate is on or active when its rules are correctly met. At this time, electricity is flowing through the gate and the voltage at its output is at the level of its On state. Logic gates are electronic versions of Boolean logic. 3.2 Positive and Negative Logic George Boole in 1854 found the missing link between mathematics and logic by inventing symbolic logic, known as 'Boolean Algebra'. Boolean Algebra is used to analyze and simplify the digital (logic) circuits. It uses only the binary numbers i.e. 0 and 1. Its advantages are simplicity, speed and accuracy. The word logic is commonly used in conversation English and it is derived CU IDOL SELF LEARNING MATERIAL (SLM)

46 Digital Circuits and Logic Designs form Greek word “LOG” which refers to reason and the suffix “IC” meaning “the study of so logic is study of reason. Gate is another common word. The common usage of “ gate ” is an opening in a wall, a means of exit or entrance. The technical definition of ‘gate’ is a natural extension of its common form . It is a device whose output is a specific when specified input condition are met. A logic gate is an electronic device which is used to make logical decisions. It has one or more input signals but only 1 output. The output is expressed in terms of binary code 0 or 1. Positive logic inputs and outputs are also called active high. Negative logic inputs and outputs are called active low. Input and output polarity is indicated by a bubble or triangle. For example, the following shows a positive logic AND gate and a negative logic OR gate. 3.3 Basic Gates Logic Gate Basic Gate OR Gate AND NOT Universal EX-OR EX-NOR Gate Gate Gates Gate Gate NAND NOR Gate Gate Fig. 3.1: Basic Gates There are 5 basic gates used in performing logic operations in Digital Electronic namely BUFFER gate, NOT gate, AND gate, OR gate, XOR gate. Each Logic Gate has A Symbol for easy to identify, a Mathematical Expression to identify mathematic logic operation and a Truth Table to completely describe operation of the Logic Gate. CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 1 47 3.4 Not Gate This gate is always single input gate. It inverts the input to get the output. Therefore this gate is also known as “inverter”. Logic - If A is true then Y is false and if A is false then Y is true. Boolean Equation Y = A Logic Diagram - Truth Table 3.1 Y A 1 AY 0 0 1 Fig. 3. 2 3.5 OR Gate It is also known as “Inclusive - OR” gate. Consider A and B are inputs and Y is output. This gate is called any or all gate. Logic - If A is true or B is true then Y is true. It means that either A should be high or B should be high or the output is high. Boolean Equation Y = A + B Logic Diagram - Truth Table 3.2 ABY A 000 B 010 100 Fig. 3.3 111 CU IDOL SELF LEARNING MATERIAL (SLM)

48 Digital Circuits and Logic Designs 3.6 NOR Gate A NOR gate is a type of logic gate that works on the principle of “neither this nor that.” This type of digital logic gate produces a high output only if two binary results are satisfied by a zero or low input. In Boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form (p NOR q) is true precisely when neither p nor q is true—i.e., when both of p and q are false. In grammar, nor is a coordinating conjunction. Logic Diagram Truth Table 3.3 A Inputs Outputs B XY Z Fig. 3.4 00 1 01 0 10 0 11 0 3.7 AND gate It has two or more input signals but only one output. All inputs must be high to get a high output. Consider A and B are inputs and Y is output. Logic - If A is true and B is true then Y is true Boolean Equation-Y = A * B Truth Table 3.4 Logic Diagram ABY 000 A 010 Y 100 111 B Fig. 3.5 CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 1 49 3.8 NAND gate Bubble indicate inversion and Bar on the equation indicates the inversion. The NAND gate has two or more inputs but only one output. All the inputs must be set to high to get a low output. If any input is low output is high. Logic Diagram Truth Table 3.5 ABY A 001 B 011 101 Fig. 3.6 110 3.9 X-OR Gate Exclusive-OR or X-OR is called X-OR because it is special case of OR gate. It is not a basic operation and can be performed using basic gates AND, OR, NOT or universal gates (NOR and NAND). If we compare truth table of X-OR gate with OR gate, then in truth table three rows are same, only fourth row is different. Hence, it is named as EX-OR which excludes the condition of OR gate,where both A and B are 1 and normal OR operation is called as Inclusive OR. Logic Diagram Truth Table 3.6 A Inputs Output B AB Y=AB 00 Fig. 3.7 01 1 10 1 11 1 0 CU IDOL SELF LEARNING MATERIAL (SLM)

50 Digital Circuits and Logic Designs 3.10 X NOR Gate This gate is NOT followed by X-OR gate. The output of X-OR gate is logic 1 when both the inputs are same, i.e., logic 0 or logic 1. The output is logic 0 when both the inputs are different, i.e., one held at logic 0 and another at logic 1.X NOR is complement of X OR operation. Logic Diagram Truth Table 3.7 AY Inputs Output B XY Z Fig. 3.8 00 1 01 0 10 0 11 1 Q. 1. Describe with symbol, truth table, operation of AND gate. Ans. A circuit which performs an AND operation is called as AND gate. This gate has two or more inputs signals but only one output signal. The AND gate has a high output only when all inputs are high. It indicates Logical Multiplication denoted by dot (.). A ABY B Output 000 010 Fig. 3.9 100 111 Q. 2. What is Input Bubbled Logic? Ans. The NOT Gate provides complement of its input signal that is when its input is “High”, the output is “Low” and when its input is “Low” the output is “High”. The “bubble” (o) present at the end of the NOT gate symbol indicates signal inversion or complement of the input signal. But this bubble can also be present at the input of the logic gates to indicate an active-LOW input. This inversion of the input signal is not just restricted to the NOT gate only but can be used on any digital circuit or gate. Thus a bubble simply works as an inverter whether present at input or output. CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 1 51 A QA Q Fig. 3.10 A bubbled gate accepts inputs in the inverted form that is if input is high the gate will accept the input as low and vice versa. Q. 3.Why NAND and NOR gates are called as Universal gates? Ans. Any Boolean (or logic) equation can be realized by using the AND, OR & NOT gates. From these three operation two more operations are derived 1. The NAND operation (AND + NOT) 2. The NOR operation (OR + NOT ) These operation are very popular and widely used. The reason being the only one type of gates either NAND or NOR are sufficient for the realization (implementing ) of any logical operation. Because of this reason NAND and NOR gates are known as universal gates. Using theses gates one can realize any given logical expression like AND, OR, NOT, XOR, XNOR, as a result they are called as Universal Logic Gates A Q B Fig. 3.11 3.11 Summary Logic Gates used in Digital Computers. Electrical signals such as voltages exist throughout the computer in either one of the two recognizable states. The two states represent a binary variable that can be equal to 1 or 0. CU IDOL SELF LEARNING MATERIAL (SLM)

52 Digital Circuits and Logic Designs 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. 3.12 Key Words/Abbreviations  EX-OR gate: Exclusive OR Gate  EX-NOR gate: Exclusive NOR Gate 3.13 Learning Activity 1. Define logic gates. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Draw the block diagram of various logic gates. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3. Describe operation of logic gates. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3.14 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions 1. What are logic gates? 2. Draw the block diagram of various logic gates. 3. Describe operation of logic gates. CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 1 53 B. Multiple Choice/Objective Type Questions 1. __________ gate is also known as “inverter”. (a) Not (b) OR (c) AND (d) NAND 2. Y = A + B is the equation of __________ gate. (a) X-OR (b) OR (c) NOT (d) NOR 3. Y = A is equation of __________ gate. (a) OR (b) NOR (c) NOT (d) AND 4. Positive logic inputs and outputs are also called __________. (a) Toggle (b) Active low (c) Zero (d) Active high 5. A __________ is an electronic device which is used to make logical decisions. (a) Logic gate (b) Encoder (c) Decoder (d) Mux Answers 1. (a), 2. (b), 3. (c), 4. (d), 5. (a) 3.15 References 1. https://www.tutorialspoint.com/computer_logical_organization/logic_gates.htm 2. https://www.geeksforgeeks.org/introduction-of-logic-gates/ 3. https://www.google.com/search?sxsrf=ACYBGNSPFRPNBXo8VBa3r8nmlq1GBWtX XA:1576059482981&q=logic+gates+applications&sa=X&ved=2ahUKEwjmxIKNr63m AhXNiVwKHThqCFsQ1QIoAHoECBUQAQ&biw=1360&bih=667 . 4. https://books.google.co.in/books/about/PULSE_AND_DIGITAL_CIRCUITS.html?id= ECeObhzCiLIC&source=kp_book_description&redir_esc=y  CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 4 LOGIC GATES 2 Structure: 4.0 Learning Objectives 4.1 Introduction 4.2 Symbols of Basic Gates 4.3 Truth Table of Basic Gates 4.4 Circuit Diagram of Basic Gates using Diodes and Transistors 4.5 Universal Properties of NAND and NOR Gate 4.6 Summary 4.7 Key Words/Abbreviations 4.8 Learning Activity 4.9 Unit End Questions (MCQ and Descriptive) 4.10 References 4.0 Learning Objectives After studying this unit, you will be able to:  Explain truth table of various gates  Describe working of logic gates  Explain functioning universal gates CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 55 4.1 Introduction The table used to represent the Boolean expression of a logic gate function is commonly called a Truth Table. A logic gate truth table shows each possible input combination to the gate or circuit with the resultant output depending upon the combination of these input(s). 4.2 Symbols of Basic Gates 1. AND Gate The AND gate is a digital logic gate with ‘n’ i/p one o/p, which perform logical conjunction based on the combinations of its inputs. The output of this gate is true A A.B only when all the inputs are true. When one or more inputs B of the AND gate’s i/p are false, then only the output of the Fig. 4.1: AND Gate AND gate is false. The symbol and truth table of an AND gate with two inputs is shown in the adjoining figure. 2. OR Gate A Y=A + B B The OR gate is a digital logic gate with ‘n’ i/p and Fig. 4.2: OR Gate one o/p, that performs a logical conjunction based on the combinations of its inputs. The output of the OR gate is true only when one or more inputs are true. If all the i/p of the gate are false, then only the output of the OR gate is false. The symbol and truth table of an OR gate with two inputs is shown in the adjoining figure. CU IDOL SELF LEARNING MATERIAL (SLM)

56 Digital Circuits and Logic Designs 3. NOT Gate Y= A A The NOT gate is a digital logic gate with one input and one output that operates an inverter operation of the Fig. 4.3: NOT Gate input. The output of the NOT gate is the reverse of the input. When the input of the NOT gate is true then the output will be false and vice versa. The symbol and truth table of a NOT gate with one input is shown in the adjoining figure. 4. NAND Gate A ZZ The NAND gate is a digital logic gate with ‘n’ i/p and one o/p, that performs the operation of the AND gate B followed by the operation of the NOT gate. NAND gate is designed by combining the AND and NOT gates. If the Fig. 4.4: NAND Gate input of the NAND gate high, then the output of the gate will be low. The symbol and truth table of the NAND gate with two inputs is shown in the adjoining figure. 5. NOR Gate A Y=A + B The NOR gate is a digital logic gate with n inputs and one output, that performs the operation of the OR gate B followed by the NOT gate. NOR gate is designed by combining the OR and NOT gate. When any one of the Fig. 4.5: NOR Gate i/ps of the NOR gate is true, then the output of the NOR gate will be false. The symbol and truth table of the NOR gate with truth table is shown in the adjoining figure. CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 57 6. Exclusive-NOR Gate A Y = AB The Exclusive-NOR gate is a digital logic gate with two inputs and one output. The short form of this gate is B Ex-NOR. It performs based on the operation of NOR gate. When both the inputs of this gate are high, then the output of Fig. 4.6: Exclusive NOR Gate the EX-NOR gate will be high. But, if any one of the inputs is high (but not both), then the output will be low. The symbol and truth table of the EX-NOR is shown in the adjoining figure. 7. Exclusive-OR Gate A Y=AB The Exclusive-OR gate is a digital logic gate with two inputs and one output. The short form of this gate is B Ex-OR. It performs based on the operation of OR gate. If any one of the inputs of this gate is high, then the output Fig. 4.7: Exclusive OR Gate of the EX-OR gate will be high. The symbol and truth table of the EX-OR are shown in the adjoining figure. 4.3 Truth Table of Basic Gates 1. AND Gate An AND gate can have two or more inputs, its output is true if all inputs are true. The output Q is true if input A AND input B are both true: Q = A AND B. Table 4.1: AND Gate Truth Table Input A Input B Output Q 00 0 01 0 10 0 11 1 CU IDOL SELF LEARNING MATERIAL (SLM)

58 Digital Circuits and Logic Designs 2. OR Gate An OR gate can have two or more inputs, its output is true if at least one input is true. The output Q is true if input A OR input B is true (or both of them are true): Q = A OR B. Table 4.2: OR Gate Truth Table Input A Input B Output Q 00 0 01 1 10 1 11 1 3. NOT Gate A NOT gate can only have one input and the output is the inverse of the input. A NOT gate is also called an inverter. The output Q is true when the input A is NOT true: Q = NOT A. Table 4.3: NOT Gate Truth Table Input A Output Q 01 10 4. NAND Gate NAND = Not AND. This is an AND gate with the output inverted, as shown by the ‘o’ on the symbol output. A NAND gate can have two or more inputs, its output is true if NOT all inputs are true. The output Q is true if input A AND input B are NOT both true: Q = NOT (A AND B). Table 4.4: NAND Gate Truth Table Input A Input B Output Q 00 1 01 1 10 1 11 0 CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 59 5. NOR Gate NOR = Not OR. This is an OR gate with the output inverted, as shown by the 'o' on the symbol output. A NOR gate can have two or more inputs, its output is true if no inputs are true. The output Q is true if NOT inputs A OR B are true: Q = NOT (A OR B). Table 4.5: NAND Gate Truth Table Input A Input B Output Q 00 1 01 0 10 0 11 0 6. EX NOR Gate Exclusive-NOR. This is an EX-OR gate with the output inverted, as shown by the 'o' on the symbol output. EX-NOR gates can only have 2 inputs. The output Q is true if inputs A and B are the same (both true or both false): Q = (A AND B) OR (NOT A AND NOT B. Table 4.6: EX NOR Gate Truth Table Input A Input B Output Q 00 1 01 0 10 0 11 1 7. EX-OR Gate Exclusive-OR. This is like an OR gate but excluding both inputs being true. The output is true if inputs A and B are different. EX-OR gates can only have 2 inputs. The output Q is true if either input A is true OR input B is true, but not when both of them are true: Q = (A AND NOT B) OR (B AND NOT A). CU IDOL SELF LEARNING MATERIAL (SLM)

60 Digital Circuits and Logic Designs Table 4.7: EX-OR Gate Truth Table Input A Input B Output Q 00 0 01 1 10 1 11 0 4.4 Circuit Diagram of Basic Gates using Diodes and Transistors (I) a) OR Gate using Diode OR gate has two or more inputs and only one output. The output of the OR gate is HIGH if one or more inputs are HIGH. In this logic gate circuit, Va and Vb are inputs and Vout is output. These symbols can take only two values either LOW or HIGH. D1 Vout Va RL Vb D2 Fig. 4.8: OR Gate using Diode Working Let us understand the working of this circuit. If all inputs are in LOW, both the diode becomes in reverse biased hence acts as an open switch. Hence, the output voltage is 0V. If A is HIGH and B is LOW, the diode D1 becomes in forward biased hence act as the closed switch. (Neglecting diode forward resistance and voltage drop across the diode) Hence the output is HIGH. Also, if A is LOW and B is HIGH, Diode D2 becomes in forward biased and act as an CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 61 open switch. Hence, the output is HIGH. If both the input is in HIGH then the output is equal to the more positive value of the input. Hence, OR function has been implemented. (b) OR Gate using Transistor Either transistor must be saturated “ON” for an output at Q. Logic OR Gates are available using digital circuits to produce the desired logical function and is given a symbol whose shape represents the logical operation of the OR gate. +6V 10K A 2N2222 typ 10K B Out 4.7K Fig. 4.9: OR Gate using Transistor (II) (a) AND Gate using Diodes Va D1 Vout Vb D2 RL AND gate has two or more inputs and only one output. The output of logic 5V AND gate is HIGH if all inputs are HIGH. For other input, the output is LOW. Circuit diagram of two-input OR gate using diodes and a resistor is shown in the adjoining figure. Fig. 4.10: AND Gate using Diodes Here, Va and Vb are inputs and V out is output. CU IDOL SELF LEARNING MATERIAL (SLM)

62 Digital Circuits and Logic Designs Working If A is HIGN and b is LOW, the diode D1 becomes in reversed biased hence act as an open switch. Also, diode D2 becomes in forward biased hence act as the closed switch. Hence, the output is LOW. If A is LOW and B is HIGH, the diode D1 becomes in forward biased hence act as the closed switch. Also, diode D2 becomes in reversed biased hence act as an open switch. The output is LOW. If all inputs are 0 then all diode becomes in forward biased and act as an open switch. Hence, the output is LOW. When all inputs are HIGH then all diodes becomes in the reversed biased hence act as an open switch. Hence, the output is HIGH. (b) AND Gate using Transistor A simple 2-input logic AND gate can be constructed using RTL Resistor-transistor switches connected together as shown below with the inputs connected directly to the transistor bases. Both transistors must be saturated “ON” for an output at Q. Input A V+ R3 10 k Q2 2N3904 Input B Q1 2N3904 R1 10 k Output Fig. 4.11: AND Gate using Transistor CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 logic 1 63 +5V (III) a) NOT Gate using Transistor and Diode +5V 1 The NOT gate can be easily understood by using a 0 LED (light emitted Diode) circuit. This is also called Light switch circuit. In this circuit, NOT gate functions like an electronic switch. When it got high input, the LED connected at the output will be OFF, as the output of NOT gate becomes 0. logic 0 Fig. 4.12: AND Gate using Transistor Here, we connect an alterable switch with the NOT gate and the output of NOT gate is connected to a LED. An LED is an electronic device which will ON and off when it receives high voltage and low voltage respectively. When the switch is connected to +5 V, the switch is on position so the LED emits light. When the NOT gate is connected to Ground, the LED will OFF so it doesn’t emit any light. (b) Not Gate using Transistor We can design a NOT gate by using a NPN transistor as shown in below picture. The Base (B) of the NPN transistor is connected with the input signal X. we connect a supply voltage of +5 V to the emitter (E) and the output Z is collected at the emitter. When the low level voltage 0 V is connected to the input, then the transistor will be OFF. So, no current flows through it. This means the supply voltage +5 V will be measured at the output port, which is considered as HIGH state. CU IDOL SELF LEARNING MATERIAL (SLM)

64 Digital Circuits and Logic Designs Similarly, when the high level voltage +5 V is +5V connected to the input, then the transistor will be ON. So, the total supply current will be drawn by transistor. R2 Z This means the no voltage is measured at the output Q1 port, which is considered as LOW state. At this situation, the output voltage is measured as +5 V, which X will be considered as HIGH logic level. The transistor designed NOT gate is shown in the adjoining figure. R1 Fig. 4.13: Not Gate using Transistor (IV) NAND Gate using Diode and Transistor This is a Diode-Transistor Logic (DTL) NAND Gate circuit using a bipolar junction transistor. A basic circuit using any general-purpose bipolar transistor such as the BC549, BC548, or BC547, could be used to construct the gate. The diodes could be any general-purpose 1N4148 type. In this configuration, the emitter-collector junctions of the bipolar transistor are in parallel across the diode. When the transistor conducts, the current flows through the transistor bypassing the diode, hence the LED switches OFF. This is a slightly complicated circuit, but not impossible to understand. As a beginner, you may be thinking that logic 0 is the same as no signal at the input. However, that is incorrect; logic 0 is equivalent to zero (ground) potential. CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 65 The 10 kΩ resistor keeps the transistor in +5V a conducting mode, however, if any one of the inputs is zero (ground), the current flow will D1 R1 R2 be through the 10 kΩ resistor, through the X Q1 Z diode, and to ground. The base current therefore shorts to ground through the diode. D2 When this happens, the transistor stops Y conducting, hence the LED comes ON. Fig. 4.14: NAND Gate using Diode and Transistor (V) NOR Gate using Transistor and Diode NOR Gate using Diode and Transistor (DTL) ... When the transistor conducts (ON), it bypasses the current because almost all the current passes through the emitter-collector junctions, and therefore the LED goes OFF. The transistor will conduct when either one or both of the inputs receive a logic 1 signal. This is a Diode-Transistor Logic (DTL) NOR Gate circuit using a general-purpose bipolar junction transistor (BC547), and general-purpose diodes (1N4148). This page shows how to make this circuit, and the implementation is on a breadboard using discrete components. The working logic is very simple. The emitter-collector junctions of the transistor connect in parallel to the light emitting diode (LED). When the transistor conducts (ON), it bypasses the current because almost all the current passes through the emitter-collector junctions, and therefore the LED goes OFF. CU IDOL SELF LEARNING MATERIAL (SLM)

66 Digital Circuits and Logic Designs The transistor will conduct when either +VCC one or both of the inputs receive a logic 1 signal. When both inputs are logic 0, the Inputs R- R2 transistor stops conducting (OFF) and all the A Q current passes through the LED instead, hence DA the LED lights up. B DZ TR Output 0V Fig. 4.15: NOR Gate using Transistor and Diode (VI) EX-NOR Gate using Diode and Transistor: XNOR gate, it uses NPN transistor. When the voltage at A and B terminals are at opposite logic state, a voltage of higher voltage minus lower voltage minus 1.2V (voltage drop between two diodes) forward bias the Emitter-Base junction of the Transistor. This turns ON the transistor and the Logic LOW voltage available at the collector of the transistor is approximately equal to 0.6+VL+VCE, where VL is the Logic LOW input and VCE is the Collector to Emitter voltage of the transistor. When the both inputs A and B are at the A 6.8k Y same Logic Levels, the Emitter to Base 10k junction of the transistor cannot be forward LOGIC biased, thus the transistor is in OFF state and INPUTS the output Y is at supply voltage. B (a) Fig. 4.16: EX-NOR Gate using Diode and Transistor (VII) EX-OR Gate using Diode and Transistor Second figure shows the circuit diagram of XOR gate, it uses PNP transistor. When the voltages at terminals A and B are at opposite logic states forward biases the Emitter-Base junction CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 67 and turns ON the transistor. Thus an approximate Logic HIGH voltage VH−0.6V−VCE is available at output terminal Y. The Logic LOW voltage is approximately 0V but the sink current limited by the collector resistance 10K ohm. As the Logic HIGH input current for TTL is approximately 0.4 mA, which is the transistors emitter current and would generate a voltage drop of approximately 4V across 10K ohm resistor. But the problem is the 10K ohm resistor cannot provide the required sink current 0.4 mA when the output Y is at Logic ZERO. Thus this XOR configuration seems to be suitable only for CMOS or TTL inputs at A and B and capable of driving only CMOS at output Y. +VCC Inputs R1 R2 A Q B DA DB TR1 Output 0V Fig. 4.17: EX-OR Gate using Diode and Transistor 4.5 Universal Properties of NAND and NOR Gate 1. NAND Gate as Universal Gate The below diagram is of a two input NAND gate. The first part is an AND gate and second part is a dot after it represents a NOT gate. So it is clear that during the operation of NAND gate, the inputs are first going through AND gate and after that, the output gets reversed, and we get the final output. (A) NOT Gate using NAND Gate Input = A = B = A Output Y = A.B = A.A (A = B = A) Y= A CU IDOL SELF LEARNING MATERIAL (SLM)

68 Digital Circuits and Logic Designs A A' A A' Fig. 4.18: NOT Gate using NAND Gate This is the circuit diagram of a NAND gate used to make work like a NOT gate. (B) OR Gate using NAND Gate: Y = A + B (OR gate) Y = A  B (Double inversion) OR Y = A  B (De Morgan’s law) Fig. 4.19: OR Gate using NAND Gate The above diagram is of an OR gate made from combinations of NAND gates, arranged in a proper manner. The truth table of an OR gate is also given beside the diagram. (C) AND Gate using NAND Gate: X Y = A.B (AND gate) X.Y Y = A.B Y The above diagram is of an AND Fig. 4.20: AND Gate using NAND Gate gate made from NAND gate. (D) NOR Gate using NAND Gate: Y = A  B (NOR gate) INPUT A Y = A.B (De Morgan’s theorem) Y = A.B (Double inversion) OUTPUT INPUT B Fig. 4.21: NOR Gate using NAND Gate CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 A 69 B (E) EX-OR Gate using NAND Gate: Q Y = AB  AB Y = AB  AB (Double inversion) Let X = AB and Z = AB Y= XZ Fig. 4.22: EX-OR Gate using NAND Gate Using De Morgan’s theorem X  Z = X.Z Y = X.Z = (AB).(AB) The above diagram is of an EX-OR gate made from NAND gate. (F) EX-NOR Gate using NAND Gate: Y = AB + AB = X + Z A Y = X  Z = X.Z Q Q = (A.(AB)’)’.(B. (AB)’)  Y = AB (AB) B Fig. 4.23: EX-NOR Gate using NAND Gate The above diagram is of an EX-NOR gate made from NAND gate. II . NOR Gate as Universal Gate: We have seen how NAND gate can be used to make all the three basic gates by using that alone. Now, we will discuss the same in case of NOR gate. (A) NOT Gate using NOR Gate: AA Y=A+B Fig. 4.24: NOT Gate using NOR Gate Y= AB A = B= A CU IDOL SELF LEARNING MATERIAL (SLM)

70 Digital Circuits and Logic Designs So, output of NOR is given by, Y= AB = AA But A + A = A Y= A The above diagram is of an NOT gate made from NOR gate. (B) OR Gate using NOR gate: R X Y=A+B A B Y= AB Fig. 4.25: OR Gate using NOR Gate The above diagram is of an OR gate made from NOR gate. (C) AND gate using NOR gate: a Y=A.B Y = A.B a AND b Y= AB b Fig. 4.26: AND Gate using NOR Gate The above diagram is of an AND gate made from NOR gate. CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 A 71 B (D) NAND gate using NOR gates : Q Y = A.B Y = A  B (using De Morgan’s theorem) Y= AB Fig. 4.27: NAND Gate using NOR Gates The above diagram is of an NAND gate made from NOR gate. (E) EX-OR gate using NOR gate Y = AB  AB Let X = AB and Z = AB Y=X+Z Y= XZ (Double Inversion theorem) Y = X.Z (De Morgan’s law)  Y = AB .(AB)    But AB = A  B and AB = A  B (by De Morgan’s law) Y = A  B . A  B Y = A  B A  B Take double inversion of RHS, we get CU IDOL SELF LEARNING MATERIAL (SLM)

72 Digital Circuits and Logic Designs  Y =  A  B  A  B A B The adjoining diagram is of EX-OR gate made from NOR gate. Q Fig. 4.28: EX-OR Gate using NOR Gate (F) EX-NOR gate using NOR gate: Boolean expression for an EX-NOR gate is, Y = AB + AB = X + Z Take double inversion of A RHS to get, AB B AB + AB = A  B Y = AB  AB AB Y = AB AB A A B AB B Fig. 4.29: EX-NOR Gate using NOR Gate  Y = A  B  A  B (using De Morgan’s law) The above diagram is of EX-NOR gate made from NOR gate. Exercise : Q.1 Explain and gate. Solution: The AND gate is a digital logic gate with ‘n’ i/ps one o/p, which perform logical conjunction based on the combinations of its inputs.The output of this gate is true only when all the inputs are true. When one or more inputs of the AND gate’s i/ps are false, then only the output of the AND gate is false. The symbol and truth table of an AND gate with two inputs is shown below. CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 73 A A.B B Fig. 4.30 An AND gate can have two or more inputs, its output is true if all inputs are true. The output Q is true if input A AND input B are both true: Q = A AND B. Input A Input B Output Q 00 0 01 0 10 0 11 1 Q.2 Explain EX-NOR gate using diode and transistor. Solution: XNOR gate, it uses NPN A 6.8k Y transistor. When the voltage at A and B 10k terminals are at opposite logic state, a LOGIC voltage of higher voltage minus lower INPUTS voltage minus 1.2V (voltage drop between two diodes) forward bias the B Emitter-Base junction of the Transistor. Fig. 4.31 This turns ON the transistor and the Logic LOW voltage available at the collector of the transistor is approximately equal to 0.6+VL+VCE, where VL is the Logic LOW input and VCE is the Collector to Emitter voltage of the transistor. When the both inputs A and B are at the same Logic Levels, the Emitter to Base junction of the transistor cannot be forward biased, thus the transistor is in OFF state and the output Y is at supply voltage. CU IDOL SELF LEARNING MATERIAL (SLM)

74 Digital Circuits and Logic Designs Q.3 Explain NAND Gate using diode and transistor. Solution: This is a Diode- +5V Transistor Logic (DTL) NAND Gate circuit using a bipolar junction transistor. A basic circuit using any R1 R2 Q1 Z general-purpose bipolar transistor D1 such as the BC549, BC548, or BC547, X could be used to construct the gate. D2 The diodes could be any general- Y purpose 1N4148 type. Fig. 4.32 In this configuration, the emitter-collector junctions of the bipolar transistor are in parallel across the diode. When the transistor conducts, the current flows through the transistor bypassing the diode, hence the LED switches OFF. This is a slightly complicated circuit, but not impossible to understand. As a beginner, you may be thinking that logic 0 is the same as no signal at the input. However, that is incorrect; logic 0 is equivalent to zero (ground) potential. The 10 kΩ resistor keeps the transistor in a conducting mode, however, if any one of the inputs is zero (ground), the current flow will be through the 10 kΩ resistor, through the diode, and to ground. The base current therefore shorts to ground through the diode. When this happens, the transistor stops conducting, hence the LED comes ON. Q.4.Explain NOT Gate using transistor and diode . Solution: The NOT gate can be easily understood by using a LED (light emitted Diode) circuit. This is also called Light switch circuit. In this circuit, NOT gate functions like an electronic switch. When it got high input, the LED connected at the output will be OFF, as the output of NOT gate becomes 0. CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 75 +5V Z R2 Q1 X R1 Fig. 4.33 4.6 Summary An AND gate produces a 1 output when all of its inputs are 1s. An AND gate performs the basic operation of multiplication. An OR gate produces a 1 output if any of its inputs are 1s. An OR gate performs the basic operation of addition. A NOT gate performs the function called inversion or complementation. A NOT gate converts the input state to an opposite output state. A NAND gate is a combination of an AND gate and an inverter. A NAND gate produces 1 output when any of the inputs are 0s. A NOR gate is a combination of an OR gate and an inverter. A NOR gate produces a 1 output only when both inputs are 0s. Boolean functions may be practically implemented by using electronic gates. The following points are important to understand. Electronic gates require a power supply. Gate INPUTS are driven by voltages having two nominal values, e.g., 0V and 5V representing logic 0 and logic 1 respectively. The OUTPUT of a gate provides two nominal values of voltage only, e.g., 0V and 5V representing logic 0 and logic 1 respectively. In general, there is only one output to a logic gate except in some special cases. There is always a time delay between an input being applied and the output responding. CU IDOL SELF LEARNING MATERIAL (SLM)

76 Digital Circuits and Logic Designs 4.7 Key Words/Abbreviations  Diodes: A semiconductor device with two terminals, typically allowing the flow of current in one direction only.  Transistor: A transistor is a semiconductor device used to amplify or switch electronic signals and electrical power. It is composed of semiconductor material usually with at least three terminals for connection to an external circuit. 4.8 Learning Activity 1. Explain EX-NOR gate using diode and transistor. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Explain EX-OR Gate using diode and transistor. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 4.9 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions 1. Explain truth table of various gates. 2. Describe the working of logic gates. 3. Explain functioning universal gates. A. Multiple Choice/Objective Type Questions 1. How many two-input AND and OR gates are required to realize Y = CD + EF + G? (a) 2,2 (b) 2, 3 (c) 3, 3 (d) 3, 2 2. Which of following are known as universal gates? (a) AND & OR (b) NAND & NOR (c) XOR & OR (d) EX-NOR & XOR CU IDOL SELF LEARNING MATERIAL (SLM)

Logic Gates 2 77 3. A universal logic gate is one which can be used to generate any logic function. Which of the following is a universal logic gate? (a) OR (b) AND (c) NAND (d) XOR 4. The NOR gate output will be high if the two inputs are __________. (a) 11 (b) 01 (c) 10 (d) 00 5. How many two input AND gates and two input OR gates are required to realize Y = BD + CE + AB? (a) 3, 2 (b) 4, 2 (d) 2, 3 (c) 1, 1 Answers 1. (a), 2. (b), 3. (c), 4. (d), 5. (a) 4.10 References 1. https://www.google.com/search?sxsrf=ACYBGNQZL0aKVuojBxCm0cx8yy4UF0rlu Q%3A1576215568820&ei=ECTzXdDiMaPEz7sPrsCYgAE&q=transistor&oq=trans&gs _l=psy- ab.1.1.35i39l2j0i67l5j0i131l3.30975.34674..36579...1.1..0.168.726.0j5......0....1..gws- wiz.....10..0i71j35i362i39j0i131i67j0i273.ZQBBZNTIK58 2. https://electronicsarea.com/or-and-and-logic-gates-with-diodes/ 3. https://www.researchgate.net/publication/325663286_Lab_1_Basic_logic_Gates_ AND_OR_and_NOT_gates_Objectives 4. http://www.ee.ic.ac.uk/pcheung/teaching/DE1_EE/Lectures/Lecture%2011%20- %20Logic%20gates%20and%20Boolean%20(x1).pdf   CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 5 BOOLEAN ALGEBRA 1 Structure: 5.0 Learning Objectives 5.1 Introduction 5.2 Boolean Expressions 5.3 Logic Expressions 5.4 Rules and Laws of Boolean Algebra 5.5 Summary 5.6 Key Words/Abbreviations 5.7 Learning Activity 5.8 Unit End Questions (MCQ and Descriptive) 5.9 References 5.0 Learning Objectives After studying this unit, you will be able to:  Explain various Boolean operations  Explain laws of Boolean operations 5.1 Introduction Mathematician George Boole invented the Boolean Algebra. This algebra deals with the rules by which logical operations are carried out. So, a digital circuit in this system is represented CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 1 79 as input and output symbols and the function of the circuit is expressed as a Boolean relationship between the symbols. Mathematician George Boole invented the Boolean Algebra. This algebra deals with the rules by which logical operations are carried out. So, a digital circuit in this system is represented as input and output symbols and the function of the circuit is expressed as a Boolean relationship between the symbols. 5.2 Boolean Expressions The rules for manipulation of binary numbers developed English mathematician George Boolea are known as Boolean Algebra. This forms the basic of all digital systems like computer, calculator etc. A Boolean variable has two values 1 and 0’s (high or low, true or false). The basic Boolean operation are AND,OR,NOT. The symbols used in logical algebra (usually) letters, do not represent numerical values. Arithmetic operations are not performed in logical algebra. In Boolean Algebra there are no fractions, decimals, negative numbers are root,cube root, logarithms, imaginary numbers and so on. Third and very important point is logical algebra allows only two possible values ‘1’ and 0’s for any variables. Thus logical algebra is ideally suited for the system based on the two opposite values such as ON and OFF.  Boolean equation It is a mathematical equation representing particular gate for input and output. 5.3 Logic Expressions AY (a) Not gate Fig. 5.1: Not Gate If A is true then Y is false and if A is false then Y is true. Boolean Equation Y = A CU IDOL SELF LEARNING MATERIAL (SLM)

80 Digital Circuits and Logic Designs (b) OR Gate It is also known as “Inclusive - OR” gate. Consider A and B are inputs and Y is output. This gate is called any or all gate. Logic - If A is true or B is true then Y is true. It means that either A should be high or B should be high or the output is high. Boolean Equation Y = A + B Logic Diagram - A Y B Fig. 5.2: OR Gate (c) AND gate A It has two or more input signals but only one output. All Y inputs must be high to get a high output. Consider A and B are B inputs and Y is output. Y = A.B Logic - If A is true and B is true then Y is true. Fig. 5.3: AND Gate Boolean Equation Y = A B (d) NAND Gate A Bubble indicate inversion and Bar on the equation Y=A.B indicates the inversion. The NAND gate has two or more B inputs but only one output. All the inputs must be set to high to get a low output. If any input is low output is high. Fig. 5.4: NAND Gate CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 1 81 5.4 Rules and Laws of Boolean Algebra  Boolean Laws A×1=A A× A =0 (a) AND Laws A×0=0 A×A=A (b) OR Laws A+A=A A+1=A A+ A =0 (c) Commutative Laws A+B=B+A A×B=B.A (d) Associative Laws A + (B + C) = (A + B) + C A × (B × C) = (A × B) . C (e) Extra Laws A × (A + B) = A A+A×B+A A × ( A + B) = A × B A+ A ×B=A+B A =A A +A×B= A +B A +A× B=A+ B CU IDOL SELF LEARNING MATERIAL (SLM)

82 Digital Circuits and Logic Designs Examples Q.1. Prove the following equations using perfect induction method (truth table) 1. A  A  B  A B Solution: A BA AB A  A  B A B 0 01 1 0 0 0 11 1 0 0 1 00 0 0 0 1 10 1 1 1 From column 5th and 6th, we can say that 2. A  B  A  B  A  B C  A  B  C  A  B  B  C Solution: LHS A B C A B A B A B A B  C A  B  A  B  A B C 0001 1 0 1 0 1 1 0011 1 0 1 0 0 1 0101 0 0 0 0 0 0 0111 0 0 0 1 1 1 1000 1 0 0 0 1010 1 0 0 0 1100 0 1 0 0 1110 0 1 0 0 RHS A B C A B C A B  C A B B C A  B  C  A  B  B  C 0 00 1 1 1 0 10 1 0 01 1 1 0 0 10 1 0 10 1 0 1 0 00 0 CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 1 83 0 11 1 0 0 0 01 1 1 00 0 1 1 0 00 0 1 01 0 1 0 0 00 0 1 10 0 0 1 1 00 1 1 11 0 0 0 0 01 1 Therefore, LHS = RHS Q.3. Prove the following equations using Boolean Laws 1. A  B  C  A  B  D  A  B  C  D Solution: LHS = A  B  C  A  B  D = A B  A B  A B D  C A B  C D {Simplifying the equations} = A B  A B  D  C A B  C D {Since A  B  A  B  A  B } = A  B  1  D  C  C  D {Taking A  B common from 1st three terms} = A  B  1   C  D {Since A+1 = A, (1 + D + C = 1} = A B  C D  A 1  A,  A B 1  A B = RHS 2. ( A  A  B)  (C  D )  A  B  C  D Solution: LHS = (A A  B) (C  D) = (A A  B)  ( C  D ) {Using De Morgan’s theorem (A  B  A  B ) } = [A  (A  B) ]  (C  D)] {Using De Morgan’s theorem ( A  B  A  B) } = [A  ( A B)]  ( C  D )] {Using De Morgan’s theorem ( A  B  A  B) } CU IDOL SELF LEARNING MATERIAL (SLM)

84 Digital Circuits and Logic Designs = [A  (A B)]  ( C  D)] { A  A } = AA  A B C D { A  A  0 } = A B C D 4. Derive the Boolean expression from given circuit. Q 1. Write Boolean expression for the given circuit. A B C Fig. 5.5 Solution: Write the sub-expression at the output of first 3 gates. Starting from top first gate is AND gate with input A and B hence its Boolean expression is AB. Second gate is OR gate with input B and C, hence its Boolean expression in B + C. Similarly, the output of third gate is BC A AB Q B B+C C BC Fig. 5.6 Then write Boolean expression for next level gate. The next level gate is AND Gate with inputs B+C and BC. Thus, its output will be BC (B+C). CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 1 85 A AB Q B B+C C BC (B+C) BC Fig. 5.7 Write Boolean expression for the final gate. The final gate is an OR gate with inputs AB and BC(B+C). Therefore the Boolean equation of the circuit is Q = AB + BC (B+C) A AB Q = AB + BC(B + C) B B+C C BC (B+ c) BC Fig. 5.8 5.5 Summary In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. It is thus a formalism for describing logical operations in the same way that elementary algebra describes numerical operations. The table used to represent the Boolean expression of a logic gate function called a truth table. A logic gate is an electronic circuit that operates on one or more input signals to produce an output signal. The switch contains two states which are ON or OFF. The ON means the logic 1 and the OFF means the logic 0. CU IDOL SELF LEARNING MATERIAL (SLM)

86 Digital Circuits and Logic Designs 5.6 Key Words/Abbreviations  Boolean Expression: Boolean expression is used in a programming language that produces a Boolean value when evaluated. 5.7 Learning Activity 1. Prove the following equations using perfect induction method (truth table). 1. A  A  B  A B 2. A  B  C  A  B  D  A  B  C  D ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Derive the Boolean expression from given circuit. (i) Write Boolean expression for the given circuit A BQ C Fig. 5.9 ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 5.8 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Explain various Boolean operations. 2. Explain laws of Boolean operations. CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 1 87 B. Multiple Choice/Objective Type Questions   1. The expression for Absorption law is given by _________ . (a) A + AB = A (b) A + AB = B (c) AB + AA’ = A (d) A + B = B + A 2. (A + B)(A’ * B’) = (a) 1 (b) 0 (c) AB (d) AB’ 3. The Boolean function A + BC is a reduced form of ____________ . (a) AB + BC (b) A’B + AB’C (c) (A + B)(A + C) (d) (A + C)B 4. In Boolean algebra, the OR operation is performed by which properties? (a) Associative properties (b) Commutative properties (c) Distributive properties (d) All of the mentioned 5. Simplify Y = AB’ + (A’ + B)C. (a) AB’ + C (b) AB + AC (c) A’B + AC’ Answers 1. (a), 2. (b), 3. (c), 4. (d), 5. (a) 5.9 References 1. https://www.electronics-tutorials.ws/boolean/bool_6.html 2. http://mathworld.wolfram.com/BooleanAlgebra.html 3. http://www.ee.surrey.ac.uk/Projects/Labview/boolalgebra/ 4. https://en.wikipedia.org/wiki/Boolean_algebra CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 6 BOOLEAN ALGEBRA 2 Structure: 6.0 Learning Objectives 6.1 Introduction 6.2 De Morgan’s Theorem 6.3 Simplification of Boolean Expression using Boolean Algebra Technique 6.4 Summary 6.5 Key Words/Abbreviations 6.6 Learning Activity 6.7 Unit End Questions (MCQ and Descriptive) 6.8 References 6.0 Learning Objectives After studying this unit, you will be able to:  Explain simplification concepts of Boolean expression.  Describe various Boolean techniques 6.1 Introduction The complement of the product of two or more variables is equal to the sum of the complements of the variables. As all possible combinations of A and B are exhausted, the theorem is proved. With De Morgan’s law and truth tables, we will be able to simplify logical expressions and models, find possibilities and even bugs. These processes help us organize, CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 2 89 simplify and almost even visualize how things will work. Truth tables are also useful in designing logic circuits and logic gates. De Morgan’s Theorems are basically two sets of rules or laws developed from the Boolean expressions for AND, OR and NOT using two input variables, A and B. These two rules or theorems allow the input variables to be negated and converted from one form of a Boolean function into an opposite form. De Morgan’s first theorem states that two (or more) variables NOR together is the same as the two variables inverted (Complement) AND, while the second theorem states that two (or more) variables NAND together is the same as the two terms inverted (Complement) OR. That is replace all the OR operators with AND operators, or all the AND operators with an OR operators. 6.2 De Morgan’s Theorem (a) State and Prove De Morgan’s Theorem This theorem is named behind the discoverer Bas Augustus De Morgan. The use of these theorems enables us to realize OR operation by using AND-NAND family gates or vice versa. De Morgan’s 1st Theorem De Morgan’s 1st theorem states that “The complement of a sum is equal to the product of the complement”. A+B = A.B Proof: By Perfect Induction Method or by Truth Table Table 6.1: De Morgan’s 1st Theorem LHS RHS A B A+B A+B A B A.B 1 00 0 1 11 0 0 01 1 0 10 0 10 1 0 01 11 1 0 00 Therefore, LHS = RHS. Hence, the theorem is proved two truth table are identical. CU IDOL SELF LEARNING MATERIAL (SLM)

90 Digital Circuits and Logic Designs Fig. 6.1: Logical Implementation of De Morgan’s Theorem1 De Morgan’s 2nd Theorem The second product is equal to the sum Table 6.2: De Morgan’s 2nd Theorem LHS RHS A B A.B A.B A B A+B 00 0 1 11 1 01 0 1 10 1 10 0 1 01 1 11 1 0 00 0 Therefore, LHS = RHS. Since two truth table are identical hence De Morgan’s 2nd theorem is proved. LHS = A.B RHS = A+B LHS = RHS Fig. 6.2: NAND Gate = Bubbled OR Gate CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 2 91 NOR Gate = Bubbled AND Gate (b) Duality Theorem The duality theorem is one of those elegant theorems proved in advanced mathematics. Duality theorems says, starting with a Boolean relation, one can derive another Boolean relation by (a) Change each OR sign to AND sign. (b) Change each AND sign to OR sign. (c) Complementing any 0 to 1 appearing in the expression. A + 0 = A A.1 = A This dual property is obtained by changing the OR sign to an AND sign and by complementing the 0 to get 1. E.g. A(B+C) = AB+AC By changing each OR and AND operation we get the dual relation AB+AC = (A+B)(A+C) By changing each AND and OR operation we get the dual relation A+BC = (A+B)(A+C) Same can be proved using truth table method. List all the standard Standard Theorems Table 6.3: Standard Theorems Boolean Theorems 1. A+0=A 2. A.1=A 3. A+1=1 4. A.0=0 5. A+A=A 6. A.A=1 7. A+A=1 8. A.A=0 9. A.(B+C) = AB+AC 10. A+BC=(A+B)(A+C) 11. A+AB=A 12. A(A+B)=A 13. A+AB=(A+B) 14. A(A+B)=AB 15. AB+AB=A 16. (A+B)(A+B)=A CU IDOL SELF LEARNING MATERIAL (SLM)

92 Digital Circuits and Logic Designs 17. AB+AC =(A+C)(A+B) 18. (A+B)(A+C)=AC+AB 19. AB+AC+BC=AB+AC 20. (A+B)(A+C)(B+C)=(A+B)(A+C) 21. A.B.C . . .= A+B+C... 22. A+B+C+ . . . = A.B.C . . . (c) Commutative law The Commutative law states that the order in which an operation is performed on a pair of variables does not affect the result of operation. In Boolean operation order of variables in OR and AND is insignificant, i.e., Cumulative law allows the changes of position of and OR and AND variables. Thus (a) A+B = B+A (b) A.B = B.A Proof by perfect induction method. Table 6.4: Induction Method A B A+B B+A A B A.B B.A 00 0 0 000 0 01 1 1 010 0 10 1 1 100 0 11 1 1 111 1 Law (a) Proved Law (b)Proved Law can be proved by perfect induction method. (d) Associative law  Law 1 The associative law that one can group any two terms of sum,or any two of a product. In other words it allows grouping of variables, i.e., this states that ring of several variable the result is the same irrespective of the grouping of variables. Thus, A+(B+C) = (A+B)+C The above laws can be proved using induction method. CU IDOL SELF LEARNING MATERIAL (SLM)