Week #3

Week #3

#7

Conjunction: ∧
  A(x) and B(x)    # python keyword "and" work like this
  A(x) ∧ B(x)      # ∧ is the symbol of "and"
  As sets: x∈A∩B

  Watch out for the English word "and"!
  1) There is a pen and a telephone.
    != P(x)∧T(x)
  2) The solution are x<10 and x>20
    # The word "and" here mean "or" in logic

Disjunction: ∨
  A(x) or B(x)     # python keyword "or" work like this
  A(x) ∨ B(x)      # ∨ is the symbol of "or"
  As sets: x∈A∪B

Negation: ¬
  Negate the statement "All employees earning over 110,000 are female." Usually prepending the word "Not" will work.

     ¬(∀e∈E, O(e) => F(e))
  -> Ǝe∈E, ¬(O(e) => F(e))
  -> Ǝe∈E,   O(e) ∧ ¬F(e)

  ¬¬(...) <=> (...)

  special
    ¬(∀x∈X, P(x) => Q(x))
  ->  Ǝx∈X, P(x) ∧ ¬Q(x)

    ¬(Ǝx∈X, P(x) ∧ ¬Q(x))
  ->  ∀x∈X, P(x) => Q(x)

Scope
  (P(x) V Q(x)) => R(x) v.s. P(x) V (Q(x) => R(x))

  (∀x∈R, Ǝy∈R, x<y) => (∀x∈R, Ǝy∈R, x2<y)
  (∀z∈R, Ǝw∈R, z<w) => (∀z∈R, Ǝw∈R, z2<w)

P(x) => (Q(x)  => R(x))
  Drawing Truth
  # I'm too lazy to draw the graph

  Tabulating Truth

  P  Q  R | Q=>R | P=>(Q=>R)
  T  T  T |  T   |    T
  T  T  F |  F   |    F
  T  F  T |  T   |    T
  T  F  F |  T   |    T
  F  T  T |  T   |    T
  F  T  F |  F   |    T
  F  F  T |  T   |    T
  F  F  F |  T   |    T

#8

Tantology, Satisfiability and Unsatisfiability
  ∀D∈D, ∀D,
  (P(x)=>Q(x)) <=> (¬P(x) V Q(x))

  ƎD∈D, ƎP∈P(D), ƎQ∈P(D), Ǝx∈D
  (P(x)=>Q(x)) <=> (Q(x)=>P(x))

  satisfiable: always true
  unsatisfiable: always false

De Morgan's Law(s):
  ¬(P V Q) <=> ¬P ∧ ¬Q
  ¬(P ∧ Q) <=> ¬P V ¬Q

P=>Q vs ¬P V Q
  P Q | P=>Q | ¬P V Q
  T T |  T   |   T
  T F |  F   |   F
  F T |  T   |   T
  F F |  T   |   T

Bi-implication
      P <=> Q
  (¬P∧¬Q)V(P ∧ Q)




Thoughts:

This week we talked conjunction/disjunction and negation, which are two of the most important concepts in this course. And I found that bi-implication is the most interesting parts.

-bi-implication
We already know that how to translate an implication into a disjunction and how to negate it. But how can we deal with bi-implication? For example if we get a bi-implication P <=> Q.
By its definition, it can be translate to (P=>Q) and (Q=>P). Then we can transform the implications into two disjunctions. Thus, we get (neg P or Q) and (neg Q or P).
Then if we open the brackets, we can get something like: (neg P and neg Q) or (neg P and P) or (Q and neg Q) or (Q and P).
Since (neg P and P) and (Q and neg Q) are unsatisfiable, we can get ride of them, then we get (neg P and neg Q) or (P and Q).
If we consider them in English, we can say that P iff Q means P and Q have to be both true or both false.


Problem Solving:

Folding

After first fold, we got a down crease
           D
After the second fold, we got an up crease on the left and a down fold on the right
     U     D     D
And then, we put UDUD into those empty spot between the three crease
  U  U  D  D  U  D  D
And then we do it recursively.


def get_creases(n):
    if n == 1:
        return ['D']
    else:
        a = ['U','D'] * (2**(n-2))
        b = []
        c = get_creases(n-1)
        i = 0
        for crease in a:
            b.append(crease)
            if i == len(c):
                break
            b.append(c[i])
            i += 1
        return b