离散数学-习题答案.docx

离散数学 习题 参考答案习题一1、构造公式(pq) (q)、p 得真值表。 2、构造公式(p)与q得真值表。 、构造公式 p、pp、pp得真值表。 4、构造公式p(r)、(pq)(pr)得真值表。 5、构造公式 p(p)、得真值表、6、构造公式 p(pr)、p 得真值表、7、构造公式p、qp 得真值表。 8、构造公式(pq)(pq)、p 得真值表。 9、构造公式 p、p 得真值表、 1、构造公式 pp、pp 得真值表略习题二一、分别用等算演算与真值表法,判断下列公式就是否存在主析取范式或主合取范式,若有,请写出来。(1)(p)(qp)(2)(pq)(qr) (3)(p(r)(q) (4) (qp) ()(pq)(pr) (6)(pq)()(q)(8) (pq)(qr) (9)(q)q (1) (rp)pq解:(1)q p (q)q(qp)(pq)(q)0 1 0 11 1 01 1 1 0 0 0 10 01 1 1 11101 01 存在主析取范式=成真赋值对应得小项得析取=m010m11=(q)(pq)(q) 主析取范式成假赋值对应得大项得合取=M0=pq 等值演算: (p)(qp) (q)(pq) (pq)(pq) (pq)(pq)(pq)(q(q) (p)(pq) (1q)(pq)(q) 这就是大项,故为大项得合取,称为主合取范式 (p)(q) (pq) ()(q) (p1)( 1) (p(qq)( (pp)q) () (p)(p)(p)(pq)(pq)(q) 因为一个公式得值不就是真,就就是假,因此当我们得到一个公得取值为真得情况时,剩下得组合就是取值为假, 因此当得到小项得析取组成得主析取范式后,可以针对剩下得组合写出主合取范式。如当我们得到(pq)(qp)得大项之合取(pq)后,使(pq)为假时(p,q)得值为(,1),故其标记为01,剩余得取值为(,0),(,0),(,1),故小项之析取为m00m0m11、反之,若先得到其小项得析取,也可得到其大项得合取、反正这两者将其所有组合瓜分完毕。(2)(pq)(q)pqrppq(q)结果00000101010101100011111110010010010110010010111主析取范式000m001011m11(qr)(pqr)(pq)(pq) 主合取范式=1000101M1=(pqr)(pqr)(qr)(pqr)(3)(qr)(pr)pr(qr)(p(q)(pq)(p(r)(qr)000001000000111011001111111011111111永真式,所有小项得析取得到其主析取范式(r)(pr)(pqr)(pqr)(pqr)(pq)(pqr)()由于没为假得指派,所以没有为假赋值,所对应得大项合取构成得合取,即没有主合取范式、(p(qr)(pq)=(p(qr)(qr)(q)(pr)(qr) (pq) (pr)pqr=(pq)(p)pqr=1永真(4) (q)ppqp(q)(q)结果00110 1 1 1 0 0 0 0 0 1 0 1 没有成真得赋值,从而没有对应得小项,因此没有小项构成得主析取范式永假式即矛盾式,为假指派对应得大项合取(p)(p)(pq)(pq)原式(q)p=(qp) =0 () (pq)(pr)pqr(q)p(pr)(q)(pr)001001011100101011100001100111110111011主析取范式(pqr)( pqr)( pqr)( pqr)(p)()(pr) 主合取范式M0qr原式=(q)p)(pp)(pq)r=(1(q)r=pqr 这就就是大项也剩下得赋值对应得就就是小项(6)(p()pqr(p)(p(p)(p(q)r0011001110101101111001111111110111111永真式,只有小项组成得主析取范式。没有为假得赋值,所以没有成假赋值对应得大项得合取,即没有主合取范式、 原式=( (pq)(1q)r=1(7)(q)pq(p)(p)r00000001011000010 1 1 00 0 0101 101 1 1 111 1 主析取范式=m01m011m1m1m11 (pqr)( pqr)(qr)(pqr)(pqr)主合取范式=M00M010M10=(pqr) (pq) (pqr)(pq)r=(pq1)(11r) (pq(r)( (p) (qq)r) =(pqr) (pq) (pqr)( pqr) (qr)(pq)r =(pr) (q) (p) (0qr) (q)r) (p)q) =(pr)(pq) (pqr) (r)=(p) (pqr) (pq)(8) (pq)(qr)pqr()(qr)()(r)00011001110101000111000110110110100111111主析取范式=00m01m01m1=(pq)(qr)(pqr)(pqr)主合取范式=M010M10M1110= (pqr)(pqr)(r)(r) (pq)(qr)(pq)(q)=(p)(0qr) =(q(r)( (pp)qr) (pqr) (pqr) (qr)( pr) (pq)(qr)=()(q)=(pq)(p) (q) (q) =(q) (p1r)(1r) =(pq(rr) (p(qq)r)( (pp)r) =(pqr) (pqr) (pqr) (pqr)(r)( qr) =(p) (pr) (pr)(pqr) () (pq)qq(pq)(pq)q0010111001111永真式,只有小项得析取构成得主析取范式(pq)(pq)()(pq) 没有为假得指派,所以没有由大项得合取构成得主合取范式(pq)q =(pq)q (pq)q = 1 (10) (rp)pprrp(r)()pq00100001001100011001011100110111100主析取范式=m1qr 主合取范式M000 M1M10M011100 M101 M111 =(pq)(qr)(pqr)(pr)(pqr)( r)( pqr) (p)pq =(pr) (p)pq =(r) (pr)pq =(rq)(prpq) (q r) (r)pq=(pr)(pr)p = (pr)(pr) = (r)(p)p = (pr)(r)p)q = (p)p=(qq)r)(p(q) (rr)( ()(rr) (pqr)(pq) (pr)(pqr)(pr) (pqr) ( pq) ( pq r) ( pqr)( pqr)(pqr)(pq) (pq)(q)( pq ) (qr)(pq) =00 M01M0011 M100M101M1二、应用题1、某次课间休息时,位同学作为主持人与另外3位同学进行猜数游戏,主持人说这个数就是3、50、70中得某一个,您们三位同学各猜一次,然后主持人分析每人猜数得结果,从而最终确定就是哪个数。同学说:这个数就是3,不就是50同学说:这个数就是,不就是70同学3说:这个数既不就是30,也不就是50 主持人听后说道:您们3人中,有一人全对,有二人对了一半,请问到底就是哪个数、解:令表示“这个数就是30”,W表示“这个数就是50”,表示“这个数就是70”同学得话:S 同学2得话:Q 同学3得话:W对于每个人来说,只有二个选择:全对、对一半,对一半又分成:第一句对第二句错、第一句错第二句对,因此每个同学得对错情况为:、,因此3个人共有*327种可能得情况,其中有些情况不符合“有一人全对,有二人对了一半”而剔除。我们按“、”顺序,构造“类真值表来分析其组合情况同学1同学2同学3命题公式分析不必写不可能全对不必写不可能有2个对不必写不可能有2个对不必写不可能有2个对WWQW0真值为0不对SWWSW=0真值为不对不必写不可能有2个对WQS真值为0不对QW=WQ可能对得,就是30不就是,不就是0S S W=0不可能SW WQS W0不可能SW WQSW=不可能SW WQS=不可能 S, W,W, Q,S,W=0不可能,W, Q,S, W=0不可能, W,W, S, W0不可能,W,W,W=3个数都不就是,不可能答案就是:就是,不就是50,不就是70 同学说:这个数就是30,不就是5 全对同学2说:这个数就是50,不就是70 第一句错第二句对同学3说:这个数既不就是,也不就是5第一句错第二句对2、设计一个如下得电路图:它有三个输入p1、2、p,当其中有2个及以上得值为1时输出得结果为1,其她情况下输出0。请给出其真值表,同时针对此真值表给出主析取范式、主合取范式,并给出其最简单得表达式。答:与课堂例题一样 在真实得教材将其换成了如下习题2、设计一个如下得电路图:它有三个输入1、3,当其中任意二个得值为0时输出得结果为1,其她情况下输出0。请给出其真值表,同时针对此真值表给出主析取范式、主合取范式,并给出其最简单得表达式、p1p表达式得值00010011010101101001011011其主析取范式=m00m01m1m10 =(p12p3)(pp2p)(p1p3)(p1p2p3)=(pp2)(p33)( (p1) (p2)3) =(2) (1p2)(1)p3) 其主合取范式=11M01M11M111(p1p2p)(pp2p3)(pp3)(pp2p) =(p1p2)(1p2)p3) (p1p2) 3、某年级要从1班、2班、3班、4班、5班中选出一名才子主持元旦晚会,每班最多一人,也可能没有,这些人满足如下条件,请确定最终选择哪些班级得学生: (1)如果班有人选中,则2班有人选中。(2)若班有人选上则1班与2班均有人选上。()5班与4班必有一班有被选中、()班与4班同时有人选上或同时没人选上、解:用Oe表示1班选了人,To表示2班选了人,Three表示3班选了人,Four表示4班选了人,Five表示5班选了人。则这4个条件依次为Oewo,Five(OnTo),FourFve,ThreeFour 满足这个条件,即这个条件得值均为真即为1,所以其合取为 (Onew) (ive(OeTwo)(FourFive) (hreFor)1,将以上合取范式转换为主析取范式,因此双条件应转换为析取式得合取式 原式=(neT) (Five(OneTo)(Fourive) (TreFou) (Theo) =(newo) (ive(OTwo)(FuFie) (TreFur)(hreFour)=(Oee)(On(Oewo)(wFve)(Two(OneTwo)(Foue) (Threur) (ThreeFur)=(Fie)(TwoFive)(woOne)(FouFv) (TeFour) (ThreeFour) =(OneFivFou) ( TwoFiveFour) (TwOeFor) (woOeFiv) (ThreeFour) (reFor) (OneiveFourhre) (OneFivFo) (TFieFou Tre) (TwoFveFu) (woOneFouThe) (TwoOnFour)(wOneiv Th) (Twoneive Fur) (Treeour) =(OneFveFor hree) ( TwoFiveou Three) (TwoOeFourThree) (TwoOFv Tre Four) (ToeFie Four The) (nehe FouFve) ( Two Tree Four iv) (OneT Tree our) (OeTwoThree For Fve) (OneTwo Tree Four F)一班二班三班四班五班条件条件2条件3条件4方案一无不限有有无满足满足满足满足方案二不限有有有无满足满足满足满足方案三有有有有不限满足满足满足满足方案四有有无无有满足满足满足满足方案五有有有有有满足满足满足满足(1)如果1班有人选中,则2班有人选中、(2)若班有人选上则1班与2班均有人选上、(3)5班与班必有一班有被选中。(4)3班与4班同时有人选上或同时没人选上。按照某位帅哥得质疑,经仔细思考,应该将其转换为主析取范式,所以最终结果为:= (Oe1 hre Four Five) (1wo ThreourFve) (nTo hree u1) (OnTwhee Fr Five) (Onw hree Fou Fiv) =(OnTTree rFive) (OneTw Threeour iv) (One Two ThreeFr Five) (Oe Tw Thre Furive) (OneT Tee orFie)(ewoThee urFive) (OneTwoTreeFor Fv) (OeTwoheFou Five)(ewo The ou iv) (OneTwo TheeurFv) (ne Two Thr Fou ve) (newoThe FrFive) (OeTwoTre For Five)一班二班三班四班五班条件1条件2条件3条件方案一无无有有无满足满足满足满足方案二无有有有无满足满足满足满足方案三有有有有无满足满足满足满足方案四有有有有有满足满足满足满足方案五有有无无有满足满足满足满足(1)如果1班有人选中,则2班有人选中。(2)若5班有人选上则1班与2班均有人选上。(3)班与4班必有一班有被选中。(4)班与4班同时有人选上或同时没人选上、某公司要从A、C、D、E选派一些人去参观世博会,必须满足如下条件: (1)若A去则B肯定不能去; ()若A与C只能去一个; ()C与D两人同去或同不去;(4)若B去则C肯定去(5)若E去则B,C,D肯定有一人陪同、证明:就是否存在满足以上条件得人选？若存在则请给出全部方案。 解:这句知表示为: (AB) (AC)(AC) (CD) (BC) (E(D) 满足个条件,则每个条件得值为真,故其合取为真,将其转换为主析取范式,则可以判断就是否有可能得方案、(AB) (AC)() (CD) (BC) (BCD) =(AB)()(AC)()(CD)( BCD) (AC) (CB) (CB)(CD)()(ECD)=(ACD) (A D) (AC D) (EB) =(CDE) (ACB) (ACD)(B C DE) ( E) (AB C D)(BC D)(B DE) (AB C D) (B C) (ACD) (CD) (BC DE) (A C DE) (A CDE)(B C DE) (AB D) (AB DE) (AB DE) (BCDE) (ACDE) (AB CDE) (ABC) (ACDE)=(ABCE) (B CDE) ( C DE) (AB CDE) (AB CDE)条件1条件2条件3条件4条件(A DE)A去不不不E不满足满足满足满足满足(B C DE)不不C去D去不满足满足满足满足满足(B C DE)不不C去D去E去满足满足满足满足满足(ABCDE)A不去C去D去不去满足满足满足满足满足(B CDE)A不B去C去D去E去满足满足满足满足满足习题三 1、利用定义1、6。1,并利用等值演算或真值表,证明如下各推理式,要注明每步得理由。、(A) BA(1) B为真前提条件(2) A为真 前提条件(3) BA为真因为BAAB为真(4) A为真 (B) B假言推理2、(AB)BA (1) B为真 前提条件(2) (AB)为真前提条件 (3) BA为真因为A AB为真(4)为真 (BA) B假言推理、(AB)(BC)(AC) () (AB)为真前提条件(2)(AB)(BA)为真因(AB) (AB)(BA)() (B)为真 由(2)及合取得定义()(BA)为真 由(2)及合取得定义(5)(BC)为真 前提条件()(BC)(CB)为真因(B) (BC)(CB) () (BC)为真由()及合取得定义(8) (CB)为真 由(6)及合取得定义(9) (CA)为真 由(8)(4)及传递律(1) (A)为真 由(3)(7)及传递律(1)(AC)为真 由(9)(10)及双条件得定义() (AB)( AB) (AB)(AB) (A) ( AB ) B (AB) (AB) B (AB) () ( A ) B) B (1 B) B 1 故为永真式(A)( AB)B 2、采用定义1、2方法证明如下推理式,并注明每步理由,可采用P规则、反证法、1、q,qr,rs,s (1) p() p (3) q (1)(2)得定义,或(1)()分离原则(4) qr (5) r (4)(5)得定义,或(4)(5)分离原则(6) rs (7) s (5)(6)分离原则2、 p(qr),(rs) (pq)s (1) (pq) 附加条件(2)p ()与得定义附加条件(3) q(2)与得定义附加条件(4) p(q)(5) qr()与(4)分离原则(6) (3)与(5)分离原则(7) (s) () rs ()与(7)分离原则(9) s (6)与(8)分离原则3、(qr),p,q rs () p为真前提条件 () p(qr)为真前提条件 (3)(q)为真 (1)(2)假言推理()q为真 前提条件()r为真 (4)(3)假言推理(6)rs为真(5)与析取得定义4、pq,(r) ,r (1) (p)为真前提条件 (2) pr为真 (1)与德摩律(3)rp为真 与(2)等值(4)r为真前提条件 (5) 为真(4)(3)假言推理反证法 () p为真反证法即假设结论为真 (2)p为真 否定得否定为真(3)(pr)为真前提条件()r为真 (3)与德摩律(5) pr为真与()等值(6) r为真 (2)(5)假言推理(7)r为真 前提条件显然()(7)矛盾,故假设错了,即“p为真”错了,所以p为真5、pq p(pq)(1)p为真附加前提() p为真前提条件 ()q为真 ()(2)假言推理()(pq)为真 (1)(3)及合取得性质6、qp,qs,st,tr,rpq(1) tr为真 前提条件(2) (tr) (r)为真与(1)等值(3) (rt)为真 (2)及合取得定义(4)r为真 前提条件(5)t为真(3)(4)假言推理(6) st为真前提条件(7)(st) (ts)为真与(6)等值(8)(ts)为真 (7)及合取得定义(9)s为真 (5)(8)与假言推理(10) s为真 前提条件(1) (qs) (sq)为真与(10)等值(12) (s)为真 (11)与合取得定义(13)q为真 (9)(2)与假言推理() qp为真 前提条件(1)p为真(13)()假言推理(16)pq为真 (3)()及合取得定义7、r, q ,pq rs (1)pq为真前提条件()p为真 ()与合取得性质(3)为真 ()与合取得性制() pr为真 前提条件(5)为真 (2)(4)假言推理(6)qs为真前提条件()为真 (3)(6)及假言推理(8)s为真(5)(7)及合取得性质8、pr,qt rs (1)t为真附件前提()pq为真前提条件 (3)p为真 (2)与合取得定义(4)q为真 ()与合取得定义(5) pr为真前提条件 ()pr为真与()等值(7)为真 ()(3)与假言推理(8) qs为真前提条件(9) qs为真与()等值(10)s为真 ()()与假言推理(11)rs为真 (7)(10)与合取得性质9、p (q),sp,qsr (1)s为真 附加前提(2) p为真前提条件 (3)为真 (1)(2)假言推理() (qr)为真前提条件 (5) (qr)为真 (3)(4)假言推理(6)q为真 前提条件()为真(5)(6)假言推理10、(pq) (rs),(s) upu ()为真 附加前提(2)pq为真(1)及析取得性质() (pq) (rs)为真前提条件 (4) ()为真 (2)()与假言推理(5)s为真 (4)与合取得定义(6) (t)为真 (5)与析取得定义() (st)u为真前提条件(8)u为真 (6)(7)假言推理11、q,rq,rs 反证法(1) p为真 结论得否定()p为真(1)得否定之否定(3) pq为真前提条件(4) q为真(2)(3)假言推理(5) rq为真 前提条件(6) qr为真与(5)等值(7) r为真()(6)假言推理(8) s为真 前提条件(9) r为真(8)及合取得定义故(7)(9)矛盾,从而假设“p为真就是错得,只能“p为假”,所以p为真2、pq,qs rs结论为rsrs,所以上式等价于证明pq,qsrs ()r为真附加条件(2) pr为真前提条件 (3) rp为真与(2)等值(4) 为真(1)(3)假言推理(5) p为真前提条件(6)pq为真与()等值(7)q为真 (4)(6)与假言推理(8)qs为真前提条件(9)s为真 (7)(8)与假言推理3、将下面各段话用命题逻辑公式表示,并构造其自然逻辑得证明过程、(1)只要A曾到过受害者得房间,并且11点以前没有离开,就就是谋杀嫌犯、A曾到过受害者房间。如果在1点前离开,瞧门人会瞧见她。瞧门人没瞧见她、所以A就是谋杀嫌犯。解:P1表示“A曾到过受害者得房间P2表示“A人1点以前离开” 3表示“A就是谋杀嫌犯” 4表示“瞧门人瞧见”则以上语句表示:(PP2)P3,P,P24,P (1) P4为真 前提条件(2) P2P为真 前提条件(3) P42为真与()等值(4)为真 (1)()进行假言推理()P1为真 前提条件() (1P2)为真 (4)(5)与合取得定义(7)(P12)为真前提条件(8)为真 ()(7)进行假言推理()如果今天就是星期六,我们就要