Skip to content

Sign in Open the app

Boolean expressions to circuits: exercises with answers

Ten formulas to turn into gate lists: for each, name the gates in evaluation order, with their inputs, so that the last gate's output is the formula, and count the gates. The formula and its truth table are under each problem; the solution gives one gate list and the count.

Work from the inside out, the way the engine evaluates: innermost parentheses first, then NOT, then AND, then XOR, then OR, with -> and <-> rewritten as the gates they do not have. Each operator becomes one gate; a chain of three ANDs is a three-input AND or two two-input ANDs, and the solution says which count it uses. An implication is an inverter and an OR; a biconditional is an XNOR gate, or an XOR followed by an inverter.

A gate list is a circuit in text form: g1 = AND(A, B), g2 = OR(g1, C), output g2. Two gate lists for the same formula are both right if their outputs agree on every row, which is what the truth table under the problem lets you check; the count may differ, and the solutions state the count of the straightforward reading, not of a shorter design. The NAND-only practice set covers rebuilding the same circuits from a single gate type.

1. Give the gate list for (A AND B) OR C. (A AND B) OR C

#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	TRUE
2	FALSE	TRUE	FALSE	FALSE
3	FALSE	TRUE	TRUE	TRUE
4	TRUE	FALSE	FALSE	FALSE
5	TRUE	FALSE	TRUE	TRUE
6	TRUE	TRUE	FALSE	TRUE
7	TRUE	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

(A AND B) OR C

Classification: contingent

g1 = AND(A, B), g2 = OR(g1, C); output g2. Two gates.

2. Give the gate list for NOT A AND B. NOT A AND B

#	A	B	f
0	FALSE	FALSE	FALSE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	FALSE
3	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

NOT A AND B

Classification: contingent

g1 = NOT(A), g2 = AND(g1, B); output g2. Two gates: the inverter sits on A alone.

3. Give the gate list for (A OR B) AND NOT C. (A OR B) AND NOT C

#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	FALSE
2	FALSE	TRUE	FALSE	TRUE
3	FALSE	TRUE	TRUE	FALSE
4	TRUE	FALSE	FALSE	TRUE
5	TRUE	FALSE	TRUE	FALSE
6	TRUE	TRUE	FALSE	TRUE
7	TRUE	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

(A OR B) AND NOT C

Classification: contingent

g1 = OR(A, B), g2 = NOT(C), g3 = AND(g1, g2); output g3. Three gates.

4. Give the gate list for A XOR B, first with an XOR gate and then with AND, OR and NOT only. A XOR B

#	A	B	f
0	FALSE	FALSE	FALSE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	TRUE
3	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A XOR B

Classification: contingent

One XOR gate, g1 = XOR(A, B). With AND, OR and NOT only, XOR elimination gives (A AND NOT B) OR (NOT A AND B): two inverters, two ANDs and an OR, five gates.

5. Give the gate list for (A AND B) OR (NOT A AND C). (A AND B) OR (NOT A AND C)

#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	TRUE
2	FALSE	TRUE	FALSE	FALSE
3	FALSE	TRUE	TRUE	TRUE
4	TRUE	FALSE	FALSE	FALSE
5	TRUE	FALSE	TRUE	FALSE
6	TRUE	TRUE	FALSE	TRUE
7	TRUE	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

(A AND B) OR (NOT A AND C)

Classification: contingent

g1 = AND(A, B), g2 = NOT(A), g3 = AND(g2, C), g4 = OR(g1, g3); output g4. Four gates, the 2-to-1 multiplexer with A as select.

6. Give the gate list for NOT (A AND B). NOT (A AND B)

#	A	B	f
0	FALSE	FALSE	TRUE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	TRUE
3	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

NOT (A AND B)

Classification: contingent

One NAND gate, g1 = NAND(A, B); or g1 = AND(A, B), g2 = NOT(g1), two gates. The same function either way: FALSE only on A = TRUE, B = TRUE.

7. Give the gate list for A -> B. A -> B

#	A	B	f
0	FALSE	FALSE	TRUE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	FALSE
3	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A -> B

Classification: contingent

There is no implication gate: implication elimination gives NOT A OR B, so g1 = NOT(A), g2 = OR(g1, B); output g2. Two gates.

8. Give the gate list for A <-> B. A <-> B

#	A	B	f
0	FALSE	FALSE	TRUE
1	FALSE	TRUE	FALSE
2	TRUE	FALSE	FALSE
3	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A <-> B

Classification: contingent

One XNOR gate, g1 = XNOR(A, B), TRUE when the inputs agree; or g1 = XOR(A, B), g2 = NOT(g1), two gates.

9. Give the gate list for A XOR B XOR C. A XOR B XOR C

#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	TRUE
2	FALSE	TRUE	FALSE	TRUE
3	FALSE	TRUE	TRUE	FALSE
4	TRUE	FALSE	FALSE	TRUE
5	TRUE	FALSE	TRUE	FALSE
6	TRUE	TRUE	FALSE	FALSE
7	TRUE	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A XOR B XOR C

Classification: contingent

g1 = XOR(A, B), g2 = XOR(g1, C); output g2. Two gates, the sum output of a full adder; the chain is a parity function.

10. Give the gate list for (A OR B) AND (C OR D). (A OR B) AND (C OR D)

#	A	B	C	D	f
0	FALSE	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	FALSE	TRUE	FALSE
2	FALSE	FALSE	TRUE	FALSE	FALSE
3	FALSE	FALSE	TRUE	TRUE	FALSE
4	FALSE	TRUE	FALSE	FALSE	FALSE
5	FALSE	TRUE	FALSE	TRUE	TRUE
6	FALSE	TRUE	TRUE	FALSE	TRUE
7	FALSE	TRUE	TRUE	TRUE	TRUE
8	TRUE	FALSE	FALSE	FALSE	FALSE
9	TRUE	FALSE	FALSE	TRUE	TRUE
10	TRUE	FALSE	TRUE	FALSE	TRUE
11	TRUE	FALSE	TRUE	TRUE	TRUE
12	TRUE	TRUE	FALSE	FALSE	FALSE
13	TRUE	TRUE	FALSE	TRUE	TRUE
14	TRUE	TRUE	TRUE	FALSE	TRUE
15	TRUE	TRUE	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

(A OR B) AND (C OR D)

Classification: contingent

g1 = OR(A, B), g2 = OR(C, D), g3 = AND(g1, g2); output g3. Three gates in two levels.

Questions

Why does an inverter count as a gate?

Because it is one: a NOT has a cost in parts and in delay like any other gate, and leaving it out changes the function. NOT A AND B needs an inverter and an AND, two gates; NOT (A AND B) is one NAND gate, or an AND and an inverter. Count what the formula actually needs.

Related

Lessons

Lesson 1: NOT, AND, OR: the basic operators (beginner, 10 min)

See also

Practice

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build 2026-11-07. Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.