《离散数学课件》命题逻辑2

1、上节课内容,等值式、基本等值式 等值演算 复合联结词 排斥或 与非式 或非式 联结词全功能集,1,(AB)AB (AB)AB,A(AB)A, A(AB)A,ABAB,第四讲 对偶与范式（1.2.4-1.3）,对偶式与对偶原理 析取范式与合取范式 主析取范式与主合取范式,2,3/48,1.2.4 对偶式,定义 在仅含有联结词, ,的命题公式A中， 将换成, 换成， 若A中含有0或1，就将0换成1，1换成0， 所得命题公式称为A的对偶式， 记为A*.,例 已知 = P (QR）,= P(QR) *= P (QR) (*)*= P (QR),则:,4,定理 设A和A*互为对偶式，p1,p2,pn是出

2、现在A和A*中的全部命题变项，将A和A*写成n元函数形式， 则 (1) A(p1,p2,pn) A* ( p1, p2, pn) (2) A( p1, p2, pn) A* (p1,p2,pn) 定理（对偶原理）设A，B为两个命题公式， 若A B，则A* B*.,例 设A*(P,Q,R)是P(QR)，证明 A*(P,Q,R)A(P,Q,R),证：因A*(P,Q,R)P(QR)，代入可得 A*(P,Q,R)P(QR)。 而按对偶式的定义，由A*(P,Q,R)可写出 (P,Q,R)P(QR) 故 (P,Q,R)(P(QR) P(QR) (德摩根律) P(QR) (德摩根律) A*(P,Q,R),6

3、/48,1.3 范式及其应用,合取式,析取式,析取范式,合取范式,主析取范式,主合取范式,主范式 范式 真假性,唯一 两者有关联 不唯一,成真解释,成假解释,对于完全解释， 合(析)取式 =极小(大)项,7/48,合取式、析取式,定义1 命题变元、或者命题变元的否定、或由它们利用合取词组成的合式公式称为（简单）合取式。 定义2 命题变元、或者命题变元的否定、或由它们利用析取词组成的合式公式称为（简单）析取式。 例 显然， P，P，PQ，PQR 均为合取式； P，P，PQ，PQR 均为析取式。,8/48,(一) 解释与合取式、析取式之间的关系,定理1 任给一个成真解释有且仅有一个合取式与之对应；

4、 任给一个成假解释有且仅有一个析取式与之对应。,例 成真解释(P,Q,R)= (1,0,1) 成假解释(P,Q,R)= (0,0,1),合取式PQR,析取式PQR =(PQR),9/48,析取范式、合取范式,定义3 形如A1 A2 An的公式称为析取范式， 其中Ai(i=1,2,n)为合取式。 定义4 形如A1 A2 An的公式称为合取范式， 其中Ai(i=1,2,n)为析取式。 例 P，P，PQ，PQ ，(PQ)(SR) 均为析取范式。 P，P，PQ，PQ ， (PQ)(SR) 均为合取范式。,10/48,例: 考察公式 =PQ的析取范式,对应于两个合取式为 PQ, PQ 于是，有 = (P

5、Q) (PQ),有两个成真解释： (1, 1), (0, 0),11/48,例: 考察公式 =PQ的合取范式,对应析取式为 PQ, PQ 于是，有： = (PQ) (PQ),成假解释 (1, 0), (0, 1),12/48,定理2 任何命题演算公式均可以化为合取范式，也可以化为析取范式。,证明： (1)设公式为永真公式 =PP (2)设公式为永假公式 =PP,证明(3)： 设公式既非永真又非永假。 设公式的成真解释为1，2，n， 成假解释为1，2，t。 根据解释和范式的关系知： 对应于成真解释1，2，n的合取式为 1，2，n 对应于成假解释1，2，t的析取式为 1，2，t 而公式 12n的成

6、真解释为 1，2，n； 公式12t的成假解释为 1，2，t。 根据两个公式逻辑等价的定义知 =12n =12t 故公式既可表示为析取范式又可表示为合取范式。,14/48,(二) 析取范式和合取范式的求解方法,等价变换法利用等价公式进行变换，将范式变换出来。 解 释 法（真值表法） 利用所有成真解释或成假解释，写出范式。,15/48,等价变换法,(1)去蕴含词与等价词： PQ =P Q PQ = (P Q) (P Q) (2)否定深入： (P Q)= PQ (P Q)= PQ， P = P (3)重复使用分配律： P (QR)=(P Q )(P R) P (QR)=(P Q )(P R),16/

7、48,解释法,(1) 求所有成真解释、成假解释； (2) 写出成真解释对应的合取式、 成假解释对应的析取式； (3) 把所有的合取式用析取词联结起来就构成析取范式，把所有的析取式用合取词联结起来就构成合取范式。,求公式的范式举例,解 (pq)r (pq)r （消去） pqr （结合律） 这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式 组成的合取式）,例 求下列公式的析取范式与合取范式 (1) A=(pq)r,解 (pq)r (pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定号内移德摩根律） 这一步已为析取范式（两个简单合取式构成

8、） 继续： (pq)r (pr)(qr) （对分配律） 这一步得到合取范式（由两个简单析取式构成）,(2) B=(pq)r,19/48,例 求公式的范式 (PQ)(RQ)P),解： 原式=(PQ)(RQ)P) =(PQ)(RQ)P) =(PQ)(PR)(PQ) =(PQ)(PR) 析取范式 = P(QR) 合取范式,20/48,解：P=1时, 原式=(1Q)(RQ)1)=QR P=0时, 原式=(0Q)(RQ)0)=0 所以有: 成真解释为：(P,Q,R)=(1,0,1), (1,0,0), (1,1,0) 成假解释为：(P,Q,R)=(1,1,1), (0, ),例 求公式的范式 (PQ)(

9、RQ)P),于是析取范式为: (PQR)(P Q R)(P Q R) 合取范式为： (P QR)P,21/48,范式不唯一性,例 求公式的范式 (PQ)(RQ)P),解1： 原式=(PQ)(PR) 析取范式 = P(QR) 合取范式 解2: 析取范式为: (PQR)(P Q R)(P Q R) 合取范式为： (P QR)P,22/48,1.3.2 主范式,定义5 对于n个命题变元P1，P2，Pn，公式 Q1Q2Qn 称为极小项，其中Qi=Pi或Pi(i=1，n)。,例 由两个命题变元P，Q组成的极小项有四个，它们分别为： PQ PQ PQ PQ,(一) 主析取范式,极小项与极大项(续),由P,

10、 Q两个命题变项形成的极小项,说明：n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.,由p, q, r三个命题变项形成的极小项与极大项,25/48,主析取范式,定义6 仅有极小项构成的析取范式称为主析取 范式。 例如，n=3, 命题变项为p, q, r时， (pqr)(pqr) m1m3 是主析取范式 定理3 任何一个合式公式，均有惟一的一个主析取范式与该合式公式等价。,主析取范式就是 公式的所有完全成真解释对应的极小项的析取。,26/48,求主析取范式的两种方法,(1)解释法: 根据公式的所有完全成真

11、解释，求出与这些成真解释对应的合取式，所有合取式的析取就为公式的主析取范式。 (2)等价变换法: 1) 先求析取范式; 2) 将不是极小项的简单合取式化成与之等值的若 干个极小项的析取，缺少的项用P P填充，需 要利用同一律（零律）、排中律（矛盾律）、 分配律、幂等律等. 3) 极小项用名称mi表示，并按角标从小到大顺序排序.,27/48,例 求公式的主析取范式 (PQ)(RQ)P),解： 原式=(PQ)(RQ)P) =(PQ)(RQ)P) =(PQ)(PR)(PQ) =(PQ)(PR) 析取范式 =(PQ(R R)(P (QQ)R) = (PQR) (PQ R)(P QR) =1011001

12、10=m4m5m6,28/48,解：P=1时, 原式=(1Q)(RQ)1)=QR P=0时, 原式=(0Q)(RQ)0)=0 所以有: 成真解释为：(P,Q,R)=(1,0,1), (1,0,0), (1,1,0),例 求公式的主析取范式 (PQ)(RQ)P),于是主析取范式为: (PQR)(P Q R)(P Q R) =101100110 =m4m5m6,例 求Q(PQ)R)的主析取范式。,解：Q(PQ)R) (PQ)(QR) (先化为析取范式) (PQ(RR)(PP)QR) (补入未出现的变元) (PQR)(PQR)(PQR)(PQR) (展开) (PQR)(PQR)(PQR) (合并相同

13、的小项) m2m3m7 2,3,7,解：给定命题公式的真值表为：,所以Q（(PQ)R）的主析取范式为: (PQR)(PQR)(PQR) 2,3,7 ；,例 求Q(PQ)R)的主析取范式。,31/48,(二) 主合取范式,定义7 对于n个命变元P1，P2，Pn，公式 Q1Q2Qn 称为极大项，其中Qi=Pi或Pi(i=1，n)。,例 由两个命题变元P，Q组成的极大项有四个，它们分别为： PQ PQ PQ PQ,由p, q两个命题变项形成的极小项与极大项,由p, q, r三个命题变项形成的极小项与极大项,34/48,主合取范式,定义8 仅有极大项构成的合取范式称为主合取范式。 定理4 任何一个合式

14、公式，均有惟一的一个主合取范式与该合式公式等价。,主合取范式就是 公式的所有完全成假解释对应的极大项的合取。,35/48,求主合取范式的两种方法,(1)解释法 根据公式的所有完全成假解释，求出与这些成假解释对应的析取式，所有析取式的合取就为公式的主合取范式。 (2)等价变换法: 1) 先求合取范式; 2) 将不是极大项的简单析取式化成与之等值的若 干个极大项的合取，缺少的项用AA填充，需 要利用同一律（零律）、排中律（矛盾律）、 分配律、幂等律等. 3) 极小项用名称Mi表示，并按角标从小到大顺序排序.,36/48,例 求公式的主合取范式 (PQ)(RQ)P),解：原式=(PQ)(RQ)P)

15、=(PQ)(RQ)P) =(PQ)(PR)(PQ) =(PQ)(PR) 析取范式 = P(QR) 合取范式 =(P(QQ)(RR)(QR) (PP) =(PQR)(PQR) (PQR) (PQR) (PQR) =000001010011111=01237,37/48,解：P=1时, 原式=(1Q)(RQ)1)=QR P=0时, 原式=(0Q)(RQ)0)=0 所以有: 成假解释为：(P,Q,R)=(1,1,1), (0, ),例 求公式的主合取范式 (PQ)(RQ)P),于是 主合取范式= (PQR) (PQR) (PQR) (PQR)(PQR) =111011010001000 =01237

16、,(F,TT),(F,T,F),(F,F,T),(F,F,F),38/48,主合取范式和主析取范式紧密相关,(PQ)(RQ)P)=456 =01237,(PR)(P (Q R) （P13） =257 =01346,(PR)(P (Q R) =1467= (1,4,6,7) = 0235= (0,2,3,5),设命题公式中含有个命题变元，且的主析取范式中含个极小项 i1，i2， ，ik，即 Ai1i2ik 那么，的主析取范式中必含2n-k个极小项。设它们是j1，j2 ，mj(2n-k)，即 j1 j2j (2n-k) 注意到iMi，Mi mi，所以 AA (j1 j2j(2n-k) j1 j2

17、j(2n-k)， Mj1 Mj2 Mj(2n-k),主析、合取范式互求,例求Q(PQ)R)的主析取范式和主合取范式。,解：给定命题公式的真值表为：,主析取范式为: (PQR)(PQR)(PQR) 2,3,7 ； 主合取范式:(PQR)(PQR)(PQR) (PQR)(PQR) 0,1,4,5,6,判定二命题公式是否等值。 当且仅当与有相同的主析（合）取范式 判定命题公式的类型。 设是含有个变元的命题公式： 为重言式，当且仅当的主析取范式中含有2n个小项。此时，主合取范式中不含任何大项，可令主合取范式为T。 为永假式，当且仅当的主合取范式中含有2n个大项。此时主析取范式中不含任何小项，可令主析取

18、范式为F。 求命题公式的成真和成假赋值。,1.3.3 范式的应用,例 判断下列命题公式的类型及成真赋值和成假赋值： (PQ)Q； (PQ)PQ； (PQ)Q。 解： (PQ)Q (PQ)Q PQQ ( F) (P(QQ)(Q(PP)(Q(PP) (PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) 0,1,2,3 （永假式）,范式的应用（例）,43, (PQ)（PQ） (PQ)(PQ)(PQ)(PQ) 0123 0,1,2,3 （重言式） (PQ)Q (PQ)(PQ) 13 1,3 （可满足式） 在本例中，成真赋值是：或；成假赋值是： 或。,44/48,你面前有两

19、扇门，其中一扇门后有宝藏，一扇门后有吃人妖怪。 在这两扇门前面，有两个人，这两个人都知道哪扇门后有宝藏，哪扇门后有吃人妖怪，而这两个人呢，一个人只说真话，一个人只说假话。 你只能问这两个人每人一个问题。你怎么问才能找到宝藏？,苹果考题：宝藏在哪里?,45/48,问： 对”此门后是否有宝藏”问题, 你的同伴回答”是”吗？,令 P：被问人说真话； Q：被问人回答“是”； R：其同伴回答“是” ； S：此门后有宝藏。 根据题意可得真值表如图所示。 根据真值表知，主析取范式为： S=(PQ)(PQ) =(PP)Q =Q 因此被问人回答“是”时，此门后一定没有宝藏。,T T T (假话) F,T F F

20、 (假话) T,F T F (真话) F,F F T (真话) T,结论: 否定被问人的回答!,46/48,专家的论证正确吗?,在研讨会上，三位专家分别发言如下: 一位专家由此得出结论：通货膨胀率将会下降。 问这位专家的论证是否正确？,美元不贬值只要而且仅仅只要如果国家税收增加，那么通货膨胀率将下降。 如果通货膨胀率下降，或者美元不贬值，则国家税收将不会增加。 或者国家税收必须增加，或者美元将贬值而且通货膨胀率将下降。,47,P：国家税收增加 Q：通货膨胀率下降 R：美元贬值,1、美元不贬值只要而且仅仅只要如果国家税收增加，那么通货膨胀率将下降。,A R (P Q),2、如果通货膨胀率下降，或

21、者美元不贬值，则国家税收将不会增加。,B (Q R) P,3、或者国家税收必须增加，或者美元将贬值而且通货膨胀率将下降。,C P (QR),P：国家税收增加 Q：通货膨胀率下降 R：美元贬值,A R (P Q) B (Q R) P C P (QR),(ABC) Q PQ RT, 论证错误!,例 某公司要从赵、钱、孙、李、周五名新毕 业的大学生中选派一些人出国学习. 选派必须 满足以下条件： (1)若赵去，钱也去； (2)李、周两人中至少有一人去； (3)钱、孙两人中有一人去且仅去一人； (4)孙、李两人同去或同不去； (5)若周去，则赵、钱也去. 试用主析取范式法分析该公司如何选派他们出国？,49,解此类问题的步骤为： 将简单命题符号化 写出各复合命题 写出由中复合命题组成的合取式 求中所得公式的主析取范式,50,例 (续),解 设p：派赵去，q：派钱去，r：派孙去， s：派李去，u：派周去. (1)若赵去，钱也去； (pq) (2)李、周两人中至少有一人去； (su) (3)钱、孙两人中有一人去且仅去一人； (qr)(qr) (4)孙、李两人同去或同不去； (rs)(rs) (5)若周去，则赵、钱也去. (u(pq),51, A的演算过程如下: A (