《命题逻辑2》由会员分享，可在线阅读，更多相关《命题逻辑2（61页珍藏版）》请在金锄头文库上搜索。
1、2.2 范式,析取范式和合取范式概念 简单合取式、简单析取式 析取范式、合取范式 求公式的析取范式和合取范式 主析取范式和主合取范式概念 极大项、极小项 主析取范式、主合取范式 求公式的主析取范式和主合取范式 求公式的主析取范式意义,2.2 范式 一、 析取范式和合取范式,定义 由有限个命题变元或其否定构成的合取式称为简单合取式。 例如,pqrs、r、s、 rr都是由命题变元p、q、r、s组成的简单合取式。,定义 由有限个命题变元或其否定构成的析取式称为简单析取式。 例如, qrr、p、 qp、 r是由命题变元p、q、r组成的简单析取式。,定理 （1）一简单合取式为永假式的充分必要条件是，它同
2、时包含某个命题变元p及其否定p。 （2）一简单析取式为永真式的充分必要条件是，它同时包含某个命题变元p及其否定p。,定义 有限个简单合取式的析取称为析取范式。即具有 A1A2An(n1)的形式的公式，其中Ai是简单合取式。,例如，F1=p(pq)r(pqr)是一析取范式。,定义 有限个简单析取式的合取称为合取范式。即具有 A1A2An (n1)的形式的公式，其中Ai是简单析取式。,例如: F2=p(pq)r(pqr)是合取范式。 F3=(prq)(pq)r(pr)也是合取范式。,析取范式、合取范式性质 （1）一析取范式为矛盾式的充分必要条件是，它的每个简单合取式都是矛盾式。 （2）一合取范式为
3、重言式的充分必要条件是，它的每个简单析取式都是重言式。,二、求公式的析取范式和合取范式,任何一个命题公式都存在与它等值的析取范式和合取范式。按下列步骤进行：,（1）利用基本等值式消去公式中的联结词 “”、“”等；,（2）利用双重否定律将 (P)置换成P消去否定号 “”，或利用德摩根定律将否定号 “” 向内深入，使之只作用于命题变元；,（3）利用分配律、交换律、结合律将公式归约为合 取范式或析取范式。,例 求F1=(p(qr)s的合取范式和析取范式,解 F1 (p(qr)s, p ( qr)s, p(qr)s (析取范式),又 F1 p(qr)s, (ps)(qr), (psq)(psr) （合
4、取范式）,另外由 F1 (psq)(psr),(p(psr)(s(psr) (q(psr),ps(qp)(qs)(qr) （析取范式） 可见公式的析取范式和合取范式并不唯一,练:求 F2= (pq) (pq)的析取范式、合取范式,解 F2 (pq) (pq)(pq) (pq), (pq)(pq)(pq) (pq),(p(q(pq)(pq(pq), (pq)(pq) （合取范式）,(p(pq)(q(pq),(pp) (pq)(pq)(qq) （析取范式）,三、主析取范式和主合取范式 定义 设有命题变元P1，P2，,Pn ，形如 的命题公式称为是由命题变元P 1，P2，Pn所产生的极小项。而形如
5、的命题公式称为是由命题变元 P1，P2，Pn所产生的极大项 。其中Pi*为Pi或为 Pi(i=1,2,n).,例如,P1P2P3， P1P2P3均是由P1，P2，P3所产生的极小项。P1P2P3是由P1，P2，P3产生的一个极大项。,n个命题变元形成2n个极小项:m0,m1,m2n-1 2n个极大项:M0,M1,M2n-1,定义 如果公式A的析取范式中所有的简单合取式都是极小项，则称该析取范式为A的主析取范式。 如果公式A的合取范式中所有的简单析取式都是极大项，则称该合取范式为A的主合取范式。,例如 (P1P2P3)(P1P2P3)(P1P2P3)是某个公式的主析取范式。,(P1P2P3)(P
6、1P2P3)(P1P2P3)(P1P2P3)是某个公式的主合取范式。,求主析取范式步骤： 求公式的析取范式； 若其中的某个简单合取式Ai中既不含命题变项pj, 也不含它的否定式pj, 则将Ai展成如下形式： Ai Ai1 Ai(pjpj) (Aipj)(Ajpj) 继续这一过程, 直到所有的简单合取式都含任意命题变项或它的否定式。 将极小项用名称按角标由小到大顺序表出。,四、求公式的主析取范式 任一给定的公式，其主析取范式和主合取范式存在并唯一。,例 求F=(pq) r的主析取范式 解：F (pq) r (pq)r)(r(pq) (pq)r)(rpq) (pq)r)(pqr) (pqp)(pq
7、q)(pqr) (rp)(rq)(rr) (pqr)(pr)(qr) 而pr p（qq）r (pqr)(pqr) m1m3,qr (pp)qr (pqr)(pqr) m3m7 而简单合取式pqr已是极小项m4 于是 (pq) r m1m3m4m7,极小项与公式的成真赋值、成假赋值的关系: 若公式A中含n个命题变项，A的主析取范式含s(0s2n)个极小项，则A有s个成真赋值，它们是所含极小项角标的二进制表示，其余2n-s个赋值都是成假赋值。 因此利用真值表也可以求公式的主析取范式,(pq)(pq)(pq)(pq) m0m1m2m3, (pq)(pq)(pq)(pq)(pq),(p(qq)(pq)
8、(p(qq), p(pq)(pp) p(pq)p,解 F1p(p(qp),练 求公式 F1 = p(p(qp)的主析取范式,五、求主析取范式的意义 1、判断公式是否等值 公式A、B有相同的主析取范式当且仅当A、B等值 2、判断公式类型 永真式的主析取范式包含所有2n个极小项；永假式的主析取范式不含任何极小项，用0表示。 3、求公式的成真、成假赋值 4、解决实际问题,练 求公式F=(q(pq)p的主析取范式并判定公式的类型、求出公式的成真赋值和成假赋值。,解,F (q(pq)p, q (pq)p, (q(pp) (pq)(p(qq), （pq)(pq)(pq)(pq)(pq), (pq)(pq)
9、(pq) m0m2m3,由此可知F是可满足公式。,练习 判断公式F=(pq)(pq)是否为重言式或矛盾式？,解 F (pq)(pq)(qp), (pq)(pq)(qp), (pq)(p(qp)(q(qp), (pq)(pq)(pp)(qq)(qp), (pq)(pq)(qp) m1m2m3,F的主析取范式既非空公式，又未包含22=4个极小项，故F不是重言式和矛盾式，只是可满足式。,例 某科研所要从名科研骨干A,B,C中挑选12名出国进修。由于工作原因，选派时要满足以下条件： （）若A去，则C同去。 （）若B去，则C不能去。 （）若C不去，则A或B可以去。 问应如何选派他们去？,解 设 p:派A
10、去 q:派B去 r:派C去 由已知条件可得公式 （pr）(qr)(r(pq) 经过演算可得 (pr)(qr)(r(pq) m1m2m5 由于 m1 = pqr m2 =pqr m5 = pqr 可知，选派方案有3种： （a）C去，而A,B都不去。 （b）B去，而A,C都不去。 （c）A,C去，而B不去。,六、求公式的主合取范式,求主合取范式步骤: 求公式的合取范式； 若其中的某个简单析取式Ai中既不含命题变项pj, 也不含它的否定式pj, 则将Ai展成如下形式： Ai Ai0 Ai (pjpj) (Ai pj) (Ai pj) 继续这一过程, 直到所有的简单析取式都含任意命题变项或它的否定式。
11、 将极大项用名称按角标由小到大顺序表出。,例 求F=(pq) r的主合取范式 解：F (pq) r (pq)r)(r(pq) (pq)r)(rpq) (pq)r)(pqr) (pr)(qr)(pqr) 而qr (pp)qr (pqr)(pqr) M2M6,p r p(qq)r (pqr)(pqr) M0M2 简单析取式（pqr）已是极大项M5 于是 (pq) r M0M2M5M6,练 求公式 F1= (pq)(pq)和 公式F2=p(p(qp)的主合取范式,解: F1 (pq)pq, (pq)(p(qq)(q(pp), (pq)(pq)(pq)(pq)(pq),(pq)(pq)(pq)(pq)
12、 M0M1 M2 M3,解 F2 p(p(qp), (pp)(pqp),11, 1,实际上,利用公式的主合取范式也可以判断公式的类型。永假式的主合取范式包含所有 2n个极大项；永真式的主合取范式不含任何极大项，用1表示。,若公式A含3个命题变元，其主析取范式为：A m0m1m4 则其主合取范式为： A M2M3M5M6M7,因此，只要能求出公式的的主析取范式，其主合取范式和成真、成假赋值及公式的类型就都迎刃而解了。,七、公式的主析取范式与主合取范式的关系,依据见教材,2.3 联结词完备集,与非、或非、异或 N元真值函数 联结词完备集相关概念 冗余联结词 独立联结词 联结词完备集 极小全功能集,
13、联结词完备集 设p、q是两个命题，p与q的否定是一个复合命题，记作pq。 称为p与q的与非式。 由定义有： pq (pq),设p、q是两个命题，p或q的否定是一个复合命题，记作pq。 称为p与q的或非式。 由定义有： pq (pq),N元真值函数,元函数就是有个自变量的函数，元真值函数就是自变量和函数值都是真值（即或）的函数。 一元真值函数有4个,二元真值函数有16个,N元真值函数,？ 一般地, n元真值函数共有多少个呢？ 每个自变量有2种取值方式, n个自变量共有2n种不同取值方式，对n个自变量的每种取值方式，函数值有2种取值方式，即为0或1，故n元真值函数共有 个。,例如, 3元真值函数共有=256个 函数F:0,1n0,1称为n元真值函数, 其中：0,1n为0, 1的卡氏积 真值函数与命题公式的关系 : 对于每个真值函数, 都可以找到许多与之等值的命题公式 ； 反过来，每
