Contents
- 1 What is Boolean Algebra and its Examples?
- 1.1 OR Gate
- 1.2 AND Gate
- 1.3 NOT Gate
- 1.4 NOR Gate
- 1.5 NAND Gate
- 1.6 From NAND gate to OR gate [Fig.]:
- 1.7 From NAND gate to AND gate [Fig.]:
- 1.8 From NAND gate to NOT gate [Fig.]:
- 1.9 Some Relations of Boolean Algebra
- 1.10 Some other useful theorems:
- 1.11 Three Laws of Boolean Algebra
- 1.12 Determination of Boolean Algebraic Relation and Design of Logic Circuit from Truth Table
Physics Topics can also be used to explain the behavior of complex systems, such as the stock market or the dynamics of traffic flow.
What is Boolean Algebra and its Examples?
A gate is a special kind of digital circuit which possesses one or more Input voltages but only one output voltage. OR, AND and NOT gates are three basic gates. Joining these gates in different ways we can construct different kinds of circuits. These circuits can perform arithmetic calculations and can conclude logical inferences like that performed by a human brain. This kind of mathematics was discovered by George Boole of England in 1854 AD. This form of mathematics is known as Boolean algebra.
Actual mathematical analysis of gates can be done with the help of Boolean algebra. Different gates can perform different algebraic processes and in this way they can arrive at logical inferences. Thus, these gates are called logic gates or logic circuits.
Boolean algebra: To appreciate the importance of binary logic, let us consider, for example,
- answer to a mathematical problem: is it ‘right’ or ‘wrong’?
- a physical statement: is it ‘true’ or ‘false’?
- a switch in a circuit: is it ‘on’ or ‘off’? .
- the voltage across a circuit element: is it ‘low’ or ‘high’?
- particle in a 2-level system: is it ‘up’ or ‘down’?
There are many situations in the physical world where only two such states are available. The method of explaining the truth by finding the answers of some two-valued questions related to a subject was first invented by Greek philosopher Aristotle. Then some mathematicians understood that it is possible to express the method of finding the truth by the logics step by step by an algebric method. Among them, the British mathematician Augustus De Morgan was notable, who found the interrelation between logic and mathematics. Then the rest of the work was completed by Bool. Almost loo years later, in 1938, the American applied mathematician first used this algebra in telephone switching circuit.
Naturally, the most convenient way to represent these two states is the use of two digits, usually 0 and 1. The logic about whether we shall use 0 or 1, is known as binary logic. The mathematical analysis of a sequence of such binary logical systems, is performed by Boolean algebra. The states of the input or output in a digital gate circuit is denoted by either 0 or 1. Moreover, a gate circuit can be used as an element of a sequence — the output of one gate can be fed as an input to the next gate. In short, a digital gate circuit is a binary logical system. Boolean algebra is, naturally, the best mathematical tool for the analysis of any circuit, however complicated, consisting of digital gates.
OR Gate
In an OR gate, there are two or more input voltages or signals and like any other gate there is one output voltage or signal. This gate is called OR gate because, If the first or the second or the third or …, i.e., if anyone of the input voltages is high, the output voltage will also be high. For example, if at least one of the input voltages of a two-input OR gate be high, its output voltage will also be high.
Working principle of OR gate: From the electrical analogy shown in Fig., it becomes clear how an OR gate works. In this circuit, two switches A and B are connected in parallel. Obviously,
- when both switches remain ‘off the bulb does not glow, i.e., the output becomes zero—no output is obtained.
- if one of the two switches, A or B, is ‘on’ but the other is ‘off: the bulb glows, i.e., a non-zero output is obtained.
- if both switches are ‘on: the bulb glows and hence an output is obtained.
So, this circuit works like an OR gate.
OR gate in electronic circuit: An actual electronic two input OR gate is shown in Fig. The simplified form of this circuit is shown in Fig. Two Input voltages are denoted by A, B and the output voltage is denoted by Y. Let the two possible states of the two input voltages be low (say, O V) and high (say, 5V). The resistance RL is permanently connected with the circuit. The gate may exist in anyone of the following four states:
Both A and B are low: In this case, the output voltage remains low. According to Fig., if both A and B are low, the two diodes remain in the non-conducting state. As a result, Y also remains low.
When A is low and B is high: In this case, the output voltage remains high. According to Fig., if A is low, the diode attached with A remains in the non-conducting state. But if B is high, the diode attached with B is forward biased and hence Y remains high.
When A is high and B is low: In this case, the output voltage remains high. According to Fig., if B is low, the diode connected with B remains in the non-conducting state. But if A is high, the diode connected with A is forward biased and hence Y remains high.
Both A and B are high: In this case, the output voltage remains high. According to Fig., if both A and B are high, the diodes connected with them are forward biased and hence Y remains high.
Truth table: A table can be prepared by taking the possible inputs and outputs of a gate. This table is called the truth table of that gate.
Truth table of a two-input OR gate is given here.
As one of the inputs or the output of a gate can remain only in the two states—low or high, this state can be easily expressed by binary digits. Expressing the lower state by 0 and the higher state by 1, the above truth table is prepared. By observing the truth table minutely, we understand that, if the state of anyone of the two inputs be 1, the output state becomes 1. So, the state of Y becomes 1, if the state of either A or B or both A and B is 1. In another way, we can regard an OR gate as an ‘any-or-all’ gate, i.e., output state will be 1. If the states of ‘any one or all’ inputs be 1.
Positive and negative logic: In case of digital signal, if lower and higher states are represented by 0 and 1 respectively, it is called positive logic. On the other hand, if lower and higher states are represented by 1 and 0 respectively, it is called negative logic. Naturally, both positive and negative logics cannot be used simultaneously.
Symbol: The symbol of an OR gate is shown in Fig. Digital circuits can be drawn using this symbol.
Booleon algebra related to OR gate: In Boolean algebra, ‘OR’ operation is denoted by the symbol ‘+ The Boolean algebraic equation related to OR gate, shown in Fig. is,
Y = A + B
This equation is read as:” Y equals A OR B’:
When A = 0 = B, then Y = 0 + 0 = 0.
When A = 0 and B = 1 then Y = 0 + 1 = 1.
When A = 1 and B = 0, then Y = 1 + 0 = 1.
When A = 1 = B, then Y = 1 + 1 = 1,
The equation 1 + 1 = 1 may appear to be absurd. But in Boolean algebra, the ‘+‘ sign does not indicate addition.
So, the equation 1 + 1 = 1 is read as “1 or 1 equals 1″
For an OR gate circuit containing three inputs, the truth table, symbol and Boolean algebraic equation are given below [Fig.]:
AND Gate
In an AND gate, there are two or more input voltages or signals and like any other gate there is one output voltage or signal. This gate is called AND gate because, if all the input voltages, i.e., the first and the second and the third and input voltages are high, only then will the output voltage be high. For example, if both the Input voltages of a two-input AND gate are high, then only its output voltage will be high.
Working principle of AND gate : From the electrical analogy shown in Fig., it becomes clear how an AND gate
works. In this circuit, two switches A and B are connected in series. Obviously,
- when both the switches remain ‘off: the bulb does not glow, i.e., output becomes zero — no output is obtained.
- if one of the two switches, A or B, is ‘on’ but the other is ‘off’ even then the bulb does not glow, i.e., output becomes zero — no output is obtained.
- only when both the switches are ‘on the bulb glows, i.e., output is obtained.
So, this circuit works like an AND gate.
AND gate in electronic circuit: An actual electronic two input AND gate is shown in Fig. 2.8. The simplified form of this circuit is shown in Fig. The two input voltages are
denoted by A, B and the output voltage by Y. Let the two possible states of the two input voltages be low (say, 0 V) and high (say, 5 V). The resistance RL and the battery VCC (=5 V) are permanently connected with the circuit. The gate may exist in anyone of the following four states:
Both A and B are low: In this case, the output voltage remains low. According to Fig., if both A and B are low, due to VCC, the two diodes are forward biased, i.e., two diodes are in the conducting state. As a result, the voltages of A, B and Y are the same, i.e., Y is also low.
If A is low and B is high: In this case, the output voltage is low. According to Fig., if B is high, the diode connected with B is reverse biased, i.e., this diode is in the non-conducting state. But if A is low, due to VCC, the diode connected with A is forward biased, i.e., this diode is in the conducting state. As a result, the voltages of A and Y are the same, i.e., Y is low.
If A is high and B is low: In this case, the output is low. The reason for this is similar to that described in 2 above.
Both A and B are high: In this case, the output is high. According to Fig., if both A and B are high, the two diodes are reverse biased, i.e., the diodes are in the non-conducting state. As a result, no current flows through RL and hence due to VCC, the output Y is high.
By comparing Fig. and Fig., we can see that an OR gate easily becomes an AND gate If we alter the ends of the diodes and apply a proper voltage (VCC) at one end of RL instead of earthing.
Truth table: Observing the truth table carefully, we understand that, if the states of both the inputs be 1, the state of the output will be 1. So, the state of Y will be 1 if states of both A and B are 1. In another way, we can regard an AND gate as an ‘all-or-none’ gate i.e., the output state will be 1 if the states of all Inputs be 1, otherwise output state will be 0.
Symbol: The symbol of an AND gate is shown in the Fig. Digital circuits can be drawn using this symbol.
Boolean algebra related to AND gate: In Boolean algebra, AND’ operation is denoted by the symbol ‘ᐧ’. The Boolean algebraic equation related to AND gate, shown in Fig. is,
Y = A ᐧB = AB
This equation is read as : ‘ Y equals A AND B ‘
When A = 0 = B, then Y = 0 ᐧ0 = 0
When A = 0 and B = 1, then Y = 0 ᐧ 1 = 0
When A = 1 and B = 0, then Y = 1 ᐧ 0 = 0
When A = 1 = B, then Y = 1 ᐧ 1 = 1.
A three-input AND gate circuit, its truth table, symbol and Boolean algebraic equation are given below [Fig.]:
Digital Signal: The waveforms of two digital signals A and B are shown in Fig. as example.
For OR gate-A + B = Y: In time intervals EF and GH, both signals A and B are in lower state i.e., 0. So, for these time intervals, output Y of OR gate will be 0. For all other intervals, A or B or both A and B are in higher state, i.e., 1 . Hence, output state Y will be 1. This output waveform is shown in Fig.
For AND gate—AB = Y: In this case, signals A and B are in higher state i.e., 1 for the time intervals CD, FG and IJ. So, for these time intervals, output Y of AND gate will be in higher state i.e., 1 . For all other intervals, A or B or both A and B are in lower state i.e., 0. Thus output Y will be in lower state i.e., 0. This output waveform is shown in Fig.
NOT Gate
In a NOT gate, there is one input and one output voltage or signal. This gate is called NOT gate because, the states of the output voltage and input voltage can never be the same. So, if the input voltage in a NOT gate is low, the output voltage will be high and vice versa. This gate is also known as inverter.
Working principle of NOT gate: From the electrical analogy shown in Fig., it becomes clear how a NOT gate works. In this circuit, a switch A and a bulb are connected in parallel. Clearly,
i) when the switch remains off, the bulb glows, i.e., an output is obtained.
ii) when the switch remains on, the bulb does not glow, i.e., output becomes zero — no output is obtained.
So, this circuit works like a NOT gate.
NOT gate in electronic circuit: An actual electronic NOT gate is shown in Fig. The simplified form of this gate is shown in Fig. Note that, diodes cannot form a NOT gate; at least one transistor is necessary.
Here, the input and the output voltages are denoted by A and Y respectively. Let the two possible states of the input and output voltages be low (say, 0 V) and high (say, 5 V), Two resistances RMB and RC and the battery VCC (= 5 V) are connected permanently with the circuit. The gate can exist in any of the two states given below:
A is low: In this case, the output voltage is high. According to, Fig., if A is low, the values of RB and RC are so chosen that the transistor is in the cut-off region, i.e., almost no current passes through the transistor. As a result, Y remains high due to VCC.
A is high: In this case, the output voltage is low. According to Fig., If A is high, due to RB and RC, the transistor is in the saturation region, i.e., maximum current flows through RC. As a result, the point P is in low state, i.e., Y is low.
Truth table:
Symbol: The symbol of a NOT gate is shown in Fig. Digital circuits can be drawn by using this symbol.
Boolean algebra related to NOT gate: In Boolean algebra, ‘NOT’ operation is denoted by giving a ‘—‘ sign above A. The Boolean algebraic equation related to NOT gate, shown in Fig. is,
Y = \(\bar{A}\)
This equation is read as: “Y equals NOT A”
When A = 0, then Y = \(\overline{0}\) = 1.
When A = 1, then Y = \(\overline{1}\) = 0.
NOT output of a digital input: According to Fig., for each lower state i.e., 0 of the input signal A (in time intervals DF and GH), the output Y remains in higher state i.e., 1. On the other hand, for higher state of A i.e., 1 (in time intervals CD, FG and HI), the output Y remains in lower state i.e., 0.
1. OR, AND and NOT gates are called basic logic gates because, any other logic gate is the combination of these three basic gates, in any manner.
2. A logic gate cannot be formed by using any one of the basic gates repeatedly. For example, combining a large number of OR gates, no AND gate or NOT gate can be constructed.
3. The NOR gate and the NAND gate, discussed in the next section have some special advantages. A logic gate of any kind can be constructed by a combination of any number of NOR gates or NAND gates only. Thus, NOR and NAND gates are called universal logic gates, although none of them are basic gates.
4. To construct different logic gates by using more than one basic gates, De Morgan’s theorem can be applied.
De Morgan’s theorem:
- \(\overline{A+B}\) = \(\bar{A} \cdot \bar{B}\).
- \(\overline{A \cdot B}\) = \(\bar{A}+\bar{B}\)
NOR Gate
Joining the input of a NOT gate with the output of an OR gate, a NOT-OR, i.e., a NOR gate is constructed [Fig.]. So, the voltage or signal that comes at the output of an OR gate, goes to the input of a NOT gate. NOT gate inverts this voltage and sends it to the output.
Truth table: In case of a NOR gate, only if the states of all of the inputs be 0, the output state becomes 1.
Symbol: Two symbols of a NOR gate are shown in Fig. Digital circuits can be drawn by using any one. The second symbol is more commonly used.
Boolean algebra related to NOR gate: The Boolean algebraic equation related to NOR gate, shown in Fig. is,
Y = \(\overline{A+B}\)
This equation is read as: “Y equals A NOR B
When A = 0 = B, then Y = \(\overline{0+0}\) = 1.
When A = 0 and B = 1 , then Y = \(\overline{0+1}\) = 0.
When A = 1 and B = 0, then Y = \(\overline{1+0}\) = 0.
When A = 1 and B = 1, then Y = \(\overline{1+1}\) = 0.
Design of basic gates using one or more NOR gates:
From NOR gate to OR gate [Fig.]:
From NOR gate to AND gate [Fig.]:
From NOR gate to NOT gate [Fig.]:
NAND Gate
Joining the input of a NOT gate with the output of an AND gate, a NOT-AND, i.e., a NAND gate is constructed [Fig.]. So, the voltage or signal that comes at the output of an AND gate, goes to the input of a NOT gate. NOT gate inverts this voltage and sends it to the output.
Truth table: In case of a NAND gate, if the state of any of the inputs be 0, the output state becomes 1.
Symbol: Two symbols of a NAND gate are shown in Fig. Digital circuits can be drawn using any one. The second symbol is more commonly used.
Boolean algebra related to NAND gate: The Boolean algebraic equation related to NAND gate, shown in Fig. is,
Y = \(\overline{A \cdot B}\)
This equation is read as: “ Y equals A NAND B”
When A = 0 = B, then Y = \(\overline{0.0}\) = 1.
When A = 0 and B = 1, then Y = \(\overline{0.1}\) = 1.
When A = 1 and B = 0, then Y = \(\overline{1.0}\) = 1.
When A = 1 and B = 1, then Y = \(\overline{1.1}\) = o.
Design of basic gates using one or moie NAND gates:
From NAND gate to OR gate [Fig.]:
From NAND gate to AND gate [Fig.]:
From NAND gate to NOT gate [Fig.]:
NOR and NAND outputs of two digital inputs: The waveforms of two digital signals A and B are shown in Fig. as an example.
For NOR gate—\(\overline{A+B}\) = Y: In time intervals EF and GH, both the signals A and B are in lower state i.e., 0. So, for these two time intervals, the output Y of NOR gate will be in higher state i.e., 1. For all other intervals, A or B or both A and B are in higher state i.e., 1. Hence, output state Y will be 0. This output waveform is shown in Fig.
For NAND gate—\(\overline{\boldsymbol{A} \cdot \boldsymbol{B}}\): Here, for the time intervals CD, FG and IJ, both the signals A and B are in higher state i.e., 1. So, for these intervals output Y of the NAND gate will be in lower state i.e., 0. On the other hand, for all other intervals, A or B or both A and B are in lower state i.e., 0. Hence output state Y will be 1. This output waveform is shown in Fig.
Some Relations of Boolean Algebra
Verification of the following relations of logic signal A, by putting A = 0 and A = 1 in each of these relations.
Some other useful theorems:
- A + AB = A
- A + \(\bar{A} B\) = A + B
- A(A + B) = A
- A(\(\bar{A}\) + B) = AB
Three Laws of Boolean Algebra
Commutative law: A+ B = B + A; AB = BA
Associative law: A + (B + C) = (A + B) + C;
A ᐧ (B ᐧ C) = (A ᐧ B) ᐧ C
Distributive law: A ᐧ (B + C) = A ᐧ B + A ᐧ C
Determination of Boolean Algebraic Relation and Design of Logic Circuit from Truth Table
To understand the process of determination of Boolean algebraic relation, first we shall discuss a truth table as an example is given below:
i) Here, we consider the rows in which Y = 1. So, second and third rows of the table are taken into consideration. First and fourth rows are ignored.
ii) In second row, for A = 1, write A and for B = 0, write \(\bar{B}\). Combined relation of these two will be A\(\bar{B}\). Again in third row, for A = 0, write \(\bar{A}\) and for B = 1, write B. Combined relation of these two will be \(\bar{A}\)B. As Y = 1 for A\(\bar{B}\) OR \(\bar{A}\)B, so, the Boolean algebraic relation will be Y = A\(\bar{B}\) + \(\bar{A}\)B.
The logic circuit associated with this Boolean relation is shown in Fig. Here, by using NOT gate, input A is converted to \(\bar{A}\). In the same way, input B is converted to \(\bar{B}\). Now, A and \(\bar{B}\) are applied as inputs to an AND gate. Similarly, \(\bar{A}\) and B are applied as inputs to another AND gate.
The outputs of these two AND gates are A\(\bar{B}\) and \(\bar{A}\)B respectively. These outputs are applied to an OR gate as Inputs. Then, the final output will be Y = A\(\bar{B}\) + \(\bar{A}\)B.
In practical field, this gate is known as Exclusive- OR gate or XOR gate. For example two way switching system in which two switches are used to control a bulb or a fan In a house.
In this system, a bulb or a fan is connected in such a way that if any one of these two switches is in ‘on’ state, the current will flow through the bulb or the fan. But if both of these two switches are in ‘on’ or ‘off’ state, then no current will flow i.e., the bulb or the fan will be in ‘off’ state. This type of circuit system is an XOR gate.
Example 1:
Truth table of AND gate: The given truth table shows that, Y = 1 in only the fourth row of the table. Hence the rest of the rows need not be taken into consideration. In the fourth row, for A = 1, write A and for B = 1 , write B. As A = 1 AND B = 1, so, final Boolean algebraic relation is Y = AB.
From above, it is clear that this is the well known Boolean algebraic relation of AND gate. Hence the corresponding logic circuit is an AND gate [Fig.].
Example 2:
Truth table of OR gate: The given truth table shows that Y = 0 in only first row of the table. Hence excluding the first row, we see that for second row, the relation is A\(\bar{B}\); for third row, the relation \(\bar{A}\)B; and the relation for fourth row is AB.
So, for Y = 1, the relation will be A\(\bar{B}\) OR \(\bar{A}\)B OR AB. Hence the Boolean algebraic relation for the given truth table is Y = A\(\bar{B}\) + \(\bar{A}\)B + AB. The corresponding logic circuit is shown below.
By simplifying the relation
Y = A\(\bar{B}\) + \(\bar{A}\)B + AB
= A\(\bar{B}\) + (\(\bar{A}\) + A)B = A\(\bar{B}\) + B [∵ \(\bar{A}\) + A = 1]
= A\(\bar{B}\) + (A + 1)B [∵ A + 1 = 1]
= A\(\bar{B}\) + AB + B = A(\(\bar{B}\) + B) + B
= A + B [∵ \(\bar{B}\) + B = 1]
This is the well known Boolean relation of OR gate. Hence the corresponding logic circuit is an OR gate [Fig.]. So, the circuit in Fig. is equivalent to a two-input OR gate.