Gates

Assignment: Gates

• Assign: Tuesday 5 September
• Due: Wednesday 13 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.

Contents

• Assignment: Gates
• Contents
• Exercises
  • 1. Circuit to Expression [4 points]
  • 2. Expression to Circuit [6 points]
  • 3. Sum-of-Products [5 points]
  • 4. Product-of-Sums [5 points] [Independent]
  • 5. Fun with DeMorgan [10 points]
  • 6. Simplification [12 points]
  • 7. XOR from Universal 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. 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

4. 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 3:

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).

5. 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_5b that is a sum of literals.

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

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

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

6. Simplification [12 points]

As seen in class, Boolean simplification uses Boolean laws to rewrite one Boolean expression step by step into another Boolean expression, where each step preserves the meaning of the expressions. Below is an example of Boolean simplification used to prove A + AB = A (one form of Absorption Law 1):

	A + AB
=	1A + AB	Identity
=	A1 + AB	Commutativity
=	A(1 + B)	Distributivity
=	A1	One law
=	1A	Commutativity
=	A	Identity

Each step of a Boolean simplification applies a simplification law to a subpart of a Boolean expression known as the redex. In the above proof, the redex on each line is highlighted in a bolded color, and the law applied to that redex is named in the following line (using the same bolded color as the redex to which is is applied). The redex colors alternate between lines to avoid confusion.

It is tedious to explicitly show each application of the commutativity and associativity laws, so these are usually omitted. With these omissions, the above derivation can be shortened to:

	A + AB
=	A1 + AB	Identity
=	A(1 + B)	Distributivity
=	A1	One law
=	A	Identity

Below is another simplification example that illustrates more laws:

	DEFG + DEFGHI+ (E'+F')G + (EF)'G'
=	DEFG +(E'+F')G + (EF)'G'	Absorption 1
=	DEFG +(EF)'G + (EF)'G'	DeMorgan
=	DEFG + (EF)'(G + G')	Distributivity
=	DEFG +(EF)'(1)	Inverse
=	DEFG + (EF)'	Identity
=	DG +(EF)'	Absorption 2 (where A=(EF)',B=DG, and commutativity and involution are used implicitly)
=	DG + E' + F')	DeMorgan

Note that a single application of the Combining law could have been used to replace the three redex applications Distributivity, Inverse, and Identity to directly simplify the redex (EF)'G + (EF)'G' to (EF)' in one step.

In this problem, you will use the laws of Boolean algebra to simplify some Boolean expressions. Each result (including intermediate ones) should used only products, sums, and negation (i.e., no XOR). Each final result should be expressed as a sum of products of literals (but here, it’s ok for individual products to include literals for only some of the inputs, not necessarily all of them). Your goal is to have the most concise final expression (smallest number of products, where each product uses the smallest number of literals).

Show your derivation in a step-by-step way, using the conventions shown in the above examples. Notes:

• Rather than using colors for redexes, you can box them or underline them.
• As in the above examples, you must list the law(s) used to justify each step. The law names do not need to be colored, but the law(s) listed on a line should justify the redex highlighed on the previous line.
• To help you think about the meaning of each Boolean expression, you must show a truth table for the original expression and verify that your final expression satisfies the same truth table. If not, you made one or more mistakes in your steps that you need to correct!

1. [3] ABC + ABC’ + A’C + A’B’C + AB’C Hint: the following laws are the only ones you need (not necessarily in this order), though you are welcome to use others: Absorption 1, Absorption 2, Combining, DeMorgan, Distributivity
2. [4] [Independent] A'B' + A'BC' + (A + C')'

3. [5] [Independent.] A' + A'B'CD' + A'B'C'D' + AB'C' + AB'CD' + ABD + BC'D

   This problem is harder and serves as a motivation for Karnaugh maps, which we will learn later.

   Hints:

   • The only laws you need are are Absorption 1, Absorption 2, and Distributivity, though you are welcome to use other ones.
   • DeMorgan and Consensus are not needed.
   • The final result should have 4 products, where each product has at most 2 literals.

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. You may want to start with the 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.

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.