Chapter 5: Propositional (unquantified) logic
=============================================
Semantics
---------
Now we start to care about meaning/interpretation.
Treats expressions as representing boolean functions of the variables.
Like the execution phase of Java.

A Propositional Formula in F will be thought of as a function of the boolean variables PV.
 If there are n variables, it's interpreted as a function from {0, 1}^n -> {0, 1}.

A function from {0, 1}^n -> {0, 1} is called a boolean function.
It can be thought of as a truth table with 2^n rows.

Start with a truth assignment t: PV -> {0, 1} (like assigning values to the boolean
 variables in Java). Can think of t as one row of a truth table.

From t we can define a truth value for all propositional formulas (generated from PV),
 called t*. So t* is a function from F -> {0, 1}. It's defined by:

  Base Case: t*(P) = t(P) if P in PV 

  Inductive Step:

    If P in F, t*(~P) = 1 - t*(P)
      [just a concise way of saying: t*(~P) = 1 if t*(P) = 0, 0 otherwise]

    If P, Q in F,
      t*(P /\ Q) = t*(P) * t*(Q) [min also works]
      t*(P \/ Q) = max(t*(P), t*(Q))
      t*(P -> Q) = (t*(P) <= t*(Q)) [using C-style <=]
      t*(P <-> Q) = (t*(P) == t*(Q)) [using C-style ==]

If t*(P) = 1 we say t satisfies P, else we say t falsifies P.

Now we say:

  P is a tautology/valid              iff all t satisfy P
         contradiction/unsatisfiable      no  t satisfies P
         satisfiable                      a   t satisfies P
         contingency                      its not a tautology and not a contradiction

Exercise: define satisfiable in terms of tautology or contradiction.

In terms of functions, P is a tautology iff it represents the constant function 1.
 Exercise: express the others in this way.

We define P and Q to be logically equivalent iff they represent the same function
 (iff have same truth table
  iff (for all t, t satisfies P iff t satisfies Q))

If PV is non-empty, there are an infinite number of propositioal formulas.
 But if PV is finite with n variables, there are only(!) 2^(2^n) boolean functions.
 So many propositional formulas are logically equivalent to others.