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.