ITPEC FE Morning October 2020 Question 2
A contradiction is a Boolean expression that always evaluates as FALSE for any assignment of truth values to its variables. Which of the following is a contradiction? Here, " · ", " + ", and " ‾ " represent the AND, OR, and NOT operators, respectively.
Explanation
The first expression, which simplifies to 0 — distributing leaves a product that contains both q and q, so it is FALSE for every input.
Distribute p over the bracket:
- •p · (p + q) = p · p + p · q = 0 + p · q = p · q
- •Then p · q · q, and q · q = 0, so the whole expression is 0
Answer (a)
Why not others:
- •(b) — p · q · p + p · q · q = 0 + p · q, which is 1 when p = 1, q = 0
- •(c) — by absorption p + p · q = p, which is 1 whenever p = 1
- •(d) — p + p · q = p + q, and adding q gives q + q = 1: it is always TRUE, a tautology, the opposite of a contradiction
Key rule: A product is a contradiction as soon as it contains a variable and its complement, since x · x = 0; a sum containing both, x + x = 1, makes a tautology.
Basic Theory · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.