csc165 week7 slog:
In this week's lecture, some inference rules about proofs were introduced. These rules help me to understand the logics of proofs better and can save my time for consideration and proving. For example,before I know the implication elimination rule, usually I would transfer "A => B" to "¬A V B" first,then if I want to infer "¬B => ¬A",I would apply implication rule to "¬B => ¬A" to get "¬A V B". Now I can eliminate these redundant processes, and directly get "¬B => ¬A" from "A => B" by implication elimination rule.
In addition, I had a brand new comprehension about how programs work by learning sorting strategies and the algorithm involves in the sorting. I learnt that the "running time" in computer science is not the actual time like the time we get after testing in python which has a unit of seconds. The "running time" is the number of steps the algorithm takes. And if we really want to compare two sorting strategies' running times. We can compare how their steps grow, and in this situation, only the highest-order term is used for the comparison and constant factor does not matter . For instance, if the running time of A is 8n^3 and the running time of B is 100n^3. Another example is that if the running time of A is 8n^3 + n and the running time of B is 8n^3 + n^2 + n. In both examples, their running time have no difference, since they have the same highest-order term, and this relationship can be shown by using an asymptotic notation,asymptotic upper-bound O(f(x)),and both A and B'S running times are in O(n^2). And an example for two running times that are different is n^2 + n and n^3 + n.
The idea of linear search is also taught in the lecture. Linear search is a method to get the running time of a function by going through the function step by step. Therefore, if I want to get the correct running time for a function, I should understand the code first, then it will become very straightforward by using linear search.
Monday, 27 October 2014
Monday, 20 October 2014
csc165 week6 slog:
In this week's lecture, a new terminology, non-boolean function is introduced to us. It is a function that returns a non-boolean value instead of True or False. For example, x + 1, 2x ,sin(x) are non-boolean functions and x > 1,8x != x are not non-boolean functions. Another new terminology called "floor" is also used this week, we can write "the floor of x" as ⌊x⌋. I think it is really easy to mix ⌊x⌋ with the absolute value of x, |x|. And the floor of x is the largest integer smaller or equal to x. For example, if x = 3.99, ⌊x⌋ equals 3, and if x = 8, ⌊x⌋ is 8. Learning more new terminologies can help me talk in a more professional way and explain things more easily when I discuss about math and computer science with others.
Then the professor taught us some new methods about proofs such as disprove a claim, proof by cases, and proof about limits. As far as I can consider, to disprove a claim is to prove the negation of the claim is right. For example, if the claim S is "Everyone likes playing basketball", then we can prove ¬S that "There is someone who does not like playing basketball".
About the proof about limits, I consider it to be the proof of a claim with a variable or more variables which are undecided. For example, the claim S1: "∀ x ∈ R, ∃y ∈ R, ∀z ∈ R, x > y => x > z". The "y" in S1 is the variable which is not decided, and we can pick a number of y in order to satisfy the claim for every situation of x and z. And the key point of the proof of limits is to choose a wise number of the "y",the undecided variable. I find that sometimes visualizes limit proof with a graph can help us choose and check the number we pick.
In this week's lecture, a new terminology, non-boolean function is introduced to us. It is a function that returns a non-boolean value instead of True or False. For example, x + 1, 2x ,sin(x) are non-boolean functions and x > 1,8x != x are not non-boolean functions. Another new terminology called "floor" is also used this week, we can write "the floor of x" as ⌊x⌋. I think it is really easy to mix ⌊x⌋ with the absolute value of x, |x|. And the floor of x is the largest integer smaller or equal to x. For example, if x = 3.99, ⌊x⌋ equals 3, and if x = 8, ⌊x⌋ is 8. Learning more new terminologies can help me talk in a more professional way and explain things more easily when I discuss about math and computer science with others.
Then the professor taught us some new methods about proofs such as disprove a claim, proof by cases, and proof about limits. As far as I can consider, to disprove a claim is to prove the negation of the claim is right. For example, if the claim S is "Everyone likes playing basketball", then we can prove ¬S that "There is someone who does not like playing basketball".
About the proof about limits, I consider it to be the proof of a claim with a variable or more variables which are undecided. For example, the claim S1: "∀ x ∈ R, ∃y ∈ R, ∀z ∈ R, x > y => x > z". The "y" in S1 is the variable which is not decided, and we can pick a number of y in order to satisfy the claim for every situation of x and z. And the key point of the proof of limits is to choose a wise number of the "y",the undecided variable. I find that sometimes visualizes limit proof with a graph can help us choose and check the number we pick.
Monday, 13 October 2014
csc165 week5 slog：
I spent most of my study time for csc165 last weekend because of the wednesday's test. I did not do very well on my assignment and previous quizzes, so I really want to get a good test mark to regain the confidence for this course. And it worked. On monday's quiz, I felt I never feel so confident when I hand in the quiz. I did three past mid-term tests to prepare for this test. However, because I really cared about my marks, I wrote too much explanation for the first and second questions, and I did not have enough time to consider the last question carefully and thoroughly.
The question asked me to prove that in (S3: ∃x ∈ D,(P(x) ∧ ¬Q(x)) v (¬P(x) ∧ Q(x))) and (S4:∃x∈ D,(¬P(x) v ¬Q(x))), one statement is true,and the other is false.
My brain was in a mess, and I thought I should first do something to make the s4 looks different:
∃x ∈ D,(P(x) ∧ ¬Q(x)) v (¬P(x) ∧ Q(x)))
<=> ∃x ∈ D,((P(x) ∧ ¬Q(x)) v ¬P(x)) ∧ ((P(x) ∧ ¬Q(x)) v Q(x)) #distributive law
<=> ∃x ∈ D,((P(x)v ¬P(x)) ∧ (¬Q(x) v ¬P(x))) ∧ ((P(x) vQ(x))∧ (¬Q(x) v Q(x))) #distributive law
<=> ∃x ∈ D, (¬Q(x) v ¬P(x)) ∧ (P(x) vQ(x)) # identity law
<=> ∃x ∈ D, ¬(Q(x) ∧ P(x)) ∧ (P(x) v Q(x)) #
And then, I found S3: ∃x ∈ D, (¬Q(x) v ¬P(x)) ∧ (P(x) vQ(x)) and S4: ∃x∈ D,(¬P(x) v ¬Q(x))
Now, I only have to give an example that when ((P(x) vQ(x)) is false to make S3 false. And my example is : D = {1,2,3,4,5), Q = {6}, P = {4}. I am not sure whether I am correct or not. I think I should be right because in this case, no P and Q is in D, so for all x in D,(P(x) or Q(x)) is false. And x in D is not (Q(x) and P(x)). While professor's solution is D ={1,2},P = {1}, Q = {1}. In professor's example, he proves that there is no x in D such that it is not (Q(x) and P(x)) and (P(x) or Q(x)), since the only x in P and Q is shared. The x that are not (P(x) and Q(x)) are outside P and Q, therefore, there does not exist a x in D such that (P(x) or Q(x)) is true.
In this week's lecture, I was taught many new skills to apply on proof. For example, I can prove a statement by proving its contrapositive, since the contrapositive of a statement is actually equivalent to the statement.
Let me set up a proof question and solve it by using contrapositive.
The square of a even number is even, prove:
∀n∈N, n^2 odd -> n odd
My solution:
I spent most of my study time for csc165 last weekend because of the wednesday's test. I did not do very well on my assignment and previous quizzes, so I really want to get a good test mark to regain the confidence for this course. And it worked. On monday's quiz, I felt I never feel so confident when I hand in the quiz. I did three past mid-term tests to prepare for this test. However, because I really cared about my marks, I wrote too much explanation for the first and second questions, and I did not have enough time to consider the last question carefully and thoroughly.
The question asked me to prove that in (S3: ∃x ∈ D,(P(x) ∧ ¬Q(x)) v (¬P(x) ∧ Q(x))) and (S4:∃x∈ D,(¬P(x) v ¬Q(x))), one statement is true,and the other is false.
My brain was in a mess, and I thought I should first do something to make the s4 looks different:
∃x ∈ D,(P(x) ∧ ¬Q(x)) v (¬P(x) ∧ Q(x)))
<=> ∃x ∈ D,((P(x) ∧ ¬Q(x)) v ¬P(x)) ∧ ((P(x) ∧ ¬Q(x)) v Q(x)) #distributive law
<=> ∃x ∈ D,((P(x)v ¬P(x)) ∧ (¬Q(x) v ¬P(x))) ∧ ((P(x) vQ(x))∧ (¬Q(x) v Q(x))) #distributive law
<=> ∃x ∈ D, (¬Q(x) v ¬P(x)) ∧ (P(x) vQ(x)) # identity law
<=> ∃x ∈ D, ¬(Q(x) ∧ P(x)) ∧ (P(x) v Q(x)) #
And then, I found S3: ∃x ∈ D, (¬Q(x) v ¬P(x)) ∧ (P(x) vQ(x)) and S4: ∃x∈ D,(¬P(x) v ¬Q(x))
Now, I only have to give an example that when ((P(x) vQ(x)) is false to make S3 false. And my example is : D = {1,2,3,4,5), Q = {6}, P = {4}. I am not sure whether I am correct or not. I think I should be right because in this case, no P and Q is in D, so for all x in D,(P(x) or Q(x)) is false. And x in D is not (Q(x) and P(x)). While professor's solution is D ={1,2},P = {1}, Q = {1}. In professor's example, he proves that there is no x in D such that it is not (Q(x) and P(x)) and (P(x) or Q(x)), since the only x in P and Q is shared. The x that are not (P(x) and Q(x)) are outside P and Q, therefore, there does not exist a x in D such that (P(x) or Q(x)) is true.
In this week's lecture, I was taught many new skills to apply on proof. For example, I can prove a statement by proving its contrapositive, since the contrapositive of a statement is actually equivalent to the statement.
Let me set up a proof question and solve it by using contrapositive.
The square of a even number is even, prove:
∀n∈N, n^2 odd -> n odd
My solution:
∀n∈N, n even -> n^2 even
Assume n∈N #n is a natural number
Assume n is even
Then ∃x ∈ N, n = 2x #definition of n even
Then n^2 = (2x)^2 = 4x^2 = 2 * 2 *x^2 # some algebra
Then ∃y ∈ N, n^2 = 4y = 2 * (2y) # let y = x^2 and we know x^2 must be positive
Then ∃z ∈ N, n^2 = 2z # let z = 2y
Then n^2 is even # by definition of n^2 even
Then n is even -> n^2 is even. #from above
Assume n∈N #n is a natural number
Assume n is even
Then ∃x ∈ N, n = 2x #definition of n even
Then n^2 = (2x)^2 = 4x^2 = 2 * 2 *x^2 # some algebra
Then ∃y ∈ N, n^2 = 4y = 2 * (2y) # let y = x^2 and we know x^2 must be positive
Then ∃z ∈ N, n^2 = 2z # let z = 2y
Then n^2 is even # by definition of n^2 even
Then n is even -> n^2 is even. #from above
Then n^2 odd -> n odd. # contrapositive
Then ∀n∈N, n^2 odd -> n odd # conclusion
Then ∀n∈N, n^2 odd -> n odd # conclusion
Another important new idea I learnt this week is the contradiction of the contrapositive. As far as I can consider, this idea is used when the conclusion P is not very clear, so we just use the negation of assumption Q, and prove the negation of Q is wrong which is called contradiction, then we can claim that Q is correct.
Sunday, 5 October 2014
CSC165week4 SLOG:
Review of the quiz#2 question:
Let C be the set of courses, and P(x,y) mean x is a prerequisite for y . CSC108 and CSC463 are courses in C. Write the following symbolically:
CSC 463 has a prerequisite for which CSC108 is not a prerequisite.
My wrong answer was:
¬∃y∈C,∃x∈C, P(CSC108, y) ∧ P(x,CSC463)
Basically, I misunderstood the question. My answer would be right if it says 'CSC 463 has a prerequisite and CSC108 is not a prerequisite' . Now I find out that the thing I am really struggling with is to understand the statement. The phrase 'for which' definitely has a different meaning to 'and', and I knew it, but I still make such mistake.
The right answer is:
∃x∈C, P(x,CSC463) ∧ ¬P(CSC108,x)
If I see such questions next time, I will first rewrite the statement into a more simple and more straightforward sentence. Take this question as an example, there exists a course which is a prerequisite of CSC463, and CSC108 is not a prerequisite of the course. In this way, I will have a smaller chance to misinterpret the statement in the future.
Lectures and assignment:
In this week's lectures, I learnt the concepts of proof. I found proof to be very interesting, since it help me to have deeper comprehension about some mathematical rules. For example, the square of an odd number is also odd. I know this rule many years ago, but I only memorize it ,and never think about why this rule is true.
Based on what I learnt about proof this week, I set up a proof question:
The square of a even number is even, prove:
∀n∈N, n even -> n^2 even
My solution:
Assume n∈N #n is a natural number
Assume n is even
Then ∃x ∈ N, n = 2x #definition of n even
Then n^2 = (2x)^2 = 4x^2 = 2 * 2 *x^2 # some algebra
Then ∃y ∈ N, n^2 = 4y = 2 * (2y) # let y = x^2 and we know x^2 must be positive
Then ∃z ∈ N, n^2 = 2z # let z = 2y
Then n^2 is even # by definition of n^2 even
Then n is even -> n^2 is even. #from above
Then ∀n∈N, n even -> n^2 even # conclusion
(P.S.: I cannot ensure this is 100% correct. If you find some errors, please let leave some comments.)
Review of the quiz#2 question:
Let C be the set of courses, and P(x,y) mean x is a prerequisite for y . CSC108 and CSC463 are courses in C. Write the following symbolically:
CSC 463 has a prerequisite for which CSC108 is not a prerequisite.
My wrong answer was:
¬∃y∈C,∃x∈C, P(CSC108, y) ∧ P(x,CSC463)
Basically, I misunderstood the question. My answer would be right if it says 'CSC 463 has a prerequisite and CSC108 is not a prerequisite' . Now I find out that the thing I am really struggling with is to understand the statement. The phrase 'for which' definitely has a different meaning to 'and', and I knew it, but I still make such mistake.
The right answer is:
∃x∈C, P(x,CSC463) ∧ ¬P(CSC108,x)
If I see such questions next time, I will first rewrite the statement into a more simple and more straightforward sentence. Take this question as an example, there exists a course which is a prerequisite of CSC463, and CSC108 is not a prerequisite of the course. In this way, I will have a smaller chance to misinterpret the statement in the future.
Lectures and assignment:
In this week's lectures, I learnt the concepts of proof. I found proof to be very interesting, since it help me to have deeper comprehension about some mathematical rules. For example, the square of an odd number is also odd. I know this rule many years ago, but I only memorize it ,and never think about why this rule is true.
Based on what I learnt about proof this week, I set up a proof question:
The square of a even number is even, prove:
∀n∈N, n even -> n^2 even
My solution:
Assume n∈N #n is a natural number
Assume n is even
Then ∃x ∈ N, n = 2x #definition of n even
Then n^2 = (2x)^2 = 4x^2 = 2 * 2 *x^2 # some algebra
Then ∃y ∈ N, n^2 = 4y = 2 * (2y) # let y = x^2 and we know x^2 must be positive
Then ∃z ∈ N, n^2 = 2z # let z = 2y
Then n^2 is even # by definition of n^2 even
Then n is even -> n^2 is even. #from above
Then ∀n∈N, n even -> n^2 even # conclusion
(P.S.: I cannot ensure this is 100% correct. If you find some errors, please let leave some comments.)
Subscribe to:
Posts (Atom)