离散数学(03)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第一章 数理逻辑,1.3 范 式 (1),1.4,析取范式和合取范式,范式就是命题公式的一种标准式，或者说命题公式的一种规范形式。其中分为析取范式和合取范式。,析取范式是由”运算而够成。合取范式是由”运算而够成。,1,为方便, 我们把合取式称呼为积, 析取式称呼为和。,定义 1.3 -1 命题公式中的一些命题变元和一些命题变元的否定之积,称为基本积(也称小项); 一些命题变元和一些命题变元的否定之和, 称为基本和(也称大项) 。基本积(和)可以看成公式的子式。,2,例如, 给定命题中的变元,P,和,Q, 则,P, ,P,Q,P,Q, ,P,P, ,Q,P,Q,等都是基本积,Q,Q,P,P,Q,P,P,P,Q,Q,等都是基本和。单独的命题也是基本积(和) ，基本积(和)中的子公式称为此基本积(和)的,因子,。,3,定理 1.3 -1,一个基本积是永假式, 当且仅当它含有,P, ,P,形式的两个因子。,证：充分性,P,P,是永假式, 而,Q,F,F, 所以含有,P,和,P,形式的两个因子时, 此基本积是永假式。,必要性 用反证法。设基本积永假但不含,4,P,和,P,形式的两个因子, 则给这个基本积中不带否定符的命题变元指派真值,T, 带有否定符的命题变元指派真值,F, 得基本积的真值是,T, 但这与假设矛盾。 证毕。,定义 1.4-2 一个由基本积之和组成的公式, 如果与给定的命题公式,A,等价, 则称它是,A,的,析取范式, 记为,5,A,：,A,1,A,2, ,A,n,n,1,这里,A,1,A,2, ,A,n,是基本积。,任何一个命题公式都可求得它的析取范式, 这是因为命题公式中出现的和,可用 , 和表达, 括号可通过德摩根定律和在上的分配律消去。,析取范式就是由基本积通过析取而成的公式,6,但一个命题公式的析取范式不是唯一的, 我们把其中运算符最少的称为,最简析取范式,。,如果给定的公式的析取范式中每个基本积都是永假式, 则该式也必定是永假式。,例 1(,a,) 求,P,(,P,Q,)的析取范式。,解,P,(,P,Q,),P,(,P,Q,),(,P,P,)(,P,Q,),7,P,(,P,Q,)不是永假式, 因为其析取范式中, 后一个基本积非永假。,如果需要求出最简的析取范式, 那么(1)式还可化简成,P,(,P,Q,),F,(,P,Q,),P,Q,P,Q,是,P,(,P,Q,)的最简析取范式，只有一个基本积。,8,(,b,) 求 (,P,Q,),(,P,Q,)的最简析取范式。,解：由E,15,(P,Q),(PQ)(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, ,P,) (,P, ,Q,) (,P, ,P,),(,Q, ,P,) (,P, ,Q,),9,定义 1.3 -3 一个由基本和之积组成的公式,如果与给定的命题公式,A,等价, 则称它是,A,的,合取范式, 记为,A,：,A,1,A,2, ,A,n,n,1这里,A,1,A,2, ,A,n,是基本和。,任何一个命题公式都可求得它的合取范式, 这是因为命题公式中出现的和,可用 , 和表达, 否定号可通过德摩根定律深入到变元,10,上, 再利用在上的分配律化成合取范式。,一个公式的合取范式也不是唯一的, 其 中运算符最少的称为,最简合取范式,析取范式、合取范式的真值问题,由定义可知，析取范式就是由一些基本积通过析取构成的命题公式。合取范式就是由一些基本和通过合取构成的命题公式。,11,如果给定的公式的合取范式中每个基本和都是永真式, 则该式也必定是永真式。,例 2求(,P,Q,),(,P,Q,)的最简合取范式。,解：记,A,(,P,Q,),(,P,Q,), 则,A,(,P,Q,),(,P,Q,) ),(,P,Q,)(,P,Q,)(,P,Q,),(,P,Q,),12,(,(,P,Q,),P,Q,)( (,P,Q,),(,P,Q,),(,F,(,P,Q,)(,P,Q,),(,(,P,Q,)(,P,Q,),(,P,Q,) (,P,Q,),(,P,Q,), (,P,Q,),所以,13,A,(,P,Q,) (,P,Q,),(,P,Q,)(,P,Q,)。,对同一个公式，我们可以分别求出析取范式和合取范式。,例 求公式(PQ),(PQ)的析取范式和合取范式,解：先求析取范式,14,(PQ),(PQ),(PQ),( P Q),( (PQ)( P Q) ),( (PQ) ( P Q) ),( PQ)( PQ) )( (PQ), (P Q) ),( PQP ) (PQ Q),(PPQ) (PQQ) (1),15,(PQ) F (P Q),(PQ) (P Q) (2),上面的(1)(2)式都是原式的析取范式 ，所以析取范式不唯一。,再求合取范式,解：(PQ),(PQ),(PQ),(PQ),16,(PQ)(PQ) ,(PQ) (PQ),(PQ)(PQ),(PQ)(PQ),(PQ)(PQ)(PQ),( PQ),17,(P,Q,P,Q,)(PQ)P),(PQ)Q),(TQ)(PP)(QP),(PQ) ( QQ),TT(QP)(PQ)Q (1),(QP)(PQ)Q (2),18,上面的（1），（2）式都是原式的合取范式 ，所以合取范式不唯一。 QP ，PQ， Q分别是原式的,基本和,。,公式的析取范式常用来判定公式是否是永假式；,公式的合取范式常用来判定公式是否是永真式；,这是由于：公式,A,为永假式,:,当且仅当,A,的析取范式为矛盾式；,19,当且仅当析取范式的每个基本积为矛盾式；,当且仅当析取范式的每个基本积至少同时含有一个命题变元,P及其它的否定 P；,同样有：公式,A,为永真式,当且仅当合取范式的每个基本和至少同时含有一个命题的变元及其否定.,范式的基本特征：不含有，,，和双否定；,20,1.3.2,主析取范式和主合取范式,利用析取范式容易判别矛盾式，利用合取范式容易判别重言式, 但是由于范式不唯一，使用起来很不方便。为了使范式唯一，我们引入一种特殊的范式-,主范式,。,定义 1. 4 在,n,个变元的基本积中, 若每一个变元与其否定不同时存在, 而两者之一必出现,21,一次且仅出现一次, 则这种基本积叫,极小项,。,极小项是由命题变元与命题变元的否定通过合取 (,类似集合运算中的,，运算后使集合变小,有A,B,A.)构成的命题公式，但是极小项中的命题变元和命题变元否定不同时存在，而两者之一必出现一次而且仅出现一次。,例如：公式 A(,P,Q,) 中有,P,和,Q,两个命题变元，,22,加上它们的否定 P,Q共能组合出4个极小项：,PQ, PQ, PQ, PQ,n,个变元可构成 2,n,个不同的极小项。例如 3 个变元,P,Q,R,可构造 8 个极小项。这就与真值表的指派构成对应, 我们把命题变元看成 1, 命题变元的否定看成 0, 那么每一极小项对应一个二进制数, 因而也对应一个十进制数。对应情况如下:,23,P,Q,R,-0 0 0-0,P,Q,R,-0 0 1-1,P,Q,R,-0 1 0-2,P,Q,R,-0 1 1-3,P,Q,R,-1 0 0-4,P,Q,R,-1 0 1-5,P,Q,R,-1 1 0-6,P,Q,R,-1 1 1-7,24,我们把对应的十进制数当作足标, 用,m,i,表示这一项, 即 ;,m,0,P,Q,R,m,1,P,Q,R,m,2,P,Q,R m,3,P,Q,R,m,4,P,Q,m,5,P,Q,R,m,6,P,Q,R m,7,P,Q,R,25,一般地,n,个变元的极小项是:,m,0,P,1,P,2,P,3,P,n,m,1,P,1,P,2,P,3,P,n,m,2,n,-1,P,1,P,2,P,3,P,n,26,定义 1.3 -5,一个由极小项之和(析取)组成的公式, 如果与给定的命题公式,A,等价, 则称它是,A,的,主析取范式。,例如：,A,PQR,PQ,(RR),(PP,)(,QQ,)R,(PQR)(PQR),(PP,)(QR)( Q R) ,27,(PQR)(PQR)P(QR)( Q R) P (QR)( Q R),(PQR)(PQR) (PQR) (PQ R) (P QR)(PQ R),(PQR)(PQR) (PQ R) (P QR)(PQ R),m,1,m,3,m,5,m,6,m,7,（1、3、5、6、7）,28,本式的证明采用了配项的方法，一般不提倡用此方法求主范式 。,前边讲过每一极小项和它的足标的二进制数一一对应, 因而和一种指派一一对应, 例如三个变元时,极小项 足标 指派,P,Q,R, 1 0 1 1 , 0 , 1,29,当且仅当将对应的指派代入该极小项, 该极小项的真值才为 1。 因此, 在命题公式的主析取范式中, 诸极小项都与真值表中相应指派处的该公式的真值为1 相对应, 反之亦然。对照下列真值表可以验证,下表中公式真值为真的分别是第,2,4,6,7,8行。对应的小项是:,m,1,m,3,m,5,m,6,m,7,。,30,P,Q,R,m,1,m,3,m,5,m,6,m,7,这就给出了利用真值表求主析取,范式的方法，也是我们常用的方法。,P Q R,P,Q,R,m,i,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,0,1,0,1,0,1,1,1,m,1,m,3,m,5,m,6,m,7,那么，,公式,A,PQR,直接等价于小项的,析取：,31,其中,m,1,P,Q,R m,3,P,Q,R,m,5,P,Q,R m,6,P,Q,R,m,7,P,Q,R,;,那么, 我们就得到公式的,析取,范式,：,P,Q,R,(,P,Q,R,) ( ,P,Q,R,) (,P,Q,R,)(,P,Q,R,)(,P,Q,R,),32,定义 1.3 -6 在,n,个变元的基本和中, 若每一个变元与其否定不同时存在, 而二者之一必出现一次且仅出现一次, 则这种基本和叫,极大项,。,极大项,是由命题变元与命题变元的否定通过析取(,类似集合运算中的,，运算后使集合变大,有A,A,B .)构成的命题公式，但是极大项中的命题变元和命题变元否定不,33,同时存在，而两者之一必出现一次而且仅出现一次，与极小项成对偶。,例如：公式,A,( P,Q)可构成的极大项共有：,P,Q, P,Q, P,Q, P,Q,n,个变元可构成2,n,个不同的极大项。类似于(但不同)极小项的记法, 它们是:,M,0,P,1,P,2,P,n,34,M,1,P,1,P,2, ,P,n,M,2,P,1,P,2, ,P,n,-1,P,n,. ,M,2,n,-1,P,1, ,P,2, ,P,n,注意：极大项的记法与极小项刚好相反，这里是将命题变元对应于 0, 命题变元的否定对应于1,恰与极小项记法相反；,35,例如 3 个变元的极大项是这样对应的,极大项 足标 指派,P,Q,R, 0 1 00 , 1 , 0,(与极小项相反 ),其目的是当且仅当将极大项的对应指派代入该极大项, 才使该极大项的真值为 0, 使今后许多运算得到方便。,36,定义 1.3 -7 一个由极大项之积组成的公式,如果与给定的命题公式,A,等价, 则称它是A的,主合取范式,。,主析取范式就是由一些不同的极小项通过析取构成的析取范式。,主合取范式就是由一些不同的极大项通过合取构成的合取范式。,37,主析取范式和主合取范式统称,主范式,例如,A,P,Q,R,的合取范式：,(,P,Q,),R,(,P,R,)(,Q,R,),(,P,R, (,Q, ,Q,)(,Q,R, (,P,P,),(,P,Q,R,)(,P,Q,R,) (,P,Q,R,),M,0,M,2,M,4,(0 , 2 , 4),38,利用真值表求主范式,例：用真值表方法求,(PQ),(PQ),的主范式。,解:,作公式的真值表如下，注意最后两列的顺序：,P Q,PQ,(PQ),PQ,原式,小项,大项,0 0,0 1,1 0,1 1,0,1,1,1,1,0,0,0,1,1,0,1,1,0,1,0,m,0,m,1,m,2,m,3,M,3,M,2,M,1,M,0,39,（,1）先求主析取范式：,因为真值表中第五列只有两个,1,，对应的原命题真值是,0 0,和,1 0,，所以我们有公式的极小项是m,0,=(PQ),和m,2,=(PQ) ，原公式主析取范式为：,(PQ),(PQ),m,0, m,2,(P Q) (P Q),40,（2）再求主合取范式：,因为真值表中第五列只有两个0，对应的原命题真值是0 1和1 1，与极小项相反，用定义得到对应的极大项是：,M,2,(P Q) 和M,0,(PQ),故原公式主合取范式为：,(PQ),(PQ),M,0, M,2,(P Q)(PQ),41,从真值表的后两列可以看出极小项与极大项是对偶的，也可用对偶性求得极大项,M,0, M,2,m,1,m,3,(P Q)(PQ),使用真值表求主范式，就是利用真值表中公式的真值情况求极小项和极大项。公式真值为1时的指派对应极小项；真值为0时的指派对应极大项。,42,一个命题公式的主析取范式和主合取范式,紧密相关, 在它们的简记式中, 代表极小项和极大项的足标是互补的, 即两者一起构成0, 1, 2, , 2,n,-1诸数,例如:,A,P,Q,R,(1,3,5,6,7) (主析取范式表示) 则,A,P,Q,R,(0,2,4),(主合取范式表示),43,一个命题公式的真值表是唯一的，所以一个命题公式的主析取(合取)范式也是唯一的。,每一个公式都能求普通的范式(析取和合取范式)，但不一定就有主范式，由真指表可以看出，当公式是偶然式时，同时有主析取和主合取范式；当公式是永真式时，只有主析取范式；当公式是永假式时，只有主合取范式；,44,两个命题公式，如果有相同的主析取范式，那,么这两个命题公式是逻辑等价的。,例 3 证明,P,Q,和,P,(,P,Q,)(,Q,P,)二式逻辑等价。,证 :,P,Q,P,(,Q, ,Q,),Q,(,P P,),(,P,Q,)(,P Q,)(,P,Q,),(1),45,P,(,P,Q,)(,Q, ,P,),P,(,P,Q,)(,Q,P,),P,(,P,Q,P,)(,Q,Q,P,),P,(,P,Q,),P,(,Q, ,Q,)(,P,Q,),(,P,Q,) (,P, ,Q,),P,Q,),(2),由于(1) (2)式相同，所以, 二式逻辑等价。,46,主范式的求法,1.利用恒等关系法：,先求出公式的普通范式，再根据原公式中含有的命题变元个数，配成符合要求的极小项或者极大项，利用恒等变形，再调整它们之间的运算关系，得到主析取（合取）范式。,47,2.利用真值表法：,列出公式的真值表，找到公式真值为1或者0的项的真值指派组合就是主范式的极小项或者极大项，再根据要求写出相应的主析取(合取)范式。,注意：极小项可以直接由原子命题的真值指派得到，而极大项刚好与极小项的取法相反。,48,例：用两种方法求公式(,Q,(,PQ,)的主范式,(1)用恒等关系法:,(,Q,(,PQ,),Q,(,PQ,),Q,(,P,Q,),Q,(,P,Q,),(,Q,(,P,P,)(,P,Q,),(,P,Q,)(,P,Q,)(,P,Q,),主析取范式，有三个极小项,P,Q, ,P,Q, P,Q,。,49,(,Q,(,PQ,),Q,(,PQ,),Q,(,P,Q,),Q,(,P,Q,),(,Q,P,)(,Q,Q,),(,Q,P,)T,P,Q,主合取范式，只有一个极大项,P,Q,50,(,1)用真值表法:,P Q,Q,PQ,Q,(,PQ,),(,Q,(,PQ,),0 0,0 1,1 0,1 1,1,0,1,0,1,1,0,1,1,0,0,0,0,1,1,1,主析取范式: (PQ)(PQ)(PQ),主合取范式: PQ,极大项也可以利用于极小项对偶而求得。,51,总 结,本次课我们学习了：,析取（合取）范式和对应的主范式,的定义和性质，以及构成范式的成分。,重点掌握：析取（合取）范式的求法，和主范式的真值表求法，恒等式变形求法的应用。,52,本次授课到此结束,作业如下:,P,20,2，3,下次课内容：1.5 推理规则和证明方法,53,