范式、重言式与可满足性

本文主要介绍了范式、重言式与可满足性的基本定理及其应用。范式是符合某一种级别的关系模式的集合,讲述了分配率和范式之间的关系。重言式是一种在所有可能的真理分配下都成立的公式,就是恒真命题。
展开查看详情

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