IB COMPUTER SCIENCE | A1.2.4 Construct and Analyse Truth Tables

Lesson objective

Construct and analyse truth tables from logic diagrams, problem descriptions and Boolean expressions. Use Boolean algebra and Karnaugh maps to simplify the output expression.

Learn

A1.2.4 | CONSTRUCT AND ANALYSE TRUTH TABLES

01 | A TABLE THAT CHECKS EVERY POSSIBILITY

Suppose a lamp should come on when the room is dark or someone requests it manually, but never when it is disabled. Testing one example might make the rule look correct. What about a manual request while the lamp is disabled? A truth table prevents us overlooking that case.

A truth table lists every possible combination of logical inputs and the output produced for each one. Each row is a separate case. It is not a sequence of events and does not mean a sensor changes over time.

We use 0 for FALSE and 1 for TRUE. Define what each signal means before calculating: a 1 can mean “disabled” just as easily as “enabled”. The meaning comes from the signal definition, not the digit alone.

02 | HOW MANY ROWS DO WE NEED?

One independent Boolean input has two possibilities: 0 or 1. Adding another independent input doubles the number of combinations because the new input can be 0 or 1 for each existing combination.

For n independent Boolean inputs, there are 2n input combinations. Two inputs need four rows; three need eight; four need sixteen. Count distinct inputs, not the number of gate symbols or the number of times a letter appears.

For X = A AND (NOT A), there is only one independent input, A. NOT A is calculated from A and cannot vary independently. That table needs two input rows, not four.

Independent inputs Calculation Input rows
1 2¹ 2
2 2² 4
3 2³ 8
4 2⁴ 16

03 | BUILD THE INPUT COLUMNS SYSTEMATICALLY

For two inputs named A and B, list 00, 01, 10 and 11. For three inputs, count in binary from 000 to 111. Each combination appears once, so there are no duplicates or missing cases.

The rightmost column changes every row. The next changes every two rows, and the next every four. In an eight-row table, A is 00001111, B is 00110011 and C is 01010101. This repeating pattern is a practical way to construct the inputs.

Other row orders can be valid if they include each combination exactly once. A consistent binary order makes mistakes easier to spot and comparisons easier to read.

Row A B C
1 0 0 0
2 0 0 1
3 0 1 0
4 0 1 1
5 1 0 0
6 1 0 1
7 1 1 0
8 1 1 1

04 | APPLY ONE GATE TO EACH ROW

Once the inputs are fixed, apply the gate’s rule independently on each row. Do not copy an output from the previous row just because the inputs look similar.

For two-input AND, only 1,1 gives 1. For inclusive OR, at least one 1 is enough, so 1,1 also gives 1. XOR instead gives 1 when the two inputs differ. This is why the final row is a useful check when comparing OR and XOR.

A B A AND B A OR B A XOR B
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

For NOT, reverse the one input. NAND, NOR and XNOR invert the complete AND, OR and XOR result respectively. Parentheses tell you which result is inverted.

05 | TURN A LOGIC DIAGRAM INTO A TRUTH TABLE

Our lamp uses three inputs: A = room is dark, B = manual lamp request, and C = lamp disabled. Output X = 1 means “lamp on”.

Logic diagram for the lamp A and B enter an OR gate to produce P. C enters a NOT gate to produce Q. P and Q enter an AND gate to produce X. A B C OR NOT P Q AND X
Follow the wires from A, B and C to the output X.

To turn the logic diagram into a truth table, start at the inputs and work towards X. Trace each gate in order and give its output a column. The OR and NOT gates can be evaluated independently before the final AND gate.

The rule is X = (A OR B) AND (NOT C). Start with A, B and C, then add an intermediate column P = A OR B and another Q = NOT C. Finally calculate X = P AND Q.

An intermediate output is a result inside the calculation. It is not a new independent input. Eight rows still cover the entire circuit because only A, B and C can vary independently.

Using extra columns makes your reasoning visible. It is much easier to find an incorrect OR result than to debug an unexplained final column.

06 | WORK THROUGH ONE ROW SLOWLY

Take A = 0, B = 1 and C = 0. The room is not dark, someone requests the lamp, and it is not disabled.

First calculate P = 0 OR 1 = 1. Then calculate Q = NOT 0 = 1. Finally X = 1 AND 1 = 1. The lamp receives an on command.

Now change only C to 1. P stays 1, but Q becomes 0. X = 1 AND 0 = 0. The disable condition overrides the request because the final AND requires both intermediate results to be 1.

A B C P = A OR B Q = NOT C X = P AND Q
0 1 0 1 1 1
0 1 1 1 0 0

07 | THE COMPLETE EIGHT-ROW TABLE

A B C P = A OR B Q = NOT C X = P AND Q
0 0 0 0 1 0
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 1 0 0
1 0 0 1 1 1
1 0 1 1 0 0
1 1 0 1 1 1
1 1 1 1 0 0

Read across one row to follow a calculation. Read down X to see the complete behaviour. Here X is 1 for 010, 100 and 110. Those are the combinations where there is a request and the lamp is not disabled.

Notice every row with C = 1 has X = 0. That supports the requirement “never on when disabled” across all combinations, not merely the first example we tested.

08 | STEP THROUGH THE CALCULATION

Select a row, predict the two intermediate outputs, then reveal each stage. The highlighted cell shows the current stage. Use the previous-stage button to revisit a result without changing the inputs.

Selected row: X = (A OR B) AND (NOT C)
A B C P = A OR B Q = NOT C X = P AND Q

09 | CONSTRUCT A TABLE YOURSELF

Complete the output for X = (A XOR B) OR C. First ask whether A and B differ. Then OR that result with C. When C is 1, the final OR must give 1.

Choose 0 or 1 in every row, then check your table. Feedback identifies the rows to revisit. Reveal the worked table after you have tried it, or reset for another attempt.

Complete X = (A XOR B) OR C
A B C Your X Feedback

10 | ANALYSE WHAT THE OUTPUT TELLS YOU

To analyse a table, describe the pattern in terms of the inputs. “The output column is 00101010” is less useful than identifying exactly when the output is 1 and explaining why. Always state the row order if you do quote an output sequence.

For the lamp, X = 1 when C = 0 and at least one of A or B is 1. X = 0 if C = 1, or if A and B are both 0. These statements describe the whole table.

You can also test a claim. “B alone guarantees X = 1” is false: A = 0, B = 1, C = 1 is a counterexample. One row is enough to disprove an “always” claim. To establish a claim over the table, check every relevant row.

11 | COMPARE EXPRESSIONS FAIRLY

Two expressions are logically equivalent if they produce the same output for every combination of their shared input variables. Matching one or two rows is not enough. Align the inputs first, then compare the output columns row by row.

For example, NOT (A AND B) and (NOT A) OR (NOT B) are equivalent. Both describe NAND. But (NOT A) AND B is not equivalent to NAND: for A = 0, B = 0 it gives 0 while NAND gives 1.

The comparison below illustrates equivalence and a tempting incorrect expression. You do not need to memorise an algebraic proof to use a complete truth table as evidence.

NAND compared with another expression
A B NOT (A AND B) Other output Match?

12 | ALWAYS TRUE, ALWAYS FALSE OR SOMETIMES TRUE?

A final output column containing only 1s represents a tautology, such as A OR (NOT A). A column containing only 0s represents a contradiction, such as A AND (NOT A). An expression that is true for some combinations and false for others is contingent.

These descriptions concern the expression over every possible input. A row where X = 0 does not make the entire expression a contradiction. Similarly, a system can legitimately have an all-zero output for some requirements; a truth table describes behaviour, while the requirements tell you whether that behaviour is appropriate.

A NOT A A OR (NOT A) A AND (NOT A)
0 1 1 0
1 0 1 0

13 | TURN A REQUIREMENT INTO A TABLE

A school equipment locker releases only when a valid card is present and the safety lock is not active. Define V = valid card and L = safety lock active. Let R = release command.

List the four input combinations and apply the wording directly. With no valid card, both rows give R = 0. With a valid card and an active lock, R is still 0. Only V = 1 and L = 0 gives R = 1. This gives the expression R = V AND (NOT L). The NOT L column shows whether the lock is inactive.

V L NOT L R
0 0 1 0
0 1 0 0
1 0 1 1
1 1 0 0

This is a simplified logical model, not a complete security or safety design. Real hardware also needs appropriate physical controls, timing and handling of faults. The table lets us check the stated Boolean rule precisely.

14 | WRITE A BOOLEAN EXPRESSION FROM A TRUTH TABLE

Return to the lamp circuit’s output column. Three input combinations produce X = 1. Write an AND term for each of those rows. Use the variable itself for a 1 and its negation for a 0.

  • ABC = 010 gives (NOT A) AND B AND (NOT C).
  • ABC = 100 gives A AND (NOT B) AND (NOT C).
  • ABC = 110 gives A AND B AND (NOT C).

OR the three terms together. Each term is true for exactly one row. The result is a sum of products, an OR of AND terms. This gives a starting expression even if all you have is the output column.

15 | SIMPLIFY USING BOOLEAN ALGEBRA

Factor out NOT C because it appears in every term. Group the last two terms so that B and NOT B can combine.

  1. X = (NOT C) AND (((NOT A) AND B) OR (A AND ((NOT B) OR B)))
    Use the distributive law to factor out NOT C, then A.
  2. X = (NOT C) AND (((NOT A) AND B) OR A)
    The complement law gives (NOT B) OR B = 1. The identity law gives A AND 1 = A.
  3. X = (NOT C) AND ((A OR (NOT A)) AND (A OR B))
    Apply the distributive law to A OR ((NOT A) AND B).
  4. X = (NOT C) AND (A OR B)
    Use the complement law again, then remove the AND with 1.

The simplified expression uses one OR, one NOT and one AND. Its output still matches all eight rows of the circuit truth table.

16 | SIMPLIFY USING A KARNAUGH MAP

A Karnaugh map (K-map) rearranges a truth table so that adjacent cells differ in exactly one input. Use one cell per input combination and copy the output from the matching truth-table row.

In this three-input map, C labels the rows and AB labels the columns. Use Gray code order 00, 01, 11, 10 so that neighbouring columns differ by one bit. For example, ABC = 100 goes in row C = 0, column AB = 10. For a four-input map, use Gray code on both axes.

Lamp output X. Labels in parentheses identify the groups.
C / AB 00 01 11 10
0 0 1 (1st group) 1 (both groups) 1 (2nd group)
1 0 0 0 0
  1. Cover every 1 with rectangular groups of 1, 2, 4, 8 or more cells, using powers of two. Include only 1s. Use the largest valid groups and aim for as few groups as possible. Groups can overlap and may wrap across opposite edges. Diagonal cells do not touch.
  2. For each group, keep the inputs that stay fixed. Write a fixed 1 as the variable, a fixed 0 as its negation, and drop any input that changes. An isolated 1 therefore keeps every input.
  3. The first group covers AB = 01 and 11 at C = 0. B stays 1 and C stays 0, giving B AND (NOT C). The second group covers AB = 11 and 10 at C = 0, giving A AND (NOT C).
  4. OR the group terms to get (B AND (NOT C)) OR (A AND (NOT C)). Factoring out NOT C gives (A OR B) AND (NOT C).

For a wrap-around example, consider a row C = 0 whose only 1s are under AB = 00 and 10. Those cells are adjacent across the map edge. A changes while B and C stay 0, so the pair gives (NOT B) AND (NOT C).

17 | CONSTRUCT AND ANALYSE WITH CONFIDENCE

To construct, identify the independent inputs, calculate the number of rows, list each combination once, label intermediate columns and apply the operations in the expression’s grouping. Finish every output cell.

To analyse, identify the combinations producing 1 or 0, interpret them using the signal definitions and use specific rows as evidence. For equivalence, compare all aligned rows; for a false “always” claim, give a counterexample.

Common mistakes include omitting 111, counting an intermediate result as another input, confusing OR with XOR, and applying NOT to one input when it should invert a whole bracket. Recheck those points before assuming the arithmetic is the problem.

Next you will use the same relationships to construct logic diagrams. The expression, diagram and truth table are different ways of representing the same logical behaviour.

MATCH THE TRUTH-TABLE IDEA TO ITS MEANING

Terminology

Terminology

Sum of products

A Boolean expression formed by OR-ing AND terms.

Karnaugh map

A grid of output values ordered so that adjacent cells differ in exactly one input.

Gray code

An ordering such as 00, 01, 11, 10 where successive labels differ by one bit.

K-map group

A rectangle containing a power of two adjacent 1s. Only inputs fixed throughout the group appear in its AND term.

Complement law

A OR (NOT A) = 1 and A AND (NOT A) = 0.

Distributive law

Allows terms to be expanded or factored, for example A AND (B OR C) = (A AND B) OR (A AND C).

Truth table

A table showing outputs for every possible input combination.

Boolean input

An input taking one of two logical values.

Independent input

An input that can vary independently in the model.

Input combination

One complete assignment of values to the independent inputs.

Output column

The results of an expression for the listed input combinations.

Intermediate output

A calculated result used by a later operation.

Boolean expression

A notation describing logical operations and grouping.

Row count

For n independent Boolean inputs, 2 to the power n.

Binary row order

Listing combinations by counting from all zeros to all ones.

NOT

Reverses a single logical value.

AND

Produces 1 only when both inputs are 1.

OR

Produces 1 when at least one input is 1.

XOR

For two inputs, produces 1 when the inputs differ.

NAND

The complement of an AND result.

NOR

The complement of an OR result.

XNOR

For two inputs, produces 1 when the inputs are equal.

Inversion

Changing a logical value to its opposite.

Parentheses

Symbols grouping operations so the intended evaluation is clear.

Logical equivalence

Matching output for every combination of shared inputs.

Counterexample

A specific case disproving a general claim.

Tautology

An expression true for every input combination.

Contradiction

An expression false for every input combination.

Contingent expression

An expression true for some combinations and false for others.

Signal definition

The meaning assigned to 0 and 1 for a signal.

Construct

Build a complete representation following its rules.

Analyse

Examine relationships and use evidence to explain behaviour.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. How many rows are needed for three independent Boolean inputs?
2. Which belong in a complete two-input table?
3. For X = A AND (NOT A), which statements are correct?
4. For P = A OR B with A = 1 and B = 1, what is P?
5. For X = (A OR B) AND NOT C with A = 0, B = 1, C = 0, which are correct?
6. Which input makes the lamp output 0 regardless of A and B?
7. What establishes logical equivalence?
8. Which disproves “B = 1 always makes the lamp turn on”?
9. Which descriptions are accurate?
10. Which help prevent construction errors?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Construct the complete table for X = A XOR B.

2. Explain why four independent inputs need sixteen rows.

3. Construct the table for X = A AND NOT B, including an intermediate column.

4. Analyse when the lamp X = (A OR B) AND NOT C is on.

5. Explain why an intermediate output does not increase the independent input count.

6. Construct a table to compare OR and XOR.

7. Show using a table that NOT (A OR B) equals (NOT A) AND (NOT B).

8. Give a counterexample to “A = 1 guarantees X = 1” for the lamp.

9. Describe a systematic method for constructing a three-input table.

10. Construct the table for R = V AND NOT L and interpret its only true row.

CONSTRUCT IT | A LOCKER RELEASE

A locker releases if a valid card V or staff override S is present, but only when safety lock L is not active. Define the release output R. Write an expression, construct all eight rows with intermediate columns and describe exactly when R is 1. Give a counterexample to the claim that a staff override always releases the locker.

SIMPLIFY AN OUTPUT EXPRESSION

A warning light W comes on when the machine is running and either the guard is open or the test switch is pressed. Let A = guard open, B = machine running and C = test switch pressed.

  1. Use the description to construct the truth table for W.
  2. Write a sum-of-products expression for the rows where W = 1.
  3. Use a Karnaugh map to simplify your expression.
  4. Use Boolean algebra to simplify the same sum-of-products expression.
Reveal worked answer

W = 1 for ABC = 011, 110 and 111. In binary input order, the output column is 0, 0, 0, 1, 0, 0, 1, 1. The three AND terms are (NOT A) AND B AND C, A AND B AND (NOT C), and A AND B AND C.

On the map, group 011 with 111 to get B AND C. Group 110 with 111 to get A AND B. OR the two terms to get (B AND C) OR (A AND B).

For the algebraic method, factor out B, then group the terms containing A. Inside the brackets, A AND ((NOT C) OR C) reduces to A. This leaves A OR ((NOT A) AND C), which distributes to (A OR (NOT A)) AND (A OR C), then reduces to A OR C. The result is W = B AND (A OR C), equivalent to the map result.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

    Selections are kept while this page is open.

    Workbook

    Workbook

    COMING SOON

    The workbook for A1.2.4 Construct and Analyse Truth Tables is coming soon. Complete the matching task and written questions in your exercise book.