Lesson 1 · Logic and the language of proof

Learning intentionTo learn the language and notation of logic, so we can read, write and negate mathematical statements precisely.

Success criteria · I can…

explain what a statement (proposition) is and use propositional symbols $P$ , $Q$ , $R$
prove a statement by exhaustion, or disprove it with a counterexample
use $\neg$ , $\wedge$ , $\vee$ and $\Rightarrow$ , and explain when $P \Rightarrow Q$ is false
negate “and”, “or” and “if…then” statements

ResourcesLesson slides
Practice worksheet
Worked solutions
Logic Translator applet
Proof Symbols applet

Lesson flow

LaunchWarm-up · True or false?Slide 3 OverviewWhat is a proof? The road map for this unitSlide 2 ReferenceKey terms and notationSlide 4 DefinitionsStatementsSlide 5 DefinitionsExamples and counterexamplesSlides 6, 7 HSC practiceHSC practice · A counterexampleSlide 8 DefinitionsNegationSlide 9 ExamplesExample 3 · NegationSlide 10 Definitions“And” and “or”Slide 11 DefinitionsImplicationSlide 12 ExamplesExample 5 · Testing an implicationSlide 13 Key ideasNegating “and”, “or”, “if…then”Slide 14 ExamplesExample 6 · Negating compound statementsSlide 15 Exit ticketExit ticketSlide 16

Warm-up · True or false?

Slide 3

Decide whether each claim is true or false. How sure are you, and why?

(a) All prime numbers are odd.

Show answerHide answer

Answer

False.

Why

2 is prime and even, so 2 is a counterexample. One counterexample is enough to disprove a “for all” claim.

(b)

n^2 + n + 41

is prime for every

n \in \mathbb{N}

Show answerHide answer

Answer

False, although it works for

n = 0

39

Why

For

n = 40

1600 + 40 + 41 = 1681 = 41^2

. Many examples never prove a statement about infinitely many cases, but one counterexample disproves it.

(c) The sum of two odd numbers is even.

Show answerHide answer

Answer

True.

Why

Checking examples such as

3 + 5 = 8

is not a proof. We prove this in Lesson 3.

(d) If

x^2 = 9

, then

x = 3

Show answerHide answer

Answer

False.

Why

x = -3

satisfies

x^2 = 9

but not

x = 3

, so it is a counterexample.

What is a proof? The road map for this unit

Slide 2

Definition

Proof

A logical argument showing that a statement is always true. A single counterexample shows that it is not.

In this unit you will learn the language of logic, then several ways to build a proof.

Lessons	Topic	Ideas
1–2	Language and notation	statements, $\neg$ , $\wedge$ , $\vee$ , $\Rightarrow$ , converse, contrapositive, $\forall$ , $\exists$
3	Direct proof and cases	odd, even, divisibility
4	Contrapositive and contradiction	irrational numbers, infinitely many primes
5–6	Inequalities	squares are non-negative, AM–GM, triangle inequality
7–9	Further induction	series, inequalities, recursion, binomial theorem
10	Calculus inequalities	increasing functions and the squeeze theorem

A proof is written for other readers, so clear setting out and signposts are part of the mark.

Key terms and notation

Slide 4

Term	Notation	Read as
Statement (proposition)	$P$ , $Q$ , $R$	a sentence that is true or false, not both
Negation	$\neg P$ or $\sim P$	not $P$
And / Or	$P \wedge Q$ , $P \vee Q$	$P$ and $Q$ , $P$ or $Q$
Implication	$P \Rightarrow Q$ or $P \rightarrow Q$	if $P$ then $Q$ ; $P$ implies $Q$
Converse	$Q \Rightarrow P$	if $Q$ then $P$
Equivalence	$P \Leftrightarrow Q$ or $P \leftrightarrow Q$	$P$ if and only if $Q$ ( $P$ iff $Q$ )
Contrapositive	$\neg Q \Rightarrow \neg P$	if not $Q$ then not $P$
Logically equivalent	$\simeq$	same truth value in every case
Quantifiers	$\forall$ , $\exists$	for all, there exists
Counterexample, contradiction		one case that disproves a statement; an impossible result

The syllabus writes = between logically equivalent statements; here we write ≃ to avoid confusion with equality. Both appear in exam papers. The converse, equivalence, contrapositive and quantifiers are developed in Lesson 2.

Statements

Slide 5

Definition

Statement (proposition)

A statement is a sentence that is either true or false, but not both. Its logical value is true or false.

We name statements with capital letters, starting at $P$ . For example, $P$ : $n$ is a multiple of 3.

Example 1 · Which are statements? If so, true or false?

(a) There are kangaroos in Australia.

Show answerHide answer

Answer

A statement, and it is true.

Why

It is a sentence that is either true or false.

(b) Close the door.

Show answerHide answer

Answer

Not a statement.

Why

It is a command, so it is neither true nor false.

(c)

x + 1 = 5

Show answerHide answer

Answer

Not a statement until

x

is known.

Why

Its logical value depends on

x

. It becomes a statement with a quantifier, for example

\exists x \in \mathbb{R}

such that

x + 1 = 5

, which is true (Lesson 2).

(d) 16 is an odd number.

Show answerHide answer

Answer

A statement, and it is always false.

Why

A statement can be false. What matters is that it has a definite logical value.

(e) History is more interesting than Science.

Show answerHide answer

Answer

Not a statement.

Why

It is an opinion, which has no logical value.

Examples and counterexamples

Slides 6, 7

Definition

Proving and disproving with examples

Proof by exhaustion: check every possible case. It is valid, but only practical when there are few cases.

Counterexample: one example showing that a statement is not always true. One counterexample disproves a statement.

No number of examples can prove a statement about infinitely many cases.

Example 2 · Exhaustion and counterexample

(a) Prove by exhaustion: all odd integers between 16 and 20 are prime.

Show answerHide answer

Answer

The odd integers between 16 and 20 are 17 and 19. Both are prime, so the statement is proved.

Why

There are only two cases, so we can check them all. That is what makes the proof valid.

(b) Disprove: all primes are odd.

Show answerHide answer

Answer

2 is prime and even, so the statement is false.

Why

A single counterexample is enough to disprove a “for all” statement.

HSC practice · A counterexample

Slide 8

Adapted from 2020 HSC Q7Consider the claim: “If

n

is prime, then

2^n - 1

is prime.” Which value of

n

is a counterexample?

n = 2

n = 3

n = 7

n = 11

Show answerHide answer

Answer

Why

2^{11} - 1 = 2047 = 23 \times 89

, and 11 is prime. For A, B and C:

2^2 - 1 = 3

2^3 - 1 = 7

and

2^7 - 1 = 127

are all prime, so they agree with the claim and are not counterexamples. A counterexample must make the “if” part true and the “then” part false.

Negation

Slide 9

Definition

Negation $\neg P$

“not $P$ ”. It has the opposite logical value to $P$ . Also written $\sim P$ .

Watch the word “all”

$P$ : All cats are fluffy.

Correct $\neg P$ : Not all cats are fluffy, so there exists a cat that is not fluffy.

Incorrect: “All cats are not fluffy.” This says no cat is fluffy, which is too strong.

Test: exactly one of $P$ and $\neg P$ is true. If you can imagine both being false, your negation is wrong.

Example 3 · Negation

Slide 10

Write the negation of each statement.

P

: It is raining.

Show answerHide answer

Answer

It is not raining.

Why

The simplest case:

\neg P

is “not

P

”.

Q

: All dogs are brown.

Show answerHide answer

Answer

Not all dogs are brown: there is a dog that is not brown.

Why

Do not write “all dogs are not brown”. That says no dog is brown, which is too strong.

R

: The bottle of water is full.

Show answerHide answer

Answer

The bottle of water is not full.

Why

Not “empty”. A half-full bottle is neither full nor empty.

S

: Some students ride to school.

Show answerHide answer

Answer

No students ride to school.

Why

The opposite of “some” is “none”.

T

x > 4

Show answerHide answer

Answer

x \le 4

Why

Not

x < 4

. The negation must include the boundary case

x = 4

U

-3 \le x \le 8

Show answerHide answer

Answer

x < -3

x > 8

Why

The “and” hidden in

-3 \le x \le 8

(that is,

x \ge -3

and

x \le 8

) becomes “or”. This previews the negation rules later in the lesson.

“And” and “or”

Slide 11

Definition

And ( $\wedge$ ) and Or ( $\vee$ )

$P \wedge Q$ is true only when both $P$ and $Q$ are true.

$P \vee Q$ is true when at least one of $P$ , $Q$ is true (inclusive or).

Truth tables use 1 for true and 0 for false. Order of precedence: $\neg$ , then $\wedge$ , then $\vee$ .

$P$	$Q$	$P \wedge Q$	$P \vee Q$
1	1	1	1
1	0	0	1
0	1	0	1
0	0	0	0

Capital letters are reserved for statements, so truth values are written 1 and 0 rather than T and F.

Example 4 · $P$ : 6 is even, $Q$ : 6 is prime

(a) Is

P \wedge Q

true?

Show answerHide answer

Answer

No,

P \wedge Q

is false.

Why

P

is true and

Q

is false. Both must be true for “and”.

(b) Is

P \vee Q

true?

Show answerHide answer

Answer

Yes,

P \vee Q

is true.

Why

At least one must be true, and 6 is even.

Implication

Slide 12

Definition

Implication $P \Rightarrow Q$

$P \Rightarrow Q$ (or $P \rightarrow Q$ ) is read “if $P$ then $Q$ ” or “ $P$ implies $Q$ ”.

Bob to Jane: “If you give me $100, then I will go shopping.” $P$ : Jane gives Bob $100. $Q$ : Bob goes shopping.

When has Bob lied? Complete the truth table for

P \Rightarrow Q

\neg P

and

\neg P \vee Q

. Then complete:

P \Rightarrow Q

is false only when …

Show answerHide answer

Answer

P \Rightarrow Q

is false only when

P

is true and

Q

is false.

Why

Bob only lies when Jane pays and he does not go shopping (row 2). If Jane never pays, Bob cannot have broken his promise, so

P \Rightarrow Q

is true. This is called being vacuously true. The columns for

P \Rightarrow Q

and

\neg P \vee Q

are identical, so

P \Rightarrow Q \simeq \neg P \vee Q

$P$	$Q$	$P \Rightarrow Q$	$\neg P$	$\neg P \vee Q$
1	1	1	0	1
1	0	0	0	0
0	1	1	1	1
0	0	1	1	1

No causal link needed

“If ABCD is a rectangle, then today is Sunday.” An implication needs no causal link between $P$ and $Q$ . Its truth depends only on the truth values of $P$ and $Q$ .

Example 5 · Testing an implication

Slide 13

P

x

is a multiple of 6.

Q

x

is divisible by 9. Complete a truth table for

P \Rightarrow Q

, giving a value of

x

for each row. Is the implication always true?

Show answerHide answer

Answer

No.

x = 24

is a counterexample, so

P \Rightarrow Q

is not always true.

Why

One value of

x

for each row:

$P$	$Q$	Example of $x$	$P \Rightarrow Q$
1	1	18	1
1	0	24	0
0	1	27	1
0	0	25	1

Rows 3 and 4 are true because

P

is false (vacuously true). Row 2 is the only row where the implication fails: 24 is a multiple of 6 but not divisible by 9.

Negating “and”, “or”, “if…then”

Slide 14

Negate…	Rule	In words
a negation	$\neg(\neg P) \simeq P$	not not $P$ is $P$
“and”	$\neg(P \wedge Q) \simeq \neg P \vee \neg Q$	at least one fails
“or”	$\neg(P \vee Q) \simeq \neg P \wedge \neg Q$	both fail
“if…then”	$\neg(P \Rightarrow Q) \simeq P \wedge \neg Q$	$P$ happens but $Q$ does not

Useful equivalence

P \Rightarrow Q \;\simeq\; \neg P \vee Q \;\simeq\; \neg(P \wedge \neg Q)

“If $P$ then $Q$ ” only fails when $P$ is true and $Q$ is false. So $\neg(P \Rightarrow Q)$ says exactly that: $P \wedge \neg Q$ .

De Morgan’s laws for sets: $\overline{A \cap B} = \overline{A} \cup \overline{B}$ and $\overline{A \cup B} = \overline{A} \cap \overline{B}$ . Same pattern: $\wedge$ matches $\cap$ and $\vee$ matches $\cup$ .

Common error

Writing $\neg(P \Rightarrow Q)$ as $P \Rightarrow \neg Q$ . The negation of an implication is an “and” statement, not another implication.

Example 6 · Negating compound statements

Slide 15

Write the negation of each statement.

(a)

x > 2

and

x

is even.

Show answerHide answer

Answer

x \le 2

x

is odd.

Why

Negating “and” gives “or”, and each part is negated:

\neg(P \wedge Q) \simeq \neg P \vee \neg Q

. (For an integer

x

, “not even” means odd.)

(b)

n

is odd or

n

is a multiple of 3.

Show answerHide answer

Answer

n

is even and

n

is not a multiple of 3.

Why

Negating “or” gives “and”:

\neg(P \vee Q) \simeq \neg P \wedge \neg Q

. Both parts have to fail.

(c) If

n

is even, then

n^2

is even.

Show answerHide answer

Answer

n

is even and

n^2

is odd.

Why

\neg(P \Rightarrow Q) \simeq P \wedge \neg Q

. Keep the hypothesis and deny the conclusion. Do not write “if

n

is even then

n^2

is odd”, which is another implication.

(d) If I live in Tasmania, then I live in Australia.

Show answerHide answer

Answer

I live in Tasmania and I do not live in Australia.

Why

Again

P \wedge \neg Q

. (The original is true, so this negation is false for everyone.)

Exit ticket

Slide 16

1. Which is the negation of “If

n

is prime, then

n

is odd”?

n

is not prime and

n

is even.B

n

is prime and

n

is even.C If

n

is odd, then

n

is prime.D

n

is not prime or

n

is odd.

Show answerHide answer

Answer

Why

\neg(P \Rightarrow Q) \simeq P \wedge \neg Q

: “

n

is prime and

n

is not odd”, and not odd means even. A negates both parts. C is the converse. D is equivalent to the original statement (

\neg P \vee Q

2. Which is logically equivalent to

P \Rightarrow Q

Q \Rightarrow P

P \wedge \neg Q

\neg P \vee Q

\neg P \wedge Q

Show answerHide answer

Answer

Why

P \Rightarrow Q \simeq \neg P \vee Q

, as the truth table shows. B is the negation of

P \Rightarrow Q

. A is the converse. D is false when

P

and

Q

are both true, but

P \Rightarrow Q

is true then.

Lesson 1 · Logic and the language of proof

Lesson flow

Warm-up · True or false?

What is a proof? The road map for this unit

Key terms and notation

Statements

Example 1 · Which are statements? If so, true or false?

Examples and counterexamples

Example 2 · Exhaustion and counterexample

HSC practice · A counterexample

Negation

Example 3 · Negation

“And” and “or”

Example 4 · PPP: 6 is even, QQQ: 6 is prime

Implication

Example 5 · Testing an implication

Negating “and”, “or”, “if…then”

Example 6 · Negating compound statements

Exit ticket

Example 4 · $P$ : 6 is even, $Q$ : 6 is prime