Like I always say, it's always sad to say goodbye :(
I would just like to say a few things about my experience in this course.
First of all, the course material was very very very very very relevant to me as a computer science student. You may think that this course may not be helpful in the real world or even outside this course, but you would be very wrong. My fellow students and I were utilising knowledge that we've learned from CSC165 without even realising it sometimes! There were many instances of this. For example when fellow students and I were having a friendly argument about something (I forgot exactly what it was), it was settled by bringing in implication and negation, P => Q, P and not Q, etc. Another example is having learned list comprehensions in CSC165 and actually using them in CSC148 and for general testing involving generating a random list (i.e. I used [int(100*random()) for i in range(20)] a lot to test functions I've made). The most recent example of CSC165 being useful outside of CSC165 is for if statements involving conjunction and disjunction. While my fellow classmates and I were discussing about a certain very long if statement with a lot of conjunctions and disjunctions, we wanted to know when it would go to the else statement and how to simplify this if statement. To figure out when it would go to the else statement, we automatically started writing up the if statement in P and Q form with conjunctions and disjunctions and then negated it. We did this automatically and we didn't even notice that we are utilizing tools we've learned in CSC165! This was an awesome experience and it was so much more awesome when we realized what we were doing! This course and all its materials is tremendously more useful than I ever thought it would be!
Though I found that the course started out really tough, everything became really clear afterwards. I'm assuming the a lot of the course material was purposely made to be difficult for us to gain a much better understanding of the less difficult material.
I would like to thank all my fellow classmates, partners, and friends for helping me better understand the material. I would also like to thank all those I've helped as well because it gave me the chance to better understand the material myself by explaining it to someone else!
I would like to thank my awesome TA Ekaterina S! Thanks for putting up with my tutorial section. I know we were very unenthusiastic but you still pushed through and brightened up everybody's day. Thanks for being clear and concise and thanks for staying after tutorials to help us sometimes. Thanks a lot kat!
Finally, I would like to thank our professor Danny Heap, for being a great and wonderful professor. He was very enthusiastic, very helpful, and very understanding. Thanks for always staying after lectures to discuss problems and clear up confusions. Thanks for staying in your office to help students, especially for all those times you've stayed to help students in your office when it was not your declared office hour. Thanks for being a good teacher and a friendly prof. Some of my fellow classmates and I were discussing how much of an amazing professor you are because most of us did not try to memorize anything from this course, but some how we just knew how to do it all.
Thanks for everything professor Danny heap!
Thanks everyone, it has been a great, enjoyable semester!
Feel free to contact me, see you all around!
Friday 5 April 2013
Sunday 31 March 2013
Halt Right There!
I'm going to be brutally honest here. I haven't had time to review course notes recently and so I was really really lost during the lectures involving reduction and halting functions. I had almost no idea what was going on and I was really confused.
Halts? Halting? Naval_gaze? Infinite loop? Halt cannot exist? What?!?
I felt horrified that I didn't have the slightest clue what was going on especially since Assignment #3's deadline was closing in, which involved using halts. So I did some strenuous reviewing of the lecture notes along with the course notes.
After reviewing, I still felt dazed and confused about what a function halts was all about. It was only when I was semi-explaining (I had a vague idea of what halts was but didn't really understand it) the course notes/lecture notes to a fellow CSC165 classmate that I had an epiphany and almost fully understood what halts is all about.
Halts is a function that would take a function and an input as a parameters and return True if and only if the given function halted on the given parameter.
Halts has proven to not be computable (i.e. impossible to write in code) because there exists a contradiction. The proof is in the course notes on page 70. With this knowledge in mind, we can reduce the halting function to another function that is similar and show that a contradiction exists to prove that this other function can not be computed as well.
For example, let's consider this function (I made this example and I'm assuming this function is not computable so let me know if I'm mistaken):
Now, let's assume this function is computable and reduce the uncomputable function halts to this function:
Assume prints_something is computable
So far this doesn't tell us anything. Now let's create an arbitrary function that function prints_something will analyze:
Considering the function f_naught, we can see that if F(i) (a function and input that was passed to halts) halts, f_naught will print something thus prints_something will return True. If F(i) does not halt, f_naught will never print something and prints_something will return False.
So now let's put all these functions together. Obviously, f_naught must go into halts since it uses F(i) from halts:
Assume prints_something is computable with valid Python code
If F(i) halts, prints_something(f_naught,'') will return True because the "F(i)" line in f_naught will stop running, thus allowing print(g) to print something.Thus halts(F, i) will consequently return True as well.
If F(i) doesn't halt, prints_something(f_naught, '') will return False because the "F(i)" line in f_naught will never stop running, thus never allowing print(g) to print anything. Thus halts(F, i) will consequently return False as well.
Thus halts(F, i) returns True when F(i) halts, and it returns False when F(i) doesn't halt.
Now, the problem should be pretty clear. We've somehow successfully created a halting function!
The meaning of reducing one function to another is if this inner function can be made, the outter function can be made. Thus:
But there exists a contradiction; halts was previously proven to not be computable
Also, if we take the contrapositive of the statement:
Halts? Halting? Naval_gaze? Infinite loop? Halt cannot exist? What?!?
I felt horrified that I didn't have the slightest clue what was going on especially since Assignment #3's deadline was closing in, which involved using halts. So I did some strenuous reviewing of the lecture notes along with the course notes.
After reviewing, I still felt dazed and confused about what a function halts was all about. It was only when I was semi-explaining (I had a vague idea of what halts was but didn't really understand it) the course notes/lecture notes to a fellow CSC165 classmate that I had an epiphany and almost fully understood what halts is all about.
Halts is a function that would take a function and an input as a parameters and return True if and only if the given function halted on the given parameter.
Halts has proven to not be computable (i.e. impossible to write in code) because there exists a contradiction. The proof is in the course notes on page 70. With this knowledge in mind, we can reduce the halting function to another function that is similar and show that a contradiction exists to prove that this other function can not be computed as well.
For example, let's consider this function (I made this example and I'm assuming this function is not computable so let me know if I'm mistaken):
def prints_something(f, x):
''' (function, object) -> bool
Return whether the given function prints anything on the given input x.
'''
# Here exists valid Python code that scans the functions codes and
# returns True if and only if the given function prints anything on
# the given input x
Now, let's assume this function is computable and reduce the uncomputable function halts to this function:
Assume prints_something is computable
def halts(F, i):
''' (function, object) -> bool
Return True if and onlf if function F halts on input i.
'''
def prints_something(f, x):
''' (function, object) -> bool
Return whether the given function prints
anything on the given input x.
'''
# Here exists valid Python code that scans the functions codes and
# returns True if and only if the given function prints anything on
# the given input x
pass
pass
So far this doesn't tell us anything. Now let's create an arbitrary function that function prints_something will analyze:
def f_naught(g):
''' (str) -> NoneType
After calling F(i), the function and input that was passed
to halts as arguments, print g.
'''
F(i)
print(g)
Considering the function f_naught, we can see that if F(i) (a function and input that was passed to halts) halts, f_naught will print something thus prints_something will return True. If F(i) does not halt, f_naught will never print something and prints_something will return False.
So now let's put all these functions together. Obviously, f_naught must go into halts since it uses F(i) from halts:
Assume prints_something is computable with valid Python code
def halts(F, i):
''' (function, object) -> bool
Return True if and onlf if function F halts on input i.
'''
def prints_something(f, x):
''' (function, object) -> bool
Return whether the given function prints
anything on the given input x.
'''
# Here exists valid Python code that scans the functions codes and
# returns True if and only if the given function prints anything on
# the given input x
def f_naught(g):
''' (str) -> NoneType
After calling F(i), the function and input that was passed
to halts as arguments, print g.
'''
F(i)
print(g)
return prints_something(f_naught, '')
If F(i) halts, prints_something(f_naught,'') will return True because the "F(i)" line in f_naught will stop running, thus allowing print(g) to print something.Thus halts(F, i) will consequently return True as well.
If F(i) doesn't halt, prints_something(f_naught, '') will return False because the "F(i)" line in f_naught will never stop running, thus never allowing print(g) to print anything. Thus halts(F, i) will consequently return False as well.
Thus halts(F, i) returns True when F(i) halts, and it returns False when F(i) doesn't halt.
Now, the problem should be pretty clear. We've somehow successfully created a halting function!
The meaning of reducing one function to another is if this inner function can be made, the outter function can be made. Thus:
prints_something is computable implies halts is computable.
But there exists a contradiction; halts was previously proven to not be computable
Also, if we take the contrapositive of the statement:
"prints_something is computable implies halts is computable"
We get:
"halts is not computable implies prints_something is not computable"
Thus, since halts was previously proven to not be computable, this implies prints_something is also not computable!
I hope this helps someone better understanding the halting function and related information!
I hope this helps someone better understanding the halting function and related information!
Sunday 24 March 2013
Understanding Big-Oh (upperbounds) with the help of 1i
The concept of Big-Oh can be quite terrifying if you don't really understand it at first. However, after more rigorous overview of course notes and reading students' slogs about Big-Oh, I felt much more comfortable with this concept and now I know why it is such an important concept for computer science students.
Refer to 1i's March 21st, 2013 slog post : http://oneicsc165.blogspot.ca/
In this course, we've been dealing with proofs for a while now and it is fairly easy to just focus on the the structure of the proof, the symbolic statement of the proof, and the math involved in linking the antecedent to the consequent. However, because it is fairly easy to do this now and it almost becomes an automatic thought process, it becomes fairly easy to forget about what each line actually means outside of all the math and steps.
This is why I liked 1i's approach at understanding exactly what Big-Oh means by going through and understanding each step of a proof. If you understand what each of the relevant lines of the proof mean instead of just performing the steps to finish the proof, you'll have a better understanding of Big-Oh.
Through each step, 1i continuously reminds us that we are making our function f(n) that is bounded by our function g(n), bigger and bigger and eventually it is shown that a constant multipled by function g(n) is still bigger in the end. This is what it means to have an upper bound and this is what Big-Oh means. Through the proof, which I initially thought was just some mathematical equations, operations, inequalities, etc that would not give us a bigger/real world picture, and through 1i's slog post, I now have a better understanding of what Big-Oh actually means.
Thanks 1i for your post!
Refer to 1i's March 21st, 2013 slog post : http://oneicsc165.blogspot.ca/
In this course, we've been dealing with proofs for a while now and it is fairly easy to just focus on the the structure of the proof, the symbolic statement of the proof, and the math involved in linking the antecedent to the consequent. However, because it is fairly easy to do this now and it almost becomes an automatic thought process, it becomes fairly easy to forget about what each line actually means outside of all the math and steps.
This is why I liked 1i's approach at understanding exactly what Big-Oh means by going through and understanding each step of a proof. If you understand what each of the relevant lines of the proof mean instead of just performing the steps to finish the proof, you'll have a better understanding of Big-Oh.
Through each step, 1i continuously reminds us that we are making our function f(n) that is bounded by our function g(n), bigger and bigger and eventually it is shown that a constant multipled by function g(n) is still bigger in the end. This is what it means to have an upper bound and this is what Big-Oh means. Through the proof, which I initially thought was just some mathematical equations, operations, inequalities, etc that would not give us a bigger/real world picture, and through 1i's slog post, I now have a better understanding of what Big-Oh actually means.
Thanks 1i for your post!
Saturday 16 March 2013
The Folding Problem
After reading about Mandy's "Streetcar Drama" and attempting it myself last week, I've decided that I'm going to try solving the "Folding" problem Danny Heap has presented to us in lectures.
The "Folding Problem" handout can be found here:
http://www.cdf.toronto.edu/~heap/165/W13/ProblemSolving/folding.pdf
1. Understand the problem:
What the problem presented to us is finding a solution to predict the sequence of up creases and down creases for any number of times you carry out a folding operation.
2. Device a plan:
My plan - a bit rudimentary and brute force - is to do carry out fold operations starting from 1 fold and observe any apparent patterns in the next fold that are relative to the the first fold. I will do this until I find a certain/definite pattern:
3. Carry out the plan:
Let v represent up creases and ^ represent up creases.
Here's a look at the table again, pointing out the noticable patterns:
4. Look back:
As we can see, the first crease, which is an up crease, remains throughout each new fold and it is the pivotal point of the crease sequence. There is always an equal number of creases to the left of the pivotal first crease and to the right of the pivotal first crease. After each new fold, the previous crease sequence is replicated to the right of the middle crease sequence. Most importantly, the sub crease sequence to the left of the middle pivotal first crease is a 180 degree rotation of the sub crease sequence to the right of the middle pivotal first crease. This means that each new fold has the previous fold's crease sequence to the right of the middle crease, which is the first initial up crease, and to the left of that middle crease is the 180 degree rotation of the previous fold's crease sequence. These patterns are shown in the table above with the first crease, which is the pivotal point through each new fold, shown as |v| and the sub crease sequence that are 180 degree rotations of eachother shown in green and red. Also, the crease sequence with the slight blue background colour shows that the previous fold's crease sequence is exactly the same as the sub crease sequence to the right of the middle crease on the next fold. Here is the necessary information again listed:
Now, with this information, we can accurately predict a pattern.
Using Python, we can write a miniture program to predict the sequence of creases for n folds:
Yay! I used recursion!
This Python has been tested and is working! Please feel free to try it out yourself!
The "Folding Problem" handout can be found here:
http://www.cdf.toronto.edu/~heap/165/W13/ProblemSolving/folding.pdf
1. Understand the problem:
What the problem presented to us is finding a solution to predict the sequence of up creases and down creases for any number of times you carry out a folding operation.
2. Device a plan:
My plan - a bit rudimentary and brute force - is to do carry out fold operations starting from 1 fold and observe any apparent patterns in the next fold that are relative to the the first fold. I will do this until I find a certain/definite pattern:
3. Carry out the plan:
Let v represent up creases and ^ represent up creases.
Folds
|
Crease Sequence
|
1
|
v
|
2
|
^vv
|
3
|
^^vv^vv
|
4
|
^^v^^vvv^^vv^vv
|
Here's a look at the table again, pointing out the noticable patterns:
Folds
|
Crease Sequence
|
1
|
|v|
|
2
|
^|v|v
|
3
|
^^v|v|^vv
|
4
|
^^v^^vv|v|^^vv^vv
|
4. Look back:
As we can see, the first crease, which is an up crease, remains throughout each new fold and it is the pivotal point of the crease sequence. There is always an equal number of creases to the left of the pivotal first crease and to the right of the pivotal first crease. After each new fold, the previous crease sequence is replicated to the right of the middle crease sequence. Most importantly, the sub crease sequence to the left of the middle pivotal first crease is a 180 degree rotation of the sub crease sequence to the right of the middle pivotal first crease. This means that each new fold has the previous fold's crease sequence to the right of the middle crease, which is the first initial up crease, and to the left of that middle crease is the 180 degree rotation of the previous fold's crease sequence. These patterns are shown in the table above with the first crease, which is the pivotal point through each new fold, shown as |v| and the sub crease sequence that are 180 degree rotations of eachother shown in green and red. Also, the crease sequence with the slight blue background colour shows that the previous fold's crease sequence is exactly the same as the sub crease sequence to the right of the middle crease on the next fold. Here is the necessary information again listed:
- First crease is an up crease
- First crease remains as the middle crease in the sequence throughout each new fold
- After each new fold, the previous fold's crease sequence is replicated to the right of the middle crease, which is the initial upcrease, and a 180 degree rotation of the previous fold's crease sequence is on the left of the middle crease
Now, with this information, we can accurately predict a pattern.
Using Python, we can write a miniture program to predict the sequence of creases for n folds:
def crease_sequence(folds):
''' (int) -> str
Return the crease sequence of a paper with certain number of given folds.
'''
if folds == 1:
return 'v'
else:
previous_seq = crease_sequence(folds - 1)
return rotate(previous_seq) + 'v' + previous_seq
def rotate(sequence):
''' (str) -> str
Return a 180 degree rotation of a given crease sequence.
'''
rotation = ''
for c in sequence:
if c == 'v':
rotation = '^' + rotation
elif c == '^':
rotation = 'v' + rotation
return rotation
Yay! I used recursion!
This Python has been tested and is working! Please feel free to try it out yourself!
Thursday 7 March 2013
What??? That was possible???
I've recently been browsing Slogs of fellow students and I've stumbled upon a very interesting post by Mandy Xu slog: http://mandyxu.blog.com/
During one of Danny Heap's lectures, a problem presented to us as "Streetcar Drama" was discussed. We did not really go in-depth on this problem and I left with the impression that this problem was unsolvable because there just wasn't enough information.
However, Mandy's slog showed me that this problem did actually have a solution and I should not have been so lazy, taking the easy path of assuming that it was unsolvable so I wouldn't have to think about it much more!
Here is the "Streetcar Drama" problem:
There are two friends having a conversation on a streetcar. We'll label them A and B:
A: Haven't seen you in a long time! How old are your three kids now?
B: The product of their ages (rounded down to nearest) is 36.
A: That doesn't really answer my question.
B: Well, the sum of their ages is - [fire engine goes by]
A: That still doesn't tell me how old they are.
B: Well, the eldest plays piano.
A: Okay, I see: their ages are - [you have to get off the streetcar]
Mandy concisely takes a mathematical approach to solving this problem. The best part of her post is that she does not tell you the answer right away. She simply gives you hints to how you might come close to the answer at first, so you can try to figure it out for yourself first.
Here was my thought process of reading her post:
As I was going along with her post, I prevented myself from scrolling all the way to see the next step or answer and only considering some of her hints to see whether I can solve this myself first.
So the first piece of information that is given to us is "The product of their ages (rounded down to the nearest) is 36." Thus you can represent this mathematically using 3 variables:
x = age of first child
y = age of second child
z = age of third child
thus x*y*z = 36
Before looking at any more of Mandy's solution or hints, I tried to solve this problem myself further first. So I considered the line "Well, the eldest plays piano."
This tells us that of the three children, there is 1 older than the others.
Let x = the eldest child. Then y and z must be < x.
Thus y and z may or may not be the same age, but we know they have to be younger.
since x*y*z = 36
What 3 numbers, one of which must be larger than the other two, gives you a product of 36?
Well, let's consider all the pairs of natural numbers that multiply to give you 36:
1 * 36 = 36
2 * 18 = 36
3 * 12 = 36
4 * 9 = 36
6 * 6 = 36
Now let's try to split any of these numbers so that they're a combination of 3 numbers, with one of the numbers being greater than the other two numbers:
1 * 1 * 36 = 36
1 * 2 * 18 = 36
1 * 3 * 12 = 36
1 * 4 * 9 = 36
2 * 3 * 6 = 36
2 * 2 * 9 = 36
3 * 3 * 4 = 36
Thus one x, y, and z have to be one of the combinations above. What other lines give us more information??
I on my own can not decipher the lines of information much further. The only things I can think of, that may not be entirely concrete are:
1 * 1 * 36 = 36
1 * 2 * 18 = 36
1 * 3 * 12 = 36
1 * 4 * 9 = 36
3 * 3 * 4 = 36
During one of Danny Heap's lectures, a problem presented to us as "Streetcar Drama" was discussed. We did not really go in-depth on this problem and I left with the impression that this problem was unsolvable because there just wasn't enough information.
However, Mandy's slog showed me that this problem did actually have a solution and I should not have been so lazy, taking the easy path of assuming that it was unsolvable so I wouldn't have to think about it much more!
Here is the "Streetcar Drama" problem:
There are two friends having a conversation on a streetcar. We'll label them A and B:
A: Haven't seen you in a long time! How old are your three kids now?
B: The product of their ages (rounded down to nearest) is 36.
A: That doesn't really answer my question.
B: Well, the sum of their ages is - [fire engine goes by]
A: That still doesn't tell me how old they are.
B: Well, the eldest plays piano.
A: Okay, I see: their ages are - [you have to get off the streetcar]
Mandy concisely takes a mathematical approach to solving this problem. The best part of her post is that she does not tell you the answer right away. She simply gives you hints to how you might come close to the answer at first, so you can try to figure it out for yourself first.
Here was my thought process of reading her post:
As I was going along with her post, I prevented myself from scrolling all the way to see the next step or answer and only considering some of her hints to see whether I can solve this myself first.
So the first piece of information that is given to us is "The product of their ages (rounded down to the nearest) is 36." Thus you can represent this mathematically using 3 variables:
x = age of first child
y = age of second child
z = age of third child
thus x*y*z = 36
Before looking at any more of Mandy's solution or hints, I tried to solve this problem myself further first. So I considered the line "Well, the eldest plays piano."
This tells us that of the three children, there is 1 older than the others.
Let x = the eldest child. Then y and z must be < x.
Thus y and z may or may not be the same age, but we know they have to be younger.
since x*y*z = 36
What 3 numbers, one of which must be larger than the other two, gives you a product of 36?
Well, let's consider all the pairs of natural numbers that multiply to give you 36:
1 * 36 = 36
2 * 18 = 36
3 * 12 = 36
4 * 9 = 36
6 * 6 = 36
Now let's try to split any of these numbers so that they're a combination of 3 numbers, with one of the numbers being greater than the other two numbers:
1 * 1 * 36 = 36
1 * 2 * 18 = 36
1 * 3 * 12 = 36
1 * 4 * 9 = 36
2 * 3 * 6 = 36
2 * 2 * 9 = 36
3 * 3 * 4 = 36
Thus one x, y, and z have to be one of the combinations above. What other lines give us more information??
I on my own can not decipher the lines of information much further. The only things I can think of, that may not be entirely concrete are:
- Friend A asked how old are your "kids" now. Usually you wouldn't refer to someone's child as a "kid" if that child was 18 or older. Thus I don't think the eldest can be 18 or 36. This is not a concrete assumption though.
- Friend A mentions how he hasn't seen friend B "in a very long time". Assuming "a very long time" means over a year, this may indicate that if friend B does have any children that is 1 years of age, friend B probably wouldn't have known about it (unless through social networking). Thus I don't think any of the children can be 1 years of age. This is also not a concrete assumption as well.
- Finally, friend B mentions that the eldest plays piano. Children don't go to school until 4, the youngest age children usually start taking piano lessons is age 5 or 6. At that age, they are just starting to learn how to play the piano. Thus to be able to "play" the piano, they must be older than 5 or 6. These assumptions are also not concrete
With the not-for-sure information I gathered through real-life intuition, this would mean any combination with:
- ages >= 18 would not be valid
- age 1 would not be valid
- and the eldest has to be >= 6 (assuming children can start playing the piano after at least a year of lessons)
2 * 3 * 6 = 36
2 * 2 * 9 = 36
This leaves us with 1 combination:
2 * 2 * 9
Thus x = 9, y = 2, and z = 2
Since my steps to the solution involves making some very bold assumptions, I am not confident in this solution at all. I am, however, happy with the fact that I even found a solution. This is the point where I looked at Mandy's steps and solutions to compare.
Well surprise surprise. After I looked at Mandy's solutions, I have the same answers!!! HOWEVER, the steps I took were completely wrong and ridiculous!
Mandy's solution was completely mathematical and the main pieces of information taken in and considered were:
- The product of their ages is 36
- The sum of their ages doesn't give you any exact information
- And there is an eldest
The biggest clue I missed was that the sum of their ages doesn't give you an exact answer.
Thus this means there are two product of 3 numbers, x*y*z, whose sum are the same:
As Mandy demonstrated, just find the possible combinations (as I did earlier), find the two combinations that have an identical sum, and choose the one that has only 1 exact eldest!
I would like to thank Mandy for posting that and for making me realize that I should not be so lazy when it comes to thinking about a complex problem!
Wednesday 27 February 2013
Proofs: Simple Structures, Complicated Content
I just wanted to slog about how to generally start a proof and set it up/structure it. There is nothing more really to say about writing up proofs beyond that because each proof is unique and the meatiest part of the proof, finding the connections, is vastly different with each different proof.
The example I will be using (even though this example is covered in lecture, I want to go more in-depth, step-by-step):
"For every natural number n, n² odd implies that n is odd"
1. Decide whether you want to prove the statement or disprove the statement. Do this by using intuition or scribbling some cases you think will make the statement wrong. Basically look for some counter-examples.
Since I can't think of any odd numbers` that has an even root, I'm going to attempt to prove this.
2. Now you're ready to begin. Always start with the symbolic representation of the original statement of what you're trying to prove or disprove. After figuring out the symbolic representation of the statement, if you decided you want to disprove it, NEGATE the statement before proceeding with the next steps.
- What does an odd natural number mean symbolically??? We'll have to refer to the symbolic definition of what it means to be an odd number by either looking it up on the internet, or finding it in the Course Notes.
- We see that for a natural number to be odd, it means there exists a natural number where 2 multiplied by that natural number, plus one, equals to our odd number. Thus the symbolic statement would be:
∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
- Since we want to prove this, then we don't need to negate it.
3. Now it's time to set up the structure for the proof, while leaving out the meat of it. While setting up the structure for a proof, you want to follow these guide lines:
- Start from left to right of the symbolic statement
- Whenever you have have a Universal Quantifier (∀), you want to assume there is a generic number of this set, and then proceed with the proof with everything below with one indent. After completing the structure and/or proof for all the proceeding elements after the universal quantifier, the whole statement after the universal quantifier, including the universal quantifier should be restated in conclusion form, aligned vertically with the original assumption line of this universal quantifier.
- Assume x∋Y # x is a generic to introduce ∀
- proceeding lines start here vertically (without a bullet obviously)
- # ***Lines connecting the antecedent to the consequent ***
- Then x∋Y................ # conclude for all x in Y
- For our example:
- Assume ∀n∋N # n is a generic natural number to introduce ∀
- Then conclude ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1) # for all n in N
- Whenever you have an Existential Quantifier (∃), you want to "pick" or "let" that number equal to something that you haven't decided yet, unless the existential is a part of your antecedent for a direct proof. So you want to have either:
- pick x = _____ then x∋Y
- or let x = _____ then x∋Y
- For our example, since our existential is part of our antecedent for a direct proof, we don't pick until we get the the consequent part of our proof
- Whenever you get to an antecedent of an implication, you want to assume the antecedent is true and the lines proceeding the proof should be indented by one. The proceeding lines should be the meat of your proof where you show a connection from the antecedent to the consequent. Then, after these lines, the consequent should be stated. Then on the next line afterwards, the whole implication should be stated without the indent, thus lined back up with the antecedent vertically.
- Assume x = y # x = y is an example antecedent
- proceeding lines start here vertically (without the bullet obviously)
- then consequent
- Then x=y ⇒consequent
- For our example:
- Then ∃ k∋N, n² = 2k + 1
- Then ∃ k₀∋N, n² = 2(k₀) + 1
- Then (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
- Keep in mind that the meatiest part of the proof, the fruit of the proof, the most meaningful part of the proof, the hardest part of the proof, are the ***Lines connecting the antecedent to the consequent ***, from the antecedent assumption. Thus you can have this structure set up while leaving space for these lines.
4. If you suspect that your antecedent implies a conjunction, you may want to have different cases set up in your proof that follow the same structure guidelines.
5. Now that you have enough information to start, setup, and structure a proof, all you need is to figure out the hard part of connecting any antecedent to the consequent. In the case of just showing if a conjunction or disjunction is true, the same structure can be followed.
- For our example:
- Then ∃ k∋N, n² = 2k + 1
- Then n² - 1 = 2k
- Then (n + 1)(n - 1) = 2k
- Then n = 2(k/(n+1)) + 1
- Then let k₀ = (k/(n+1))
- Then∃ k₀∋N, n² = 2(k₀) + 1
6. When concluding a disprove, state that the original statement is incorrect because you showed the negation to be true.
7. This is just a simple guide, there are many other things you may need to think of while proving such as should you take the contrapositive of the statement? Should you perform a direct proof? Should you perform an indirect proof? Should you prove by contradiction? Etc.
So he final product for our proof of ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
is:
- Assume ∀n∋N # n is a generic natural number to introduce ∀
- Then ∃ k∋N, n² = 2k + 1
- Then n² - 1 = 2k
- Then (n + 1)(n - 1) = 2k
- Then n = 2(k/(n+1)) + 1
- Then let k₀ = (k/(n+1))
- Then∃ k₀∋N, n² = 2(k₀) + 1
- Then ∃ k₀∋N, n² = 2(k₀) + 1
- Then (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
- Then conclude ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1) # for all n in N
So this would be a proper proof with proper structure (minus the bullet points on each line).
Hope someone finds this helpful!
Wednesday 20 February 2013
Applying skills learned in CSC165
I found it very interesting that something we've learned from CSC165 was very useful and relevant to courses outside of CSC165. For example, in our CSC148 project, one of our tasks was to compare two sets of elements to see whether they had any elements in common.
After reading the instructions for this particular task my partners and I instantly thought of Venn Diagrams, sets, subsets, etc. We were conditioned on how to approach this question logically through CSC165. So basically, what it boiled down to, was that we had to create a class method that would check whether two sets had no elements in common. In regards to Venn Diagrams, this meant that there must be no overlapping elements in the two sets (no elements in the intersection of the two sets).
Thinking about this logically, like we were taught in CSC165, was not so difficult anymore. What was even more surprising was that we've made very similar functions in CSC165 lectures. We've made functions that addressed these exact questions and the functions involved List Comprehension!
We were taught how to understand and make use of list comprehension in CSC165, but not in CSC148, and now my partners and I had the opportunity to apply what we've learned from one course to the other. It was an exciting moment!
The best part of this experience was that the class method worked flawlessly with the list comprehension and the method's body was only a one-liner; return one list comprehension.
Now, here's what I was talking about:
The required method's docstring:
"Return True iff there are no elements in common between this multiset and the other multiset."
Our body for the function:
return True not in [item in other.multiset for item in self.multiset]
This way, our function looked a lot cleaner and a lot more lines of space were saved because we didn't have to create actual looks to make this function (which we would have done if we didn't know about list comprehensions).
Subscribe to:
Posts (Atom)