Summary
With proofs finished, the new material shifted focus to algorithms and efficiency. The algorithms discussed were sorting algorithms and the upper/lower-bounds of of these implementations were analyzed.
Challenges/Thoughts
While other courses have also taught efficiency of sorting algorithms to some degree, the upper-bound and lower-bound was a new concept for me. The difficult part was working with a code to find the number of iterations in its best and worst case scenarios. While the upper-bound and lower-bound allows over and under-estimations of iterations for the appropriate situation, I still found it difficult to accumulate all the steps and write it in manipulable math symbols. Hopefully, this will become easier with more practice.
Example
During lecture, the penny piles problem was mentioned. The professor asked if there was any number that could not be made between 0 and 64 by transferring half of one box's contents at a time (given that the contents contain and even number of coins) where one box started with 0 and the other at 64.
The professor gave some hints to approach the problem. The ones that I found helpful were to work backwards and to find relationships of smaller cases. In the case of smaller cases, he told us that you could scale the problem down. It 12 can be achieved when starting with 0 and 32, 24 can be achieved with 0 and 64 because the relationship is scaled by factor of 2.
With this in mind, I tried finding a relationship between reaching a smaller number and a larger number from the same number of coins. I found that, any even number in the range is solvable and that they all eventually reached 16 on one side and 48 on the other before reaching the solution. Since this was true, all even numbers in the range must work as well because with the allowed operations and total number of coins, if one side is odd, so must the other side. To get to an odd number, the step prior to reaching that odd number would have been contained double the coins of one side while the other would have contained what it has now minus what the first side contained (odd - odd). Since both boxes would have required an even number of coins prior to reaching that even number, and since all even numbers are reachable, all even numbers within the range 0 to 64 must also be solvable.
Friday 31 October 2014
Friday 24 October 2014
Weeks 6 and 7
Summary
The focus over these couple weeks were the structure of proofs and strategies for proving statements. While week 6 focused more on the structure and general thought process of how to approach proofs, week 7 covered the full proof including the numbers or variables required to satisfy or falsify a statement.
Challenges/Thoughts
The real challenge of proofs came from the intuition and thinking required to first understand a statement. While the proof structure has a general template to follow for all statements, each statement is different and requires what is being said to be understood in English. I also learned that while a statement may seem trivial, it is actually not so simple to write down why it is true in formal proof structure.
Example
The example covered in lecture that floor of x (the largest integer that is less than or equal to x) is always smaller than x + 1 was quite interesting. When you read this in English, it seems so obvious that something smaller than or equal to x must be smaller than x + 1, but to convert that into a formal proof requires practice.
In mathematical symbols (LaTeX):
$\forall x \in R, [x] < x + 1$
First we assume a general x' that is a real number $R$.Assume $x in R$
A proof requires all the thoughts required to solve a problem, even thoughts that seem trivial. So we must first state that:
Then [x] <= x # Here we must justify why; and in this case it is due to the definition of floor.
Then we can write the following:
Then x < x + 1 # This is a tautology, always true.
Putting that together:
Then [x] <= x < x + 1
Then [x] < x + 1 # Transitivity
Since, the general number x satisfies [x] < x + 1, the statement is true.
The focus over these couple weeks were the structure of proofs and strategies for proving statements. While week 6 focused more on the structure and general thought process of how to approach proofs, week 7 covered the full proof including the numbers or variables required to satisfy or falsify a statement.
Challenges/Thoughts
The real challenge of proofs came from the intuition and thinking required to first understand a statement. While the proof structure has a general template to follow for all statements, each statement is different and requires what is being said to be understood in English. I also learned that while a statement may seem trivial, it is actually not so simple to write down why it is true in formal proof structure.
Example
The example covered in lecture that floor of x (the largest integer that is less than or equal to x) is always smaller than x + 1 was quite interesting. When you read this in English, it seems so obvious that something smaller than or equal to x must be smaller than x + 1, but to convert that into a formal proof requires practice.
In mathematical symbols (LaTeX):
$\forall x \in R, [x] < x + 1$
First we assume a general x' that is a real number $R$.Assume $x in R$
A proof requires all the thoughts required to solve a problem, even thoughts that seem trivial. So we must first state that:
Then [x] <= x # Here we must justify why; and in this case it is due to the definition of floor.
Then we can write the following:
Then x < x + 1 # This is a tautology, always true.
Putting that together:
Then [x] <= x < x + 1
Then [x] < x + 1 # Transitivity
Since, the general number x satisfies [x] < x + 1, the statement is true.
Friday 26 September 2014
Week 3
Summary of Material
Week three covered conjunction, disjunction, negation, and implication using predicates. Also, a new visual proof called Truth Tables, a neatly organized table of binary elements True and False.
Challenges/Thoughts
The conjunction and disjunction material were very similar to the previous weeks' lectures on union and intersection of sets and therefore was simple to understand. Negation was interesting because it showed that to negate a quantified statement, you could simply replace the negation with the opposite quantifier. (A negation of a universal statement simply requires an existential statement with the negation symbol removed. ) This is very similar to the first week's material where the focus was to simply prove or disprove a statement; where it was taught that a single counter-example would falsify a whole universal statement. It was interesting to see that the material from this week builds upon its previous weeks' and further expands those concepts.
Example
This week's example will be on negation.
Negation of universal quantifier
Ex. All apples in the basket are red.
We can write this as:
A - the universe of all apples, where apples are represented by x
R(x) - where x, the apple, is red
In semi-formal language:
For all x element of A, R(x)
The negation would become:
Not all apples in the basket are red, or
Not (all x element of A, R(x)) - where the Not negation envelopes the whole statement
This although correct, is not preferable because the negation applies to the whole statement. Instead by looking at the meaning, we can reword it to say that there is at least one apple that is not red.
So the final negation is:
There exists an x of element A, Not R(x) - now the Not negation only deals with the R(x) predicate to mean that x does not have the property R (red).
The negation of this statement is similar to falsifying it (This is because of the negation is true, then it must be false.), but it is not necessary to give an example or necessary to be true as it is just another statement.
Week three covered conjunction, disjunction, negation, and implication using predicates. Also, a new visual proof called Truth Tables, a neatly organized table of binary elements True and False.
Challenges/Thoughts
The conjunction and disjunction material were very similar to the previous weeks' lectures on union and intersection of sets and therefore was simple to understand. Negation was interesting because it showed that to negate a quantified statement, you could simply replace the negation with the opposite quantifier. (A negation of a universal statement simply requires an existential statement with the negation symbol removed. ) This is very similar to the first week's material where the focus was to simply prove or disprove a statement; where it was taught that a single counter-example would falsify a whole universal statement. It was interesting to see that the material from this week builds upon its previous weeks' and further expands those concepts.
Example
This week's example will be on negation.
Negation of universal quantifier
Ex. All apples in the basket are red.
We can write this as:
A - the universe of all apples, where apples are represented by x
R(x) - where x, the apple, is red
In semi-formal language:
For all x element of A, R(x)
The negation would become:
Not all apples in the basket are red, or
Not (all x element of A, R(x)) - where the Not negation envelopes the whole statement
This although correct, is not preferable because the negation applies to the whole statement. Instead by looking at the meaning, we can reword it to say that there is at least one apple that is not red.
So the final negation is:
There exists an x of element A, Not R(x) - now the Not negation only deals with the R(x) predicate to mean that x does not have the property R (red).
The negation of this statement is similar to falsifying it (This is because of the negation is true, then it must be false.), but it is not necessary to give an example or necessary to be true as it is just another statement.
Friday 19 September 2014
Weeks 1 & 2
Summary of Material
Starting this week, the course covered the basic transition from casual language to formal, mathematical language. The material covered included Quantification, Predicates, Implications, and Verification/Falsification.
Challenges/Thoughts
The main focus was to give a sense of what formal language resembled and was not too difficult yet. While there were no difficult concepts covered in this week's class, I found vacuous truths to be interesting. I had always thought that to prove a statement to be true, one would have to show that it is not falsifiable and have to show some cases where the statement does appear to be true. Once learning that a statement need only be unfalsifiable, I was at first doubtful that it would be sufficient proof. However, in logic, there is a direct relationship between truth and false, meaning that False and True resemble the relationship between complement sets. Considering False to be the complement of True, if the existence of a false case cannot be proven, then the set of False, or complement of True must be empty; this leads to the conclusion that not True is false.
Example
The example covered for this week's SLOG will cover the bridging between casual language and formal language.
Lets imagine a house with many cats, fat and small (not fat). In the house, there is one play room where most of the cats are kept.
Casual statement: There are some small cats outside the play room.
This sentence states, in formal language, that there is at least one small cat not inside the play room. This can be quantified by an existential quantifier. (I will not be writing formal expression for this week's SLOG.) We will simply represent the universe in the following manner.
Let C be the universe of all the cats in the house.
Let F be the set of all the fat cats in the universe (house).
Let P be the set of all the cats in the play room
In order to prove this statement, only one example of a cat that is both small and not in the room is sufficient, as some in formal language means one or more. That is, a single existence of a cat that is not in the set F and not in the set P.
In order to falsify this statement, we must prove that no cats in the house are small and outside the room. There must be no cats that are both outside the set F and outside the set P. A cat may not be in either set, but cannot be outside both sets.
Starting this week, the course covered the basic transition from casual language to formal, mathematical language. The material covered included Quantification, Predicates, Implications, and Verification/Falsification.
Challenges/Thoughts
The main focus was to give a sense of what formal language resembled and was not too difficult yet. While there were no difficult concepts covered in this week's class, I found vacuous truths to be interesting. I had always thought that to prove a statement to be true, one would have to show that it is not falsifiable and have to show some cases where the statement does appear to be true. Once learning that a statement need only be unfalsifiable, I was at first doubtful that it would be sufficient proof. However, in logic, there is a direct relationship between truth and false, meaning that False and True resemble the relationship between complement sets. Considering False to be the complement of True, if the existence of a false case cannot be proven, then the set of False, or complement of True must be empty; this leads to the conclusion that not True is false.
Example
The example covered for this week's SLOG will cover the bridging between casual language and formal language.
Lets imagine a house with many cats, fat and small (not fat). In the house, there is one play room where most of the cats are kept.
Casual statement: There are some small cats outside the play room.
This sentence states, in formal language, that there is at least one small cat not inside the play room. This can be quantified by an existential quantifier. (I will not be writing formal expression for this week's SLOG.) We will simply represent the universe in the following manner.
Let C be the universe of all the cats in the house.
Let F be the set of all the fat cats in the universe (house).
Let P be the set of all the cats in the play room
In order to prove this statement, only one example of a cat that is both small and not in the room is sufficient, as some in formal language means one or more. That is, a single existence of a cat that is not in the set F and not in the set P.
In order to falsify this statement, we must prove that no cats in the house are small and outside the room. There must be no cats that are both outside the set F and outside the set P. A cat may not be in either set, but cannot be outside both sets.
Subscribe to:
Posts (Atom)