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

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.

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.

Also ,we learn how to draw it in a graph.
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

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"

¬(∃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