Topic 1.5 Logic and Proof I - Implications and Direct Proof

Question 1

What is an implication?

Answer 1

An implication is the statement ‘If p, then q”, where p refers to the hypothesis and q the conclusion (written p => q)

Question 2

What does it mean to say that an implication is true?

Answer 2

This is to say that the truth of the hypothesis p necessarily entails the truth of the conclusion q

Question 3

How would you write a theorem for the following? Let A, B and C be sets. If A is a subset of B and B is a subset of C, then A is a subset of C

Answer 3

((A⊆B)∩(B⊆C))⇒(A⊆C)

Question 4

What is the contrapositive?

Answer 4

Not q implies not p

Question 5

What is the converse?

Answer 5

‘q’ implies ‘p’

Question 6

Which proofs are logically equivalent?

Answer 6

Direct proofs, the contrapositive and the biconditional of statements, as the implication requires that either both be true or both be false (proving one statement is the same as proving the other)

Question 7

What does p <+> q denote?

Answer 7

If we let p and q be statements, p <+> q denotes the biconditional of p and q, read “p if and only if q”

Question 8

How do you prove “if and only if” statements?

Answer 8

To prove these statements, you must prove two components: must prove p => q, must prove q => p. You must prove both as they are independent statements

Question 9

Prove the following theorem: Let A and B be sets. The set A is a subset of B if and only if the union of A and B equals B

Answer 9

Suppose A⊆B. To prove A∪B=B, we need to show A∪B⊆B, and B⊆A∪B by definition. If a∈A∪B then either a∈A, in which case a∈B since A⊆B, or a∈B and so in both cases a∈B