T7-D2: [Boolean Logic Laws] DIY (Ref: T8-Q1)
T8-D3: [Logic Design, [From Quiz 2, Spring 2009] -- SOLN SKETCH
(a)-------------------------------
A B C | F
-------------------------------
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
-------------------------------
(b)F = ~A~B~C + ~AB~C + A~B~C + AB~C + ABC
(c)Simplify
F = [ ~A~B~C + ~AB~C ] + [ A~B~C + AB~C ] + [ AB~C + ABC ] (Note: AB~C is repeated)
= ~A~C(~B + B) + A~C(~B + B) + AB(~C + C)
= ~A~C + A~C + AB = ~C(~A + A) + AB
= ~C + AB
(d) DIY
Let G = "food is good" p q | (p->q) (~p+q)
and C = "food is cheap" -------------------------
0 0 | 1 1
(p -> q) or "p implies q" 0 1 | 1 1
is defined by tt on right. 1 0 | 0 0
Note: (p -> q) = (~p+q) 1 1 | 1 1
(proof using tt) -------------------------
^ ^
Restaurant 1 says:
"Good food is not cheap"
"food is good" implies not "food is cheap"
(G -> ~C) = ~G + ~C
Restuarant 2 says:
"Cheap food is not good"
"food is cheap" implies not "food is good"
(C -> ~G) = ~C + ~G = ~G + ~C
So, they are saying the same thing (logically).
But the impression they convey (you get) is a different story.
1. A*(A+B) = A [Absorption Law]
--------------------------
A B | A+B A*(A+B)
--------------------------
0 0 0 0
0 1 1 0
1 0 1 1
1 1 1 1
--------------------------
^ ^
The corresponding columns are identical. Equality proved!
2. ~(X*Y) = (~X + ~Y) [de Morgan's Law]
-------------------------------------------
X Y | X*Y ~(X*Y) ~X ~Y (~X+~Y)
-------------------------------------------
0 0 0 1 1 1 1
0 1 1 0 1 0 1
1 0 1 0 0 1 1
1 1 1 0 0 0 0
-------------------------------------------
^ ^
The corresponding columns are identical. Equality proved!
3. X+(Y*Z) = (X+Y) * (X+Z) [Distributive Law]
-------------------------------------------------------
X Y Z | (Y*Z) X+(Y*Z) (X+Y) (X+Z) (X+Y)*(X+Z)
-------------------------------------------------------
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1
-------------------------------------------------------
^ ^
The corresponding columns are identical. Equality proved!
Output = ~a*~b + ~a*b + ab = ~a + b (after simplification)
Alternate way: ~Output = a*~b; So, Output = ~(a*~b) = ~a + b.
F = X~Y + ~XZ + XYZ
(a)-------------------------------
X Y Z | F
-------------------------------
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
-------------------------------
(b)F = ~X~YZ + ~XYZ + X~Y~Z + X~YZ + XYZ
(c)Simplify
F = (~X~YZ + ~XYZ) + (X~Y~Z + X~YZ) + (X^YZ + XYZ) (Note: X~YZ is used twice!)
= ~XZ(~Y + Y) + X~Y(~Z + Z) + AB(~C + C)
= ~XZ + X~Y + XZ = Z(~X + X) + X~Y
= Z + X~Y
(d) DIY
-------------------------------
A B C | M (Majority)
-------------------------------
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
-------------------------------
M = (~a)bc + a(~b)c + ab(~c) + abc
= [ (~a)bc + abc ] + [ a(~b)c + abc ] + [ ab(~c) + abc ]
M = bc + ac + ab [note: can you see/hear what this formula say?]
= bc + a(b+c)
(Remark: The above formula "says" M is true iff at least
two of inputs (a, b, or c) are 1's. Can you "hear" it?)
(Also, this circuit is the same as that for the carry signal
in the 1-bit adder describe in lecture notes and Figure 4.24 [SG].