ch10.1.ppt boolean Algebra and Logic gates

Bolean Algebra and Logic gates

1. Chapter 10.1 and 10.2: Boolean Algebra
Based on Slides from
Discrete Mathematical Structures:
Theory and Applications

2. Discrete Mathematical Structures: Theory and Applications 2
Learning Objectives
Learn about Boolean expressions
Become aware of the basic properties of
Boolean algebra

3. Discrete Mathematical Structures: Theory and Applications 3
Two-Element Boolean Algebra
Let B = {0, 1}.

4. Discrete Mathematical Structures: Theory and Applications 4
Two-Element Boolean Algebra

5. Discrete Mathematical Structures: Theory and Applications 5

6. Discrete Mathematical Structures: Theory and Applications 6

7. Discrete Mathematical Structures: Theory and Applications 7

8. Discrete Mathematical Structures: Theory and Applications 8
Two-Element Boolean Algebra

9. Discrete Mathematical Structures: Theory and Applications 9
Two-Element Boolean Algebra

10. Discrete Mathematical Structures: Theory and Applications 10

11. Discrete Mathematical Structures: Theory and Applications 11

12. Discrete Mathematical Structures: Theory and Applications 12

13. Discrete Mathematical Structures: Theory and Applications 13

14. Discrete Mathematical Structures: Theory and Applications 14
Boolean Algebra

15. Discrete Mathematical Structures: Theory and Applications 15
Boolean Algebra

16. Discrete Mathematical Structures: Theory and Applications 16

17. Discrete Mathematical Structures: Theory and Applications 17
Find a minterm that equals 1 if
x
1 = x
3 = 0 and x
2 = x
4 = x
5 =1,
and equals 0 otherwise.
x’
1
x
2
x’
3
x
4
x
5

18. Discrete Mathematical Structures: Theory and Applications 18
Therefore, the set of operators {
.
, +, ‘} is
functionally complete.

19. Discrete Mathematical Structures: Theory and Applications 19
Sum of products expression
Example 3, p. 710
Find the sum of products expansion of
F(x,y,z) = (x + y) z’
Two approaches:
1)Use Boolean identifies
2)Use table of F values for all possible 1/0
assignments of variables x,y,z

20. Discrete Mathematical Structures: Theory and Applications 20
F(x,y,z) = (x + y) z’

21. Discrete Mathematical Structures: Theory and Applications 21
F(x,y,z) = (x + y) z’
F(x,y,z) = (x + y) z’= xyz’ + xy’z’ + x’yz’

22. Discrete Mathematical Structures: Theory and Applications 22

23. Discrete Mathematical Structures: Theory and Applications 23

24. Discrete Mathematical Structures: Theory and Applications 24
Functional Completeness
This means that the set of operators {
.
, +, '} is
functionally complete.
Summery:
A function f: B
n
 B, where B={0,1}, is a Boolean function.
For every Boolean function, there exists a Boolean expression
with the same truth values,
which can be expressed as Boolean sum of minterms.
Each minterm is a product of Boolean variables or their complements.
Thus, every Boolean function can be represented
with Boolean operators ·,+,'

25. Discrete Mathematical Structures: Theory and Applications 25
Functional Completeness
0100111 
The question is:
Can we find a smaller functionally complete set?
Yes, {
.
, '}, since x + y = (x'
.
y')'
Can we find a set with just one operator?
Yes, {NAND}, {NOR} are functionally complete:
NAND: 1|1 = 0 and 1|0 = 0|1 = 0|0 = 1
100
{NAND} is functionally complete, since {. , '} is so and
x' = x|x
xy = (x|y)|(x|y)
NOR: