Gates

Assignment: Gates

• Assign: Thursday 26 January
• Due: Friday 3 February
• Policy: Individual graded synthesis assignment
• Submit: Upload a PDF written on the cs240-gates-worksheet.pdf submission sheet
• Reference:
  • Digital Logic
  • Boolean Laws

Contents

• Assignment: Gates
• 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 [18 points]
  • 7. XOR from Universal Gates (12 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.5] $(A + B)(A + B’)$
2. [2] $ABC + A’B + ABC’$
3. [2.5] [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 literals (a literal is a variable or its negation). Each minterm corresponds to a row in a truth table whose value is 1. An example 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.
2. [3] Draw a circuit that is a direct translation of bexp₃ without any simplification. For the circuit, use the same layout 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 literals. Each maxterm corresponds to a row in a truth table whose value is 0. An example sum-of-products 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. [1] 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. [1.5] 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. [2] [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. [2.5] [Independent] Using the DeMorgan and Involution laws, Express the inverse of A'(B+(C'D)')(E'+F) as a a boolean expression bexp_5f that is a sum of products. Show the application(s) of each law.

6. Simplification [18 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 in a sum-of-products form. Your goal is to have the most concise final expression (smallest number of products, where each product uses the smallest number of literals). Updated on 2023/03/02: Here, it’s OK individual products include literals for only some of the inputs (not necessarily all of them).

Show your deriviation 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. [5] ABC + ABC’ + A’C + A’B’C + AB’C Hint: the following laws are the only ones you need (not in this order), though you are welcome to use others: Absorption 1, Absorption 2, Combining, DeMorgan, Distributivity
2. [6] [Independent] A'B' + A'BC' + (A + C')'

3. [7] [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 sum-of-products result should have 4 products, where each product has at most 2 literals. Updated on 2023/03/02: Here, it’s OK individual products include literals for only some of the inputs (not necessarily all of them).

7. XOR from Universal Gates (12 points)

The goal of this problem is to draw two circuits that implement two-input XOR:

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

Rather than using trial and error (which is very unsatisyfing) to develop these circuits, you should derive them using the laws of Boolean algebra in conjunction with the definitions of XOR, NAND, and NOR gates. I.e., 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 equilvalent one that uses only NAND or NOR.

Hints:

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

• The only two Boolean laws you need are DeMorgan and Involution (Double Negation). Update on 2023/02/03: actually, Distributivity is necessary in some cases as well.

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

• Full credit for a correct circuit will be awarded only if the circuit is accompanied by a correct algebraic derivation that corresponds to the circuit.

• Half credit will be awarded for a correct circuit without an algebraic derivation as long as you explain why the circuit correctly calculates XOR.

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.