From 2cf1f35d29ca2a9e74a1fa1a275729268ac9fca9 Mon Sep 17 00:00:00 2001 From: lshprung Date: Mon, 13 Apr 2020 12:20:52 -0700 Subject: Post-class 04/13 --- 1.5.md | 2 ++ 1.7.md | 111 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 113 insertions(+) create mode 100644 1.7.md diff --git a/1.5.md b/1.5.md index 3bdb0ab..586ec5f 100644 --- a/1.5.md +++ b/1.5.md @@ -90,3 +90,5 @@ Ex. Let S(x) be "x is a student," A(x,y) be "x has asked y a question," and F(x) - True if S(x) or F(y) is false (contradicts the statement) --- + +[1.7 ->](1.7.md) diff --git a/1.7.md b/1.7.md new file mode 100644 index 0000000..5508169 --- /dev/null +++ b/1.7.md @@ -0,0 +1,111 @@ +[\<- 1.5](1.5.md) + +--- + +# 1.7 Intro to Proofs p1 + +A **proof** is a valid argument where each proposition before the conclusion is **true (≡T)**, so the conclusion is **true (≡T)** + +- e.g. Prove 7 < sqrt(59) < 8 + - Brainstorming + - 7 = sqrt(49) + - 8 = sqrt(64) + - Because 59 is between 49 and 64, the statement should be true + - 49 < 59 < 64 + - If x >= 0, y >= 0 and x x+y∈ℤ + - m * (a/b) = (ma/b) + - 1/(m/n) = (n/m) + - a∈ℚ -> -a∈ℚ + +- Do **not** assume things like odd+odd = even + +Def: An integer n is even iff Ǝk∈ℤ s.t. n=2k +Def: An integer n is odd iff Ǝk∈ℤ s.t. n=2k+1 + +--- + +- Aside: people often write "assume p" whn they mean "assume p is true" + +Ex. Prove that the square of an odd integer is odd +- Rewrite the sentence: "∀(integers)x, if x is odd, then x^2 is odd" +- Aside: To show a proposition is true ∀x∈S, one method is to show it is true for an arbitrary x∈S +- Can we say "5 is odd and 5^2 = 25 is odd" so the proposition is true? + - This does not prove it, since it only shows the statement is true for 5, and 5 is not arbitrary + +Scratch Work + +|Given/Know/Assumptions|Want to Show| +|----------------------|------------| +|x is odd |x^2 is odd | +|x=2k+1 for some k∈ℤ |x^2 = 2(ℤ)+1| + +- The second to last step is called the "penultimate step" + +- Let x be an arbitrary odd integer. +- Then, Ǝk∈ℤ s.t. x=2k+1. +- Then, x^2 = (2k+1)^2 = 4k^2 + 4k +1 = 2(2k^2 + 2k)+1 +- Since (2k^2 + 2k)∈ℤ, x^2 is odd. ▣ + - ▣ is a symbol to show "done with proof" + +- Scratch Work is useful for constructing a proof, but it is not necessary to submit in an hw assignment + - If scratch work is included it MUST be clearly differentiated from the actual proof + +This was an example of a **direct proof** of an implication. To show `p->q`, we assume p is true and show that it follows that q is true + +--- + +## Proof by Contraposition + +- Recall, `p->q ≡ ┓q->┓p`, so we can prove `p->q` by using the **contrapositive** and + 1. assume ┓q is true (q is false) + 2. show it follows that ┓p is true (p is false) + +# 1.7 Intro to Proofs p2 + +- Ex. For all integers a,b is a*b is even, then a is even or b is even + +Scratch Work + +|Known|Want to Show| +|-----|------------| +|ab is even|a is even or b is even| +|ab = 2l, l∈ℤ|a=2(ℤ) or b=2(ℤ)| + +- Direct Proof: + - Let a,b be arbitrary integers where a*b is even. Then, Ǝl∈ℤ s.t. ab = 2l. a = (2l)/b = 2(l/b). We need to prove that l/b is an integer, but we don't know that it is :( + +### Proof by Contraposition +- Prove if ┓(a is even or b is even), then ┓(a*b is even) +- If a is odd and b is odd, then a*b is odd + +Scratch Work + +|Known|Want to Show| +|-----|------------| +|a is odd, b is odd|ab is odd| +|a = 2k+1, k∈ℤ|ab = 2(ℤ)+1| +|b = 2l+1, l∈ℤ|| + +- Proof: + - We proceed by contraposition, and assume a,b, are arbitrary odd integers. This means Ǝk,l∈ℤ s.t. a=2k+1 and b=2l+1. ab = (2k+1)(2l+1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1. Since 2kl+k+l∈ℤ, ab is odd. ▣ -- cgit