(CSC165)_Oct 24_More About Proof

After we learned the general structure of proof, professor began to introduce some example of actually proving some statement to help us build the logical connection. Actually, when writing proof, it is a lot similar to what we learned about 1) problem solving and 2) logic.

Sometime we need to decide if we want to prove the statement or disprove it. To prove it, we can use direct prove or indirect prove. Direct prove are more like doing logical analysis step by step after assuming the antecedent and finally to arrive at the conclusion. Indirect prove is very useful when its hard to find the connection from a direct way, and, in this case, we can prove the original statement by proving its contrapositive. Since, we know a statement's truth value is the same as its contrapositive. I think after more practice, the idea thinking pattern of trying to prove a statement is to think through both side, and being able to figure out which is a more efficient way to write a proof.

In terms of disprove, some of us have questions about how we could know the statement was wrong in the first place. Actually, most of the questions we have at this moment is very easy to find out if it is wrong by simply plugging some examples. However, when facing with a more complex statement, the professor told us, which I think is quite interesting but probably very important, that when we tried to prove a statement, and stuck somewhere during the process, we may think backwards and also think about disproving it. Basically, we can prove the original statement's converse to disprove the statement. Alternatively, if we want to do the disprove directly, we can also assume the antecedent, and after that if we can logically find a contradiction, we also achieve our goal.

(CSC165)_Oct 17_Proof

During the past two weeks, in addition to mid-term and assignment, we begin to learn writing proofs using the logic related knowledge we had. It was first actually very impressive that the professor mentioned that he focus more on the structure of the proof rather than the specific technique used in the the proof. It actually make a lot sense since CSC165 is more about logical thinking rather math, and it is particularly important because we can apply the knowledge we potential will learn in the future to it.

Basically, for a direct proof,  the structure is generally:

Assume quantifier (domain) ....

    Assume .....

        Let ___ be ___

        Then .....

        .

        .

        .

        Then ....

    Then ....

Then....

(Note: the indentation is also a important part of the structure.)

In addition to a direct proof, we have choices proof the contrapositive, and disproof the negation.

(CSC165)_Oct10_Folding Problem p2

Folding Times	Up (u) or Down (D)
1	D
2	UDD
3	UUDDUDD
4	…

We first did 3 experiment and tried to find the pattern. After having a guess, we, then, can make prediction based on the pattern we assumed, and compare it to the actual experiment.

Predictions	Actual results
D	D
U     D     D	UDD
U U D D U D D	UUDDUDD
	…

We found it easier to do when list the predicted result like shown in the table above. We actually thought it in a recursive way. We saw a triangle containing 4 result as a small unit of the problem. 

                                          D                    or              U                     or ...

                                      U D D                              U U D

Because the results in red color are always identical and in green will always be different, we can easily know all the red ones if the line above is given, and every the green one if any green one is known.  Clearly, the red ones are quit simple, but the green one is harder. However, soon, we find that the two result at the right and left end of each line is always U (left) and D (right). This not only shows the problem is solvable because we can predict both all the red and green results, but it lets us to found that everything happened on one side of a line will happen adversely on the other side.

With the pattern found,  we successfully predicted the fourth folding's result.

Predictions

D

U        D        D

U   U   D   D   U   D   D UUDUUDDDUUDDUDD

We can only do the reduction from 1 to n line by line, but we cannot skip any line to do prediction and we found its really hard to write down a math expression to show our prediction. At the end of the lecture the professor indicated that we can try this in possibly. Right! After I know how to convert recursive idea into code in python I will definitely try it out!

  

(CSC165)_Sep 28_Folding Problem

Friday's class was indeed a surprise to me. We actually had an problem solving exercise with a Folding problem. I grouped with a classmate to try to solve the problem together. After we carefully went through and understood the problem, we first wrote down a brief plan, which included steps such as experiments, recording results, finding pattern, making predictions, comparing predictions with actual results and so on. I really think the plan helped us a lot during the problem solving process.

In my previous experience, when trying to solve a relatively complex problem, after figuring out the question, I normally immediately start thinking. However, because there might be many factors that I can start with, it often takes me an unnecessarily long time to start the whole process. In comparison, during the class, in addition to the instruction, which specifically requires a plan, a time limit and pressure from the teamwork encouraged us prepare the plan right after understanding the problem. This turned out to be very helpful for us to organize our thoughts much more efficiently.

We found the pattern and did several successfully prediction, but when we were trying to figure out a mathematic function to show the result with n times of folding, we couldn't do it. Writing this blog is actually a way to look back and I think it worth a try to do it with some programming rather than purely math.

(CSC165)_Sep 20th_Logic XD

I really enjoy studying logic related topics. Although I have learned most of the content of this week when I was in high school back in China, it is still amazing to learn it in a different language and especially with excellent examples. However, the problems including conduction of two statements and negation are new to me.

A tricky word introduced in the class is 'unless', and if we try to think about it in logic directly, it will be very confusing. However, we can translate it to 'if not' to help us understand. For example:

Do not go, unless you are crazy.

Do not go, if you are not crazy.

not crazy => not go

go => crazy      

I think we can generalize it using P and Q:

P unless Q

P if not Q

P => not Q

Q => not P

Q if not P

So, to sum up, we can translate P unless Q to: (1) P if not Q (2) Q if not P.

(CSC165)_Sep 15th_The Intro

I'm seating in the room next to the classroom finishing the last part of the Tutorial Exercise, and I believe it is a good time to write down some thoughts after three lectures of the first week. CSC165 - Mathematical Expression and Reasoning for Computer Science does not teach specifically how to write a program, but, instead, it provides a guide to logically express and understand ideas or arguments in Math or CS world.

Ambiguity is a main difference between human language and machine language; therefore, learning how computers actually run with the programming language is critical.  However, still, it is good to know that programers will often write down comments for not only him/herself but also other readers of the program.

The first week's lectures are actuarially quit simple, but professor Heap emphasized Problem Solving skill, which I believe will be very useful in addition to the 'happiness' of solving a complex problem. There are several steps we should take in general to solve a problem. A clear understanding of the problem and a expectation and plan of the solution are important. Alternative methods should be thought about and notes of both what works and what doesn't are useful. A review right after solving the problem can help us learn more from the problem-solving process. Additionally, professor showed us an example of an conversation between two people, which is very helpful to demonstrate problem-solving process. It especially helped me understand why some method not working can also provide useful information.

To sum up, the content of first week is not hard, but I'm expecting a much deeper discussion in area like logic in the coming weeks.