# 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.

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!