Chapter 2 · Computational Thinking & Algorithms
2.6Propositional Equivalence
How to prove that two logical expressions that look different always give the same result, and why that helps.
Written and checked by Muhammad Raheel(opens in a new tab)
Full Stack Developer · AI Engineer · Reviewed 21 Oct 2026 · 3 min read
On this page
Two sentences can use different words and still say the same thing. Logic works the same way. Two expressions can look very different on paper, yet give the same answer every single time. When that happens, we call them equivalent. This topic shows how to test for it and why it is useful.
The test is simple. Build a truth table for both expressions. If their results are the same in every row, they are equivalent. One different row is enough to say they are not. The book writes equivalence with the symbol ≡.
The book's example (Figure 2.6)
The figure on page 25 compares two expressions:
- Expression 1: (A AND NOT B) OR (B AND NOT A)
- Expression 2: (A OR B) AND (NOT A OR NOT B)
Here is the truth table from the figure:
| A | B | Expression 1 | Expression 2 |
|---|---|---|---|
| F | F | F | F |
| F | T | T | T |
| T | F | T | T |
| T | T | F | F |
All four rows match, so the two expressions are equivalent. Both are true only when exactly one of A and B is true. The figure calls this XOR. Its Venn diagram shades A without B and B without A, and leaves the middle (A AND B) out.
The figure has no caption in the book. The text simply calls it Figure 2.6.
Identifying Equivalent Logical Expressions
How do you find out if two expressions are equivalent? The book gives two tools.
The first tool is the truth table. You list every possible combination of truth values. Then you work out each expression in every row and compare the results.
The second tool is logical laws. These are rules that change an expression into a simpler one without changing its meaning. They help you reduce a long expression to a short one.
Importance of Equivalence in Logic
Why should you care? Because simpler is better. If a short expression means the same as a long one, you can use the short one. You save time and effort, and you are less likely to make a mistake. The book also says equivalence makes reasoning and decisions correct, and that it is useful in both mathematics and computer science.
In programming, equivalent expressions can make code more efficient.
Practice this topic
Short questions
1.What is propositional equivalence?2 marks
Answer
From the book: "Propositional equivalence is a concept in propositional logic. It explains when two logical expressions have the same meaning. Even if expressions look different, they may give the same result."
2.When are two logical expressions equivalent? Which symbol shows equivalence?2 marks
Answer
From the book: "If two expressions have the same truth values in all cases, they are equivalent. The symbol "≡" is used to show equivalence."
3.How are equivalent logical expressions identified?3 marks
Answer
From the book: "Equivalent logical expressions are identified using truth tables. Each expression is tested for all possible truth values. If the results match in every case, they are equivalent. Logical laws can also help identify equivalence."
4.Why is equivalence important in logic?3 marks
Answer
From the book: "Equivalence is important because it helps simplify logic problems. It allows us to replace complex expressions with simpler ones. This saves time and effort." It also "helps avoid logical errors" and "ensures correct reasoning and decisions."
5.How does equivalence help in programming?2 marks
Answer
From the book: "In programming, equivalent expressions improve code efficiency. Equivalence helps avoid logical errors."
6.Name the two expressions that Figure 2.6 shows are logically equivalent. In which cases are both true?3 marks
Answer
Expression 1 is "(A AND NOT B) OR (B AND NOT A)" and Expression 2 is "(A OR B) AND (NOT A OR NOT B)". From the figure: "Both expressions are true in the same cases (XOR)." Its truth table shows both are T when A = F, B = T and when A = T, B = F, and F in the other two rows.
7.What is the role of logical laws in identifying equivalence?2 marks
Answer
From the book: "Logical laws can also help identify equivalence. These laws simplify expressions. Identifying equivalence helps reduce complex expressions."
Long questions
1.Explain propositional equivalence. Describe how equivalent logical expressions are identified and why equivalence is important.8 marks
Answer
Cover all three parts, using the book's text:
- Propositional equivalence (verbatim): "Propositional equivalence is a concept in propositional logic. It explains when two logical expressions have the same meaning. Even if expressions look different, they may give the same result. Propositional equivalence is checked using truth tables. If two expressions have the same truth values in all cases, they are equivalent. The symbol "≡" is used to show equivalence."
- Example from Figure 2.6: "(A AND NOT B) OR (B AND NOT A)" and "(A OR B) AND (NOT A OR NOT B)". "Both expressions are true in the same cases (XOR)." Draw the figure's truth table: rows FF, FT, TF, TT give F, T, T, F for both expressions.
- Identifying Equivalent Logical Expressions (verbatim): "Equivalent logical expressions are identified using truth tables. Each expression is tested for all possible truth values. If the results match in every case, they are equivalent. Logical laws can also help identify equivalence. These laws simplify expressions. Identifying equivalence helps reduce complex expressions."
- Importance of Equivalence in Logic (verbatim): "Equivalence is important because it helps simplify logic problems. It allows us to replace complex expressions with simpler ones. This saves time and effort. In programming, equivalent expressions improve code efficiency. Equivalence helps avoid logical errors. It ensures correct reasoning and decisions. This concept is useful in mathematics and computer science. Understanding equivalence strengthens logical thinking."
- Close with the TIDBIT: "Equivalent expressions may look different but always give the same result; they help simplify complex logic."
Aim for 250-350 words.
2.Using a truth table, show that (A AND NOT B) OR (B AND NOT A) and (A OR B) AND (NOT A OR NOT B) are logically equivalent.6 marks
Answer
Follow the book's method: "Each expression is tested for all possible truth values. If the results match in every case, they are equivalent."
- Two propositions A and B give 4 rows: FF, FT, TF, TT.
- Work out each expression row by row (Figure 2.6's truth table):
A B (A AND NOT B) OR (B AND NOT A) (A OR B) AND (NOT A OR NOT B) F F F F F T T T T F T T T T F F - The last two columns match in every row, so the expressions are equivalent. Write the result as the figure does: "Therefore: (A AND NOT B) OR (B AND NOT A)⟺(A OR B) AND (NOT A OR NOT B)", or with the text's symbol "≡".
- Mention the figure's line: "Both expressions are true in the same cases (XOR)", and the Venn diagram: only "A AND NOT B" and "B AND NOT A" are shaded; "A AND B (not included)".
Note: the text uses "≡" for equivalence, the figure uses "⟺". Both are accepted here; "≡" is the symbol the text gives.
Aim for a full truth table plus 80-120 words.
In this chapter
- 2.1Introduction to Computational Thinking
- 2.2Problem Solving Using Computational Thinking
- 2.3Logic as a Knowledge Representation Framework
- 2.4Propositional Logic
- 2.5Truth Tables
- 2.6Propositional EquivalenceYou are here
- 2.7Propositional Satisfiability
- 2.8Predicate Logic
- 2.9Quantifiers in Predicate Logic
- 2.10Applying Predicate Logic to Real-World Problems
- 2.11Logic-Based Reasoning and Inference