Two statements can look different and still say the same thing. With the conditional and the truth tables you already have, you can test this precisely, and a few standard equivalences then let you rewrite statements without building a table every time.
Key idea
$A$ and $B$ are logically equivalent, written $A \equiv B$, when they have the same truth value in every row of the truth table. The most used ones are De Morgan's laws, $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ and $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$, and the conditional laws $P \to Q \equiv \neg P \vee Q \equiv \neg Q \to \neg P$.
Why it works
Why does the "and" turn into an "or" when you negate it? $P \wedge Q$ claims two things at once. To deny it, you only need one of them to fail: "not both" means "at least one is false," which is $\neg P \vee \neg Q$. In the same way, $P \vee Q$ claims at least one thing, and denying it means neither holds: $\neg P \wedge \neg Q$. For the conditional, $P \to Q$ is false only when $P$ is true and $Q$ is false; $\neg P \vee Q$ is false in exactly the same row, so they match everywhere.
| Name | Equivalence |
|---|---|
| Double negation | $\neg\neg P \equiv P$ |
| De Morgan | $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$, $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ |
| Conditional | $P \to Q \equiv \neg P \vee Q$ |
| Contrapositive | $P \to Q \equiv \neg Q \to \neg P$ |
| Negated conditional | $\neg(P \to Q) \equiv P \wedge \neg Q$ |
| Distributive | $P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$ |
Worked examples
Worked example: Checking an equivalence with a table
Is $P \to Q$ equivalent to its converse $Q \to P$? Is it equivalent to its contrapositive $\neg Q \to \neg P$?
- $P \to Q$ has column T, F, T, T (rows TT, TF, FT, FF).
- $Q \to P$ is false only when $Q$ is true and $P$ is false, row FT: column T, T, F, T. The columns differ, so the converse is not equivalent.
- $\neg Q \to \neg P$ is false only when $\neg Q$ is true and $\neg P$ is false, that is, $Q$ false and $P$ true: row TF. Column T, F, T, T, the same as $P \to Q$.
Answer: Not equivalent to the converse; equivalent to the contrapositive.
Worked example: Negating in English
Negate "The store is open and the lights are on."
- The statement is $P \wedge Q$, so its negation is $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$.
- In words: "The store is not open, or the lights are not on."
- The tempting answer "The store is not open and the lights are not on" is too strong: it says both fail, but one failure is already enough.
Answer: The store is not open, or the lights are not on.
Worked example: Rewriting with the laws
Simplify $\neg(\neg P \vee Q)$.
- De Morgan: $\neg(\neg P \vee Q) \equiv \neg\neg P \wedge \neg Q$.
- Double negation: $\neg\neg P \equiv P$, so the result is $P \wedge \neg Q$.
- Check one row: with $P$ true and $Q$ false, $\neg P \vee Q$ is false, so the original is true, and $P \wedge \neg Q$ is true too.
Answer: $P \wedge \neg Q$
Common mistake
Two common slips. First, negating "$P$ and $Q$" as "not $P$ and not $Q$"; the negation is "not $P$ or not $Q$." Second, treating a conditional as equivalent to its converse. "If it rains, the ground is wet" does not mean "if the ground is wet, it rained" (a sprinkler can wet the ground). Check by finding one row where the two statements differ; that settles it.