Week #2

Week #2

#4

def qo(S1, S2):
    return not all({x in S2 for x in S1})

def q1(S1, S2):
    return any({x in S2 for x in S1})

def q1(S1, S2):
    return all({x in S2 for x in S1})

def q3(S1, S2):
    return not any({x in S2 for x in S1})

- All employees earn 42000
  q2(E, O)
- Some female earn over 42000
  q1(F, O)
- Some male doesn't earn over 42000
  q0(M, O)
- All male doesn't earn over 42000
  q3(M, O)

Universal/Existential duality
- To verify a universal ("for all") claim, show there is no counter-example.
- To falsify a universal claim, find at least one counter-example.
- To verify an existential claim, show there is at least one example.
- To falsify an existential claim, show there are no example.

Sentences
  Sentence refer to expression that we structured to evaluate to either ture or false

The employee earn over 55000
         --> which employee?
Every employee makes less than 55000
           --> which set of employees?

Symbols
  The value of symbols is not making the sentence short. It is to make teh statement symbolically and clearly emphasize the connection between two subjects.
  L(x): x∈L

  For all employees, the employee makes less than 5500.
->∀ employees x, x makes less than 55000.
->∀x ∈ E, L(x)
  # The first line & the third line are DIFFERENT
  # If L(x) is an empty set, the sentence is True, because there's no counter-example.

also:
  some employee earns over 55000
  ∃x ∈ E, L(x)
  # And this is not a statement about an element x

Implication

  There is a couple of ways to expression the definition.

  "If a employee is male, then he earns less than 55000."
  This could accurately be expressed using universal quantification by restricting the et we are considering.
∀x ∈E M, L(x)
  The form "if P, then Q." is called implication

Verifying implication
  which of the following statements are a counter-example to:
  ST1:"If the employee is male, then he earns less than 55000."

  Al       |  male  | 60000
  Ellen  | female | 50000
  Gwen | female | 95000
  Carlos|  male  | 40000


  If P then Q ---> counter-example: P and not Q

  If you eat vegetable, then you can have your dessert.

   eat veg, get des T
  Xeat veg, get des T
  Xeat veg,Xget des T
   eat veg,Xget des F

#5

Implication informaton
    x  E, if F(x), then L(x)
  If this implication is True, what can we deduce from about the following sets?
  1) F, the set of female employees? F
  2) L
  3) not F
  4) not L

Symbolic expression:
  ∀x∈E, F(x) => L(x)

Reverse the implication, you can get the converse.
  ∀x∈E, L(x) => F(x)
  We cannot say if the implication is true, the converse of the implication is also true.
  But if L == F, we can say so.

Negation and Contrapositive
  ¬: not

  ∀x∈E, F(x) => L(x)
  The contrapositive of the implication:
  ∀x∈E, ¬L(x) => ¬F(x)

  1) When x in F:
      impl: x in L
      cont: x in L
  2) When x not in F:
      impl: nothing
      cont: nothing
  3) When x in L:
      impl: nothing
      cont: nothing
  4) When x not in L:
      impl: x not in F
      cont: x not in F

  e.g. ∀n∈N, P(n) => Q(n)
    P(n): n is a multiple of 4
    Q(n): n^2 is a multiple of 4

    implication  : ∀n∈N,  P(n) =>  Q(n)
    converse     : ∀n∈N,  Q(n) =>  P(n)
   contrapostive: ∀n∈N, ¬Q(n) => ¬P(n)

    - n is a multiple of 4:
  impl: n^2 is multi of 4
conv: nothing
cont: n^2 is mulit of 4

- n is not a multiple of 4
impl: nothing
conv: n^2 is not a multiple of 4    # assume the converse is true
cont: nothing

- n^2 is a multiple of 4
impl: nothing
conv: n is a multiple of 4
cont: nothing

- n^2 is a multiple of 4
impl: n is not a multiple of 4
conv: nothing
cont: n is not a multiple of 4

Nature Language
    If nominated, I will not stand.
    If you think I'm lying, then you're a liar.
    Whenever I hear that song, I think about ice cream.
    Differentiability is sufficient for continuity.
    Matching fingerprints and a motive are enough for guilt.
    You can't stay enrolled in CSC165 without a pulse.
    Successful programming requires skill.
    I'll go if you insist.
    Don't knock it unless you've tried it.
=if not
    # P
    # Q


#6

Vacuous Truth
  P(x) => Q(x) False when T => F
  ∀x∈R, x2 - 2x + 2 = 0

  To find out if the implication is False. You have to find a counter-example true in P and false in Q.
  -> You can't find an x is true in P. -> You can't, so the implication is true.

  FALSE imply everything

Equivalence
  "Every male employee (M) earns between 25000 and 45000."
  Both the implication and its converse are true.

  ∀x∈R, x2-2x+2 = 0 <=> x > x+5
  is equivalent to
  ∀x∈R, x2-2x+2 = 0  => x > x+5
  ∀x∈R, x2-2x+2 = 0 <=  x > x+5

Idiom
  Every D that is a P is also a Q
  -> ∀x∈D, P(x) => Q(x)
  -> ∀x∈(D∩P), Q(x)
  -> ∀x∈, P(x)∧Q(x)
  # Those three statements are different!




Thoughts:

This week a key concept we talked about is the implication, and I found something really interesting about it. And here I'm mainly going to talk about -justify/falsify an implication, and -translate English to symbols.

-justify/falsify an implication
Firstly we know that an implication means an 'if, then' statement. For example, "If you eat vegetable, then you can have your dessert." or P => Q. And if we step forward, an 'if, then' statement means if P is true, then Q must be true. And this definition of implication does not mentioned anything about what will it happens if P is false. So, if P is false, then Q can be either True or False, which means that there are no restriction of Q. Thus if P is False, then whatever Q is the implication is still True; if P is True, the implication is True iff Q is True (This have the similar with truth table -- me from the future). So the only thing that can falsify an implication is a counter-example showing that there exists a situation that P is True and Q is False. Back to our dessert vegetable example, the only thing that can falsify the statement is ate some vegetables, but my mom didn't give me my dessert.So there is still some possibility that I didn't eat any vegetable but still getting the dessert. So whenever I heard my mom saying so, I'll risk not eating any vegetables and pray for the possibility to raise. So if I'm becoming a parent, I will tell my child something like "You can get your dessert if and only if you eat vegetables." (How I learned how to be a parent in a computer science class)

-translate English to symbols
During the lecture there is an exercise for us to find out what is P and what is Q from a English sentence (and it's also in the lecture note). And it is definitely the hardest question that class. Besides all the 8 sentences given, there are some challenging sentences I came up.
K(n): n is known
Pr(n): n is a programmer
Pm(n): n is a program
W(n,p): n writes p
  * All known programs are written by some known programmers.
    forall p, Pg(p) and K(p) => exists n, Pr(n) and K(p) and W(n, p)