CSC165 Week12

Finally, we are here, the last week of this semester, cheers!!!

We covered countability and induction in the last week. For the countability part, we got a very tricky question at the lecture. It asks if X={natural numbers} has the same size as Y={even natural numbers}. Intuitively thinking, X contains 0,1,2,3,4,5...... and Y contains only 0,2,4,6.....so X's size is larger than Y's. BUT, THAT IS WRONG!!!!  In fact they have the same size! It was quite confused to me but it make sense after Larry's explanation. We can think in this way, say X={number of coin in the world}, Y={number of tail of coin in the world}, then it is easy to see that these two sets have the same size, since each coin has one and only on tail, so the number of coin must be equal to the number of tail.

The second part of lecture involves the introduction of induction. Induction is a very important tool in mathematic proof. When we get several special case for some NATURAL number, we may possible to prove some properties for all natural number. This is called the induction, The following is an general example in class.

The last part of the lecture was about the review for the final exam.

That's all for week 12. Good luck everyone on your final exam!!!

CSC165 Week11

There was no class for my section since we had a fall break. Not too much to say about week 11 here.

CSC165 Week 10

We finished about the proof of big-Oh and big-Omega. Here is a short summary of chapter 4 about those proofs:

1. Definition of big-Oh, big-Omega.

2. big-Oh proofs for polynomials(standard procedure with over/underestimates)

3.big-Oh proofs for non-polynomials (need to use limits and L’Hopital’s rule)

4. proofs for general big-Oh statements(pick B and c based on known B’s and c’s)

 We also started chapter 5 this week. It's about the computability. For anything that in order to be computable for computers, that function can only go through by finite times. It can not be infinite. If the function is supposed have infinite loop inside, the result will never be computed. 

CSC165 Week9

For this week, we started the proof of 'big-Oh' of polynomials, non-polynomials and limits. The proof structure is the same as we used before but with much more details in it.  It involves a lot of application of math which means it is not that easy to see how to do it, since some math stuff can not be used directly.

For those function in form of polynomial the proof is kind of easy. Basically is find the upper-bound of the left side by overestimating and find the lower-bound of the right side by underestimation and then choose a c that connects the two bounds. For disproving, it just the same as what we've done before, prove the negation of the original statement.

For non-polynomials we need to use limits to prove the big-Oh. The steps are follow:
1. Prove the limit of the function is infinite as n goes to infinite. This step may involves using the L'Hopital's rule.
2. Translate the limit into its definition.
3. Relate it to the definition of big-Oh.

CSC165 Week7

This week we learned more proofs. They involves more rules and many other concepts. The proofs covered in this week are more and more detailed.

For most of mathematic proofs, the key thing is to understand the definition we are given.Then try to derive something that has the same form of the definition. For example

In the above example, we have 7(7i^2+2i)+1. We have to see that is the same form of 7k+1, just for k=7i^2+2i. The idea is the same as picking delta wisely for the last week's proof.

CSC165 Week 6

It looks like most people did very well in the midterm test. Cheers!

This week we learned more about the proofs. Proof of some mathematical things are not that direct, especially for some limits. For those kind of proofs, we need to understand what does limit mean in mathematic. Then, in order to prove it, it is necessary for us to pick delta wisely. 

Disprove something is the same as prove the negation of that. That is quite straight forward for me.

Since we only had a two hours lecture and no tutorial this week..I guess thats all for this week.

CSC165 Week5

Took 2 hours lecture after the test is so tired but start learning proof is exciting. Especially the one given in class showed that 'it is not bad even if you left everything blank and others did well'. You are much better than this if wrote something in the test.

There are several ways of thinking about proof. I believe that in most cases it is not that easy to show something directly, therefore we have to come up with some alternative ways, such us using contrapositive, contradiction. For example, to prove P=>Q is the same as prove ~Q=>~P, because we know that the contrapositive is the same as the original statement in logic. Here is the proof of that
(~Q=>~P)=>(Q or ~P)=>(P=>Q)

Another way of proving an implication statement is by using contradiction. To use this we need to assume the negation of the statement is right, then derive some results based on these assumptions, if some of them contradict each other, it means our assumptions are wrong which is the negation of the original statement. Therefore the original statement is true.

The last part of the lecture was about proof for existence. It seems easy for me because once we can show one example then we can finish the proof.

Hope everyone get a great mark for the test.

CSC165 Week 4

After 4 weeks learning about the logic I found that English is could be so ambiguous. Especially when several antecedents come together with condition, conjunction, disjunction, etc. Even some simple statement can be ambiguous. For example, A and B both guarantees that C is true. I will say if A true and B true then C is true. But some people may think A guarantees C is true individually and B guarantees C is true individually, too.

For week four, we learned about Bi-implication, Transitivity, Mixed Quantifiers and the Proofs.

The Bi-implication means the antecedent is sufficient and necessary for the consequent and vice versa. Say, if P => Q then Q => P and P <=> Q.

When two quantifiers show in one statement, then the order of them will affect the meaning of that statement. The order is a critical problem when we are expressing some mathematical theorems. Sometimes ' for all y, exists an x' is totally different from 'exists an x, for all y'. Therefore we have to pay attention to that when we use mixed quantifiers.

The proofs can give us a better understand about the logic, how thing go at each step. One interesting thing is when we try to proof some thing, we can start it from the conclusion to the assumption first, then write the answer start from assumption. Because sometime, the specific variation of assumption is hard to see.

CSC165 week3

This week we learned about the conjunction, disjunction, negation and implication. These topics seem easy at first glance. However, when the negation combines with conjunction and disjunction, the whole statement becomes complicated and much more hard to be understood. In order to understand it, you have to analyse the negation of each part of the statement step by step.

Here is one example in class which I found a little bit difficult to understand and I think it is quite useful for us to understand the further questions.

After taking the negation of the original statement, it seems messy because you are negating the whole statement witch several parts. Therefore we need to negate each of them one by one. First the negation of the universal is exist, so 'for all x' becomes 'there exists a x', then negation of 'exists a y' is 'for all y', now it makes sense, 'there exists a x, for all y such that blablabla'. The last part is P(x,y), it simply becomes not P(x,y), so the negation is 'There exists a x, for all y such that not P(x,y)'.

Each complicated statement can be understood step by step, figure out the meaning of each part in it.

CSC165 week1&2

After two weeks of learning CSC165, I found that it's quite interesting in thinking in logic way. Something I thought before taking this course was totally wrong. For example, P only if Q means P→Q but not Q→P, I used to think that 'only if' means assuming, that if Q, then P, now I know that not right.

Another interesting part is we can symbolize a sentence, and it makes the sentence much more clear in logic. We can do this to understand some confuse sentence.