SLOG 11

This week we had our last three lessons, and it is still a little bit tough for me to understand them.

The content we learned this week is about halt, and it is related to another lesson I am taking, which is programming.

Halt, which means ‘stop’, is opposite to the computing method ‘loop ’. If a code runs, and it can finally return a result (sometimes maybe more results), then the function halts; on the other hand, if it keeps looping, the function does not halt.

Then the ‘halt’ problem leads to another important topic, ‘computable’ and ‘non-computable’.

To comprehend ‘computable’, we have to firstly comprehend the concept of ‘well-defined’. A function is well-defined if and only if we can tell what f(x) is for every x in some domain. A function is computable if and only if it is well-defined and we can tell how to compute f(x) for every x in the domain. Here is another definition. If function f(n) can be implemented by extending another function g(n), then we say f reduces to g.

Now we can combine and simplify these two definitions: ‘f reduces to g’ means ‘g computable⇒ f computable’. It is an important transformation because we can solve the problems about ‘computing’  by using the knowledge on proof. It is also remarkable that ‘g computable⇒ f computable’ can be written as ‘f non-computable⇒ g computable’.

Above are what we learn this week, and next week we may learn more interesting theories on computing.

SLOG 9

Since I don't know how to copy the content that includes the symbols(for example for all, there exists....),I choose to copy the picture with the content I wrote in Word document.Thank you for understanding.

SLOG 8

Since I don't know how to copy the content that includes the symbols(for example for all, there exists....),I choose to copy the picture with the content I wrote in Word document.Thank you for understanding.

SLOG 7

Since I don't know how to copy the content that includes the symbols(for example for all, there exists....),I choose to copy the picture with the content I wrote in Word document.Thank you for understanding.

SLOG 6

                     This week is the week for us to learn the proof methods, and we finished the method ‘proof by cases’. And then professor introduced the concept of counting steps, which includes the worst case and the best case. Let us talk about proof by cases firstly.

      Sometimes we have to prove some claims that have conclusive antecedents. For example, if we now have a claim with an antecedent like this: | x - y | = e, we have to consider it by cases, for we know few ways to prove directly by absolute value. So we split | x - y | = e into two cases: 

x - y = e and | x - y | = -e. Then we prove in this structure:

Case 1： x - y = e

......

Case 2： x - y = -e

......

Then we have a lot of ways to figure out the claim, since we are familiar to the equation

 x - y = e and x - y = -e, and we know plenty of ways to do transformation on them.

  After that, we learned how to count steps. It is a tough part because we need to be careful or we will easily go on a wrong way. Counting the worst case is the most representative case of counting steps because it includes all the possibilities. Worst case is the situation that the algorithm has to run the largest times that it can run. For example, the worst case ①of the algorithm 

def LS(A, x): 

’’’

Return index i, x == A[i].

Otherwise, return -1 

’’’

i = 0                   ①

while i < len(A):         ②

if A[i] == x:         ③

    return i         

i = i + 1           ④

return -1              ⑤

  

 If it is in the worst case:

 It has to run once at step ①, twice at step ②, once at step ③, once at step ④, and once at step ⑤ if len(A) = 1.

It has to run once at step ①, three times at step ②, twice at step ③, twice at step ④, and once at step ⑤ if len(A) = 2.

It has to run once at step ①, four times at step ②, three times at step ③, three times at step ④, and once at step ⑤ if len(A) = 3.

......

So when len(A) = n, it has to run 1+( n + 1) + n + n +1 = 3n + 3 times.

   Next week we are supposed to enter a new world of logic. Although until now I have no idea about how that world is, I cannot be more excited on exploring it!

SLOG 5

Since I don't know how to copy the content that includes the symbols(for example for all, there exists....),I choose to copy the picture with the content I wrote in Word document.Thank you for understanding.

SLOG 4

Since I don't know how to copy the content that includes the symbols(for example for all, there exists....),I choose to copy the picture with the content I wrote in Word document.Thank you for understanding.

SLOG 3

Since I don't know how to copy the content that includes the symbols(for example for all, there exists....),I choose to copy the picture with the content I wrote in Word document.Thank you for understanding.

It is an example that perfectly shows what proof is, right?

I think proof is an interesting section in logic because that is an integrative application of the Logic and Maths knowledge.I will try my best to get command of it.

SLOG2

    This week I enjoyed a good time learning some complicated logic converts, which make me enable to turn some kinds of statements into symbolical descriptions, and of course, vice versa.
    It is an interesting process turning a normal sentence into some symbols, and the most important thing is they finally refer to the same meaning! I did not even imagine I could use some symbols to represent statements before attending the class this week!
    Actually, to realize those magical things I mentioned above, I only need several simple symbols.
The symbols are : ¬(negate),   ∧(and), ∨(or), ==> , <==, ∃(some) and ∀(all)
For example, if there is a statement “All the employees earn more than $3000.”
How to turn it into some symbols?
    FIRSTLY ，you have to assume that “earn more than $3000” as P, the set of employees as E
    SECONDLY, do the convert, following the meaning of the statement.
∀x∈ E, P.
    It is easy and clear, right?
    Then how to convert “Not all employees earn more than $3000 ”?
¬∀x∈ E, P. You can also state that in this way: ∃ x∈ E, P.

    It is, maybe, the best choice during this year to join this class, because it has been greatly helping me understand the logic world, which is a world I had never considered about.
    Of course, a good class should create some challenges for students to improve them and help them be experts in the fields that the class talks about. This class is a typical good class. After the class on Monday, I spent about 3 hours in the library, looking at the teaching materials, trying to find the specific logical relationship among those symbols I did not even see before.Unfortunately, I still failed. But the tutorial gave the hope and useful help, and now I can proudly say I have totally got command of the symbols and their logical relationship.

SLOG1

    During this week, I mean, from September 15th to September 21th, I learned a lot of interesting converts and theories about logic applications. Generally, they are separated into two parts.
    The first part is talking about the difference between  ALL and SOME, which are, actually, the basic antecedents of the following second part. Maybe someone will think it is funny, or even ridiculous for a university lecture to talk about the distinction of ALL and SOME, because they think these two word are maybe two of the most simple words in English. In fact, I used to think in that way before. But now, after this week, I will not do that anymore. There is actually a charming world inside these two words. For example, ALL，of course, means the whole collections, can be used to describe a unit that contains everything you need. Then an interesting thing comes---How can we verify a universal claim? Or how to falsify it? These are really not a complicating question, but what they need is logic----the purpose of attending this lecture. The answers to these questions are that we need to show there is no counter-example to verify a universal claim. Conversely, showing there is at least one counter-example is required. That is an interesting beginning of the logic subject, isn’t that?
    In the second part, we learned the implication, which sounds much more like a word in logic.An implication consists two elements---antecedent(P) and consequent(Q). The format is like P   ====>  Q, and if we change the order of P and Q, we can get converse; if we toggle the truth value of the original implication, we can get negation; if we change both the order and the truth value, we can finally get contrapositive. Here are some incredibly amazing things: The truth value of the origin is the same as the contrapositive, which means, when the origin is true, the contrapositive must be true; when the origin is false, the contrapositive must be false. So do negation and converse. That is very wonderful and unbelievable, and I am still eager to know the reason.
    I really enjoyed the class this week, especially when I found the content of this class is related to my another class-------MAT135. Both of the two classes were talking about the unit, and I can understand them better through reviewing the content of the two lectures, and then find the part to help me understand them each other better.
    This week I find I can understand and process almost all the knowledge by listening carefully to the professor and reviewing the slides literally. During the first week, I was still not in a terrific condition.
   Tutorial is another good thing to talk about here. This week is the first week for the tutorial, and the teaching assistant patiently responded and explained almost all the questions and confusions we had, besides finishing his mission----working out the exercise and telling us the answers.
   Above all, this week is really an unforgettable one, and I believe I will improve in the future and will finally get a great mark in this lecture!