Normal form A literal is a wff of the form p or of the form a p a wff is in disjunctive normal form iff it is a disjunction of conjunctions of literals m70 ∨∧ A wff is in conjunctive normal form iff it is a conjunction of disjunctions of literals p Logic in Computer Science -p6/19
Normal Form • A literal is a wff of the form p or of the form ∼ p • A wff is in disjunctive normal form iff it is a disjunction of conjunctions of literals. _ m i=1 ^ ni j=1 pij • A wff is in conjunctive normal form iff it is a conjunction of disjunctions of literals. ^ m i=1 _ ni j=1 pij Logic in Computer Science – p.6/19
Disjunctive Normal Form Theorem 1. Let h be any truth function with n arguments where n>l, and let p1, ...,pn be distinct propositional variables. Then there is a wff a in disjunctive normal form such that h=Ap1…入nA 2. For every wff b of propositional calculus there is a wff a in disjunctive normal form such that b is equivalent A Logic in Computer Science-p. 7/19
Disjunctive Normal Form Theorem 1. Let h be any truth function with n arguments, where n ≥ 1, and let p1, · · · , pn be distinct propositional variables. Then there is a wff A in disjunctive normal form such that h = [λp1 · · · λpn]A. 2. For every wff B of propositional calculus there is a wff A in disjunctive normal form such that B is equivalent A. Logic in Computer Science – p.7/19