Week 7

The first thing we learned this week is how to prove a claim false.

For example:

           Claim: all x in X, all y in Y, P(x, y) => Q(x, y)

           To prove this claim false, we can prove: {all x in X, all y in Y, P(x, y) => not Q(x, y)} or                   {exist x in X, exist y in Y, not( P(x, y) => Q(x, y))}. But we cannot prove {all x in X, all y in                Y, not(P(x, y) => Q(x, y))}.

Then we learned some allowed inference. By these inferences, we can have faster ways to prove or disprove claims.

These are some examples of inferences, and there are actually more inferences that can be found in slides of week 7.

Different sorting strategies have different efficiency, which is the speed of a function that ignores hardware, programmer virtuosity. The speed we count is in the worst case in the course CSC165.

Week 6 Different kinds of proofs

This week, we learned many different kinds of proofs. Like non-boolean proof, limit proof, and proof for a sequence and also prove by cases.

To prove or disprove a statement about sequence, we just use the skills we learned in last week. But for proving non-boolean statements, we learned some new skills. We are use the non-boolean functions and we can also break down the functions to make it more precise, and then we can only use part of the functions.

Then, we can also proof a statement by cases. If a implication can be true in several different conditions, then we need to prove each of the conditions to show the implication is true. And for some "or" statement, we also need to prove it by cases. For example, there's a general format in notes:

Week 5 Direct and Indirect Prove(as well as prove by contradiction)

In this week, we learned several ways to prove different kinds of proves.

For example, when proving existence, we just need to give one example that satisfies the statement, then the statement is proved.

There are also several ways to prove an implication, two of the ways are direct proof and indirect proof. In direct proof, we prove the implication directly ( We assumed p(x) and get q(x) by several steps, p(x) => q(x)). In indirect proof, we prove the contrapositive of the proof, which is equal to the implication (we prove not q(x) => not p(x) instead of p(x) => q(x)).

Then we can also prove an implication by use of contradiction(a special case of contrapositive). A general format is shown in notes:

A general form of a direct proof for an existential implication is also shown in notes:

Week 4 mixed quantifiers and proofs

In this week, we learned mixed quantifiers and proofs.

First we learned that the meaning of a statement may change when we change the sequence of universal quantifiers and existential quantifiers. For example, let C be a set of courses, r(x, y) means x is the prerequisite course for y, then the meaning of "all x in C, exist y in C, r(x, y)" is different from "exist y in C, all x in C, r(x, y)". The first statement means all courses in C has a prerequisite and the second statement means there exist a course y where all courses in C are its prerequisite.,

Then we learned how to make proofs, the professor said there are two main steps of an argument to convince audience something true or false:
   1. think about why you believe true/false informal reasoning.
   2. write up your reasoning in a clear(existing, funny, suspenseful) way

The proof need to follow a specific structure. In class, a structure is showed: