Gate diagrams to Boolean expressions: exercises with answers

Ten small gate networks described in words. For each one, write the Boolean expression the output computes, one subexpression per gate, with a gate that feeds another written inside its parentheses. The formula under each problem is the answer, with its truth table.

Read a network from the inputs to the output: every gate becomes an operator applied to the expressions on its input wires, and a gate whose output feeds another gate becomes a parenthesised subexpression. Two-input gates map to AND, OR, XOR, NAND(…, …), NOR(…, …) and XNOR(…, …); an inverter is NOT. A three-input AND or OR is one operator with three operands, written as a chain without parentheses.

Several networks compute well-known functions: the full adder's sum (two XOR gates), the majority function (three ANDs into an OR), a 2-to-1 multiplexer, and a NAND feeding both inputs of a second NAND, which is an AND. Where the simplifier can shorten the hand-written formula, the step list shows the law: (A XOR B) XOR C is flattened by associativity, and the double NAND is folded by idempotence.

1. An AND gate on A and B feeds an OR gate together with C. Write the output.

(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

The AND gate is the inner subexpression and the OR gate is the outer operator: (A AND B) OR C. Without parentheses the formula reads the same way, because AND binds tighter than OR, but writing them keeps the gate structure visible.

2. An inverter on A feeds an AND gate together with B. Write the output.

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

NOT A AND B: the inverter applies to A only, before the AND. NOT (A AND B) would describe an inverter after the AND, a NAND.

3. Two AND gates, one on A and B and one on C and D, feed an OR gate. Write the output.

(A AND B) OR (C AND 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	TRUE
4	FALSE	TRUE	FALSE	FALSE	FALSE
5	FALSE	TRUE	FALSE	TRUE	FALSE
6	FALSE	TRUE	TRUE	FALSE	FALSE
7	FALSE	TRUE	TRUE	TRUE	TRUE
8	TRUE	FALSE	FALSE	FALSE	FALSE
9	TRUE	FALSE	FALSE	TRUE	FALSE
10	TRUE	FALSE	TRUE	FALSE	FALSE
11	TRUE	FALSE	TRUE	TRUE	TRUE
12	TRUE	TRUE	FALSE	FALSE	TRUE
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 AND B) OR (C AND D)

Classification: contingent

(A AND B) OR (C AND D), a sum of two products: three gates in two levels.

4. An OR gate on A and B feeds an inverter. Write the output.

NOT (A OR B)

#	A	B	f
0	FALSE	FALSE	TRUE
1	FALSE	TRUE	FALSE
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 OR B)

Classification: contingent

NOT (A OR B), which is one NOR gate, NOR(A, B): TRUE only on A = FALSE, B = FALSE.

5. An XOR gate on A and B feeds a second XOR gate together with C (the sum output of a full adder). Write the output.

(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

(A XOR B) XOR C

Associativity · (A XOR B) XOR C = A XOR B XOR C
(A XOR B) XOR C → A XOR B XOR CResult: A XOR B XOR C

A XOR B XOR C · verified equivalent on every row · simplified, not minimal

Classification: contingent

(A XOR B) XOR C. The step list flattens it by associativity to A XOR B XOR C, the parity of the three inputs, TRUE on the rows with one or three TRUE inputs.

6. An OR gate on A and B and an OR gate on C and D feed an AND gate. Write the output.

(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

(A OR B) AND (C OR D), a product of two sums; the parentheses are required here, since OR binds less tightly than AND.

7. A NAND gate on A and B feeds both inputs of a second NAND gate. Write the output and say what it computes.

NAND(NAND(A, B), NAND(A, B))

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

NAND(NAND(A, B), NAND(A, B))

Idempotence · NAND(A, A) = NOT A
NAND(NAND(A, B), NAND(A, B)) → NOT NAND(A, B)Result: NOT NAND(A, B)

NOT NAND(A, B) · verified equivalent on every row · simplified, not minimal

Classification: contingent

NAND(NAND(A, B), NAND(A, B)). A NAND with both inputs tied is an inverter, so the network is NOT of NAND, that is A AND B; the step list folds the repeated operand by idempotence to NOT NAND(A, B).

8. An AND gate on A and B, and an AND gate on C and the inverted A, feed an OR gate (a 2-to-1 multiplexer with A as select). Write the output.

(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

(A AND B) OR (NOT A AND C): when A is TRUE the output copies B, when A is FALSE it copies C. Four gates: the inverter, two ANDs and the OR.

9. Three AND gates, on A and B, on A and C and on B and C, feed a three-input OR gate. Write the output.

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

#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	FALSE
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 (A AND C) OR (B AND C)

Classification: contingent

(A AND B) OR (A AND C) OR (B AND C), the majority function: TRUE when at least two inputs are TRUE. The three-input OR is one operator with three operands.

10. An AND gate on A and B, and an AND gate on C and the output of an XOR gate on A and B, feed an OR gate (the carry output of a full adder). Write the output.

(A AND B) OR ((A XOR B) AND C)

#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	FALSE
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 ((A XOR B) AND C)

Classification: contingent

(A AND B) OR ((A XOR B) AND C). Its table is TRUE on the same four rows as the majority function of problem 9, so the two networks compute the same carry; the step list shows no law, because the simplifier does not expand XOR here.

Questions

Does the order of inputs on a gate matter?

Not for AND, OR, XOR, NAND, NOR and XNOR, which are commutative: NAND(A, B) and NAND(B, A) are the same function. It does matter for which signal goes through an inverter, and for the data and select inputs of a multiplexer, so name the wires before you write the formula.

Lessons

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

Glossary

Combinational logic: meaning and examples

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.

Gate diagrams to Boolean expressions: exercises with answers

Questions

Related

Lessons

Glossary

See also

Practice