Chapter 3
SSK3207 – Chapter 7
*
Chapter 7
Boolean Algebra and Logic Gate
SSK3207 – Chapter 7
*
Topics
7.1) Basic Operations of Boolean Algebra
7.2) Relationship between basic operation
of Boolean and basic logic gate
7.3) Basic Theorems of Boolean Algebra
7.4) Relationship between Boolean
Function and Logic Circuit
SSK3207 – Chapter 7
*
7.5) Truth Table
7.6) Karnaugh Map
7.7) Example of Digital Problem
7.8) Create a Logic Circuit Using Only
NAND Gates or NOR Gates
SSK3207 – Chapter 7
*
7.1) Basic Operations of Boolean Algebra
Boolean Algebra was introduced by George Boole in the year 1854.
Like other algebras, it uses variables (called statements) and operations (called relations).
Variables in Boolean algebra is called logic variable that only has 2 possible values, either true (1) or false (0) whereas its operation is called logical operations.
SSK3207 – Chapter 7
*
There are 3 basic logical operations, i.e. AND (.), OR (+) and NOT ( ).
These operations are used to combine operands (logical constants and variables) to form logical expressions.
The following are a few logical expressions with X, Y and Z as the logical variables that can only have the value of FALSE (or 0) or TRUE (or 1).
X = NOT X
X.Y + Z = NOT( X AND Y) OR Z
SSK3207 – Chapter 7
*
Other than the basic logical operations of AND, OR and NOT, there are multiple of other logical operations, among them are NAND, NOR and XOR that are widely used in building logical circuits in computers.
These logical operations are combination of a few of the basic logical operations, e.g. :
NAND is a combination of AND followed by NOT
NOR is a combination of OR followed by NOT
SSK3207 – Chapter 7
*
The following is a truth table for the logical operations of AND, OR, NOT, NAND, NOR and XOR.
P
Q
NOT P
P AND Q
P OR Q
P XOR Q
P NAND Q
P NOR Q
0
0
1
0
0
0
1
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
0
1
1
0
1
1
0
0
0
SSK3207 – Chapter 7
*
Summary
1. AND (symbol: .)
The AND operation only gives the TRUE (or value 1 in binary) result if and only if the value of all the variables are TRUE
2. OR (symbol : +)
The OR operation only gives the TRUE result if the value of one or all of the variables is/are TRUE.
3. NOT (symbol : )
The NOT operation will change the value of the operand, i.e. TRUE to FALSE and vice-versa
SSK3207 – Chapter 7
*
4. NAND
The NAND operation only gives the TRUE result if one or both of the operands are FALSE
5. NOR
The NOR operation only gives the TRUE result if and only if both operands are FALSE
6. XOR
The XOR operation only gives the TRUE result if and only if only one of the operands is TRUE
SSK3207 – Chapter 7
*
7.2) Relationship Between Basic Operation of Boolean and Basic Logic Gate
The basic construction of a logical circuit is gates.
The logical functions are presented through the combination of gates.
Gate is an electronic circuit that emits an output signal as a result of a simple Boolean operation on its inputs.
The basic gates that used in a digital logic is the same as the basic Boolean Algebra operations such AND, OR, NOT, NAND and NOR.
SSK3207 – Chapter 7
*
Table below shows the symbols, Boolean algebra and the truth table for the gates
A B F
0 0 1
0 1 0
0 0
1 1 0
A B F
0 0 1
0 1 1
0 1
1 1 0
A B F
0 0 0
0 1 1
0 1
1 1 1
A B F
0 0 0
0 1 0
0 0
1 1 1
F
F
F
F
Name Graphic Symbol Boolean Algebra Truth Table
A
B
A
B
A
B
A
B
A
F
AND
OR
NOT
NAND
NOR
F = A . B
Or
F = AB
F = A + B
_____
F = A + B
____
F = A . B
Or
F = AB
_
F = A
B F
0 1
1 0
4. NAND
The NAND operation only gives the TRUE result if one or both of the operands are FALSE
5. NOR
The NOR operation only gives the TRUE result if and only if both operands are FALSE
6. XOR
The XOR operation only gives the TRUE result if and only if only one of the operands is TRUE
*
SSK3207 – Chapter 7
*
7.3) Basic Theorems of Boolean Algebra
1. Identity Elements 2. Inverse Elements
1 . A = A A . A = 0
0 + A = A A + A = 1
3. Idempotent Laws 4. Boundess Laws
A + A = A A + 1 = 1
A . A = A A . 0 = 0
5. Distributive Laws 6. Order Exchange Laws
A . (B + C) = A.B + A.C A . B = B . A
A + (B . C) = (A+B) . (A+C) A + B = B + A
SSK3207 – Chapter 7
*
7. Absorption Laws 8. Associative Laws
A + (A . B) = A A + (B + C) = (A + B) + C
A . (A + B) = A A . (B . C) = (A . B) . C
9. Elimination Laws 10. De Morgan Theorem
A + (A . B) = A + B (A + B) = A . B
A . (A + B) = A . B (A . B) = A + B
SSK3207 – Chapter 7
*
All the theorems and laws can be proven by substituting the value of 0 or 1 for each variables A, B and C based on the Truth Table for each logical operation given.
These theorems and laws are extremely important in the computer environment because it is used to simplify logical expressions that are produced when designing the logical circuit of the computer
SSK3207 – Chapter 7
*
7.5) Relationship Between Boolean Function and Logic Circuit
Any Boolean function can be implemented in electronic form as a network of gates called logic circuit.
The following are examples of Boolean functions and their logic circuit.
SSK3207 – Chapter 7
*
1) F = A . B + C + D
A
B
C
D
F
A . B
C + D
SSK3207 – Chapter 7
*
2) G = A . (B + C + D)
A
B
C
D
G
SSK3207 – Chapter 7
*
7.5) Truth Table
A truth table displays the relationship between the truth values of propositions.
Eg: Construct a truth table for a Boolean function, X = A + B . C
SSK3207 – Chapter 7
*
A B C A+B A+B A+B . C
0 0 0 0 1 0
0 0 1 0 1 1
0 1 0 1 0 0
0 1 1 1 0 0
1 0 0 1 0 0
1 0 1 1 0 0
1 1 0 1 0 0
1 1 1 1 0 0
SSK3207 – Chapter 7
*
Logically equivalent : X + Y = X . Y
Logical Equivalence:
Two logic expressions are called logically equivalent if and only if, they have identical values for each of the statement’s variables.
X
Y
X + Y
X + Y
X . Y
0
0
0
1
1
0
1
1
0
0
1
0
1
0
0
1
1
1
0
0
SSK3207 – Chapter 7
*
7.6) Karnaugh Map
A graphical way of depicting the content of a truth table where the adjacent squares differ by only one variable.
For the purposes simplification, the Karnaugh map is a convenient way of representing a Boolean function of a small number (up to four) of variables.
The map is an array of 2n squares, representing all possible combination of values of n binary variables.
Code Distance
Let’s first define the concept of Code Distance.
The distance between two binary code-words is the number of bit positions in which the two code-words have different values.
For example, the distance between the code words 1001 and 0001 is 1 while the distance between the code-words 0011 and 0100 is 3.
This definition of code distance is commonly known as the Hamming distance between two codes.
SSK3207 – Chapter 7
*
Calculation of Hamming Distance
In order to calculate the Hamming distance between two strings, and , we perform their XOR operation, (a⊕ b), and then count the total number of 1s in the resultant string.
*
Hamming distance Calculation
In order to calculate the Hamming distance between two strings, and , we perform their XOR operation, (a⊕ b), and then count the total number of 1s in the resultant string.
Example
Suppose there are two strings 1101 1001 and 1001 1101.
11011001 ⊕ 10011101 = 01000100. Since, this contains two 1s, the Hamming distance, d(11011001, 10011101) = 2 (variable).
SSK3207 – Chapter 7
*
SSK3207 – Chapter 7
*
Example: Karnaugh Map with 2 variables, A and B
00
01
10
11
A
B
0
0
1
1
_ _
A B
_
A B
_
A B
A B
B
_
B
B
_
A
A
A
SSK3207 – Chapter 7
*
B
A
0 1
0
1
TRUTH TABLE
input
output
Relationship between Truth Table and Karnaugh Map
KARNAUGH MAP
A B F
0 0
0 1
1 0
1 1
00 01
10 11
SSK3207 – Chapter 7
*
The number of squares in Karnaugh map depends on the number of variables:
if n variables, there are 2n squares in the
Karnaugh Map
Example : i) 2 Variables
2² = 4 squares in the Karnaugh Map
ii) 3 Variables
2³ = 8 squares in the Karnaugh Map
SSK3207 – Chapter 7
*
The arrangement of squares in the Karnaugh map is free as long as the adjacent squares that are next to each other only differ by one variable.
BC
BC
000
001
011
010
100
101
111
110
000
001
010
011
100
101
110
111
A
_ _
B C
_
B C
B C
_
B C
_
A
A
00 01 10 11
0
1
A
Cannot!
SSK3207 – Chapter 7
*
Example:
a) 3 variables
_
C
C
001
001
010
011
110
111
100
101
_ _
A B
_
A B
A B
_
A B
AB
C
_
C
C
000 010 110 100
001 011 111 101
C
_ _ _ _
A B A B A B A B
AB
SSK3207 – Chapter 7
*
or others as long as the value of adjacent squares differ by only 1 variable.
b) 4 variables
0000 0001 0011 0010
0100 0101 0111 0110
1100 1101 1111 1110
1000 1001 1011 1010
00
01
11
10
00 01 11 10
AB
CD
SSK3207 – Chapter 7
*
Getting an expression from a Karnaugh map
Example : Given the following Truth Table with 3 inputs (A, B and C) and 1 output (F).
F
1
0
1
1
1
Only 4 combinations of input that give output, F = 1
A
B
C
0
0
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
0
1
1
1
0
0
1
1
1
0
*
SSK3207 – Chapter 7
*
Step 1:
Make a Karnaugh Map with 3 variables.
Step 2:
For each output F = 1, write 1 in the square that has the same combination of input as in the truth table.
1
1
1
1
00
1
1
0
0
00
01
01
11
11
10
10
BC
BC
A
A
SSK3207 – Chapter 7
*
Step 3:
group the adjacent squares with the following steps :
i) If a Karnaugh map has n variables, begin grouping with 2 n-1
ii) If there are no 2 n-1 adjacent squares (which the value is 1), proceed with 2 n-2 squares until 2 n-n
OR until no squares which the value is 1 are not grouped
2n-1 = 23-1 = 22 = 4
2n-2 = 23-2 = 21 = 2 For n = 3
2n-3 = 23-3 = 20 = 1
SSK3207 – Chapter 7
*
1
A
BC
only insert output which value is equal to 1 to the appropriate squares
A B C
00 01 11 10
0
1
1
1
1
B C A B
1
2
3
Answer : F = B C + A B + A B C
How to turn k-map into function
For 1, The Output is one, but the value for B and C is 0 therefore we write not B and not C
For 2, The Output is 1, A is 1 , therefore no changes to A Both B (00 & 01) has value 0 , therefore we write A and not B
For 2, The Output is 1, however A is 0, therefore we write not A and Both B &C have value 1
*
SSK3207 – Chapter 7
*
Explaination:
ð begin grouping with 23-1 = 4 adjacent squares. (none in the above Karnaugh map)
ð proceed with 23-2 = 2 adjacent squares (there are 2 in the above Karnaugh map)
ð if there are still squares with value 1 that are not grouped yet, proceed with 2 3-3 = 1 square (there is one in the above Karnaugh map)
ð get the expression from each group of squares.
A
BC
3 variables => n = 3
00 01 11 10
0
1
1
1
1
1
SSK3207 – Chapter 7
*
SUMMARY (3 variables) n = 3
_
C
_
B B
C
_ _ _ _
B C B C B C B C
_
A
A
A
BC
_
A
A
1) 4 adjacent squares
SSK3207 – Chapter 7
*
_ _ _ _
B C B C B C B C
_
A
A
_
A C
(2) 2 adjacent squares
A C
_ _
A B
_
A B
_
A B
A B
A
BC
SSK3207 – Chapter 7
*
A
BC
A
BC
1
1
1 1
1
0
1
00 01 11 10
1
1 1 1 1
00 01 11 10
0
1
_
C
AB
_
F = C + AB
A
_
B C
_
F = A + B C
Other examples
1
2
For 1, we group 4 adjacent squares , BC (00 & 10)- for C , both are 0. But the output is 1, therefore we write not C
For 2, BC (11 & 10) ..A is 1 and same as the output , we take B from (11 & 10) coz both have the same value, and is the same as the output, therefore it remain unchanged, we write AB
*
SSK3207 – Chapter 7
*
_ _ _ _ _ _
F = C D + B D + AB C
_
F = B + C
1
1
1
1
1
1
1
_ _ _ _
CD CD CD CD
CD
AB
_ _
AB
_
AB
AB
_
AB
00 01 11 10
0
1
BC
A
1
1
1
1
1
1
_
C
B
1
2
3
1
2
*
SSK3207 – Chapter 7
*
7.7) Example of Digital Problem
ð To design a logic circuit of an Alarm System at the office (with one door and one window) that will be rang if the door or window is/are opened after working hours.
ð The followings are steps that are to be taken to design a logic circuit.
SSK3207 – Chapter 7
*
1. Problem Determination
Determine the problem that has to be solved
to design a logic circuit for an alarm system that will trigger the emergency bell if door or window is/are opened outside office hours.
2. Conceptualization
Obtain the relevant logical variables and make a
logical table and also a truth table. Obtain the
logical expression from the truth table
SSK3207 – Chapter 7
*
The related variables are :
Time T = 0 (work time) T = 1 (not work time)
Doors D = 0 (closed) D = 1 (opened)
Windows W = 0 (closed) W = 1 (opened)
Whether Bell B will ring (1) or will not ring (0) depends on all three logical variables (depending on the condition or problem given)
SSK3207 – Chapter 7
*
Logic Table
INPUT
OUTPUT
Time
Door
Window
Bell
Work
closed
closed
Doesn’t ring
Work
closed
opened
Doesn’t ring
Work
opened
closed
Doesn’t ring
Work
opened
opened
Doesn’t ring
Not Work
closed
closed
Doesn’t ring
Not Work
closed
opened
Will Ring
Not Work
opened
closed
Will Ring
Not Work
opened
opened
Will Ring
SSK3207 – Chapter 7
*
Truth Table
(based on logical table above)
INPUTS
OUTPUT
T
D
W
B
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
SSK3207 – Chapter 7
*
B is the output or the function that we have to find. The B function or expression can be obtained through many methods based on the truth table. One of the methods is by using a Karnaugh map.
Below is the Karnaugh Map for the Truth Table above
From the Karnaugh Map above,
B = TW + TD
1 1 1
00 01 11 10
0
1
WD
T
TD
TW
SSK3207 – Chapter 7
*
3. Solution or summary
The expression B above can be further summarized using theorem or the laws in Boolean algebra
B = TW + TD
= T(W + D) (from the Law of Distribution)
4. Execution
From the expression obtained, the following is the logic circuit for B.
SSK3207 – Chapter 7
*
D
W
T
(W + D)
T(W + D)
SSK3207 – Chapter 7
*
7.8) Building logical circuits using only NAND or only NOR gates
Most components in computers are built using only type of gate either the NAND or the NOR gates. This can further simplify the construction of such circuits (i.e. do not need to use various gates in a logic circuit)
To build a circuit that only uses NAND or NOR gates, firstly the expression for the circuit has to be changed into an expression that only has either the NAND or NOR operations only. To change it, the De Morgan and Involution theorems are used.
SSK3207 – Chapter 7
*
The Involution theorem is as follow:
Example:
Using the logic expression in section 6.7 , B = T(W + D), draw a logic circuit by using:
1. Only NAND gates
2. Only NOR gates
A = A
=
SSK3207 – Chapter 7
*
B = T.(W + D)
= T.(W + D) Involution Theorem
= T. (W . D) De Morgan theorem
= T. (W . D) Involution Theorem
1. Using only the NAND gate
To get an expression that only uses the NAND operations, eliminate the OR operation in the expression by using the Involution theorem and De Morgan theorem.
( W+D = W . D )
( W+D = W+D )
SSK3207 – Chapter 7
*
T
W
D
Hence, the logic circuit for B that use only the NAND gates can be drawn as follow:
SSK3207 – Chapter 7
*
2. Using only the NOR gate
To get an expression that only uses the NOR operations, eliminate the AND operation in the expression by using the Involution theorem and the De Morgan Theorem.
B = T.(W + D)
= T . (W + D) Involution Theorem
= T + (W + D) De Morgan theorem
( T.(W+D) = T.(W+D) )
SSK3207 – Chapter 7
*
The expression no longer has the AND operation and all the OR operation has the complement sign or NOT symbol (or the NOR operation). Hence, the logic circuit for B that only uses the NOR gates can be drawn as follow:
T
W
D