Change site officially.

I can no longer bear this site. It is so unstable that I cannot login most of the time. It really negatively affects my slog uploading. I will move all my slogs to the new wordpress blog site. The new address is csc165rioli.wordpress.com

Supplement for week 5 —— Recommendation of others' slog

After viewing some others SLOG, I found I may forget to mention important point of proof.

Basically it is about the general structure of the proof. For the statement of A implies B, we use "Assume" to stipulate all the assumptions are true and in implication the assumption should be true, otherwise we cannot falsify it. Then we use "Let" to illustrate the relation between A and B, by this way we get the A implies B. We use "Then" to indicate the assumption of statement is correspond with the implication.

Here I want to recommend the slog:

http://165timeslogically.blogspot.ca/

The slog has a good format of writing the structure of proof:

  "Assume .........
           Assume.......
              Let (here you define your variables)
              Prove! (here you do the proof!)
           Then... (you show that you assumption is valid)
   Then ... (here, you have proven the whole statement)"

The indentation here is very important as it implies the logic of each sentence just like Python does.

We are not required to complete the whole proof these days, but it is still important to know about the structure as it is the basis.   

Reflection of CSC165 Lec 5 Oct. 7

Reflection of CSC165 Lec 5 Oct. 7

This week the content is less than before as the first period is used as term test. The professor introduced some different ways of proving.

5.1 Contrapositive and contradiction

5.1.1 Proof using Contrapositive

Sometimes it is hard to prove P => Q directly. However, as we have learnt before, P => Q <=> ¬Q => ¬P. By using thie property, we can say if ¬Q => ¬P is true, then P => Q is true. We may still apply the chain method as introduced in 4.2 to prove that ¬Q => ¬P is true.

A typical example is to prove  ∀n∈N, n2 is odd =>n is odd.

If we try to prove it in a direct way, that is, get rid of the square, we would probably get n = and it hard to get through. (k could be everything ∈N)

However, by proving if n is not odd => n2 is odd, we get:

n is even => n2 is even

n = 2k + 1 and n2 = 4k2 + 4k + 1 = 2(2k2 + 2) + 1

Let k be 2k2 + 2

n2 is even.

5.1.2 Proof using Contradiction

In some cases, the P in P => Q is not explicit. For example: There are infinitely many even natural numbers.

Here we see the result Q "there are infinitely many even natural numbers", but the P is abstract. In this case, we would use the way of contradiction.

Proof:

assume there are a finite number of even numbers

# assuming ¬Q

  then there exists a largest even number, m

  then let m’ = 2m

  then m’ is an even number, and larger than m

  # contradiction, since m is the largest even number

then there are infinitely many even numbers

# assuming ¬Q leads to contradiction, so Q.

The # here is important as others may not quite understand what the content is about, the comments after hashtag would help others understanding.

5.2 existential, sequence

5.2.1 direct proof of existential

  As mentioned in the beginning of the course as this figure shows

one example could verify existential

5.2.2 prove a claim about a sequence

  The proof may consist several different structures and multiple quantifiers. One example introduced in class is:

∀n∈N, an = n2

Now prove:

∃i∈N, ∀j∈N, aj <= i => j < i

The professor still use the way of contrapositive, but I think it is also okay to prove it directly.

an = aj = (j2 ≤ i) => j ≤ i

since j ∈N and j2∈N, they are either positive or zero,so j2≥j. Thus,   j ≤j2 and j2≤i, j ≤i

Reflection of CSC165 Lec. 4 Sep. 30th.

Reflection of CSC165 Lec. 4 Sep. 30th.

Just something I want to write at first. I regard SLOG as another way to review the whole course,  so my goal is to repeat all the contents the professor taught as completely as possible. This is also a process of self-check if I am good at everything from this lecture. However, it is not a simple copy of the professor's powerpoint. I will rewrite all content in my own words, just like I am the teacher and I will teach students by this slog. The slog will contain some of my personal views or comments of the lecture. To make it clearer, I will use Italic font to mark it, and as some of you may find, I use bold font  to emphasize the concepts or sentences which I think is crucial.

Also, I plan to write a slog about recommending others' slog as I really see some interesting thing that I may neglect. This will be done later and separately.

4.1 Bi-implication, transitivity, mixed quantifiers

4.1.1 Bi-implication

Bi-implication is a bilateral implication. That is to say, P implies Q and Q implies P. (P => Q ) ∧ (Q => P), also we give a new sign P <=> Q to indicate bi-implication.

To more comprehensively understand bi-implication, we may try to modify it in the form (X ∧ X ) ∨ ( X ∧ X ).

By doing this we need to be familiar with the law mentioned in 3.3.2. In fact, I do not really pay attention to this part last time doing the slog as I do not quite get the reason why are we using it. I found it becomes extremely important in this lecture, so I want to do a review about laws first.

Laws:

1. De morgan's laws:

¬(P ∨ Q) <=> ¬P ∧ ¬Q

¬(P ∧ Q) <=> ¬P ∨ ¬Q

De morgan's law could be easily deduced by negating P ∧/∨ Q. Remembering the result would be efficient to solve the problem when it is comlicate.

2. Commutative laws:

P ∧ Q <=> Q ∧ P

P ∨ Q <=> Q ∨ P

We can change the order of Q and P as in and, or  relation they are lateral, but the change could not be made if P => Q as they have causality.

3. Associative laws:

4. Distributive laws:

I want to put associative law and distributive law together as they both talk about the situation when we have three predicates.

The associative law claims:

(P ∧ Q) ∧ R <=> P ∧ (Q ∧ R)

(P ∨ Q) ∨ R <=> P ∨ (Q ∨ R)

Associative law means if all three predicates are in the same condition, the parenthesis will not the affect the result.  

The distributive law claims:

(P ∨ Q) ∧ R <=> (P ∧ R) ∨ (Q ∧ R)

(P ∧ Q) ∨ R <=> (P ∨ R) ∧ (Q ∨ R)

Distributive law works quite the same as (P + Q) * R as P and Q are respectively distributed to R.

5. Identity laws:

P ∧ (Q ∨ ¬Q) <=> P

P ∨ (Q ∧ ¬Q) <=> P

The (Q ∨ ¬Q) is an empty set as one thing cannot be itself and not itself at the same time. A predicate and an empty set would lead to the predicate itself.

The (Q ∧ ¬Q) is always "all" set as it claims something would either be Q or not Q, which include all the possibilities, so it will also not affect the result.

6. Idempotent laws

P ∧ P <=> P

P ∨ P <=> P

P and P , P or P will not change the result of P, so it is the same as P itself. I still do not know the meaning of this one in fact.

Now we know  (P => Q ) ∧ (Q => P) is P <=> Q and (P => Q)  ¬P ∨ Q. P <=> Q ¬P ∨ Q) ∧ (¬Q ∨ P)

The negation of P <=> Q is ¬(P <=> Q), which could be written like (P ∧ ¬Q )∨(¬P ∧ Q).

This means either P or Q is true, but not both is true. In daily speak either or could mean one of them (but not both) is true, but in logic either or contains both and. To specifically present either or but not both, we can also use symbol exclusive or, ⊕.

4.1.2 Transitivity

Transitivity basically means the passing property of implication. For example:

P=> Q  and Q=> R, we can conclude with P =>R

The figure of transitivity would be like this: Since P => Q, Q must be true when P is true, R must be true when Q is true. So R contains a larger region than Q and R.

A classic type of transitivity could be Syllogism. A syllogism is a kind of logical argument that applies deductive reasoning to arrive at a conclusion based on two or more propositions that are asserted or assumed to be true. For example:

"All men are mortal.

Socrates is a man.

Therefore, Socrates is mortal."

The example here is not really elaborate as it does not fit the form of predicate, but let's just regard Socrates as P, man as Q, mortal as R. This clearly fits the figure above. Also keep in mind in computer science these P, Q, R may not have any logic relation. They could be anything irrelevant with implication.

4.2 Proofs

"A proof is an argument that convinces someone who is logical, careful and precise"

What we have learnt so far about proof are mostly concepts which is not worthy to conclude, but it shows us a general pattern of proof something. Let's say we want to find P(x) => Q(x), but P and Q seems irrelevant. We can firstly find P(x) => R(x) which R(x) is directly led by P(x). R(x) => R1(x) which R1(x) is directly led by R(x), we follow the pattern until we find Rn(x) => Q(x). The proofs is broken into several steps and each step is easy to follow.

The unexpected hanging paradox is also introduced in class, I found this topic extremely interesting and did a lot of research on it. To save the time and space, I do not want to repeat the paradox itself and the proof about it in class. I think one argument in the proof sounds weak: "It cannot be on Friday, since after Thursday noon it would not be a surprise anymore." This statement is only true when he survives the first four days, but he may still be hanged up in the four days before. Thus, from the prespective of prisoner, the only thing he know is that he is 50% likely to be hanged up in the coming weekdays in the first four days, and this uncertainty becomes a surprise.

4.3 Problem solving session.

In CS or mathematics, we need a series of process to solve one problem. This series of work is called "Polya’s problem solving scheme". This is extremely useful in real life cases as not that much variables or quantifiers are difined. It suggests the following steps:

◆ understand the problem

◆ devise a plan

◆ carry out the plan

◆ look back

◆ acknowledge when, and how, you’re stuck

The case being given in class is called Folding, I am going to solve this problem following the Polya’s problem solving scheme.

1. Understand the problem

The process is written on the paper handout clearly. The aim is to find the pattern of crease's direction(face up or face down).

2. Devise a plan

I want to fold the strip 1 to 4 times and record the data of crease's direction. Then I try to observe the pattern and conclude the general law of it.

3. Carry out the plan

When fold 1 time:	↓	1
When fold 2 times:	↓↓↑	3
When fold 3 times:	↓↓↑↓↓↑↑	7
When fold 4 times:	↓↓↑↓↓↑↑↓↓↓↑↑↓↑↑	15

I observe the following pattern through the data I collected:

1. the first one is always ↓.

2. the beginning is the same.

3. There are always odd number of creases, and the rear part is the reverse of the from part from the middle to the beginning.

4. Look back

I see the phenomenon and I also need to know why it happens.

1. the first one is always  ↓ because we "keep holding the right end and unfold the entire strip." and "Fold the strip so that the left end is on top of the right end. " Thus, no matter how many times I fold, the first one will always be ↓.

2. 2 happens because the N+1th fold is one the basis of Nth fold, so the initial pattern would  always be the same.

3. 3 happens because we always unfold the strip from the middle and do it again and again.

After understanding these patterns, we could conclude something more general and abstract.

Let's see this:

When fold 4 times:

↓↓↑↓↓↑↑↓↓↓↑↑↓↑↑

In fact ,we could separate the creases into three parts:

When fold 4 times:

↓↓↑↓↓↑↑

↓

↓↓↑↑↓↑↑

The first part equals to "when fold 3 times".

The second part could be called "new", it is always the middle and always face down as explained in 1.

The second part is the reverse of the first part from the end to the beginning.

By this way, we could predict the pattern when we fold the fifth times:

When fold 5 times:

↓↓↑↓↓↑↑↓↓↓↑↑↓↑↑

↓

↓↓↑↓↓↑↑↑↓↓↑↑↓↑↑

5. Acknowledge when, and how, you're stuck

The most difficult part is to observe the phenomenon through the data collected. Sometimes the pattern hides in the data and it hard to find. I need to try a lot of different possibilities.