Week 7 Review of [Proof]

I am going to review proofs in this week's notes.

1. Proof by cases:

First step is to split argument into different cases then prove the conclusion for each case.

From all the lecture examples and tutorial examples, I think the trick to decide if we need to proof by cases is that see if there is a "\/" (or) show up. 

For example, the example in class, for all nature numbers n , n^2+n is even. We assume n is a nature number, n could be either even or odd,  then there exists a k, n = 2k+1 \/ n = 2k. Then we prove case 1 : n = 2k+1 and case 2: n = 2k. Same as the tutorial question. root(rs) = 0 so either r = 0 \/ s = 0. Then we consider two cases.

Note: See \/ => Proof by cases.

2. Proof <=>:

The trick for this kinda of proof is that when => is true DOES NOT MEAN <= is True. When we want to disprove a poof, we always negate it, and prove the negation is true. The good thing about negate a universal quantifier will become a existential quantifier. To prove a existential quantifier is true, we just need to let xxx= xxx, prove the statement is true.

3. Review proof patterns:

1) introduction rules: negation introduction, conjunction introduction, disjunction introduction, implication introduction, equivalence introduction, universal introduction, existential introduction.

2)elimination rules: negation elimination, conjunction elimination, disjunction elimination, implication elimination, equivalence elimination, universal elimination, existential elimination.

:( Midterm Keep Calm and Carry On

So it was soooooo easy but I did not do well...

Something learnt from this midterm:
1. Never think it is too easy
2. Check it over and over again
3. Do not hand your paper early
4. Read question carefully
5. Believe there is always a trick or keyhole

I made a stupid mistake on question 2. The question asks us to negate a statement and it says  the negation symbol applies only to predicates such as m+n = q. When I was doing the test, I did not read the question carefully. In other words, I totally ignored this sentence and remembered to apply to the smallest part. Then a mistake made that I applied on q. It did not even make any sense. q is a natural number how can I negate it. However, I did not think about it this way. I even explained in words how this could be negative. For part b, I did the same thing again.  It was really stupid and I am so frustrating about it.

However, like Larry proved last class, it is not a big deal. I will get back for test 2. Just learn from my mistakes. Keep calm and carry on. I know I can do this!!!!!

[Proof] can be tricky

So we finished the first midterm :) It was quit easy (hope I did not make any stupid mistakes)
After the midterm we started the lecture. Larry was funny as always he pulled out a proof which was:
(I will copy the proof down to review the basic structure of proof)
Proof:
assume you left all questions blank
#that's pretty bad!                                -----> remember to put comment when you right a proof
    then you get 20%
    assume class average is 70% #pretty high!
        then you are 50% below average
        in this term test #70% - 20% = 50%
        then this term test weighs 6% of final grade
        # according course info sheet
        then you are 3% below average
        in term of final grade #6%*50%=3%
        then it is below are the acceptable
        margin of error #5% in physics
        then it is totally acceptable
then it is not bad even if you left everything blank and others did well.
                                                                 ----> remember the last ''then'' will in line with first ''assume''


Last week, we learnt direct proof for universally quantified implication which is for all x belongs to X, P(x) => Q(x).

For example:

         

However, sometimes it is hard to prove this way so we might try prove the contrapositive of the original statement. 

Sometimes it is not clear what P is, in this situation, we use contradiction.
For Example, to prove "There are infinitely many even natural numbers." We suppose there is a finite number of even number => then there must be a largest one, call it X => but if I double X => I get a larger number, a larger even number => so X is NOT the largest one.

Assignment 1 some tricky questions

So we are mainly working on Assignment 1 this week.

Overall this assignment is pretty easy, but there are some tricky questions.

Question 1

(a) All acronyms are catheterized unless they are bifurcated.
At first I thought the sentence means there are two types of acronyms: catheterized and bifurcated. It shows that these two have no intersection part which means there is no such acronyms that is catheterized and bifurcated. So when we negate it, it will be there exists an acronym which is catheterized and bifurcated.  Then in symbolic form is ∃a∈A,B(a)⋀C(a)

When I look at this question again, I find this is the right way which means ALL acronyms are catheterized and bifurcated.  So when we negate it, it will be there exists an acronym which is non-catheterized and non-bifurcated.

(e) For an acronym to be catherized, it is necessary and sufficient that it be diagonal.
According to the lecture slides of week 2, we now that " For P to be true, Q is necessary."
In this question P: an acronym to be catherized Q: it be diagonal
For an = For every = All the negation will be there exist an acronym which is catherized and non-diagnonal or non-catherized and diagonal. Then in symbolic form is
∃a∈A,(D(a)∧¬C(a)) ⋁ (C(a)∧¬D(a))

Question 3

(a) One, and only one, student in X is more popular than Zorn.
When I look at the question the first time, I got confused by "One and only one", then I thought about it, "one and only one" simply means "there exists one student x who is more popular than Zorn".

∃x∈X,(P(x,Zorn)∧S(x))∧(∀y∈X,(S(y)∧P(y,Zorn))⇒EQ(x,y))