06 / 18 · Make the structure visible
Same truth in every row
Use a complete truth table to test equivalence, not a few favorable examples.
Builds on Necessary or sufficient: is registration enough?
Go to practice ↓A question to keep in mind
Are 'not both' and 'at least one not' really the same condition?
Two formulas are logically equivalent when they have the same truth value under every assignment. The biconditional P ↔ Q is true when P and Q match. A formula A ↔ B is true in every row exactly when A and B are equivalent.
For n independent statement letters there are 2^n assignments. With two letters, checking all four rows is exhaustive within this propositional model. It is not empirical testing of four real cases.
De Morgan's laws give ¬(P ∧ Q) equivalent to ¬P ∨ ¬Q, and ¬(P ∨ Q) equivalent to ¬P ∧ ¬Q. A conditional P → Q is equivalent to ¬P ∨ Q and to its contrapositive ¬Q → ¬P, but not generally to Q → P.
Work through an example
- To refute equivalence between P → Q and Q → P, use P = T, Q = F: the first is F and the second T.
- To establish De Morgan's law for two letters, compare its two sides at T,T; T,F; F,T; F,F. No mismatching row exists.
- The reason this works is completeness of the small truth table, not how many examples happen to agree.
Your turn
0 / 3Test the two sides of 'not both'.
Read solution · does not award completion
- P=T, Q=T →
¬(P ∧ Q): F;¬P ∨ ¬Q: F - P=T, Q=F →
¬(P ∧ Q): T;¬P ∨ ¬Q: T - P=F, Q=T →
¬(P ∧ Q): T;¬P ∨ ¬Q: T - P=F, Q=F →
¬(P ∧ Q): T;¬P ∨ ¬Q: T
The columns match in all four rows. This proves this propositional equivalence.
Which is always equivalent to P → Q?
Read solution · does not award completion
¬Q → ¬P
If a sufficient condition held without its necessary condition, the original rule would fail.
Three independent letters give how many truth-table rows?
Read solution · does not award completion
8
Exhaustive enumeration is reliable for small propositional formulas, but grows exponentially.
Bring it back to your own work
Take a 'not both' constraint from everyday life. Rewrite it with 'or', and test the case in which exactly one condition holds.