Proof By Cases---Week 6

Sometime, it is more convenience to prove some proofs by cases. Consider the following proof:

"for all n belongs to N, n^2+n is even"

in order to prove above, it is more convenience to consider the case where n is odd ,then the case n is even.

First, we consider n is odd, then we can use definition of odd to assume n is of the form n=2k+1,where k is natural number. Then n^2+n=(2k+1)(2k+2)=2(k+1)(2k+1)=2m ,where m is a natural number of the form m=(k+1)(2k+1), therefore by definition  n^2+n is also even.

second, we consider n is even, then we can again use definition of even to assume n is of the form n=2k, where k is natural number. Then  n^2+n=(2k)(2k+1)=2n ,where n is a natural number of the form n=k(2k+1), so by definition n^2+n is also even.

So, no matter n is odd or even, we conclude that n^2+n is  even.

Finally, proof by cases are  good techniques that can make some proofs become so easy , therefore we need to know when or how to use proof by cases in the future.

proof from different directions--Week 5

proof from different directions:

ex:
Prove: for any natural number n, n^2 odd implies that n is odd.

if we start to assume the domain and the antecedent, we may write like this:

assume n is typical natural number.
assume n^2 is odd,
then exist k belongs to N, n^2=2k+1

and from above we want to show that n is odd.

we may find that it is almost impossible for us to proof the case n is odd from n^2 is odd.

However, we may use the fact that the contrapositive of the original statement and the original statement are equivalent, so if we can proof the contrapositive of the original statement, we will find it is much more easier.

which is n is even implies n^2 is even

For _All_Exists and Exists_For_All--Week 4

Here is one example of python code  to show the differences between for _all_exists and exists_for_all

let S1=S2={1,2,3,4}

def forall_exists(S1,S2):
      return all({any({x+y==5 for y in s2}) for x in S1})

def exists_forall(S1,S2):
      return any({all({x+y==5 for y in S1}) for x in S2})

the first python function will return True, since for all x in S1(x=1 or x=2 or x=3 or x=4), we can find one instance of y in S2 that satisfy x+y==5. (if we pick x=1 ,we can choose y=4 such that x+y=5. if we pick x=2, we can choose y=3 such that x+y=5 and so on)

So the statement inside the all will return True. (all{True, True,True,True} return True) ,therefore the first function will return True.

what second function saying is that for all x in S2,  then for all y in S1, x+y=5. we  find each time we choose x, we can pick a y that make x+y=5 false. for example, if we choose x=1, then we pick y=1, then we see that x+y=5 is false). So the  function will have the result any{False, False, False, False} in which will return  False

More on negation-- Week 3

As i mention in Week 1's blog, negation means negative of the original 

statement. In this week, we put all the universal  , existing quantifier 

and implication together and we try to negation them all  at once. Here 

is one example:

¬(∀ X∈R, ∃ y∈R, P⇒Q)⇔  (∃ x∈R, ∀ y∈R, ¬(¬PvQ) )
(∃ x∈R, ∀ y∈R, P^ ¬Q)

although, negation of such long statement seems to be hard at the beginning, 

but after many times practicing the negation, it becomes pretty computational 

and easy.

'Natural' Language (Implication)--Week 2

There are three  implications are so confuse for me to know which is the 'P' and which is the 'Q' in this week's lecture.

1. Successful program requires skill
2. I'll go only if you ins is
3. Don't know it unless you're tried it.

At the beginning, i am so confused about which implies which. For example statement 1, i think it's the skill implies successful program, however after asking many people for help, I understand that skill don't implies successful program (many people have skill but not everyone of them can make successful program) It's the successful program that implies skill.

This week, i find that there are great differences between  Natural language and the mathematical logic. As  beginners, it may takes us some times to know the differences between them. However, as we think more throughly, logic can also become intuitive for us!

Logic Implication VS Natural Language--Week 2

"If you eat your vegetables, then you can have dessert" (Week 2, Lecture 1)

In our daily language, the implication above means that you can have your dessert if and only if you eat your vegetables. There is no way that you don't eat your vegetable and have the dessert still. This is pretty much intuitive and well-accpeted by us.

However, when it comes to logic, the above statement has different approaches.

if you eat your vegetables, you will surely have your dessert. however, if you don't eat your vegetables, you can have the probability that you can still have the dessert. That mean if we see you have dessert, we are not sure whether you eat the vegetables or not.These refers to something called Vacuous Truth. Once the antecedent is false, the statement is automatic true regardless of the consequent. The reason to explain Vacuous Truth is that we can never find any counter-example to false the statement. Therefore, the whole statement is true.

How 'negation' works --week 1

Negation means a negative statement.
Negation can be done easily by put 'not' into the original statement.

for instance:
5+5 equals 10 (original true statement)
5+5 not equal 10 (negation statement)

one should understand that (not any) means none, (not all) means at lease one statement  is false