---

UIT2201: CS & the IT Revolution
Tutorial Set 8 (Spring 2013)

(D-Problems discussed on Wednesday, 20-Mar-2013)
(Q-Problems due on Friday, 22-Mar-2013)

---

Practice Problems: (not graded)
These are practice problems for you to try out. (If you have difficulties with these practice problems, please quickly see your classmates or the instructor for help.)

T7-PP1: (Binary Representations) Problems 1, 2, 5 of Section 4.2.1, p.142 of [SG3].

T8-D0: Read Ch. 4.3--4.4 (pp. 156--178) of [SG3]

T8-D1: [Simple Logic Circuit Design]
Practice Problem 2 in p.169 (Ch.4.4.2)of [SG3].

Design a circuit using AND, OR and NOT gates to implement the following truth table for the XOR (exclusive-OR) operation. It is true if and only if a is 1 or b is 1 but not both.

a b Output =============== 0 0 0 0 1 1 1 0 1 1 1 0

T7-D2: [Boolean Logic Laws]
Using truth tables, prove the following logical law (DeMorgan's Law).
        ~(P + Q) = (~P) * (~Q)

T8-D3: (Logic Design) [From Quiz 2, Spring 2009]
Click here --> Fig-T8-Q3-2009-Sp-Quiz-2.pdf

T8-D4: (Advertising War)
There are two pricy restaurants next to each other. One has a sign that says,

"Good food is not cheap."

and the other has a sign that says,

"Cheap food is not good."

(a) Formulate the statements given in the sign as logic formulae.
(b) Are the signs saying the same thing?

T8-D5: [Creative, Interesting Interpretations]
Give more interesting and creative interpretations of
        G = A + (B*(~C))

T8-Q1: (10 points) [Boolean Logic Laws]
Using truth tables, prove the following logical laws.
        1. A*(A+B) = A               [Absorption Law]
        2. ~(X*Y) = (~X + ~Y)               [de Morgan's Law]
        3. X+(Y*Z) = (X+Y)*(X+Z)         [Distributive Law]

T8-Q2: (5 points) (Simple Logic Circuit Design)

Problem 18 in p.185 (Ch. 4) of [SG3]. Using the circuit construction algorithm of Section 4.4.2, design a circuit using only AND, OR and NOT gates to implement the following truth table.

a b Output =============== 0 0 1 0 1 1 1 0 0 1 1 1

T8-Q3: (10 points) [Logic Design, [From Quiz 2, Spring 2008, Q2]
Click here --> Fig-T8-Q3-2008-Sp-Quiz-2.pdf

T8-Q4: (10 points) [Design of the 3-bit-Majority Circuit]
Build a 3-input "majority-rules" circuit. This is a circuit that has 3 inputs and one output. The value of its output is 1 if and only if two or more of its inputs are 1; otherwise, the output of the circuit is 0. For example, if the 3 inputs are 0, 1, and 1, your circuit should output a 1. If its 3 inputs are 0, 1, 0, it should output a zero.
(Note: This circuit is used in fault-tolerant computing -- see Prob 19 of Ch.4. of [SG] for details.)

A7-2013: (?? What? )