01204211/activity2 logic and proofs

This is part of 01204211-58.

In-class activities

A. Inference rules

A1. Use a truth table to prove Hypothetical syllogism. That is show that the conclusion $P\Rightarrow R$ logically follows from hypotheses $P\Rightarrow Q$ and $Q\Rightarrow R$.

A2. Use inference rules and standard logical equivalences to show that hypotheses

• $P\Rightarrow R$
• $Q\Rightarrow R$

leads to the conclusion $(P\vee Q)\Rightarrow R$.

A3. Use inference rules and standard logical equivalences to show that hypotheses

• $P\Rightarrow Q$
• $P\Rightarrow \neg Q$

leads to the conclusion $\neg P$.

A4. Using inference rules to argue that if we assume

• $\neg P\Rightarrow Q$,
• $(P\vee R)\Rightarrow \neg S$,
• $W\Rightarrow S$, and
• $\neg Q$

then we can conclude that $W$ is false.

B. Proofs

B1. Prove the following statement.

If integer a divides integer b, and b divides integer c, then a divides c.

C. Proofs by contradiction

C1. Let's reconsider this theorem.

Theorem: For any positive numbers $n$ and $a$ such that $a>{\sqrt {n}}$, we have that $n/a<{\sqrt {n}}$.

Prove this theorem by contradiction.

C2. In this problem, we will try to reconstruct Euclid's proof that there are infinitely many primes.

Homework 2

Due date: TBA

H3. Prove the following statement.

If integer c divides both integers a and b, then c divides a - b.