===============================================================
Lect 4 - April 9, 2009 - ECS 20 - Spring 2009 - Martel
===============================================================

Today: o Finish sentential logic
       o First-Order Logic

-------------------
1. Validity (truth) 
-------------------

Definitions: (t.a.  stands for truth assignment)
-----------
1. alpha is a TAUTOLOGY     if t(alpha) = 1 for ALL t.a. t:     |=  alpha
2. alpha is a CONTRADICTION if t(alpha) = 0 for ALL t.a. t:     |=  \neg alpha
3. alpha is a SATISFIABLE   if t(alpha) = 1 for SOME t.a. t:    
4. alpha and beta are EQUIVALENT if t(alpha) = t(beta) for all t.a. t 
                              alpha |= =| beta

 Prop: There is an algorithm (=a precisely-describable procedure, mechanism, recipe) 
       that, given a WFF of sentential logic, decides
       - if it is a tautology.
       - if it is a contradiction 
       - if it is a satisfiable.
       - if if the formula is equivalent to some second provided formula 

 Proof: "Truth-table algorithm"

 Discuss the (in)efficiency of the truth-table algorithm.
 REMARKABLE CLAIM: no efficient means are known for any of these problems....

Example of a tautological formula: 
   |= (P->Q) or (Q->P)        

-----------------
2. Various "laws"
-----------------

Section 4.7   "basic laws" 

Associative:  P and (Q and R) |= =| (P and Q) and R     //Mention the similarities to arithmetic
              P or (Q or R) |= =| (P or Q) or R         //laws with or corresponding to addition 
                                                        //and and corresponding to multiplication
Commutative: P and Q |= =| Q and P 
              P or Q |= =| Q or P

DeMorgan's:   not (P and Q) |= =| not P or not Q     EMPHASIZE
              not (P or Q) |= =| not P and not Q     EMPHASIZE

Absorption:   P or  (P and Q) |= =| P
              P and (P or Q)  |= =| P

Contradiction P and 0 |= =| 0
              P or 0 |= =| P

Contradiction P->Q |= =| not P or Q
              P->Q |= =| not(P and not Q)

Contraposition P -> Q |= =| not Q -> not P         EMPHASIZE

-----------------
3. Derivations (Arguments: section 4.9)
-----------------

One of the reasons to have axioms like those above is to develop
a notion of "what is provable". 
The idea is to create a "logical system" with three components:
  - formal syntax
  - formal semantics (truth-assignment notion)
  - derivation system

To formalize any proof system would require us to write down a lot 
of details, so I won't do it, but will give an example. Basically, a "formal proof" is going to be a list of WFFs where each WFF in the list is either: 
  - an assumption, or 
  - an axiom (it appear on a list like that just given), 
  - it follows from a previous set of lines in the proof by one of 
    a number of enumerated rules.  

We did this in an informal way to show the sqrt(2) was irrational.

Example:
  |-   (PQ)(P v R -> S)(SQ -> X) -> X  

   1.  PQ          assumption
   2.  P v R -> S  assumption 
   3.  SQ -> X     assumption 
   4.  P           "conjunction elimination" (P & Q => P) applied to (1)
   5.  Q           "conjunction elimination" (P & Q => Q) applied to (1)
   6.  P v R       "disjunction introduction" (P  -> P v R) applied to (4)
   7.  S           modus ponens ([A->B and A] gives B) applied to (2) and (6)
   8.  SQ          "conjunction introduction" (S, Q => SQ) applied to (7) and (5)
   9.  X           modus ponens applied to (3) and (8)

therefore

 |-  (PQ)(P v R -> S)(SQ->X) -> X  //The given statement is provable

Once you have a formalized derivation system spelled out, we define

       |- phi      can derive (prove) phi (from the emptyset -- no assumptions)
 Gamma |- phi      can derive phi from Gamma  (the assmptions)
  
  We call |- the "syntactic turnstyle operator"

SOUNDNESS:   Gamma |- phi  implies  Gamma |= phi   (usually "easy")
     
(Gamma |= phi  means that phi is True whenever Gamma is true).

COMPLETENESS Gamma |= phi implies   Gamma |- phi   (usually "hard")

-------------------------------------------
4. Adding quantifiers  -- First order logic: 4.10
-------------------------------------------

For a set A, a Propositional function is an expression p(x) such that p(x) is T or F when x=a for any a in A (note: whether it is T or F typically depends on which a in A).

A is the Domain of p(x); and the set Tp of all elements a in A such that p(a) is T is called the Truth Set of p(x).

Frequently A is a set of numbers (the Integers Z, or positive integers N, ...)

Examples  where A is N: 

i) p(x) IS " 2x >10", then the Truth Set Tp is  {6,7, 8, ...)

 ii)             x+ 5 > 3 is true for all x (so Tp is N).

Quantifiers: For a Propositional function  we often want to ask if it is T for all values in the set, or if it is sometimes true.

"All apples are bad"      Use A(x) takes x as a food and returns T if it is an apple, B(x) also takes a food x and is T if the food is bad.

    (\for all x) (A(x) -> B(x))   // universe of discourse?

"Some apples are bad"
    
    (\exists x) (A(x) and B(x))   // universe of discourse?

"BILLY has beat up every other boy at the Davis elementry school"

    (\all x) ((Student(x) and Boy(x) and (x != BILLY) -> HasBeatenUp(BILLY, x)) 

                 // universe of discourse?

In general, (for all x in A) p(x) 
is True when 
 Tp =A

And (there exists an x) p(x) is True unless Tp   is empty.

*Universe of discourse* = what quantifiers range over 
Always important to know the universe of discourse; it's implicit or explicit 
in any discussion of logical formulas involving quantifiers.

   More examples (mostly not done in class):

 Lewis Carol:
   All lions are fierce                        (\forall x) (L(x) -> F(x))
   Some lions do not drink coffee              (\exists x) (L(x) and \neg C(x))
   Some fierce creatures do not drink coffee   (\exists x) (F(x) and \neg C(x))

1. "Nobody likes a sore loser" 

 universe of discourse = human beings  (is this really unambiguous?)
 L(x,y) - predicate - true iff person x likes y  (is this really unambiguous?) 
 S(x)  - person x is a sore loser

 (\forall x) (S(x) -> (\forall y) \neg L(y,x)

 (apparently, a sore loser doesn't like even himself)

2. "If anyone in the dorm has a friend who has the measles,
then EVERYONE in the dorm will have to be quarantined."

universe of discourse - people
D(x) - person x lives in some (unspecified but understood) dorm
Q(x) - person x must be quarantines
F(x,y) - person x is friends with person y
M(x) - person x has the measles (oh no!)

   not forall
(exists x) (D(x) and (exists y)(F(x,y) and F(y)))  ->
   (forall x)(D(x) -> Q(x)) 

*Universe of discourse* = what quantifiers range over 

3.  T/F: universe of discourse :    
   **Natural numbers 8*

(forall x)(exists y) (x<y)   TRUE
(exists y)(forall x) (x<y)   FALSE  
(exists x)(forall y) (x<y)   FALSE
(forall y)(exists x) (x<y)   FALSE

4. Alternating quantifiers and games -- chess -- white to mate in 
   in 3 starting in position alpha

   (\exists  W1) (all B1) (exists W2) (all B2) (exists w3) 
    (WhiteHasWon(Board(p, W1,B1,W2,B2,W3)))

Negation of Quantified Statements: 4.11

DeMorgan's Laws: not (for all x in A) p(x)  |==| (there exists some x in A) not p(x)

  All cars are blue, Negation: Not the case that all cars are blue" same as: There is some car that is not blue.

not (exists x in A) p(x)  |==| (For all x in A) not p(x)