Logic

Mathematics is the only subject where you cannot get the wrong answer by accident. Either your argument is logically valid or it is not, and there is no "mostly true" in between. Logic is the grammar that makes this discipline possible — the rules for combining true statements to produce other true statements, and for spotting the gap when an argument secretly does something it should not.

What a statement is

A statement (or proposition) is a sentence that is either true or false — not both, not neither. "$2 + 2 = 4$" is a statement (true). "$\sqrt{2}$ is rational" is a statement (false). "$x + 1 = 5$" is NOT a statement unless we are told what $x$ is — it is an open formula. "Is mathematics beautiful?" is also not a statement — it has no truth value.

The four connectives

From simple statements you build complicated ones using four logical connectives:

And $(P \wedge Q)$: true exactly when BOTH $P$ and $Q$ are true.

Or $(P \vee Q)$: true exactly when AT LEAST ONE of $P, Q$ is true. (Mathematicians always use "or" inclusively — both being true counts.)

Not $(\neg P)$: true exactly when $P$ is false.

If...then $(P \Rightarrow Q)$: FALSE only when $P$ is true and $Q$ is false. In every other case — including when $P$ is false — the implication is true ("vacuously"). This last point trips up beginners; see the trap below.

The widget below builds the truth tables for these connectives line by line. Watch how $P \Rightarrow Q$ behaves in the $P = \text{false}$ rows — both come out true. Then type your own expression (e.g., P AND (NOT Q) or NOT P OR Q) to see its column appear:

Implication, converse, and contrapositive — do not confuse them

From any implication $P \Rightarrow Q$ you can form three relatives:

The original: $P \Rightarrow Q$.

The converse: $Q \Rightarrow P$. NOT logically equivalent to the original. ("If it rains, the ground is wet" is true; "if the ground is wet, it must be raining" is false — a sprinkler also makes the ground wet.)

The contrapositive: $\neg Q \Rightarrow \neg P$. Logically equivalent to the original. ("If the ground is not wet, then it did not rain" says exactly the same thing as "if it rains, the ground is wet" — they have the same truth table.)

The contrapositive is the engine of proof by contrapositive: to prove "if $P$ then $Q$," prove the contrapositive instead. Sometimes it is much easier.

Try it

• State the contrapositive of "If $n^2$ is even, then $n$ is even." Is the contrapositive easier or harder to prove than the original?
• Truth-tableise $P \Rightarrow Q$: list the four cases of $(P, Q)$ and the truth value of $P \Rightarrow Q$ in each. The result should match the rule above.
• What is the negation of "for all $x \in \mathbb{R}, x^2 \geq 0$"? (Hint: the negation of "for all" is "there exists".)
• You read "all squares are rectangles." What is the converse? Is the converse true?

Pause: students confuse "$P \Rightarrow Q$ is true" with "$P$ is true and $Q$ is true." They are NOT the same. "If pigs fly then $2 + 2 = 5$" is true. Why?

A trap to watch for

The most damaging logical confusion is mistaking "$P \Rightarrow Q$" for "$P \Leftrightarrow Q$." A theorem of the form $P \Rightarrow Q$ does NOT automatically come with its converse. "Every square is a rectangle" is true; "every rectangle is a square" is false. To prove an "if and only if" statement, you must prove both directions separately. The fix: when reading a theorem, identify the hypothesis and conclusion explicitly. Ask "does this theorem say the converse?" If it does not, do not assume it.

What you now know

You can identify a statement, combine statements with the four connectives, distinguish a conditional from its converse and contrapositive, and recognise the contrapositive as a logically valid proof technique. The next section introduces sets — the language in which every mathematical object is now packaged.

Quick check

References

• Lang, S. (1971). Basic Mathematics. Springer. Intermezzo, §2 — the four connectives and the converse / contrapositive distinction.
• Velleman, D. (2019). How to Prove It: A Structured Approach, 3rd ed. Cambridge. Chapters 1 and 3 — the canonical introduction to propositional logic for math students.
• Halmos, P. (1974). Naive Set Theory. Springer. Chapter 1 — logic and quantifiers as the prerequisite to set theory.