1

Chapter two
Boolean Algebra and Logic Gates

2.1. Overview
De Morgan came close to capturing the connection between logic and
mathematics. But, it was Boole who put it all together. He invented a new
kind of algebra called Boolean algebra. Boole proved binary or two-
valued logic is valid for letters and symbols instead of words. The
advantages of Boolean algebra are simplicity, speed and accuracy.

2.2. The OR Gate

A gate is a logic circuit with one output and two or more inputs; an
output signal occurs only for certain combinations of input signals.

Figure 2-1 shows a two-inputs OR gate where A and B are the inputs
and Y is the output. There are only four possible cases to analyze:

5V
5V

(a) (b)
2

5V
5V 5V
5V 5V

(C) (D)

Figure 2-1: Possible cases of Diode OR gate

Case 1: A = 0 and B = 0. Therefore, Y = 0

Case 2: A = 0 and B = 1. Therefore, Y = 1. Figure 2-1 (b) shows the

circuit of this condition. The upper diode is off, the lower diode is on and
the output Y= 1 logic.

Case 3 A= 1 and B= 0. The upper diode is on, the lower diode is off and
Y= 1 logic.

Case 4: A= 1 and B= 1. Both sides are forward biased. Since, the voltage
are in parallel, the output voltage is ideally 5 V. Therefore, Y= 5 V as in
figure (2-1d).

Table 2-1 lists the input-output condition of an OR gate. The OR

gate has a 1 output when either A or B or both are 1.

Table 2-1: Truth table of OR gate

A B Y
0 0 0
0 1 1
1 0 1
1 1 1
3

Most digital circuits use diodes and transistors as switches to

change from one voltage level to another. In digital circuits low and high
voltages are often represented by 0 and 1 respectively. For in instance, in
the OR gate of figure 2-2, the input levels are either 2 or 10 V (low or
high). The operation of this circuit like that of figure 2-1.

Table 2-2: Truth table of OR gate in figure 2-2

A B Y
Y
2V 2V 2V
2V 10 V 10 V
10 V 2V 10 V
10 V 10 V 10 V
Figure 2-2: Diode logic OR gate

The OR gate can have any number of inputs. Figure 2-3 shows a
three-input OR gate. If A or B or C is high, Y will be high because the
diode associated with the high input will turn on. Letting 0 stands for low
and 1 for high, we get the truth table of 2-3. In general, no matter how
many inputs are there, the OR gate has a 1 output when any or all of the
inputs are 1.

The number of horizontal rows in a truth table equals 2 n where n is

the number of inputs. For a two-input gate, the truth table has 22 or 4
rows. A three-input gate will have a truth table of 2 3 OR 8 rows; while, a
four-input gate results in 24 or 16 rows and so on. To include all possible
entries, it helps to list the entries in a binary number progression.
4

Table 3-2: Truth table of three-input OR gate

A A B C Y
0 0 0 0
B
0 0 1 1
C Y 0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
Figure 2-3: three-input OR gate

We can also use transistors to make OR gates. Figure 2-4 depicts a

three-input OR gate where A, B and C are the inputs and Y is the output.

+ VCC

A B C

Figure 2-4: Transistor OR gate circuit

5

The circuit has three npn emitter followers in parallel. With all
input voltages in the low state, the output must be low because the
emitters follow the inputs. When any or all the inputs go high, the output
follows. Therefore, we have OR gate action. There are many other ways
to build OR gate by using various combinations of resistors, diodes and
transistors.

2.3. The AND Gate

The and gate is another kind of digital circuit, it has an output only
when all inputs are present. Consider the two-input AND gate of figure 2-
5. Again, use ideal diodes and restrict all voltages to either 0 or 5 V. there
are four cases to analyze:

Case 1: A= 0 and B= 0, then Y= 0

Case 2: A= 0 and B= 1, then Y= 0

Case 3: A= 1 and B= 0, then Y= 0

Case 4: A= 1 and B= 1, then Y= 1

Table 2-4: Truth table of AND gate

A B Y
Y 0 0 0
0 1 0
1 0 0
1 1 1

Figure 2-5: Diode AND gate circuit

6

As usual, we can summarize the circuit action by a truth table (2-

4). The AND gate has 1 output when A and B are 1, an output occurs
only when all inputs are present.

The AND gate can have more than two inputs. For instant, figure
2-6 shows a three-input AND gate.

Table 2-5: Truth table of three-input AND gate

10 V

A B C Y
0 0 0 0
Y 0 0 1 0
Y
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Figure 2-6: Three-input AND gate

If any input is at 0 V (grounded), the diode connected to that input

is forward biased or shorted; therefore, the output will be shorted to
ground. Therefore, Y= 0 when any input is 0. The only way to make Y=
10 V is to have all inputs simultaneously equal to 10 V. In this case, no
current flows through the R and the output voltage rises to the supply
voltage. If we let 0 stand for low voltage and 1 for high voltage, we get
the truth table as in table 2-5. In general, no matter how many input are
there, the AND gate has an output only when all output are present.

We can build AND gates with transistors instead of diodes. Figure

2-7 presents one way to make a three-input AND gate.
 7

+
A B C

11 V

Figure 2-5: Transistor OR gate

Here is how it works? Suppose the input voltages (A, B and C) are either
0 or 10 V. If any of the inputs 0 V (grounded), the base-emitter diode of
the associated transistor will be on (ideally, a short); therefore, the output
will be held approximately at ground, so that Y= 0. The only way to
make Y= 10 V is to rise all inputs to 10 V. Under this condition, none of
the base-emitter diode is on and the output is free to rise to 10 V. By
letting 0 stands for low voltage and 1 for high voltage, we can get a truth
table like table 2-5.

2.4. Positive and Negative Logic System

A positive logic system is a system in which a 1 represents the more

positive of the two voltage levels; in a negative system the 1 stands for
the more negative. For instance, suppose a digital system has voltage
levels of + 5V and 0V. we are free to choose the definition for a 0 and 1.
If we say a 1 stands for + 5V and 0 for 0V, the system becomes a positive
logic system. On the other hand, if we let 1 denotes 0 V and let 0
8

symbolize + 5V, we have a negative logic system. The distinction

between positive and negative logic is important because an OR gate in a
positive logic system becomes an AND gate in a negative logic system.
To understand why, consider the circuit of figure 2-8. Inputs are either +
5V or 0V. The truth table for this circuit (2-6) gives actual levels.

Figure 2-8: Diode logic gate

Table 2-6 Table 2-7 Table 2-8

A B Y A B Y A B Y
0V 0V 0V 0 0 0 1 1 1
0V 5V 5V 0 1 1 1 0 0
5V 0V 5V 1 0 1 0 1 0
5V 5V 5V 1 1 1 0 0 0

The output is 5V when either A or B is 5V. Is this gate an OR gate or

an AND gate? The answer depends on how we define 0 and 1. If 1 stands
for + 5V and a 0 for 0V, we have a positive logic system and can show
the truth table as in table 2-7. This truth table of an OR gate because there
is a 1 when A or B is 1. On the other hand, if a 1 stands for 0V and a 0 for
+ 5V, we have a negative logic system. By looking at table 2-6 and
writing 1 for each 0-entry and a 0 for each 5V entry, we get the truth table
9

of table 2-8. By inspection of this table, a 1 output occurs only when A

and B are 1; therefore, the circuit is an AND gate in a negative logic
system.

A digital system can be either a positive or a negative logic system; it

all depends on how we define 0 and 1. The choice of which system to use
is arbitrary-like defining the direction of current from + to – or from – to
+. For consistency, we shall use positive logic; 1 always will stand for the
more positive of the two voltage levels.

2.5. The NOT gate

Another of the basic digital gates is the NOT gate, also called a
"complementary" gate or an "inverter". This gate has one input and one
output. All it does is invert the input signal; if the input is high, the output
is low and vice versa.

Figure 2-9 shows one way to build a NOT gate. When the input
voltage is high enough, the transistor saturates; therefore, the output is
low. On the other hand, when the input voltage is low enough, the
transistor cuts off and the output voltage is high. The truth table of the
NOT gate is

Table 2-9: Truth table of NOT gate

+ Vcc

A Y
0 1
1 0

Figure 2-9: NOT gate circuit

11

We call this gate a NOT gate because the output is not the same as the
input.

2.6. OR addition

In Boolean algebra when we solve an equation, we get either a 0 or

1. No other answers are possible because the set of numbers includes
only the binary digits 0 and 1. Another difference about Boolean
algebra is the meaning of plus sign. In Boolean algebra, the + sign
symbolizes the action of an OR gate.

Figure 2-10: Two-input OR gate symbol

1- Y= A + B = 0 + 0 = 0
2- Y= A + B = 0 + 1 = 1
3- Y= A + B = 1 + 0 = 1
4- Y= A + B = 1+ 1 = 1

In decimal addition 1 + 1 = 2
In binary addition 1 + 1 = 10
In OR addition 1+1=1

2.7. AND Multiplication

In Boolean algebra, when we write

11

Y= A · B or Y= A B

we mean A and B are to be combined in the same way that an AND gate
combines A with B to give a Y output. For instance, let us solve Y=AB
for the four possible cases

1- A = 0, B = 0 leads to Y= AB= 0 · 0 = 0
2- A = 0, B = 1 leads to Y= AB= 0 · 1 = 0
3- A = 1, B = 0 leads to Y= AB= 1 · 0 = 0
4- A = 1, B = 1 leads to Y= AB= 1 · 1 = 1
The results of AND multiplication are the same as for ordinary
multiplication.

Figure 2-11: Two-input AND gate symbol

Example 2-1

What is the Boolean expression for the output of the circuit shown
in figure 2-12

Figure 2-12
12

Solution:
Y=AB+B

Example 2-2

Evaluate the Boolean expression in the preceding example for

1- A = 0 and B = 1
2- A = 1 and B = 0
Solution
1- Y = A B + B = 0 · 1 + 1 = 0 + 1 = 1
2- Y = A B + B = 1 · 0 + 0 = 0 + 0 = 0

Example 2-3

Find the Boolean expression for the output in figure 2-13 and
evaluate the expression for A = 0 and B = 1.

Figure 2-13

Solution
Y = (A + B) B
Y = (0 + 1) 1 = 1
13

2.8. The NOT Operation

In Boolean algebra the expression

Y=A

Means you are to change A in the same way a NOT gate changes A. Read
the expression Y = A as Y equals NOT A. The bar over A means you
change or complement the quality to the alternative digit. In other words,
when A = 0

Y=A=0=1

When A = 1

Y=A=1=0

The NOT operation is also called "negation" or "inversion" and the

prime is sometimes used instead of a bar to signify the NOT operation.
That is

Y = A'

it can be used instead of Y = A

Figure 2-14 depicts the symbol for a NOT gate.

Figure 2-14: NOT gate symbol

 14

Let us summarize the OR, AND and NOT rules:

OR AND NOT

0+0=0 0·0=0 0' = 1

0+1=1 0·1=0 1' = 0

1+0=1 1·0=0

1+1=1 1·1=0

Example 2-4

Write the Boolean equation for the output of figure 2-15

Figure 2-15

Solution
'
Y=A+B

Example 2-5

Solve the Boolean equation of the preceding example for all possible
input conditions.
15

Solution

1- A = 0, B = 0
' '
Y=A+B =0+0 =0+1=1
2- A = 0, B = 1
' '
Y=A+B=0+1 =0+0=0
3- A = 1, B = 0
' '
Y=A+B=1+0 =1+1=1
4- A = 1, B = 1
' '
Y=A+B=1+1 =1+0=1

2.9. De Morgan's Theorem

De Morgan's important contributions to logic are these two theorems:

A+B=A·B ………….2-1

A·B =A+B ………….2-2

To prove equation 2-1, we need to show that the left side equals the
right side for all possible values of A and B. Here are the four possible
cases:

Case 1: A = 0 and B = 0
Left side: A + B = 0 + 0 = 0 = 1
Right side: A · B = 0 · 0 = 1·1= 1
Case 2: A = 0 and B = 1
Left side: A + B = 0 + 1 = 1 = 0
Right side: A · B = 0 · 1 = 1 · 0 = 0
Case 3: A = 1 and B = 0
Left side: A + B = 1 + 0 = 1 = 0
16

Right side: A · B = 1 · 0 = 0 · 1 = 0
Case 4: A = 1 and B = 1
Left side: A + B = 1 + 1 = 1 = 0
Right side A · B = 1 · 1 = 0 · 0 = 0

Since, no other combinations of A and B exists, we have proved De

Morgan's first theorem A + B = A · B. To summarize the proof, we can
show the truth table for each expression (tables 2-10 and 2-11).

Table 2-10 Table 2-11

A B A+B A B A·B
0 0 1 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 0 1 1 0

The circuit meaning of the first theorem important. A + B represents a

logic system in which a NOT circuit follows an OR gate (figure 2-16a).
Also, A · B describes a logic system in which the outputs of two NOT
circuits are used as the inputs to an AND gate (figure 2-16b). De
Morgan's theorem tell us these tow systems are interchangeable. In figure
2-17a, a NOT follows an OR gate; we call this particular combination a
NOT-OR or simply NOR gate.

a b

Figure 2-16: A NOR gate is equivalent to an inversion followed by an AND gate

17

Y=A+B

a b

Figure 2-17: Logic symbol for NAND gate

The second De Morgan's theorem is

A·B=A+B

The complement of a product equals the sum of the complements. This

theorem is easily proved. Tables 2-12 and 2-13 give the truth tables for
each expression. Note that the truth tables are identical.

Table 2-12 Table 2-13

A B A·B A B A+B
0 0 1 0 0 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 0

Therefore, the expressions are equivalent and the logic circuits

represented by A · B and A + B are interchangeable. Figure 2-18 shows
these circuits.
 18

a b

Figure 2-18: A NAND gate is equivalent to an inversion followed by an OR gate

In figure 2-19a, a NOT follows an AND gate; this particular

combination is called a NOT-AND gate or simply a NAND gate. The
NAND symbol is shown in figure 2-19b.

A A
AB AB
B B

a b

Figure 2-19: Logic symbol for NOR gate

B
C

a b

Figure 2-20: : A NAND gate is equivalent to an inversion followed by an OR gate

The output of figure 2-20a is A B C, whereas the output of figure

2-20b is A + B + C. To show the two circuits are interchangeable, we
must prove
19

By using the second De Morgan's theorem

ABC=AB·C=AB+C=A·B+C=A+B+C

2.10. The Universal Building Block

Given any Boolean expression, we can build a logic circuit for it.
Conversely, given a logic circuit, we can write a Boolean expression. As
an example, (A + B) C suggest a logic circuit in which A and B are first
ORed and then ANded with the complement of C. figure 2-21 depicts the
logic circuit.

= (A + B) C
C

Figure 2-21: producing a given Boolean expression

De Morgan's theorems are important and should be summarized. We

repeat them in words:

 The complement of a sum equals the product of the complements.

 The complement of a product equals the sum of the complements.

Example 2-6

Prove the following identity

A·B=A+B
21

Solution

Using De Morgan second theorem

A·B=A+B=A+B

Example 2-7

Prove the three-input NAND gate of figure 2-20a is interchangeable with

the logic circuit of figure 2-20b.

To build the logic circuit associated with any Boolean expression,

we can use OR gates for signs, AND gates for signs and NOT
circuits for overhead bars. In other words, OR, AND and NOT circuits
are the basic building blocks of all logic circuits.

The NAND gate has an interchanging property: it can be used to

build an OR gate or an AND gate or a NOT gate. Because of this, NAND
gates are all we need to build any logic circuit. Therefore, the NAND gate
is a universal building block (A similar statement can be made for the
NOR gate).

We can use NAND gates to make an AND gate. Figure 2-22 shows how

Figure 2-22: AND logic operation can be performed by using two NAND gates

We can also make an OR gate using NAND gates. Figure 2-23 depicts
how to connect NAND gates.
21

Figure 2-23: OR logic operation can be performed by using three NAND gates

This means we can build any logic circuit using only NAND gates (a
similar statement applies to the NOR gate).

2.11. Laws and theorems of Boolean Algebra

Here are some basic laws and theorems of Boolean algebra

A + B = B + A ………...(2-3)
Commutative Laws
A·B=B·A ………...(2-4)

A + (B + C) = (A + B) + C ……….(2-5) Associative Laws

A (B C) = (A B) C ………(2-6)

Distributive Law
A (B+C) = A B + A C ………(2-7)

These first five laws are identical to those of ordinary algebra.

The next group of laws is the backbone of Boolean algebra. First,

22

A + 0 = A …………….(2-8)

A · 0 = 0 …………….(2-9)

A + 0 = A should remind us of an OR gate, whereas

A · 0 = 0 suggests the AND gate. The remaining identities in the group

are

A + 1 =1 ………….(2-10)

A · 1 = A …………(2-11)

A + A = A ………..(2-12)

A · A = A ………...(2-13)

A + A = 1 ………...(2-14)

A · A = 0 ………...(2-15)

These formulas are very basic and should be summarized. The next three
formulas are already familiar: the double –complement theorem and De
Morgan's theorem.

A = A …………..(2-16)

A + B = A · B …………(2-17)

A · B = A + B …………(2-18)

Finally, there is a group of miscellaneous theorems, all of which can be

derived from the identities already listed. Some of these theorems are:

A + A B = A ……………………………..(2-19)

A (A + B) = A …………………………….(2-20)

(A + B) (A + C) = A + B C ……………….(2-21)

A + A B = A + B…………………………..(2-22)
23

A (A + B) = A B ……………………………(2-23)

(A + B) (A + C) = A C + A B ………………(2-24)

A B + A C = (A + C) (A + B) ………………(2-25)

One more point, positive and negative logic give rise to a basic duality in
all the identities. This means that, given any Boolean identity, we can
produce a dual identity by:

Changing sign to sign, and vice versa completing all 0s and 1s.

For instance, given equation (2-8),

A+0=A

Complement the sign and the 0 to get the dual identity,

Equation 2-11

A·1= A

As another example , equation 2-14 is

A+A=1

To get dual identity, complement the sign and 1 to get

A·A=0

Example 2-8

Prove the following

1- A + A = A
2- A · A = A
Solution
24

1- Prove this by substituting the possible values of A, which are 0 and

1.

When A = 0

A+A=A

0 + 0=0

0=0

When A = 1

A+A=A

1+ 1 = 1

1= 1

2- Prove A · A = A in the same way

2.12. TTL NAND gates

NAND gates are the least expensive circuits. Because of this, there are
the most widely TTL gates. Figure 2-24 depicts the schematic diagram
for a two-input NAND gate.

Figure 2-24: Two-input TTL NAND gate circuit

25

H.W

What does TTL stand for and what are the characteristics of TTL?