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

Disjunctive Normal Form
WORD AND EXPRESSIONS
literal 文字
fundamental conjunction 基本合取式
fundamental disjunction 基本析取式
disjunctive normal form 析取范式
full disjunctive normal form 主析取范式
conjunctive normal form 合取范式
full conjunctive normal form 主合取范式
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.
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∧┐P.
(3)范式:析取范式与合取范式统称为范式。
显然, 任何合(析)取范式的对偶式是析(合)取范式.
析取范式与合取范式的性质:
(1) 一个析取范式是矛盾式,当且仅当它的每一个简单合取式都是矛盾式;
(2)一个合取范式是重言式,当且仅当它的每一个简单析取式都是重言式.
从定义不难看出:
(1)一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定式。
(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定式。
例如:(p∧┐q)∨(┐q∧┐r)∨r是一个析取范式,
而(p∨q∨r)∧(┐p∨┐q)∧r是一个合取范式。
注:单个文字既是简单析取式又是简单合取式。
因此形如┐p∧q∧r的公式既是由一个简单合取式构成的析取范式,又是由三个简单析取式构成的合取范式。
类似地,形如p∨┐q∨r的公式既可看成析取范式也可看成合取范式。
例如,PQ 的析取范式与合取范式:
PQ (P∧Q)∨(P∧Q)
----析取范式
PQ (P∨Q)∧(P∨Q)
----合取范式
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
and such that the wff contains only connectives of , and .
Step 2. Move all negations inside to create literals by using De Morgan’s equivalences
and
Step 3. Apply the distributive law and associative law to obtain a disjunctive normal form.
求命题公式的范式的基本步骤:
(1)将公式中的联结词化归成┐,及(先用相应的公式去掉和).
P43
公式E16 PQP∨Q
公式E21 PQ (P∧Q)∨(P∧Q)
公式E20 PQ (PQ)∧(QP)
再用E16 PQ (P∨Q)∧(P∨Q)