Logic & truth-table drills

What the exam actually asks

Two logic tasks recur on every paper. Q1 hands you a definition such as *"$P \leftrightarrow Q$ means $(P \to Q) \land (Q \to P)$"* and asks you to prove the equivalence with a truth table. Q8(a) hands you English sentences and asks you to translate them into a knowledge base of implications. Both are mechanical once you have the drill in muscle memory — so we rebuild them cold here.

The truth-table method (the only method you need)

1. List every combination of the variables. Two variables ⇒ $2^2 = 4$ rows ($n$ variables ⇒ $2^n$ rows).
2. Add one column per sub-expression, evaluating inside-out.
3. Two formulas are logically equivalent iff their final columns are identical on every row.

The one fact that makes implication painless: $P \to Q$ is false on exactly one row — when $P = T$ and $Q = F$ — and true on the other three. Equivalently $P \to Q \equiv \lnot P \lor Q$.

Worked example — the past-paper pair $(\lnot P \to \lnot Q) \equiv (P \lor \lnot Q)$

This exact pair has appeared as a cold-retrieval question. Build both columns:

| $P$ | $Q$ | $\lnot P \to \lnot Q$ | $P \lor \lnot Q$ | |----|----|----|----| | T | T | T | T | | T | F | T | T | | F | T | F | F | | F | F | T | T |

For $\lnot P \to \lnot Q$: it is false only when its antecedent $\lnot P = T$ (i.e. $P = F$) and its consequent $\lnot Q = F$ (i.e. $Q = T$) — that is the single row $P{=}F, Q{=}T$. Every other row is true. The right column $P \lor \lnot Q$ is likewise false only at $P{=}F, Q{=}T$. The columns match on all four rows ⇒ EQUIVALENT. (Both reduce to $\lnot(\lnot P \land Q)$.)

The Q8 encoding step (logic half)

Forward chaining (L10.3) needs the sentences as implications. Translate each English statement into premise → conclusion:

- *"When the cat is absent, the mice are present"* ⇒ $cat\_absent \to mouse\_present$ - *"When the dog is present, the cat is absent"* ⇒ $dog\_present \to cat\_absent$ - *"When the dog is absent and the cat is absent, the mice are present"* ⇒ $dog\_absent \land cat\_absent \to mouse\_present$

Given facts $\{dog\_absent, cat\_not\_sleeping\}$. You fire these in L10.3 — here, just get the encoding exact.