3.5. Compressing Truth Tables and K-maps
The process of compressing truth tables.
Truth table compression is done by:
- Row compression(use OR function).
A B F2 F2 c
0 0 0 F2(0,B)=0
0 1 0
1 0 1 F2(1,B)=(^1 1 0) B
In the above table, we are applying Shannon’s Expansion Theorem
F '2=BF(. B= )0 +B..F(B= )1 =B1. +B0. =B which can be compressed to
A F2 c
0 0
(^1) B
2) In general, any truth table can be compressed by applying the Shannon’s Expansion
Theorem with respect to the least significant bit, as shown below:
A B C F3 F3 c
0 0 0 0 0
0 0 1 0
(^0 1 0 0) C
0 1 1 1
1 0 0 1 1
1 0 1 1
(^1 1 0 1) C
1 1 1 0
So we can compress it to
A B F3 c
0 0 0
(^0 1) C
1 0 1
(^1 1) C
Example
Compress function F(x,y,z) = Σ(1,3,6,7):
a) about z
b) about x
a) about x, y & z