范式、重言式与可满足性

1 . Normal Forms, Tautology and Satisfiability 2/3/12 1 

2 . DeMorgan’s Laws • ¬(p∨q) ≡(¬p∧ ￢ q) “neither” – driving in negations flips ands to ors • ¬(p∧q) ≡(¬p∨ ￢ q) “nand” – Driving in negations flips ors to ands • Also law of double negation: ¬¬p ≡p • By repeatedly replacing LHS by RHS all negation signs can be pressed against variables • ￢ (p∨(q∧r)) ≡ ￢ p∧ ￢ (q∧r) ≡ ￢ p∧( ￢ q∨ ￢ r) 2/3/12 2 

3 . Distributive Laws, Normal Forms • p∧(q∨r)≡(p∧q)∨(p∧r) • p∨(q∧r)≡(p∨q)∧(p∨r) • By applying these transformations, every formula can be put in either – Conjunctive normal form (and-of-ors-of- literals), or – Disjunctive normal form (or-of-ands-of-literals) • ￢ p∨ ( ￢ q∧ ￢ r) is in DNF • ( ￢ p∨ ￢ q)∧( ￢ p∨ ￢ r) is an equivalent CNF 2/3/12 3 

4 . Tautology • A tautology is a formula that is true under all possible truth assignments p q ￢ (p∧q) ≡ (¬p∨ ￢ q) T T T T F T F T T F F T 2/3/12 4 

5 . Satisfiability • A satisfiable formula is one that is true for some truth assignment p q ￢ p∧q T T F T F F F T T F F F • A formula is unsatisfiable (last column all F) iff its negation is a tautology (last column all T) 2/3/12 5 

6 . P = NP? • One can in principle always determine whether a formula is satisfiable, unsatisfiable, a tautology by filling in the truth table and looking at the last column. • Each line is easy, but the table for a formula with n variables has 2n rows. • n = 100 => 2n >> age of the universe, in nanoseconds • Is there a subexponential algorithm? 2/3/12 6