New version page

# U of I CS 231 - Circuit analysis summary

Pages: 41
Documents in this Course

23 pages

24 pages

24 pages

14 pages

43 pages

9 pages

4 pages

23 pages

24 pages

4 pages

31 pages

28 pages

27 pages

31 pages

20 pages

22 pages

22 pages

4 pages

25 pages

34 pages

33 pages

21 pages

23 pages

25 pages

24 pages

24 pages

22 pages

23 pages

42 pages

33 pages

23 pages

26 pages

16 pages

21 pages

33 pages

26 pages

17 pages

27 pages

38 pages

14 pages

17 pages

4 pages

25 pages

37 pages

37 pages

3 pages

23 pages

25 pages

25 pages

50 pages

28 pages

17 pages

13 pages

21 pages

9 pages

40 pages

52 pages

16 pages

12 pages

26 pages

25 pages

31 pages

24 pages

3 pages

4 pages

30 pages

6 pages

34 pages

17 pages

21 pages

25 pages

33 pages

14 pages

25 pages

12 pages

36 pages

13 pages

25 pages

23 pages

8 pages

27 pages

22 pages

22 pages

24 pages

41 pages

35 pages

26 pages

25 pages

45 pages

5 pages

37 pages

14 pages

22 pages

24 pages

25 pages

24 pages

17 pages

34 pages

33 pages

44 pages

23 pages

27 pages

23 pages

16 pages

22 pages

84 pages

25 pages

28 pages

34 pages

29 pages

44 pages

19 pages

27 pages

17 pages

20 pages

27 pages

33 pages

26 pages

28 pages

25 pages

22 pages

25 pages

48 pages

23 pages

23 pages

13 pages

23 pages

5 pages

23 pages

4 pages

25 pages

26 pages

25 pages

17 pages

11 pages

27 pages

24 pages

25 pages

33 pages

28 pages

24 pages

29 pages

20 pages

2 pages

26 pages

24 pages

20 pages

## This preview shows page 1-2-3-19-20-39-40-41 out of 41 pages.

View Full Document

End of preview. Want to read all 41 pages?

View Full Document
Unformatted text preview:

CS231 Boolean Algebra 1Circuit analysis summary• After finding the circuit inputs and outputs, you can come up with either an expression or a truth table to describe what the circuit does.• You can easily convert between expressions and truth tables.Find the circuit’sinputs and outputsFind a Booleanexpressionfor the circuitFind a truth tablefor the circuitCS231 Boolean Algebra 2Boolean operations summary• We can interpret high or low voltage as representing true or false.• A variable whose value can be either 1 or 0 is called a Boolean variable.• AND, OR, and NOT are the basic Boolean operations.• We can express Boolean functions with either an expression or a truth table.• Every Boolean expression can be converted to a circuit.• Next time, we’ll look at how Boolean algebra can help simplify expressions, which in turn will lead to simpler circuits.CS231 Boolean Algebra 3Expression simplification• Normal mathematical expressions can be simplified using the laws of algebra• For binary systems, we can use Boolean algebra, which is superficially similar to regular algebra• There are many differences, due to– having only two values (0 and 1) to work with– having a complement operation– the OR operation is not the same as additionCS231 Boolean Algebra 4Formal definition of Boolean algebra• A Boolean algebra requires– A set of elements B, which needs at leasttwo elements (0 and 1)– Two binary (two-argument) operations OR and AND– A unary (one-argument) operation NOT– The axioms below must always be true (textbook, p. 33)• The magenta axioms deal with the complement operation• Blue axioms (especially 15) are different from regular algebra1. x + 0 = x 2. x • 1 = x3. x + 1 = 1 4. x • 0 = 05. x + x = x 6. x • x = x7. x + x’ = 1 8. x • x’ = 09. (x’)’ = x10. x + y = y + x 11. xy = yx Commutative12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’sCS231 Boolean Algebra 5Comments on the axioms• The associative laws show that there is no ambiguity about a term such as x + y + z or xyz, so we can introduce multiple-input primitive gates:• The left and right columns of axioms are duals– exchange all ANDs with ORs, and 0s with 1s• The dual of anyequation is always true1. x + 0 = x 2. x • 1 = x3. x + 1 = 1 4. x • 0 = 05. x + x = x 6. x • x = x7. x + x’ = 1 8. x • x’ = 09. (x’)’ = x10. x + y = y + x 11. xy = yx Commutative12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’sCS231 Boolean Algebra 6Are these axioms for real?• We can show that these axioms are valid, given the definitions of AND, OR and NOT• The first 11 axioms are easy to see from these truth tables alone. For example, x + x’ = 1 because of the middle two lines below (where y = x’)x y xy00 001 010 011 1x y x+y00 001 110 111 1x x’0110x y x+y00 001 110 111 1CS231 Boolean Algebra 7Proving the rest of the axioms• We can make up truth tables to prove (both parts of) DeMorgan’s law• For (x + y)’ = x’y’, we can make truth tables for (x + y)’ and for x’y’• In each table, the columns on the left (x and y) are the inputs. The columns on the right are outputs.• In this case, we only care about the columns in blue. The other “outputs” are just to help us find the blue columns. • Since both of the columns in blue are the same, this shows that (x + y)’ and x’y’ are equivalentx y x + y (x + y)’ x y x’ y’ x’y’00 0 1 00 1 1 101 1 0 01 10 010 1 0 1001 011 1 0 1100 0CS231 Boolean Algebra 8Simplification with axioms• We can now start doing some simplificationsx’y’ + xyz + x’y= x’(y’ + y) + xyz [ Distributive; x’y’ + x’y = x’(y’ + y) ]= x’•1 + xyz [ Axiom 7; y’ + y = 1 ]= x’ + xyz [ Axiom 2; x’•1 = x’ ]= (x’ + x)(x’ + yz) [ Distributive ]= 1 • (x’ + yz) [ Axiom 7; x’ + x = 1 ]= x’ + yz [ Axiom 2 ]1. x + 0 = x 2. x • 1 = x3. x + 1 = 1 4. x • 0 = 05. x + x = x 6. x • x = x7. x + x’ = 1 8. x • x’ = 09. (x’)’ = x10. x + y = y + x 11. xy = yx Commutative12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’sCS231 Boolean Algebra 9Let’s compare the resulting circuits• Here are two different but equivalentcircuits. • In general the one with fewer gates is “better”:– It costs less to build– It requires less power– But we had to do some work to find the second formCS231 Boolean Algebra 10Some more laws• Here are some more useful laws (p. 37). Notice the duals again!• We can prove these laws by either– Making truth tables:– Using the axioms:1. x + xy = x 4. x(x + y) = x2. xy + xy’ = x 5. (x + y)(x + y’) = x3. x + x’y = x + y 6. x(x’ + y) = xyxy + x’z + yz = xy + x’z (x + y)(x’ + z)(y + z) = (x + y)(x’ + z)x y x’ x’y x + x’y x y x + y00 00 001 01 110 10 111 11 1x + x’y = (x + x’)(x + y) [ Distributive ]= 1 • (x + y) [ x + x’ = 1 ]= x + y [ Axiom 2 ]CS231 Boolean Algebra 11The complement of a function• The complement of a function always outputs 0 where the originalfunction outputted 1, and 1 where the original produced 0.• In a truth table, we can just exchange 0s and 1s in the output column(s)f(x,y,z) = x(y’z’ + yz)x y z f(x,y,z)000 1001 1010 1011 1100 0101 0110 1111 0x y z f’(x,y,z)000 0001 0010 0011 0100 1101 1110 0111 1CS231 Boolean Algebra 12Complementing a function algebraically• You can use DeMorgan’s law to keep “pushing” the complements inwards• You can also take the dual of the function, and then complement …

View Full Document
Unlocking...