Chapter1.4-Propositional_logic(Disjunctive Normal Form).ppt

Disjunctive Normal Form 2 Chapter 1:Propositional Logic WORD AND EXPRESSIONS ? literal 文字? fundamental conjunction 基本合取式? fundamental disjunction 基本析取式? disjunctive normal form 析取范式? full disjunctive normal form 主析取范式? conjunctive normal form 合取范式? full conjunctive normal form 主合取范式 3 Chapter 1:Propositional Logic Disjunctive Normal Form ? Definition A propositional variable or its negation is called literal. ?文字:命题变元及其否定统称为文字(如 P , ┐ P). ? A fundamental disjunction is either a literal or a disjunction of two or more literals. ?简单析取式:仅有有限个文字组成的析取式。?如:P,┐P?Q,P?┐P,Q?P?┐P, P?┐Q?R?┐ S. 4 Chapter 1:Propositional Logic Disjunctive Normal Form ? Definition A disjunctive normal form is either a fundamental conjunction or a disjunction of two or more fundamental conjunctions. (1) 析取范式:一个命题公式称为析取范式,当且仅当它具有形式: A1 ∨ A2 ∨……∨ An (n 大于等于 1)其中 Ai(i=1,2,3, … n)为简单合取式. 如: P∨┐ Q , (P∧ Q) ∨(P∧┐Q∧ R), Q ∧┐ P. (2) 合取范式:一个命题公式称为合取范式,当且仅当它具有形式: A1 ∧ A2 ∧……∧ An (n 大于等于 1)其中 Ai(i=1,2,3, … n)为简单析取式. 如: P∨┐ Q , (P∨ Q) ∧(P∨┐Q∨ R), Q ∧┐ Chapter 1:Propositional Logic ?(3) 范式:析取范式与合取范式统称为范式。?显然, 任何合(析)取范式的对偶式是析(合)取范式. 析取范式与合取范式的性质: (1) 一个析取范式是矛盾式,当且仅当它的每一个简单合取式都是矛盾式; (2) 一个合取范式是重言式, Chapter 1:Propositional Logic ?从定义不难看出:?(1)一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定式。?(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定式。 7 Chapter 1:Propositional Logic 例如: (p∧┐ q)∨(┐q∧┐ r)∨r是一个析取范式, 而 (p ∨q∨ r)∧(┐p∨┐ q)∧r是一个合取范式。注:单个文字既是简单析取式又是简单合取式。因此形如┐p∧q∧r的公式既是由一个简单合取式构成的析取范式,又是由三个简单析取式构成的合取范式。类似地,形如 p∨┐q∨r的公式既可看成析取范式也可看成合取范式。 8 Chapter 1:Propositional Logic ?例如, P? Q 的析取范式与合取范式: ? P ? Q ?(P∧ Q) ∨(?P∧? Q) ?---- 析取范式? P ? Q ?(?P∨ Q) ∧(P∨? Q) ?---- 合取范式 9 Chapter 1:Propositional Logic construct an equivalent disjunctive normal ? For any wff we can construct an equivalent disjunctive normal form by three steps: ? Step all occurrences (if there are any) of the connectives and by using the equivalences ?