命题逻辑2.ppt

文档介绍：范式
析取范式和合取范式概念
简单合取式、简单析取式
析取范式、合取范式
求公式的析取范式和合取范式
主析取范式和主合取范式概念
极大项、极小项
主析取范式、主合取范式
求公式的主析取范式和主合取范式
求公式的主析取范式意义
范式
一、析取范式和合取范式
定义由有限个命题变元或其否定构成的合取式称为简单合取式。
例如,¬p∧q∧r∧s、¬r、s、¬r∧r都是由命题变元p、q、r、s组成的简单合取式。
定义 由有限个命题变元或其否定构成的析取式称为简单析取式。
例如, ¬ q∨r∨¬r、p、¬ q∨p、¬r是由命题变元p、q、r组成的简单析取式。
定理
(1)一简单合取式为永假式的充分必要条件是,它同时包含某个命题变元p及其否定¬p。
(2)一简单析取式为永真式的充分必要条件是,它同时包含某个命题变元p及其否定¬p。
定义有限个简单合取式的析取称为析取范式。即具有 A1∨A2∨…∨An(n≥1)的形式的公式,其中Ai是简单合取式。
例如,F1=p∨(p∧q)∨r∨(p∧q∧r)是一析取范式。
定义有限个简单析取式的合取称为合取范式。即具有 A1∧A2∧…∧An (n≥1)的形式的公式,其中Ai是简单析取式。
例如:
F2=p∧(p∨q)∧r∧(p∨q∨r)是合取范式。
F3=(p∨r∨q)∧(p∨q)∧r∧(p∨r)也是合取范式。
析取范式、合取范式性质
(1)一析取范式为矛盾式的充分必要条件是,它的每个简单合取式都是矛盾式。
(2)一合取范式为重言式的充分必要条件是,它的每个简单析取式都是重言式。
二、求公式的析取范式和合取范式
任何一个命题公式都存在与它等值的析取范式和合取范式。按下列步骤进行:
(1)利用基本等值式消去公式中的联结词“”、“”等;
(2)利用双重否定律将(P)置换成P消去否定号 “”,或利用德•摩根定律将否定号“” 向内深入,使之只作用于命题变元;
(3)利用分配律、交换律、结合律将公式归约为合取范式或析取范式。
例求F1=(p∧(qr))s的合取范式和析取范式
解 F1(p∧(q∨r))∨s
p∨( q∨r)∨s
p∨(q∧r)∨s (析取范式)
又 F1p∨(q∧r)∨s
(p∨s)∨(q∧r)
(p∨s∨q)∧(p∨s∨r) (合取范式)
另外由 F1(p∨s∨q)∧(p∨s∨r)
(p∧(p∨s∨r))∨(s∧(p∨s∨r))∨(q∧(p∨s∨r))
p∨s∨(q∧p)∨(q∧s)∨(q∧r) (析取范式)
可见公式的析取范式和合取范式并不唯一
练:求 F2= (p∨q) (p∧q)的析取范式、合取范式
解 F2 ((p∨q) (p∧q))∧((p∧q) (p∨q))
((p∨q)∨(p∧q))∧((p∧q)∨(p∨q))
(p∨(q∨(p∧q)))∧(p∨q∨(p∧q))
(p∨q)∧(p∨q) (合取范式)
(p∧(p∨q))∨(q∧(p∨q))
(p∧p) ∨(p∧q)∨(p∧q)∨(q∧q) (析取范式)
三、主析取范式和主合取范式 定义设有命题变元P1,P2,…,Pn ,形如的命题公式称为是由命题变元P 1,P2,…,Pn所产生的极小项。而形如的命题公式称为是由命题变元P1,P2,…,Pn所产生的极大项。其中Pi*为Pi或为Pi(i=1,2,…n).
例如,P1∧P2∧P3, P1∧P2∧P3均是由P1,P2,P3所产生的极小项。P1∨P2∨P3是由P1,P2,P3产生的一个极大项。
n个命题变元形成2n个极小项:m0,m1,…,m2n-1  2n个极大项:M0,M1,…,M2n-1
定义如果公式A的析取范式中所有的简单合取式都是极小项,则称该析取范式为A的主析取范式。
如果公式A的合取范式中所有的简单析取式都是极大项,则称该合取范式为A的主合取范式。
例如(P1P2P3)(P1P2P3)(P1P2P3)是某个公式的主析取范式。
(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3)是某个公式的主合取范式。