Truth table, K-map and circuit
Truth table
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Karnaugh map of F
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 13 | 0 |
| 1 | 0 | 12 | 11,2,3 | 11 |
A Bcovers 6, 7A Ccovers 5, 7B Ccovers 3, 7
Minimal expressions for F
F = A B + A C + B CF = (A + B) (A + C) (B + C)Paste the first form into Project, Analyze Circuit, Expression. Do not mix + with * in Logisim: a + b*c is read as (a + b)·c.
Canonical forms
Σm(3, 5, 6, 7)
ΠM(0, 1, 2, 4)
The minimal form shown is one of possibly several equally small answers.
Logisim circuit
4 gates (NOT, AND and OR), wired, saved in the 5.0.0 format.
Preview the circuit
Drawing the circuit.
Check it in Logisim
- Open the file in Logisim-evolution 5.0.0. Wires stay grey until you click the canvas or press Ctrl+R.
- Project, Analyze Circuit, Table: it shows the same table as above.
- Or run the vector:
java -jar logisim-evolution-5.0.0-all.jar --no-splash -w main main.vec.txt main.circ. It must printFailed: 0.
How to read a Karnaugh map
A K-map is a truth table laid out so that neighbouring cells differ in one variable. That makes simplification a matter of drawing rectangles.
- Gray-code order. Rows and columns are labelled 00, 01, 11, 10, not 00, 01, 10, 11. Only one bit changes from one label to the next, and the last label is also a neighbour of the first, so the map wraps around the edges.
- Group the 1s. Draw rectangles around adjacent 1s. The size must be 1, 2, 4, 8 or 16 cells.
- Make groups large. A bigger group gives a shorter term. Groups may overlap, and may wrap around an edge or a corner.
- Read each group. Keep only the variables that do not change inside the group. A variable that is 1 throughout appears as itself; one that is 0 throughout appears complemented.
- Don’t cares. Include an x cell only when it lets a group grow.
- Add the terms. The OR of the group terms is the minimal sum of products.
Load an example into the tool above to see the groups:
Worked examples
Each file below was written by the tool and passed its truth table as a test vector in Logisim-evolution 5.0.0 (F96).
| 3-input majority | F = A B + A C + B C | Three pairs of 1s, each group of two cells. | .circ, vector |
|---|---|---|---|
| 4 variables, wrap-around | F = ~A B D + ~B ~D | The four corners are one group of four because the map wraps. | .circ, vector |
| BCD segment a | Sa = A + ~B ~D + B D + C | Inputs 10 to 15 never occur, so they are don't cares and the groups grow. See the [7-segment decoder generator](/tools/7-segment-decoder/). | .circ, vector |
| Full adder, S and Cout | Cout = A B + A Cin + B Cin | S has no groups at all: every 1 is isolated, which is why an XOR appears in the usual drawing. See the [full adder project](/projects/full-adder/). | .circ, vector |
No rows match.
Why this solver builds the Logisim circuit
Most solvers stop at the equation. This one also gives you the expression in Logisim’s own syntax and a .circ file with the gates placed and wired, saved in the Logisim-evolution 5.0.0 format.
A circuit written by the tool opened in Logisim-evolution 5.0.0. Three input pins A, B and C feed three AND gates through vertical wires, and the three AND outputs feed one OR gate that drives the output pin F. A text label above the circuit names the expression.
In our run the file opened with the gates and wires as drawn. Like every file opened in 5.0.0, it shows grey wires until you click the canvas or press Ctrl+R (F45). The generated circuit uses plain wires, not tunnels. Logisim’s Analyze Circuit refuses to build expressions for a circuit with tunnels (F48); for ours, it showed the expression:
The Analyze Circuit window on the Expression tab for the generated circuit. It shows F = A·B+A·C+B·C in Mathematical notation, with the buttons Import Table, Build Circuit, Optimize minterms, Optimize maxterms, Export Table and Export TeX.
Notes on the file:
- Gates use their default size, so every connection point is the one we measured for 5.0.0 (F96).
- Input pins are listed top to bottom in the order of your variables, which is the order the command line and test vectors use.
- Unconnected gate inputs are ignored by Logisim and would not show as an error, so we check each file by comparing its whole table, not by looking at the drawing.
- Circuits are written for up to 10 inputs. Expressions, tables and K-maps work up to 12 inputs.
- The file does not open in classic 2.7.1 (F04).
Paste it into Logisim
Copy the Logisim-syntax expression
Choose the Logisim syntax in the tool and press Copy next to the sum of products.
Check: The text on the clipboard has no apostrophes.
Open the analysis
In Logisim-evolution, choose Project, then Analyze Circuit.
Check: The Combinational Analysis window opens.
Enter the names and the expression
Add the input and output names on the Inputs & Outputs tab, then type or paste the expression on the Expression tab. Names should start with a letter; the project’s source rejects others.
Check: The Expression tab shows your expression.
Click Build Circuit
Pick a circuit name that is not the name of an existing pin or circuit. See the combinational analysis guide.
Check: The circuit tree lists a new circuit.
Logisim expression syntax
The 5.0.0 expression window accepts the forms below. The first column marks what we confirmed by running the 5.0.0 parser on it (F37); the rest is from the project’s source and we did not run it.
| NOT | ~A A' (also !A and ¬A) | ~A and A' run through the parser; the others from the source |
|---|---|---|
| AND | A B (a space) A*B A&B (also &&, ·, ∧) | space, * and & run through the parser; the others from the source |
| OR | A+B A|B (also ||, ∨) | + and | run through the parser; the others from the source |
| XOR | A^B (also ⊕) | ^ run through the parser; ⊕ from the source |
| Constants | 0 1 | from the source |
No rows match.
When Logisim cannot read an expression it shows messages such as “Unrecognized characters”; see the error list.
Do it inside Logisim instead
If your course wants Logisim’s own tool: Project, Analyze Circuit. The window has the tabs Inputs & Outputs, Table, Expression and Minimized, where the last shows a Karnaugh map, and a Build Circuit button (F95). The Table tab of our full adder read “8 of 8 rows shown”. If the circuit uses tunnels Logisim says “Computing truth table instead of expression due to Tunnel”, then still shows the table and expressions (F48). The source sets limits on inputs and outputs that we did not reach. The combinational analysis guide has the full walk-through.
Limits
- K-map drawing: 2 to 6 variables. Tables, expressions and the expression forms: up to 12 inputs and 8 outputs. Logisim’s own window accepts more.
- Circuits: up to 10 inputs and 1,000 gates.
- Above 8 inputs, or for a very large chart, the minimal cover uses a fast heuristic and the tool labels the result “near-minimal”. At 8 inputs or fewer the cover is exact, and the tool says when several equally small answers exist.
- No flip-flops or state machines; this is combinational logic only.
Privacy
Everything runs in your browser. Your expressions and tables are not sent anywhere. The page address keeps the function you entered (up to 8 inputs) so you can share a link; clear the address to remove it.