The Language of Proof in HSC

Related Content Outcome

  • MEX-P1 The Nature of Proof

This post will primarily look at the following dot-point from page 28 of the Extension II syllabus:

  • use the formal language of proof, including the terms statement, implication, converse, negation and contrapositive (ACMSM024)
    • –  use the symbols for implication (⇒), equivalence (⇔) and equality (=) , demonstrating a clear understanding of the difference between them (ACMSM026)
    • –  use the phrases ‘for all’ (∀), ‘if and only if’ (𝑖𝑓𝑓) and ‘there exists’ (∃) (ACMSM027)
    • –  understand that a statement is equivalent to its contrapositive but that the converse of a true statement may not be true

The purpose of this post is not to re-explain everything that would have been covered in the textbooks but to give the reader some extra tips and tricks, with example applications from the 2020 HSC paper and other school trial papers.

This post will not delve into too much detail of these tricks without the proper logical framework – one should look at studying MATH3066 at the University of Sydney for a more fleshed out course in the Foundations of Mathematics. A lot of what I learned here is from the legacy course MATH3065 Logic and Foundations lectured by Dr. David Easdown, and I have him to thank for my education in Logic.

Truth Tables

I find it interesting as much as shocking that the syllabus fails to mention the logical connectives ‘and‘ and ‘or‘, but expects students to learn negation (‘not‘), implication (‘if … then …‘) and equivalence (‘if and only if … then …‘) as well as their associated symbols. The syllabus also fails to mention any need to study the Truth values of statements as they interact with each other using these connectives.

To help understand these logical connectives, I would suggest learning their Truth tables. Essentially, a Truth table tabulates all the possibilities of the final truth value when two (or more) statements interact with each other via these logical connectives.

For the following, P and Q are logical statements.

Negation

P¬P
TF
FT
How to read this truth table: If P is True, then its negation not P is False. If P is False, then its negation not P is True.

And (Conjunction)

PQP Q
TTT
TFF
FTF
FFF
Connecting two statements with ‘and’ is True whenever P and Q are both True. If at least one of them is False, then ‘P and Q’ is False.

Or (Disjunction)

PQP Q
TTT
TFT
FTT
FFF
Connecting two statements with ‘or’ is True whenever at least one of P or Q are True. If both of them are False, then ‘P or Q’ is False.

Implication

PQP ⇒ Q
TTT
TFF
FTT
FFT
If a True statement implies a False statement, then that implication is False.

This one is the least intuitive to understand when P is a False statement. One quick way to reconcile this is to look at an example:

We know that Pythagoras’ Theorem can be written as the implication:

If a triangle with sides \(a\), \(b\), \(c\) with \(c > a\) and \(c > b\) is right-angled, then \(c^2 = a^2 + b^2\).

In Pythagoras’ Theorem, P is the statement ‘a triangle with sides \(a\), \(b\), \(c\) with \(c > a\) and \(c > b\) is right-angled’ and Q is the statement ‘\(c^2 = a^2 + b^2\)’.

Applying this Theorem to a triangle that isn’t a right-angled triangle will make the statement P False. No matter what the result of Q is, whether it is True or False does not matter, it will not disprove the Theorem (and make it False). As statements must either be True or False but not both, this means that P ⇒ Q must necessarily be True for when P is a False statement.

Converse, Inverse, Contrapositive

Given an implication P⇒Q, its:

  • Inverse is: ¬P⇒¬Q
  • Converse is: Q⇒P, also read as ‘only if P then Q’. Note the order of P and Q and the direction of the implication.
  • Contrapositive is: ¬Q⇒¬P. This is logically equivalent to the original implication. One can construct Truth tables to see that they have the same Truth values:
PQ¬P¬Q¬Q ⇒ ¬P
TTFFT
TFFTF
FTTFT
FFTTT
Compare the truth values of P⇒Q and ¬Q⇒¬P to see they are the same.

Logical Equivalence

When we join the implication and its converse together with the logical connective ‘and’, we get something that reads like this:

‘if P then Q’ and ‘only if P then Q’

This can be shortened to ‘if and only if P then Q’. The natural way to combine the symbols for ‘(P⇒Q)(Q⇒P)’ would then be a double arrow ⇔.

Implication Technically Doesn’t Need Its Own Symbol

This is the first important result that isn’t specifically mentioned in the HSC but learning it will make light work of the seemingly difficult questions found in some trial papers and Question 8 of the 2020 HSC paper.

The implication P⇒Q is logically equivalent to a statement that relies only on disjunction and negation. Nevertheless, the ⇒ notation makes it much more intuitive to understand as a directional movement of going from one statement towards another statement.

Let’s have a look at the truth table for the following:

PQ¬P¬PQ
TTFT
TFFF
FTTT
FFTT
The truth table for ¬PQ is the same as P⇒Q!

This is a very important result:

P⇒Q is the same as ¬P∨Q.

De Morgan’s Laws

Another important result in Set Theory as well as Logic (which both have operations that are under the same category called Boolean Algebras) is De Morgan’s Laws. In set theory, De Morgan’s Laws are:

  • \((A\cup B)^c = A^c \cap B^c\)
  • \((A\cap B)^c = A^c \cup B^c\)

Similarly in Logic:

  • \(\neg(A \lor B) = \neg A \land \neg B\)
  • \(\neg(A \land B) = \neg A \lor \neg B\)

Proof: Left as an exercise for the reader. (Hint: Draw a truth table).

Negation of Implication

In my conversations with some students from other schools, they have shared that their teachers do not know the answer to the question ‘What is the negation of the implication?’

In this post, we have built enough of a framework to deal with this kind of question without having to scratch our head in confusion for too long.

Firstly, note that ¬(P⇒Q) is logically equivalent to ¬(¬PQ).

Next, applying De Morgan’s Laws, we simplify it down to P¬Q.

Hence:

¬(P⇒Q) is the same as P¬Q

Let’s have a look at question 8 from the HSC 2020 paper:

This question can be represented in symbols as the following:

\[ P \Rightarrow (Q \Rightarrow R) \]

Where P is the statement ‘\(n\) is even’, Q is the statement ‘\(n\) is a multiple of 3’ and R is the statement ‘\(n\) is a multiple of 6’.

So let’s have a look at the negation: \(\neg (P \Rightarrow (Q \Rightarrow R))\).

We start by transforming the implications to:

\[\neg (\neg P \lor (\neg Q \lor R)) \]

Apply De Morgan’s Law to the outer set of brackets:

\[ P \land \neg(\neg Q \lor R) \]

Apply De Morgan’s Law to the next set of brackets:

\[ P \land (Q \land \neg R) \]

Hence, the solution to Question 8 is B.

Without the necessary framework, this question was done very poorly across the state.

Negation of Quantifiers

The final result is the negation of a quantified statement:

  • \(\neg (\forall x \in X: P)\) becomes \(\exists x \in X: \neg P\)
  • \(\neg (\exists x \in X: P)\) becomes \(\forall x \in X: \neg P\)

An example from the 2020 James Ruse trial paper:

The negation of \(\forall p \in P\) swaps it to \(\exists p \in P\). Note that the \(\in P\) does not become \(\not \in P\).

By applying what was previous discussed about the negation of an implication, we get ‘\(p\) is of the form \(4m + 1\) and \(p\) cannot be written as a sum of two squares.’

Hence, the answer is D.

Conclusion

Without a logical framework of how statements interact with each other, one who is left only to their intuition will find questions like those mentioned above confusing. Although the syllabus only vaguely mentions using some of the logical framework, the 2020 examination has set a precedent that it is the best interests for students (and teachers) to explore further into Logic, and the foundations of mathematics.

In modern mathematics as found in university, many proofs and definitions rely on the language introduced in this Extension II topic as well as Sets. It is due to these foundational concepts that make the study of mathematics rigorous.

Many first year undergraduates experience their first ‘shock to the system’ when confronted with the epsilon-delta definition of a (real function’s) limit:

\[\forall \epsilon > 0; \exists \delta > 0 : 0<|x-a| < \delta \Rightarrow |f(x) – L| < \epsilon\]

Learning the language of Proof is a good start in the HSC Extension II syllabus to ease first year undergraduates into understanding these types of definitions in the future – but the syllabus is silent, or just vague with its terminology of ‘use’ and ‘understand’, on how to develop this framework well.

In this post, I have highlighted just some areas that teachers and students should explore to develop that framework.

  • Introduce the concept of Truth tables even though they will not be assessed: this helps the student understand how the logical connectives work.
  • Show that the logical statement \(P \Rightarrow Q\) is the same as the statement \(\neg P \lor Q\).
  • Use De Morgan’s Laws to negate conjunctions or disjunctions.
  • Show how quantified statements transform under negation.
  • Do more reading and exploration into the Foundations of Mathematics! The historical developments in Logic have been profound in the last century such as Gödel’s Incompleteness Theorem and Turing Machines (which set our society up for the modern computer today), and to avoid even a nominal discussion is a missed opportunity. Veritasium does a wonderful video on all this here:

Leave a comment

Your email address will not be published. Required fields are marked *