命题逻辑的应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,命题逻辑应用,及习题课,1,推理证明(形式证明)下列各式:,(1),(2),AB,CB AC,(3)(AB)(CD),BE,DF,(EF),ACA,(4)SQ,RQ,R(RS),2,形式证明（推理）下列论述：,如果今天是星期四，那么有一次离散数学测验或大学英语测验。如果大学英语老师生病，那么没有大学英语测验。今天是星期四并且大学英语老师生病，所以，我们有一次离散数学测验。,由红、黄、蓝、白四队进行桥牌对抗赛。如果红队第三，则当黄队第二时，蓝队第四；或者白队不是第一，或者红队第三；事实上，黄队第二。因此，如果白队第一，那么蓝队第四。,3,李明或王平参加这场排球賽，那么红队一定赢这场球赛，如果红队赢了这场球赛，红队将参加全校冠亚军决赛。但红队未能进入全校决赛，故此李明或王平没有参加这场排球赛。,如果乙不参加篮球赛，那么甲就不参加；如果乙参加篮球赛，那么甲和丙就参加；因此，如果甲参加球赛，那么丙就参加。,如果李敏来华工，若王军不生病，则王军一定去看李敏。如果李敏出差广州，则李敏一定来华工。王军没有生病，所以，如果李敏出差广州，王军一定去看望李敏。,4,5,一、命题逻辑在刑侦推理的应用,例1 在一起凶杀案中，侦查人员了解到以下一些情况：,（1）凶手是甲或乙或丙；,（2）只有是盗窃杀人案，甲才是凶手；,（3）如果是盗窃杀人案，那么被害人的财物会丢失；,（4）如果乙是凶手，那么案件发生在中午12点以后；,（5）案件发生在中午12点以前，并且被害人的财物没有丢失。,问：谁是凶手？,解 简单命题用符号表示如下：,P,：甲是凶手,Q：乙是凶手,R：丙是凶手,S：本案是盗窃杀人案,T：被害人的财物丢失,U,：案件发生在中午,12,点以后,前提:PQR,P,S,ST,QU,U,T,6,前提:PQR,P,S,ST,QU,U,T,推理如下：,（1）,U,T,P 前提引入,（2）,U,T(1)I 化简,（3）QU P 前提引入,（4）,Q,T(2)(3)I 拒取,（5）,T,T(1)I 化简,（6）ST P 前提引入,（7）,S,T(5)(6)I 拒取,（8）,P,S,P 前提引入,（9）,P,T(7)(8)I 假言推理,（10）,P,Q,T(4)(9)I 合取引入,（11）,(,P,Q,)T(10)E 置换,（12）PQR P 前提引入,（13）R T(11)(12)I 析取三段论,结论是R，即丙是凶手。,7,例2 在一起凶杀案中，公安人员掌握了如下情况：,（1）甲或乙是凶手；,（2）如果甲是凶手，那么作案地点不在办公室；,（3）如果丙的证词真实，则办公室里有枪声；,（4）只有作案地点在办公室，丙的证词才不真实。,公安人员因此得出:如果办公室里无枪声,那么凶手是乙不是甲。,问：此推理是否有效？,解简单命题用符号表示如下：,P,：甲是凶手,Q,：乙是凶手,R,：作案地点在办公室,S,：丙证词真实,T,：,办公室里有枪声,前提:,PQ P,R,ST,S,R,结论:,T,P,Q,8,前提:ST,S,R,P,R,PQ 结论:,T,P,Q,判定如下：,（1）,T,附加前提引入,（2）ST 前提引入,（3）,S,(1)(2)拒取,（4）,S,R 前提引入,（5）R (3)(4)假言推理,（6）P,R,前提引入,（7）,P,(5)(6)拒取,（8）PQ 前提引入,（9）Q (7)(8)析取三段论,（10）,P,Q (7)(9)合取引入,（11）,T,P,Q (5)(10)CP规则,这表明，公安人员的推理有效。,9,例3 某侦查员掌握了以下情况：,（1）如果A是凶手，则B或C不可能都不是凶手；,（2）如果D不是凶手，则B也不可能是凶手；,（3）或者C不是凶手，或者D是凶手；,（4）只有A是凶手，E才是凶手；,（5）E是凶手。,问：由这些情况，可推出什么结论？,解：简单命题用符合表示如下：,p：A是凶手,q：B是凶手,r：C是凶手,s：D是凶手,t：E是凶手,10,前提:p(q,r),s,q,rs,tp,t,推理如下：,（1）tp 前提引入,（2）t 前提引入,（3）p,(1)(2)假言推理,（4）p(q,r)前提引入,（5）q,r (3)(4)假言推理,（6）,q,r (5)置换,(7)rs 前提引入,（8）rs (7)置换,（9）,q,s (6)(8)假言三段论,（10）,s,q,前提引入,（11）,ss (9)(10)假言三段论,（12）s (11)置换,由前提推出的结论：s，即ADE是凶手。,11,例4 在一起集团作案中，侦查人员了解到如下一些情况：,（1）甲和乙不同时作案；,（2）如果丙作案，那么乙也作案；,（3）如果丁作案，那么甲也作案；,（4）或者戊和已不同时作案，或者丙作案。,据此,侦查人员做出推断,如果丁和已一同作案,那么戊不会作案.,问：这一推断正确吗？,解：简单命题用符号表示如下：,p：甲作案,q：乙作案,r：丙作案,s：丁作案,t：戊作案,u：已作案,12,前提:,(pq),rq,sp,(tu)r 结论:(su),t,证明:（1）su 附加前提引入,（2）s (1)化简,（3）sp 前提引入,（4）p (2)(3)假言推理,（5）,(pq)前提引入,（6）,p,q (5)置换,（7）,q (4)(6)析取三段论,（8）rq 前提引入,（9）,r (7)(8)拒取,（10）,(tu)r 前提引入,（11）,(tu)(9)(10)析取三段论,（12）,t,u (11)置换,（13）u (1)化简,（14）,t (12)(13)析取三段论,（15）(su),t (1)(14)CP规则,所以，侦查人员的推断正确。,13,二、组合电路,命题逻辑的知识在日常生活和工程技术中应用非常广泛，特别在组合电路设计中更是如此。为了今后逻辑电路设计的需要，现将与命题逻辑联结词对应的门电路罗列于下：,门电路 命题表示 逻辑代数表示,F=A F=A,F=AB F=AB,F=AB F=A+B,F=(AB)F=AB,14,门电路 命题表示 逻辑代数表示,F,=(,A,B,),F,=,A,+,B,F=A,B,F=A,B F=A,B,（一）、电路化简,已知逻辑电路如下，在逻辑代数中可以利用卡诺图进行化简，这里要求利用已学知识将其化简。,15,F=(（PQ）(P(QR),PQ,R,F,(PQ)(PR)(QR),16,F=(PQ)(P(QR)(PQ)(P,R)(QR)PQ)(P(QR)(P(Q R)(QR),(PQ)(PQ)(P R)(P(QR)(QR),(PQ)(PR)0,(PQ)(PR),(P(QR),P(QR),P,Q,R,&,1,F,17,（二）、电路的等价变换,在电路设计中，为了减少逻辑电路的故障，便于维修，尽量采用统一的元器件。最常用的元件是“与非门”器件。如逻辑电路如下：,F=(PQ)R,(PQ)R,(PQ)R,(PQ)R),(,P,Q),R,该逻辑电路可以用“与非门”组合而成。,P,Q,R,F,P,Q,R,&,1,F,1,18,(三)、全加器的设计,计算机的加法运算可归结为二进制数码的相加运算，全加器中某一位是由被加数和加数对应位及低一位进位相加而成，同时还要处理该位相加后向高位进位的问题。假设P和Q为相加两数第i位的数码，R为i-1位向第i位的进位，S是P、Q、R 相加后在本位得到的数码，J是第i位向第i+1位的进位数码。,其运算真值如下：,P,Q,R,S,J,0,0,0,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,0,1,1,0,0,1,0,1,0,1,0,1,1,1,0,0,1,1,1,1,1,1,J=（PQR）（PQR）（PQR）（PQR）,S=（PQR）（PQR）（PQR）（PQR）,19,利用等价变换化简J：,J=(PQR)(PQR)(PQR)(PQR)(PQR)(PQR),(PQR)(PQR)(PQR)(PQR)(PQR)(PQR),(PQ)(PR)(QR),S无法化简,所以全加器逻辑电路图如下：,J,S,P Q R,20,