CMPS140, Winter 2012, Section 01: Lecture 11

For Quiz 3:
   Know Previous quizzes

Proposiitonal Logic:
 decidabily, NP-Complete, complete, sound , universally complete.

Lisp
  (2 functions)

31 T/F


NP-completeness


Minimax
    alpha-beta
       example:

                              max       *
                                min   *   *
                                     2 5 1 3

                Minimax returns  game theoretic value of 2
               Minimax alpha-beta also returns 2, but never looks at the 3! Why

Search algorithms
 know definitions and theorems.
   Informed

  Deterministic versus Stochastic

Game Theoretic Value

Satisfiability

Chess


     first order logic is semi-decidable , complete (resolution and Existential Graphs),
       and not Universally Complete  (Godel's Theorem), sound

semi decidable means if you know in {T,F} you can determine which, but not if you
only know {T,F,Maybe} and at least exponential to find a proof in the
worst case.



some game theory:


    Minmax (zero-sum players play simultaneously)
            23
             34
                       game theoretic value is 3, since both
                       players have dominant strategies.


                                    31
                                    24           since there is no
                                    dominant strategy
                            the optimal play for both players will be
                            "stochastic".


                        43
                        23

      player 1 has a dominant strategy so player two should always play
      second column,
      so that 3 is the game-theoretic  value for the first player.



  4 Propositional Proof Techniques for Prop Logic:
       Truth Tables
       Sat Matrices
       Resolution
       Existential Graphs.

Read about  Resolution in Chapter 7-8 of text.

Existential Graphs:
____________________

   Logic       EGs
     P          P
     ~P        (P)
     P and Q    P Q
     P or Q     ((P) (Q))
     P => Q     (P (Q))

Idea:  Circle Goal derive an empty circle on the sheet!

Rules:  ((x)) ---> x.
      x ((x)x)     ---> x (())

       x can kill inner copy at any level of nesting:   x   (z(x y)) --> (z(y))

Example:
[A => (B or C)) and ~C  and B => D  therefore A => D.

   in EGs:    ((A (((B) (C)))) (C) (B (D))      ((A (D)))   )

    Negate goal:
       (((A (((B) (C)))) (C) (B (D))      ((A (D)))   ))
     Remove Double Negation
       (A (((B) (C)))) (C) (B (D))      ((A (D)))

     Remove double negation:
        (A (B) (C))    (C) (B (D))     A (D)

     Kill A:
        ((B) (C))   (C) (B (D)) A (D)

     KILL (D):    ((B) (C)) (C)   (B) A (D)

     KILL (B):
                 ((C))   (C)  (B) A (D)

     KILL   (C):      () (C)   (B) A (D)

     We are done since there is a () on the sheet!!!



In resolution:
     First convert to CNF:
       1. ~A or B or C   given
       2. ~C               given
       3. ~B or D          given
        4. A                drom negated goal
       5 ~D                from negated goal


       6. ~B               3,5
       7. ~A or C          1,6
       8. C                4,7
       9. {}               2,8  we have derived {} so we are done!

SAT matrix     011*
              **0*
               *0*1
               1***
              ***0     which is UNSAT = contradiction!