Mathematical Reasoning
The logic beneath every proof — telling a statement from an ordinary sentence, combining and negating statements with precision, and recognising when an argument is genuinely valid
- What makes a sentence a statement, and the idea of a truth value.
- Negation, and how to combine statements with the connectives "and" and "or".
- The quantifiers \(\forall\) ("for all") and \(\exists\) ("there exists"), and how to negate them.
- Implications, the biconditional, and the language of necessary and sufficient conditions.
- The converse, inverse and contrapositive, and why a statement equals its contrapositive.
- Truth tables, logical equivalence with De Morgan's laws, and the standard methods of proof.
Statements
Mathematical reasoning rests on a single sharp idea: a statement is a sentence that is either true or false, but not both. That true-or-false label is its truth value. Questions, commands, exclamations, opinions and open sentences (those containing a variable whose value is not fixed) are not statements, because no definite truth value can be attached to them.
"The number \(7\) is prime" is a statement (true); "Close the window" is not (a command); "\(x+2=5\)" is not (its truth depends on \(x\)); and "Algebra is beautiful" is not (an opinion). We label statements with small letters \(p,q,r\) so they can be manipulated like algebraic symbols.
Negation
The negation of a statement \(p\), written \(\neg p\) ("not \(p\)"), simply reverses its truth value: if \(p\) is true then \(\neg p\) is false, and vice versa. The negation is not formed by adding "not" carelessly, but by denying exactly what the statement asserts.
Negating twice returns the original statement. The negation of "\(\sqrt{2}\) is rational" is "\(\sqrt{2}\) is not rational", and the negation of "all triangles are equilateral" is "there is a triangle that is not equilateral" — note how the quantifier flips, a point made precise in Section 34-4.
Compound Statements & Connectives
Joining statements with connectives builds compound statements. The connective "and" (\(\wedge\), conjunction) demands that both parts hold; "or" (\(\vee\), disjunction) asks only that at least one hold. These behave exactly like intersection and union of sets.
To negate an "and" or an "or", flip the connective and negate each part: \(\neg(p\wedge q)\equiv \neg p\vee\neg q\) and \(\neg(p\vee q)\equiv \neg p\wedge\neg q\). So the negation of "it is cold and raining" is "it is not cold or it is not raining". A common error is to keep the same connective — that gives the wrong statement.
Quantifiers
Open sentences become statements once a quantifier fixes "how many". The universal quantifier \(\forall\) means "for all" or "for every"; the existential quantifier \(\exists\) means "there exists" or "for some". A single example settles an existential claim, while a single counterexample destroys a universal one.
Negation swaps the quantifiers and negates the inside. The denial of "every student passed" is "some student did not pass" — not "every student failed". This swap is one of the most frequently tested ideas in the chapter.
Implications
The implication \(p\Rightarrow q\) ("if \(p\), then \(q\)") is the backbone of every theorem. Here \(p\) is the hypothesis and \(q\) the conclusion. It claims only that \(q\) follows whenever \(p\) holds, so it is false in just one case — a true hypothesis with a false conclusion.
The phrases "\(p\) only if \(q\)", "\(p\) is sufficient for \(q\)", and "\(q\) is necessary for \(p\)" all say \(p\Rightarrow q\). The biconditional \(p\Leftrightarrow q\) ("if and only if") requires the implication to hold in both directions.
Converse, Inverse & Contrapositive
From any implication \(p\Rightarrow q\) we can form three relatives by swapping or negating its parts. Only one of them — the contrapositive — is guaranteed to carry the same truth value as the original, a fact that underlies an entire method of proof.
The converse is \(q\Rightarrow p\), the inverse is \(\neg p\Rightarrow\neg q\), and the contrapositive is \(\neg q\Rightarrow\neg p\). A statement and its contrapositive are logically equivalent, and so are the converse and inverse; but a statement and its converse are generally not.
Truth Tables & Logical Equivalence
A truth table lists every combination of truth values for the parts and computes the result, settling any question about a compound statement mechanically. Two statements are logically equivalent (\(\equiv\)) when their final columns match in every row.
A compound statement true in every row is a tautology; one false in every row is a contradiction. Building the tables for \(p\Rightarrow q\) and \(\neg p\vee q\) shows their last columns agree, proving the equivalence above without any words.
Methods of Proof
Reasoning culminates in proof — establishing a statement beyond doubt. Four methods cover almost everything in the course, and choosing the right one often makes a hard argument easy.
A direct proof assumes \(p\) and reasons forward to \(q\). A proof by contrapositive proves \(\neg q\Rightarrow\neg p\) instead, exploiting its equivalence to \(p\Rightarrow q\). A proof by contradiction assumes the statement is false and derives an impossibility — the classic route to "\(\sqrt{2}\) is irrational". And a single counterexample is enough to disprove a universal claim, since it makes \(\forall x\,p(x)\) false at once.
Putting It to Work
Problem. Which of these are statements? (a) "\(6\) is an even number." (b) "Solve the equation." (c) "\(x+3=7\)." (d) "This chapter is interesting."
Solution. (a) is a statement (true). (b) is a command, (c) is an open sentence whose truth depends on \(x\), and (d) is an opinion — none of these has a definite truth value, so only (a) is a statement.
Problem. Write the negation of "Every prime number is odd."
Solution. Swap the quantifier and negate the inside:
In words: "There exists a prime number which is not odd" — true, since \(2\) is such a prime.
Problem. Let \(p\): "\(2\) is even" and \(q\): "\(9\) is prime". Find the truth values of \(p\wedge q\) and \(p\vee q\).
Solution. Here \(p\) is true and \(q\) is false:
Problem. For "If a number is divisible by \(6\), then it is divisible by \(3\)", write the three relatives.
Solution. With \(p\): "divisible by \(6\)" and \(q\): "divisible by \(3\)":
The original and its contrapositive ("if not divisible by \(3\), then not divisible by \(6\)") are both true; the converse and inverse are both false.
Problem. Write the negation of "The sky is blue and the grass is green."
Solution. Negate each part and flip "and" to "or":
In words: "The sky is not blue or the grass is not green."
Problem. Disprove the claim "For all real \(x\), \(x^2>x\)."
Solution. A single counterexample is enough; take \(x=\tfrac12\):
The inequality fails here, so the universal statement is false.
Chapter Summary
A sentence that is true or false but not both; label it \(p,q,r\).
\(\neg(p\wedge q)\equiv\neg p\vee\neg q\); \(\neg(p\vee q)\equiv\neg p\wedge\neg q\).
\(\neg(\forall x\,p)\equiv\exists x\,\neg p\); one counterexample kills \(\forall\).
\(p\Rightarrow q\equiv\neg p\vee q\); false only when \(p\) true, \(q\) false.
\(p\Rightarrow q\equiv\neg q\Rightarrow\neg p\); converse is not equivalent.
Direct, contrapositive, contradiction, or disproof by counterexample.
Problems
Name the idea first — statement, negation, connective, quantifier, implication, or proof — then apply it. Difficulty rises down the list.
- Decide which are statements: (a) "\(8<5\)", (b) "Where are you going?", (c) "\(y-1=0\)", (d) "\(0\) is a natural number".
- Write the negation of "\(\sqrt{3}\) is irrational".
- Let \(p\): "\(5>3\)" and \(q\): "\(4\) is odd". Find the truth values of \(p\wedge q\) and \(p\vee q\).
- Write the contrapositive of "If it rains, then the match is cancelled".
- Write the converse and the inverse of "If a triangle is equilateral, then it is isosceles".
- Write the negation of "There exists a real number whose square is negative".
- Identify the connective in "\(7\) is prime and \(7\) is odd", and state whether the compound statement is true.
- Use De Morgan's law to negate "The bus is late or the road is blocked".
- Rewrite "\(n\) is even is sufficient for \(n^2\) to be even" as an implication, and state its contrapositive.
- Construct the truth table of \(\neg p\vee q\) and verify that it equals \(p\Rightarrow q\).
- Disprove "For every integer \(n\), \(n^2-n+11\) is prime" with a counterexample.
- Name the method best suited to proving "\(\sqrt{2}\) is irrational" and outline its first step.
- Show, using a truth table, that \(p\vee\neg p\) is a tautology and \(p\wedge\neg p\) is a contradiction.