# Problem Solving with Logic Gates

• Due: 5 pm Friday 11 February 2022

• Summary: In this lab you will use logic gates in a circuit to solve a logical puzzle. Instead of building logic gates using transistors, we will use TTL chips, which have several logic gates in a single chip.

• Collaboration: You will work during lab in randomly assigned pairs. You must complete the work together in these groups, whether during or after the scheduled lab time.

• Submitting: After completing each exercise, show your completed circuit to the instructor or a course mentor. If you are unable to complete the lab during class time, schedule a time during office hours to demonstrate your circuit.

## The Problem

There is an old puzzle in which a farmer $$F$$ must transport a wolf $$W$$, a goat $$G$$, and a cabbage $$C$$ across a river. However, the farmer can only transport one of $$W$$, $$G$$, or $$C$$ across the river at a time, and if left together and unattended, the goat will eat the cabbage and the wolf will eat the goat. Let $$F=0$$ indicate the presence of the farmer on the west bank of the river and $$F=1$$ indicate presence on the east bank. Use similar definitions for $$W$$, $$G$$, and $$C$$.

The remainder of this lab will work through the process of building a circuit using TTL chips to indicate whether a particular configuration of $$F$$, $$W$$, $$G$$, and $$C$$ is “unsafe”.

## Background

TTL chips look approximately like this. They are 14-pin “dual in-line packages” (DIPs), meaning that the chips are long and narrow with 7 pins on each side. Each chip has a small notch in one end for orientation. When the notch is pointed upward as in the diagram, the pins are numbered from 1 to 14 starting in the upper-left corner and proceeding counter-clockwise.

For purposes of your logic design, note we have the following TTL chips available in the lab:

• 1-input inverter (NOT) (6 gates per chip);
• 2-input AND, OR, NAND, NOR, XOR (4 gates per chip);
• 3-input AND (3 gates per chip).

We will provide a pinout diagram, showing what each pin on each chip is for. Please note that the pinout for different chip types (AND, OR, etc) is different.

Please note carefully, that you must connect each chip to power and to ground. It is important that you use the correct pins for this. Reversing power and ground will destroy the chip. Make sure you connect to +5V and ground, not the adjustable +V or -V rows.

To do this, we recommend you connect the +5V row at the top of the protoboard to leftmost column of the breadboard sections (labeled “+” in this diagram, connected by red jumper wires on most breadboards). Each chip needing a power connection can connect a jumper wire from the appropriate row to that column (because the entire column contains power). This stragegy avoids a series of long messy wires.

Similarly, connect the ground row at the top of the protoboard to an appropriate ground (right) column on the breadboard (labeled “-” in this diagram, connected by black jumper wires on most breadboards). Each chip’s ground pin can then be connected easily to the ground column with a short jumper wire.

### Seating chips in the board

In the previous lab, you may have noticed the “channel” between banks of pin connection points, located between columns “e” and “f” in this diagram). To seat a chip in the protoboard, orient it such that its notch is facing upward as in the diagram, then place its two rows of pins such that they straddle one of the valleys in the board. This helps you attach power and ground to the correct pins, and ensures that none of the pins are connected together.

The chips may take some careful coaxing to seat them properly. We suggest placing one row of pins loosely into their holes in the board, and then using a fingernail to get the other row of pins lined up and started into their holes. Once all pins have been started correctly, you can press firmly, and the chip should snap into place. (Please be gentle until the pins are started well, or they will get bent, but then do press firmly to make sure the chip is fully inserted and that each pin makes a good connection with the board.)

### Removing chips from the board

Be careful not to pull chips out of the board at an angle, which could bend or break the pins. Grab the chip at the top and bottom edges (where the chip crosses the channel on the protoboard). If you cannot remove the chip by hand, we can remove it carefully using a chip puller from the supply cabinet.

### Working with Resistors

Now that we’re working with TTL chips and the logic switches in the lower left corner of your protoboard, you can safely omit resistors from your circuits. Instead of turning the circuit on and off, logic switches make a connection from your wire to either +5v or ground. That eliminates the need for pull-down or pull-up resistors. The other use case for resistors in our previous lab was to limit the current through transistors and LEDs. As long as you use the logic indicators on the right side of the board instead of raw LEDs, you can omit these resistors as well.

Please double-check to make sure your logic indicator and logic switch sections are set to TTL mode. While you’re double-checking your board configuration, make sure your TTL chips are powered from +5V and ground, not the adjustable +V or -V rows.

## Lab Work

We expect that you will be able to complete this work during normal lab time. Please show your work to the instructor or a mentor after each step in the lab work section below. If you are unable to finish all of the steps below during our scheduled lab, you may save your circuit on the board. Once you have completed the lab, schedule a time during my office hours where at least one member of your group can demonstrate your completed lab and show its correct operation.

1. Derive a truth table defining a function that gives 1 if the farmer is in danger ($$D$$) of losing the goat or the cabbage. You may assume that a trip across the river can be made instantaneously, so that if an item (or farmer) is not on one side of the river it must be on the other side.

Write the inputs of your truth table in the order $$F$$, $$W$$, $$G$$, $$C$$ and use canonical order for the rows.

2. Use a Karnaugh map to generate a reduced sum-of-products expression for this function. Then simplify the expression further with boolean algebra. Your final result should include only 8 literals (i.e., a variable or its complement), including repeated occurrences of the same variable.

3. Draw (on paper) a logic circuit diagram that implements your function from step 2. Label parts of the circuit that should be wired to the logic indicators on your protoboard to show when the farmer is in danger of losing either the goat or the cabbage. We recommend leaving plenty of space between the gates to allow for annotating both ends of each wire (as directed in the hints below).

4. Using TTL chips, construct and test a circuit that implements your circuit diagram from step 3.

5. Propose a solution to this puzzle starting with $$F$$, $$W$$, $$G$$, and $$C$$ initially on the west bank and must be transported to the east bank. Use your circuit to check your solution.

### Hints

• Check the part number on each chip carefully as you get it from the supply cabinet, and as you put it back. If you can not see the number well, hold it up to the light to cast shadows on the etching/relief. This can be surprisingly helpful.
• Make a diagram of your physical circuit as you build it, recording where each gate in your logic circuit diagram is located on the protoboard.
• Record the row and chip side (e.g. 42L, 19R) for each end of the wire in your diagram
• As you make each physical connection between logic gates, check the connection off in your logic circuit diagram.
• Arrange your switches for $$F$$, $$W$$, $$G$$, and $$C$$ in the same order as they are in your truth table.

#### Acknowledgements

Based on the fox, goose, and bag of beans puzzle.

Copyright © 2018, 2019, 2020, 2022 Marge Coahran, Janet Davis, Charlie Curtsinger, and Jerod Weinman

This work is licensed under a Creative Commons Attribution NonCommercial 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/4.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.