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.

Hints: When you want to prove this statement: "If x and y are integers and $x^{2}+y^{2}$ are even, then x + y is even. ". You can think of it as: "If x and y are integers, then (if $x^{2}+y^{2}$, then x+y is even)". That is because (P and Q) => R is equivalent to (P => (Q => R)). Therefore, in this case, you can start by assuming that x and y are integers.

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

B4. Assume that $x$ is a non-zero rational number. Prove that if $y$ is irrational, then $xy$ is irrational.

Source:

• B1 and B3 are from เอกสารประกอบการสอนวิชา Math 217 แนวคิดหลักมูลของคณิตศาสตร์ โดย รุ่งนภา ภักดีสู่สุข ม.เชียงใหม่.
• B2 is from whitman.edu.
• B4 is from Rosen, Exercise 27, Section 1.5, pp. 75

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: 11 Sept. 2015 9 Sep 2015

H1. Prove the following statement.

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

H2. Prove that if $x$ and $y$ are real numbers, then $\max(x,y)+\min(x,y)=x+y$

H3. Prove that $|xy|=|x||y|$, where $x$ and $y$ are real numbers.

H4. Prove that for any positive integer $n$, $n$ is an odd number if and only if $5n+6$ is odd.

Sources:

• H2, H3, and H4 is from Rosen, Examples 33, 23, and 39, Ch.1, pp. 67.