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

Prove the following statements. (Hint: try direct proofs and proofs by contraposition.)

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

B2. If $x$ and $y$ are integers and $x^{2}+y^{2}$ are even, then $x+y$ is even.

B3. If x is irrational, then ${\sqrt {x}}$ is also irrational.

B4.

Source: B1 and B3 are from เอกสารประกอบการสอนวิชา Math 217 แนวคิดหลักมูลของคณิตศาสตร์ โดย รุ่งนภา ภักดีสู่สุข ม.เชียงใหม่. B2 is from whitman.edu.

C. Proofs by contradiction

C1. Let's reconsider this theorem again.

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. Prove this statement. (Note that you do not have to use proof by contradiction.)

Suppose that I have k pairs of socks (each pair with a distinct color). If I pick k + 1 socks, then there will be at least one pair of socks with the same color.

C3. In this problem, we will try to reconstruct Euclid's proof that there are infinitely many primes. We will prove by contradiction. So let's get you started.

The first step is to assume that there are finitely many primes. Let n be the number of prime numbers, and $p_{1},p_{2},\ldots ,p_{n}$ are all prime numbers.

The key to obtain the contradiction is to consider this number $L$ defined to be

$L=1+p_{1}\times p_{2}\times p_{3}\times \cdots \times p_{n}$

Use this starting point to complete the proof. (Hint: What can you say about $L$? Is it a prime number? Do we really need to know for sure if it is a prime number?)

Homework 2

Due date: TBA

H3. Prove the following statement.

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