BCS1130-3 Proofs

Lecture notes

Proof by contradiction

• You assume that what you want to prove is false
• You deduce something absurd
• Assumption “not p” cannot be true $⟹$ then p must be true

Proof by contrapositive

• If you want to prove “if p, then q”
• You can prove “if not q, then not p” (logically equivalent to the first one)

Quantifiers

When dealing with proof by contrapositive, the quantifier must not change, only the implication

Example

$\forall x\in N,x>2:x$ prime $\to$ x is odd Contrapositive: $\forall x\in N,n>2:x$ even $\to$ x is not prime

• x even $⟹x=2k,k\in N,n>1$
• x has more than 2 divisors, namely 1, 2k, 2, k
• $⟹$ x is not prime $\square$

Example

$\forall x,y\in R,x,y>0:x^2+y^2>1⟹x+y>1$ Contrapositive: $\forall x,y\in R,x,y>0:x+y\le 1⟹x^2+y^2\le 1$

• Let $x,y\in R,x,y>0$
  • $x+y\le 1$
  • $⟹(x+y{)}^2\le 1^2=1$
  • $⟹x^2+2xy+y^2\le 1$
  • $⟹x^2+2xy+y^2-2xy\le 1-2xy\le 1$
    • $1-2xy$ is obviously smaller than 1
  • $⟹x^2+y^2\le 1\square$

Lecture slides