This week, I learnt how to sort algorithm complexity. Moreover I learnt how to prove and disprove the claim. To prove falsity one must be able to find a negation case. Danny also told us during his lecture about the allowed interference. There are 5 inference type in the proof structure Danny introduced to us at first.
1. Conjunction elimination
2. Existential instantiation
3. Disjunction elimination
4. Implication elimination
5. Universal elimination
All above 5 allowed inferences are basically what I have learnt last week when I learnt how to prove the claim through use of proof structure. Nevertheless, thing I found easy was an implication introduction. Unlike an elimination, introduction comes up with an assumption, and based on the assumption introduced, one is able to draw out the conclusion whether the claim is true or false.
The most difficult thing that I have learnt during week 7 is about sorting algorithms. Danny introduced this topic using the card game to enable students to see how algorithms work. Somehow I felt this is a lot like what I learnt in CSC108, when I studied the looping function and its indentation on python programming. However, since I am still on a stage where I am learning Python language, this algorithms which Danny told the class is still unfamiliar to me. I guess that means I need more practice for both CSC108 and CSC165 class.
POLYA's METHOD: Now it is time for challenging question which I made for myself. This time, I followed Polya's method which Danny instructed the class to do.
First, here is the problem. Write out the proof of the below claim,
∀x ∈ N, (∃y∈ N, x² = 2y + 1) → (∃y∈ N, x^6 = 2y +1)
1. Understanding the problem
The problem is asking to prove for all x which is natural number, if there is some x^2 = 3y=1, then there is also x^6 which is equivalent to 2y+1.
2. Devising a Plan
My plan to this problem is to figure out what value I need to substitute for y in order to satisfy the claim. Also I need to keep in mind about the power rule as I need to use this rule to figure out x^6 in terms of x^2. Also what I already know is that there is domain assumption for all x which is natural number. Also ∃y∈ N on the left hand side is included in antecedent which means this ∃y∈ N is also a part of antecedent assumption. Also I need to specify two y values; one for antecedent and the other for consequent by using the symbol y' and yo.
3. Carrying out the Plan
∀x ∈ N, (∃y∈ N, x² = 2y + 1) → (∃y∈ N, x^6 = 2y +1)
Assume x ∈ N # Domain assumption
Assume ∃y∈ N, x² = 2y + 1 # Antecedent assumption
Let yo be such that x = 2yo +1
Let y' = 4yo³ + 6yo² + yo # since yo ∈ N
Then, y' ∈ N.
Then, x^6 = (x²)^3 = (2yo + 1)³ = 2(4yo³ + 6yo² + yo) +1 = 2y' + 1
Then, ∃y∈ N, x^6 = 2y +1
Then, (∃y∈ N, x² = 2y + 1) → (∃y∈ N, x^6 = 2y +1) # introduce∃
Then, ∀x ∈ N, (∃y∈ N, x² = 2y + 1) → (∃y∈ N, x^6 = 2y +1) # introduce ∀
4. Looking back
Looking back this problem, I think it is possible for this claim to true, as I was able to prove this claim using what I have learnt so far from week 1 to 7. I just add few comments on the proof outline just to make sure I did not mess anything up. Also I checked using yo = 1 and y' = 11 to see whether my proof to this question is actually correct.
No comments:
Post a Comment