Problem Solving with Logic Gates

Due: 11:59 pm (US CDT/UTC-5) Monday 7 September 2020
Summary: In this assignment you will use logic gates in a circuit to solve a logical puzzle.
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: Submit your farmer.circ, truth-table.txt, solution.txt and references.txt to the appropriate Assignment on Gradescope. Be sure to follow the submission guidelines and use exactly these file names.

Overview

You will continue to use Logisim to build a circuit modeling a small logic puzzle. You will also see Logisim’s support for test files, which make it possible to validate your circuits without manually setting inputs and checking outputs.

Grading

Your grade on this assignment will depend on the correctness of your circuit. I will use a test suite to validate your circuit’s output. To receive an A on this assignment, your circuits must pass every test case. Circuits that fail fewer than 5% of the test cases will receive at most a B, and circuits that produce a significant number of incorrect outputs will receive a C or lower.

Testing circuits requires that the names of inputs and outputs be specified exactly in the test files. Please pay close attention to the instructions when setting up your circuit; any submission whose names do not match exactly may fail several (or all) test cases, which will likely lead to a very poor grade.

Finally, some consideration may be given to the clarity of organization within your circuits. Wires and gates should be laid out in a fashion that facilitates comprehension.

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 Logisim to indicate whether a particular configuration of $F$ , $W$ , $G$ , and $C$ is “unsafe”.

Getting Started

To begin this assignment you will need access to an installation of Logisim. If you are working on MathLAN, you can start Logisism with the following shell command:

$ java -jar /home/curtsinger/shared/logisim.jar

You can also install Logisim on your personal computer. To do this, you will need to copy the Logisim file from the MathLAN path above or download logisim.jar directly. You can then start the program with Java on your own machine.

Lab Work

Although your final materials will be submitted for grading, we ask that you show your work to the instructor or a mentor after each step in the lab work section below.

Part A: Truth Table

In the first part you will derive a truth table defining a function that gives 1 if the farmer is in danger 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 (i.e., 0) it must be on the other side (i.e., 1). This truth table will also function as your unit tests for your circuit, to verify it produces the intended outputs, so we will need to write it in a particular format.

You will write the inputs of your truth table in the order $F$ , $W$ , $G$ , $C$ , followed by the the output $D$ (for “danger”). Download and then add rows to the file truth-table.txt to complete the function specification. Please add your rows in canonical order.

Part B: Reduction and Simplification

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 variables, including repeated occurrences of the same variable.

You should also manipulate the expression so as to (ultimately) minimize the total number of gates required for implementation. Note: a bubble on an input to a gate counts as/requires an inverter, but a bubble on an output of a gate (e.g., XNOR, NAND, and NOR) is its own integrated circuit, and counts as a single gate.

Part C: Circuit Implementation

Create a file in logisim called farmer.circ. In the “main” subcircuit, implement the logic function you produced in B in Logisim using logic gates, wires, and I/O pins. You will need to use Logisim’s “Attribute Table” to alter the label of each pin to match those in the heading of the truth table you established (i.e., F, W, G, C, and D). You do this by selecting the pin while in edit mode (when the mouse arrow in the toolbar is highlighted, not simulation mode when the pointing hand is highlighted), and editing the “Label” attribute. Note that adding free-floating text (by selecting the italic “A” in the toolbar) does not accomplish this.

Remember to implement your circuit using the minimal number of gates. While you are welcome to use input bubbles (rather than inverters) to negate inputs to a gate for a more compact display, these count as separate gates (whereas an integrated NOR (etc.) is only a single gate.

Part D: Circuit Testing

While you could verify your circuit’s outputs manually for the sixteen input case, we can instead test it automatically using Logisim’s test vectors. To run the tests in your truth-table.txt file, select Test Vector from the Simulate menu item in Logisim. Click the Load Vector button and open the test file. The test vector window will then show you which tests (truth table rows) your circuit passes or fails.

If you get an error complaining that the test vector in your file does not match the circuit because a test vector column has no matching pin, then you need to check that all the pins were labeled correctly, as specified in Part C above.

If your circuit does not pass all the tests, make sure you have implemented the translation of the boolean function you created in Part B to a circuit in Part C correctly.

Part E: Puzzle Solution

Generate a solution to this puzzle starting with $F$ , $W$ , $G$ , and $C$ initially on the west bank (all zeros) and must be transported to the east bank (all ones). Record your solution in solution.txt by adding lines to the sequence in which the farmer moves from side to side (0 to 1 to 0 …) with at most one other bit toggling from line to line (representing the passenger accompanying the farmer).

Use your circuit to (manually) check your solution, where $D$ should remain de-asserted for each line of the input settings.

Acknowledgements

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

CC-BY-NC 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.