in the lecture , we learnt the halt and countable and computable.
a computable function is a well-defined function, a well- defined function is a 1-1 and onto function .
hat(f,n)is a non-computable function.
using diagonalization , implement halt function with a function that we want to prove that is un-computable.
2014年12月2日星期二
2014年11月24日星期一
csc165 halt NOV.24th.2014
In last week lecture, we leaned about some functions with "halt"
we know that not all the functions are uncomputable.
infinity is not always equals to infinity. If one infinity has more members that has finite numbers then it should be larger.However, two sets have the same size if they are one to one or onto
one to one is that for every x and y f (x ) = f (y ) => x = y
onto is that for every y, there existed a x such that f (x ) = y
we know that not all the functions are uncomputable.
infinity is not always equals to infinity. If one infinity has more members that has finite numbers then it should be larger.However, two sets have the same size if they are one to one or onto
one to one is that for every x and y f (x ) = f (y ) => x = y
onto is that for every y, there existed a x such that f (x ) = y
2014年11月15日星期六
NOV 15th.2014 CSC165 big omega & prove general statement about 2 functions
big omega:
∃C ∈ R+，∃B∈N，∀ n ∈ N,n >=B ⇒ f(n)>=c.g(n)
prove general statement about 2 functions:
I think this is just a little change from the 1function's style. One more assume for the second function and leads to the conclusion of the connection between the 2 functions.Pay attention to the choice of picking B,C sometimes we use the max or min of the two numbers, of we might use the ceiling or the floor.
∀ f,g∈F, (f∈O(h))∧g∈O(h))⇒(f+g)∈O(h)
Prove:
Assume f,g∈F #Just the old thing
assume f∈O(h))∧g∈O(h) #Just the old thing
∃cf ∈ R+ ,∃Bf∈N,∀ n ∈ N, n>=Bf ⇒f(n)<=cf *h(n)# nearly the od thing ,just a little bit different on the c, which becomes cf(also B) now.
∃cg ∈ R+ ,∃Bg∈N,∀ n ∈ N, n>=Bg ⇒g(n)<=cg* h(n)#now the f(n) becomes g(n),which is for the second function.
Pick C = Cf + Cg,Then C∈ R+
Pick B = max(Bf,Bg)
assume n ∈ N ∧ n >=B
Then (f+g)(n) = f(n)+g(n) <=Cf*h(n)+Cg*h(n)
=(Cf+Cg)h(n)=Ch(n)#now we can find how to pick C,which is Cf + Cg
∀ n ∈ N, n>=B,(f+g)∈O(h)
∃cf,cg ∈ R ,∃Bf,Bg∈N,∀ n ∈ N, n>=B⇒(f+g)∈O(h)
∀ f,g∈F, (f∈O(h))∧g∈O(h))⇒(f+g)∈O(h)
∃C ∈ R+，∃B∈N，∀ n ∈ N,n >=B ⇒ f(n)>=c.g(n)
prove general statement about 2 functions:
I think this is just a little change from the 1function's style. One more assume for the second function and leads to the conclusion of the connection between the 2 functions.Pay attention to the choice of picking B,C sometimes we use the max or min of the two numbers, of we might use the ceiling or the floor.
∀ f,g∈F, (f∈O(h))∧g∈O(h))⇒(f+g)∈O(h)
Prove:
Assume f,g∈F #Just the old thing
assume f∈O(h))∧g∈O(h) #Just the old thing
∃cf ∈ R+ ,∃Bf∈N,∀ n ∈ N, n>=Bf ⇒f(n)<=cf *h(n)# nearly the od thing ,just a little bit different on the c, which becomes cf(also B) now.
∃cg ∈ R+ ,∃Bg∈N,∀ n ∈ N, n>=Bg ⇒g(n)<=cg* h(n)#now the f(n) becomes g(n),which is for the second function.
Pick C = Cf + Cg,Then C∈ R+
Pick B = max(Bf,Bg)
assume n ∈ N ∧ n >=B
Then (f+g)(n) = f(n)+g(n) <=Cf*h(n)+Cg*h(n)
=(Cf+Cg)h(n)=Ch(n)#now we can find how to pick C,which is Cf + Cg
∀ n ∈ N, n>=B,(f+g)∈O(h)
∃cf,cg ∈ R ,∃Bf,Bg∈N,∀ n ∈ N, n>=B⇒(f+g)∈O(h)
∀ f,g∈F, (f∈O(h))∧g∈O(h))⇒(f+g)∈O(h)
2014年11月9日星期日
NOV 9th.2014 CSC165 big-oh of n^2 maximum slice
prove 3n^2+2n∈O(n^2)
that ∃c∈R+,∃B∈N,∀ n ∈ N,3n^2+2n<=C*n^2
pick C = 5
pick B = 0
assume n∈N # generic intro ∀
assume n>=B
assume n>=B #antecendent
Then 3n^2+2n <= 3n^2+2n^2 # 2n <= 2n^2
= 5n^2
= Cn^2 #since c=5
Then N>=B ==> 3n^2+2n<=C*n^2
....
prove 3n^2+3n+5 ∈O(n^2)
<= 3n^2 +2n^2 + 5
<= 3n^2 + 2n^2 +5n^2 # N>=1 #pay attention to 5n^2 that n=0
=10 n^2
=c n^2
that ∃c∈R+,∃B∈N,∀ n ∈ N,3n^2+2n<=C*n^2
pick C = 5
pick B = 0
assume n∈N # generic intro ∀
assume n>=B
assume n>=B #antecendent
Then 3n^2+2n <= 3n^2+2n^2 # 2n <= 2n^2
= 5n^2
= Cn^2 #since c=5
Then N>=B ==> 3n^2+2n<=C*n^2
....
prove 3n^2+3n+5 ∈O(n^2)
<= 3n^2 +2n^2 + 5
<= 3n^2 + 2n^2 +5n^2 # N>=1 #pay attention to 5n^2 that n=0
=10 n^2
=c n^2
2014年10月27日星期一
CSC165 sorting strategies
In these week lecture, we learned about the sorting strategies, using an example of ordering a deck of cards from largest to the smallest. we have insertion sort , selection sort and other more complicate sorts such as Radix, Quick sort, Tim, Merge sort.
we always think about the worst case in sorting or counting costs.
We also talks about how to disprove a implication, which maybe useful in A2
conjunction elimination: when A and B is True ,then both A B is true. If A and B is false, then at least one of them is false.
existential instantiation: we just need one example
disjunction elimination: If we know A or B is true ,while A is false ,we certainly know that B must me true
implication elimination: When A implies B, if A is true, then B must me true. (know A then know B)If not B is true, then not A must be true.
universal elimination: if there exists one x that is not P(x), then the universal statement will be false
we always think about the worst case in sorting or counting costs.
We also talks about how to disprove a implication, which maybe useful in A2
conjunction elimination: when A and B is True ,then both A B is true. If A and B is false, then at least one of them is false.
existential instantiation: we just need one example
disjunction elimination: If we know A or B is true ,while A is false ,we certainly know that B must me true
implication elimination: When A implies B, if A is true, then B must me true. (know A then know B)If not B is true, then not A must be true.
universal elimination: if there exists one x that is not P(x), then the universal statement will be false
2014年10月19日星期日
OCT.18th.2014 CSC165 Proof
In this week lecture,we learned how to make a proof.
Some points should be made attention:
1) the form and the structure of a proof
2)the key point(maybe the most complicate part)
3)the annotation
sometimes we find the statement to difficult to proof, we could think about the contrapositive or the negation of the origin, since they have connections to it.
proof by cases
In such problems, the provident should be separated into several cases.such that case, case2 and so on (i.e to prove all natural number, we should divide them into case1: odd number case2: even number)
when we need to prove a existence we just need only one element.
Some points should be made attention:
1) the form and the structure of a proof
2)the key point(maybe the most complicate part)
3)the annotation
sometimes we find the statement to difficult to proof, we could think about the contrapositive or the negation of the origin, since they have connections to it.
proof by cases
In such problems, the provident should be separated into several cases.such that case, case2 and so on (i.e to prove all natural number, we should divide them into case1: odd number case2: even number)
when we need to prove a existence we just need only one element.
2014年10月4日星期六
OCT 4th CSC165 Double Quantifiers
In the lecture this week, we talked about transitivity , double quantifiers and how to transform a statement graphically.
When we have two different quantifiers in one statement, we could not switch their position at any tome since it may be totally change the meaning.
If the statement talks about subset , and the quantifiers are in the same type ,the order doesn't matter.
(A ∧ B) ⇒C⇔(A ⇒ C )∨( B ⇒ C )
(A ∨ B) ⇒C
when the statement is true :
1) if c is true , then A and B at least one true
2)if c is false, then both A and B must be false
when the statement is false:
c must be false
When we have two different quantifiers in one statement, we could not switch their position at any tome since it may be totally change the meaning.
If the statement talks about subset , and the quantifiers are in the same type ,the order doesn't matter.
Also ,we learn how to draw it in a graph.
lim x ^2=0.36
lim x ^2=0.36
x ->0.6
The graph shows that every time my 'enemy' finds a e ,the I find a d.However, if e is chosen after d,everything will mess up. Every time I pick a d, my 'enemy' will pick a higher number,then I will fail to satisfy it all the time.
Something that I have made sure in the TUT:
there exists a dog doesn't have its day and its cat means neither have is day nor its cat.
Also, here is the Guarantees that make us really uncomfortable:
(A ∨ B) ⇒C⇔(A ⇒ C )∧( B ⇒ C )(A ∧ B) ⇒C⇔(A ⇒ C )∨( B ⇒ C )
(A ∨ B) ⇒C
when the statement is true :
1) if c is true , then A and B at least one true
2)if c is false, then both A and B must be false
when the statement is false:
c must be false
2014年9月27日星期六
Sep 27th 2014 CSC165 TUT
some questions that I had already solved in the TUT
1) " every course has a prerequisite" rewrite it symbolically:
∀y∈c, ∃∈x, p(x,y)
∃∈c,∀y∈c,p(x,y)
the order doesn't matter at this sentence ,so it is the same.
2)"some course have several prerequisites"
∃x,y,z∈c, p(x,y)∧p(z,y)∧x!=z
in this translation, "two means several", what we only to do is just define x,z two "courses" which is not the same
3) "there is no prerequisite for CSC108"
1) " every course has a prerequisite" rewrite it symbolically:
∀y∈c, ∃∈x, p(x,y)
∃∈c,∀y∈c,p(x,y)
the order doesn't matter at this sentence ,so it is the same.
2)"some course have several prerequisites"
∃x,y,z∈c, p(x,y)∧p(z,y)∧x!=z
in this translation, "two means several", what we only to do is just define x,z two "courses" which is not the same
3) "there is no prerequisite for CSC108"
¬(∃x∈c,p(x,CSC108) if and only if (i could not find the symbol on internet,but it is the same meaning)∀x∈c,¬p(x,CSC108)
negate the whole sentence needs to change existence to global
However ,there are still some question that I want to figure out.
"Some course have the same prerequisites"
The rewriting of this sentence is
∀x,y,z,w∈c,(p(x,w)∧p(y,w)∧p(z,w))⇒x=y ∨ x=z∨y=z
I could understand the meaning, however, why we need to use x,y,z to represent "some "prerequisite?
In my opinion, I could just only use x, y just like following:
∀x,y,w∈c,(p(x,w)∧p(y,w))⇒x=y
Isn't it still represent the same meaning?Or, this sentence only means that "if x,y are prerequisites of course w, then x is equal to y" and this meaning nothing because it is always right?
Sep. 27.2014 CSC165 Tabulating truth
I just reviewed the slide last week and found a question that had not been solves on the lecture. That is the tabulating truth table.So i try to figure out the difference between the table P implies (Q implies R) and (P and Q)implies R
Here is the table of P implies (Q implies R):
P Q R Q implies R P implies (Q implies R)
T T T T T
T T F F F
T F T F F
T F F T T
F T T T T
F T F F T
F F T T T
F F F T T
and then, here is the table of (P and Q)implies R that I made:
P Q R P and Q (P and Q)implies R
T T T T T
T T F T F
T F T F F
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
we could easily find that the finally bool result of these two tables are completely the same
So, my conclusion is P implies (Q implies R) if and only if (P and Q)implies R
订阅：
博文 (Atom)