week 12

This week we are working on the assignment 3. After finishing the question 5, I have a general idea about it.

I am thinking that every function has a character whether its gonna halt or not.

Then I can reduce Halt to every function. Simply, I can just put my function in to Halt.

As a result, a function is not computble is a sequence of halt is not computble. The contrapositive is 'if halt computable then the original function is computable.'

Week 10

I got my second term test back this week, I did OK in this test which I got a 80%s BUT I make few mistakes and I think I should learn something from them.(I will analyze them later in this post). And we get our assignment 2 result back, we r almost getting a full mark but has a terrible mistake that we made a typo on a symbol of the negation of a question so its proof doesn't make any sense....

From those mistakes, 

1) double check the negation

2) pay attention to the symbols in () especially when we try to negate it.

3) when stuck, try the contrapositive.

 

week 9

This week we have the second term test which is about the proof and the structure of a prove. I think I did good on it but I have some thoughts about it.
 First, what kinds of comments are really necessary for the proof.
 Second, when you stuck at some proof you should try the negation and the    contrapositive of the statement.
 Third, is there a way to check whether the proof is right or not?

week 8

This week we learn about worst case complexity and how to calculate it by counting steps.

Every function has an upper bound and lower bound so that we always consider the worst case --- the upper bound for complexity.

Since complexity is going to be a very large number, the constant in it really doesn't matter any more. For example, O(18n^2) roughly is O(n^2).

For calculating the steps of a function, we count the constant steps first and then count the outer loop(let's say n steps) and then the Loop Guard and then the inner loop(lets say n^2) and so on.

week 7

In this week, since we are working on the assignment 2, I have some thoughts about proving structure in general:

    first of all, if it is a universal quantifier, then you assume an general element which meets the requires, then prove it by assuming the first part of the implication True and using the condition to transfer to a statement which is the latter part of the implication.

    Secondly, if it is an existential quantifier(most the case it is in a disproof), then you pick a element that satisfies the implication. After all these, you have proved a negation of an original statement.

Moreover, we learn some sorting algorithms and how to count the steps. Most of the case, we are consider the worst case of an sorting algorithm and after all the constant in front of the number of steps is not that important anymore.

week 6 -- solving negation problem analysis

This week we get out first midterm back, overall, I did OK on this test since I got 85%. But I found myself keep having the same problem on how to negate an implication without hesitation.

For an implication like:
                       ∀a∈ N, P(a) ⇒ Q(a)

P(a) ⇒ Q(a) equals:
                      ∀a∈ N, ¬P(a) ∨ Q(a)

hence the negation:

                       ∃ a∈ N, P(a) ∧ ¬Q(a)


Let's try another way(this is a tricky False statement):

the only false of it :
                       ∃ a∈ N, P(a) ⇒ ¬Q(a)
P(a) ⇒ ¬Q(a) equals:
                       ∃ a∈ N,  ¬P(a) ∨ ¬Q(a)

Let's use "negation" of implication:(False)
so the negation of ∀a∈ N, P(a) ⇒ Q(a)
                       is ∃a∈ N, ¬P(a) ⇒ ¬Q(a)
equals:
                   ∃a∈ N, P(a) ∨ ¬Q(a)

week 5 proof outline

proof outline:

1. for all x in R, P --> Q:

The method we learned in the lecture is trying to prove a statement from base case or in other words, using P to get to Q by transforming the equation or inequation. (it's like the firse step of mathmatic indaction)

2. there exist a x in R, P --> Q:

Just find a example.

3. if the sttement is hard to prove:

try to prove the contropositive.

week 4 review Symbolic Logic

1. the sentence P --> Q:

    (a) If P, then Q.

    (b)P implies Q.

    (c) P only if Q.

    (d) It is necessary that Q for P.

    (e) It is sufficient that P for Q.

2. the sentence: All x in R, P --> Q:

    (a) equavelent to : All x in R, not P or Q

    (b) negation: Exist x in R,  P and not Q

    (c)convers: All x in R, not P --> not Q
                       All x in R, Q --> P

    (d)contropositive: All x in R, not Q --> not P

Week 3

  This week's content is pretty tricky because we are trying to translate English to symbols. The problem is that English may not very clear stating a statement but symbol only leads to one possibility. For example, English has exclusive situation about "or" or "and" but not symbol. Moreover, it's a special case that when we facing an "unless", we can just translate it to "if not".

  Conjunction:

              A conjunction is false is either part is False. * its different from application.*

  Negation:

           Basically a negation is to put a "Not" in front a statement, and sometimes it give us a counterexample as well.

Week 2

  This week's lectures are basically discussed about math logic or statement in computer science. Firstly, we review how to use math symbols to state English sentences or in the opposite way. For example, there are two main types of statements to describe quantifiers which are universal claims and existential claims. 

  However, there are something unclear for me about describing existential claim. In this week's tutorial problem set, there is a statement start with "there is one of three...". I am confused about this question because I cannot be sure whether it is saying "there is exactly one" or "there exists one".

  Secondly, graphic diagram-- Venn diagram is very helpful to understand the relationships between claims. Every time if you are not sure about some quantifiers' relations, to draw a diagram is the best to get a better understanding.