Reasoning and Logic

Logic is the grammar of the rest of the syllabus. Once you can say precisely what a statement claims — and what would make it false — proofs stop being guesswork.

Propositions

A proposition is a statement that is either true or false, but not both.

• "The square root of 16 is 4" — a proposition, and true.
• "$7$ is an even number" — a proposition, and false.
• "Solve the equation" — a command, not a proposition.
• "What time is it?" — a question, not a proposition.
• "$x + 3$" — an expression, with no truth value at all.

A simple proposition contains no connective. A compound proposition is built from simpler ones joined by connectives.

Connectives and truth tables

$$\begin{array}{cc|cccc} p & q & p \wedge q & p \vee q & p \to q & p \leftrightarrow q \\ \hline T & T & T & T & T & T \\ T & F & F & T & F & F \\ F & T & F & T & T & F \\ F & F & F & F & T & T \end{array}$$

A truth table with $n$ propositions has $2^n$ rows — 4 rows for two propositions, 8 for three, 16 for four.

A compound proposition that is always true is a tautology; one that is always false is a contradiction.

$$p \vee \neg p \text{ is a tautology} \qquad p \wedge \neg p \text{ is a contradiction}$$

The conditional

$p \to q$ is the connective students find least intuitive, because it is true whenever $p$ is false.

Think of it as a promise: "If you pass the test, I will buy you lunch." The promise is broken only if you pass and get no lunch. If you fail, the promise was never tested, so it has not been broken — the statement stands as true.

This gives a useful rewriting:

$$p \to q \equiv \neg p \vee q$$

Check it against the table: $\neg p \vee q$ is false only when $\neg p$ is false and $q$ is false — that is, when $p$ is true and $q$ is false. The same single row ✓

In $p \to q$, $p$ is sufficient for $q$, and $q$ is necessary for $p$.

Converse, inverse and contrapositive

From the conditional $p \to q$:

Take "If it rains, then the match is cancelled."

• Converse: "If the match is cancelled, then it rained." (It might have been cancelled for another reason.)
• Inverse: "If it does not rain, then the match is not cancelled."
• Contrapositive: "If the match is not cancelled, then it did not rain."

Example. The contrapositive of "if $x > 3$ then $x^2 > 9$" is "if $x^2 \le 9$ then $x \le 3$". Both are true. The converse — "if $x^2 > 9$ then $x > 3$" — is false, since $x = -4$ gives $x^2 = 16 > 9$ but $x < 3$.

Logical equivalence and De Morgan's laws

Two propositions are logically equivalent, written $\equiv$, when their truth tables agree in every row.

De Morgan's laws:

$$\neg(p \wedge q) \equiv \neg p \vee \neg q$$ $$\neg(p \vee q) \equiv \neg p \wedge \neg q$$

In words: negating a compound statement flips each part and swaps and for or.

"It is not true that the shop is open and the bank is open" means "the shop is closed or the bank is closed" — at least one of them is shut.

Other laws worth recognising:

Methods of proof

Direct proof. Assume $p$ and reason to $q$.

Proof by counterexample. To disprove a universal claim, one counterexample is enough. "Every prime number is odd" is destroyed by $2$ — a single case, and the claim is finished.

Proof by contradiction. Assume the statement is false and derive an impossibility.

Proof by mathematical induction. For a statement $P(n)$ about positive integers:

1. Base case — show $P(1)$ is true.
2. Inductive step — assume $P(k)$ is true, and use that to show $P(k+1)$ is true.
3. Conclusion — therefore $P(n)$ is true for all $n \ge 1$.

Prove that $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.

Base case: when $n = 1$, the left side is $1$ and the right side is $\frac{1 \times 2}{2} = 1$ ✓

Inductive step: assume $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$. Adding the next term:

$$1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$ $$= (k+1)\left(\frac{k}{2} + 1\right) = (k+1) \cdot \frac{k+2}{2} = \frac{(k+1)(k+2)}{2}$$

which is the formula with $n$ replaced by $k+1$ ✓

Conclusion: by induction, the result holds for all $n \ge 1$.