Gates

Assignment: Gates

• Assign: Tuesday 3 September
• Due: Wednesday 11 September
• Policy: Individual graded synthesis assignment
• Submit: Upload a PDF written on the cs240-gates-worksheet.pdf submission sheet
• Reference:
  • Digital Logic
  • Boolean Laws

Goals

• To understand how circuits model computation with inputs, wires, and gates.
• To master converting between logical expressions, truth tables, and gate diagrams.
• To become comfortable applying Boolean algebraic laws.
• To understand universal logical gates—giving you a taste of how complex computation can be expressed with very simple building blocks.

Time reports

For a (slightly different) version of this assignment in a previous semester, students self-reported the following times:

• 25% of students spent <= 4 hours.
• 50% of students spent <= 5 hours.
• 75% of students spent <= 8 hours.

Contents

• Assignment: Gates
  • Time reports
• Contents
• Exercises
  • 1. Circuit to Expression [4 points]
  • 2. Expression to Circuit [6 points]
  • 3. Equivalences [4 points]
  • 4. Fun with DeMorgan [10 points]
  • 5. Sum-of-Products [5 points]
  • 6. Product-of-Sums [5 points] [Independent]
  • 7. XOR from Universal Gates (8 points)
  • 8. Universal Muxification of Gates (8 points)
• Submission

Exercises

Please write your answers on the cs240-gates-worksheet.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.

1. Circuit to Expression [4 points]

Write truth tables (2 points) and unsimplified Boolean expressions (1 point each) for each of the output signals $F_1$ and $F_2$ in the following circuit. Create the boolean expressions via a direct translation of the circuit.

2. Expression to Circuit [6 points]

Draw unsimplified circuits to implement the following Boolean expressions. We use the apostrophe$’$ notation as an alternative to the overbar to indicate logical negation of the preceding term. The apostrophe binds tightly. For example, $AB’$ means $(A)(B’)$. Use many-input AND, OR, NOR, or NAND gates where they are useful (instead of using only 2-input gates).

1. [1] $(A + B)(A + B’)$
2. [2] $ABC + A’B + ABC’$
3. [3] [Independent] $A’B’ + A’BC’ + (A + C’)’$

3. Equivalences [4 points]

In each of the following subparts, are circuits $O_1$ and $O_2$ equivalent (do they always produce the same output when given the same inputs)?

If they are not, provide an example value for $A$ and/or $B$ and what the different outputs of $O_1$ and $O_2$ become (a counterexample). If they are equivalent, provide a short explanation.

a.

b.

c.

d. [Independent]

4. Fun with DeMorgan [10 points]

Lois Reasoner thinks that AB + A'B' simplifies to 1 by the Inverse law.

1. [2] Show that Lois is wrong by fleshing out a truth table to find all rows in which AB + A'B' evaluates to 0, not 1. Circle these rows.

2. [2] By part (a), A'B' is clearly not the inverse of AB. Using DeMorgan’s law, express the inverse of AB as a Boolean expression bexp_4b that is a sum of literals.

3. [1] Extend the truth table from part (a) to add columns for bexp_4b and AB + bexp_4b. All entries in the column for AB + bexp_4b should have the value 1, showing that bexp_4b is indeed the inverse of AB.

4. [2] Using the DeMorgan and Involution (double-negation) laws, express the inverse of A'B' as a boolean expression bexp_4d that is a sum of literals. Show the application(s) of each law.

5. [3] [Independent] Using the DeMorgan and Involution (double-negation) laws, express the inverse of (A'+B+C') as a boolean expression bexp_4e that is a product of literals. Show the application(s) of each law.

5. Sum-of-Products [5 points]

Recall that a sum-of-products form is a boolean expression that is a sum of minterms, where each minterm is a product of one literal for every input variable (a literal is a variable or its negation). For example, ABC and ABC' are minterms of a circuit with 3 inputs, but AB is not.

An example of a sum-of-products expression is (A'BC') + AB'C + ABC'. Using a circuit layout convention similar to that suggested from DDCA, this example can be expressed as the following circuit:

A nice feature of this layout convention is there is never more than one inverter per input.

Below is a truth table.

1. [2] Write a sum-of-products Boolean expression bexp₅ for the output $Y$ of this truth table. (Hint: See Section 2.2.2 of DDCA.)
2. [3] Draw a circuit that is a direct translation of bexp₅ without any simplification. For the circuit, try to use the same input order and layout convention as in the example shown above.

$A$	$B$	$C$		$Y$
0	0	0		1
0	0	1		0
0	1	0		1
0	1	1		0
1	0	0		1
1	0	1		1
1	1	0		0
1	1	1		1

6. Product-of-Sums [5 points] [Independent]

Recall that a product-of-sums form is a boolean expression that is a product of maxterms, where each maxterm is a sum of one literal for every input variable. An example product-of-sums expression is (A+B+C)(A+B+C')(A+B'+C)(A'+B+C).

Using the same truth table from Problem 5:

1. [2] Write a product-of-sums Boolean expression bexp₆ for the output $Y$ of the truth table
2. [3] Draw a circuit that is a direct translation of bexp₆ without any simplification. For the circuit, use a layout that is analogous to the layout of the sample circuit in Problem 3 (where the and and or gates are appropriately swapped).

7. XOR from Universal Gates (8 points)

NAND and NOR are universal gates: each one alone can be used to build any other logical gate. The goal of this problem is to demonstrate how this works by drawing two circuits that implement two-input XOR:

1. [4] Using only 2-input NAND gates.
2. [4] [Independent] Using only 2-input NOR gates.

Your approach may combine your intuition, trial-and-error, and applying the laws of Boolean algebra in conjunction with the definitions of XOR, NAND, and NOR gates. Regardless of strategy, you’ll want to think about DeMorgan’s law. One concrete strategy is to start with the sum-of-products or product-of-sums definition of A XOR B and use Boolean laws to convert the original expression to an equivalent one that uses only NAND or NOR.

Hints:

• Recall that A NAND B = (AB)' and A NOR B = (A+B)'

• The only Boolean laws you need are DeMorgan, Involution (Double Negation), and Distributivity.

• The minimal number of NAND gates is 4, but nearly full credit will be awarded for 5 NAND gates.

• The minimal number of NOR gates is 5, but nearly full credit will be awarded for 6 NOR gates.

8. Universal Muxification of Gates (8 points)

Recall that a simple MUX (a 2:1 mux) has 3 inputs: a selector input S, and two choice inputs, labeled 0 and 1:

2:1 muxes are universal in the sense that any circuit can be implemented using just 2-to-1 muxes. In this problem, you will show this by using muxes to implement various gates. In each circuit, draw the specified number of 2:1 muxes and implement the given boolean expression. A mux input can be A, B, 0, 1, or the output of another device (e.g., another mux or a decoder). Be sure to label the S, 0, and 1 inputs of every mux.

1. [1 point] Use one 2:1 mux to implement NOT A (i.e. A')
2. [2 points] Use one 2:1 mux to implement A AND B (i.e. AB)
3. [2 points] [Independent] Use one 2:1 mux to implement A OR B (i.e. A+B)
4. [3 points] [Independent] Use two 2:1 muxes to implement A NAND B

Submission

Please write your answers on the cs240-gates-worksheet.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.