Logic Gates and Circuits

For longer questions the examiner gives the circuit and asks for the truth table for every input combination. The cleanest method is to add one column per gate in the order the signals flow, then fill in the table row by row.

Method. (1) Write down every input combination (2ⁿ rows). (2) Add an intermediate column for each internal gate, named after the gate (X, Y or Gate 1, Gate 2). (3) Fill in each intermediate column by applying the gate's rule to its input columns, row by row. (4) The final-output column Q is built from whatever feeds the last gate, using its rule.

Example — the circuit Q = (A AND B) AND NOT C.

There are three inputs (A, B, C), so there are 8 rows. The internal gates are:

• An AND gate with inputs A, B. Call its output X = A AND B.
• A NOT gate with input C. Call its output Y = NOT C.
• An AND gate with inputs X and Y. Its output is the final Q.

Filling in A AND B (which is 1 only on rows where both A and B are 1) and NOT C (which flips the C column), then ANDing the two intermediate columns:

Reading off the final column: this circuit outputs 1 on exactly one row, where A = 1, B = 1, C = 0.

You can sanity-check a single row by hand. Take row 7 (A = 1, B = 1, C = 0): A AND B = 1, NOT C = 1, 1 AND 1 = 1. Correct.

Example — a smaller circuit: Q = (NOT A) AND B.

Two inputs means 4 rows. One intermediate column (X = NOT A):

Output Q is 1 only when A = 0 and B = 1.