离散数学答案命题逻辑

1、 /17第二章命题逻辑习题2.11.解不是陈述句，所以不是命题。（2）x取值不确定，所以不是命题。问句，不是陈述句，所以不是命题。惊叹句，不是陈述句，所以不是命题。是命题，真值由具体情况确定。是命题，真值由具体情况确定。是真命题。是悖论，所以不是命题。vq是假命题。解是复合命题。设p：他们明天去百货公司；q：他们后天去百货公司。命题符号化为P2是疑问句，所以不是命题。是悖论，所以不是命题。是原子命题。是复合命题。设p：王海在学习；q：李春在学习。命题符号化为pAqo是复合命题。设p：你努力学习；q：你一定能取得优异成绩。P*不是命题。不是命题。是复合命题。设p：王海是女孩子。命题符号化为：p。

2、解如果李春迟到了，那么他错过考试。要么李春迟到了，要么李春错过了考试，要么李春通过了考试。李春错过考试当且仅当他迟到了。如果李春迟到了并且错过了考试，那么他没有通过考试。4解（l）pT（qvr）o（2）pTq。qTp。qTp。习题2.2解是1层公式。不是公式。一层：pvq，p二层：poq所以，（pvq）T（poq）是3层公式。不是公式。（pTq）人（qo（qTr）是5层公式，这是因为一层：pTq，q，r二层：qTr三层：qo（qTr）四层：（qo（qTr）解A=（pvq）Aq是2层公式。真值表如表2-1所示：表2-1A二qA（PTq）TP是3层公式。真值表如表2-2所示:表2-2表2-33.解

3、A二(pAq)vP真值表如表2-5所示:表2-5所以其成真赋值为：00，10，11；其成假赋值为01。A二rT(pAq)真值表如表2-6所示：表2-6所以其成真赋值为：000，010，100，110，111；其成假赋值为001，011，101。A二(pTq)吕(PVq)真值表如表2-7所示，所以其成真赋值为：00,11；成假赋值为:01，10，。解设A-pv(pAq)，其真值表如表2-8所示:表2-8设A=(pAq)A(pvq),其真值表如表2-9所示：表2-9设A=(pTq)k(poq)，其真值表如表2-10所示：表2-10设A=(pTq)A(qTr)T(pTr)，其真值表如表2-11所示:

4、表2-1111111111故A二(pTq)a(qTr)T(pTr)为重言式。习题2.31解真值表如表2-12所示：表2-12pqpq-1paiqpvq|(Pvq)0011101011001010010101100010由真值表可以看出7pvq)和aq所在的列相应填入值相同，故等值。真值表如表2-13所示：表2-13Pq1qpaqpaiq(Paq)v(pAiq)001000010000101011110101由真值表可以看出p和(paq)v(paq)所在的列相应填入值相同，故等值。真值表如表2-14所示：表2-14PqiP1qpTqpTiq(PTq)a(PTiq)0011111011011110

5、010101100100由真值表可以看出P和(pTq)A(pTq)所在的列相应填入值相同，故等值。真值表如表2-15所示：11111112-15由真值表可以看出pT(qTr)和(pq)Tr所在的列相应填入值相同，故等值。2.证明(l)(pAq)v(pvq)o(pAq)v(p人iq)OpA(qvq)op。(2)(pTq)A(qTP)O(pvq)a(qvp)O(pAq)v(pAp)v(qAq)v(qAp)O(pAq)v(pAq)。由(2)可得，(poq)。(pAq)v(pAq)(ipvq)A(vq)o(q_p)a(ipq)o。(4)pT(qTr)opv(qvr)Oqv(pvr)oqT(pTr)。p

6、T(qvr)Opv(qvr)O(pvq)vrO(pAq)vrO(pAq)Tr(pTq)a(rTq)O(pvq)a(rvq)O(pAr)vqO(pvr)Tq3.解(pTq)O(pvq)OpAq2(pTq)O(pvq)OpAq(3)i(poq)i(pTq)a(qp)(pTq)v(qp)O(pAq)v(pAq)Opoq。4同理可证(poq)Opoq。4.解与习题2.2第4(4)相同。2真值表如表2-16所示：表2-16真值表如表2-17所示，所以公式是矛盾式。表2-17pqpqpvqpaqA0011100011010010010101100100真值表如表2-18所示，所以公式是重言式。表2-18p

7、qrpAqpaqarA000001001001010001011001100001101001110101111111真值表如表2-19所示，所以公式仅为可满足式。表2-19pqppTq(pTq)A001011011101100100110100真值表如表2-20所示，所以公式是重言式。表2-20PqrPTqrqPAr(PTq)a(rq)(PAr)qA000110111001100011010110111011110111100010011101001001110110111111111111解设p：他努力学习；q：他会通过考试。则命题符号化pTq。其否定(pTq)Op人q。所以语句的否定：他

8、学习很努力但没有通过考试。设p：水温暖；q：他游泳。则命题符号化p分q。其否定(p今qOpoq。所以语句的否定：当且仅当水不温暖时他游泳。设p：天冷；q：他穿外套；r：他穿衬衫。则命题符号化pT(q人-r)其否定一(p(qAr)(pV(qAr)Opa(qAr)opA(qvr)所以语句的否定：天冷并且他不穿外套或者穿衬衫。设p：他学习；q：他将上清华大学；r：他将上北京大学。则命题符号化P(qr)其否定(pT(qvr)o(PV(qvr)op八qar所以语句的否定：他努力学习，但是没有上清华大学，也没有上北京大学6解设p：张三说真话；q：李四说真话；r：王五说真话。贝V：poq,qor(oqor)

9、,ro(pAq)为真，因此po(pAq)o(pApAq)v(pA(pvq)opAq为真。因此，p为假，q为真，所以r为假。故张三说谎，李四说真话，王五说谎。7.解设p：甲得冠军；q：乙得亚军；r：丙得亚军；s：丁得亚军。前提：pT(qvr)，qTp，sTr，p结论：s证明pT(qvr)为真，其前件p为真，所以qvr为真，又qTp为真，其后件p为假，所以要求q为假，所以r为真。又sTr为真，其后件r为假，所以要求s为假，故s为真。习题2.41.解设p：明天下雨；q：后天下雨。命题符号化pvq。设p：明天我将去北京；q：明天我将去上海。命题符号化pvq。2.解(pTq)vpo(pTq)Ap)v(p

10、Tq)Ap)o(pvq)Ap)v(pvq)Ap)opv(pAqAp)opvqpI(qvp)o(pv(qvp)o(pv(qAp)v(qAp)o(pv(qAp)o(pvq)opAqo(pTq)vr)o(paq)vr)opAqAr3.证明因为，,v,A,T,o是功能完备联结词集，所以，含有,v,A,T,o外的其他联结词的公式均可以转换为仅含，v，A，o中的联结词的公式。又因为pTqopvqpoqo(pTq)A(qTp)o(pvq)A(qvp)即含有T，吕的公式均可以转换为仅含八中的联结词的公式。因此，含八外其他联结词的公式均可以转换为仅含中的联结词的公式。故，V，A是功能完备联结词集。4.证明,a是

11、极小功能完备集，因而只需证明,a中的每个联结词都可以用T表示，就说明T是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，po(pAp)OpTp，pAqoii(pAq)oi(pTq)o(pTq)T(pTq)。对于证明1是极小功能完备集，可类似证明。习题2.51.解(pAq)V(pAq)；(pA(qVr)v(par)vp2.解(pTq)T(rTS)O(pvq)v(rvs)o(pAq)VrVs即为其析取范式。(pTq)T(rTs)o(pAq)vrvsO(pVrVs)A(qVrVs)即为其合取范式。pA(q吕r)opA(qVr)A(rVq)即为其合取范式。pA(qor)opA(qAr)v(q

12、Ar)O(pAqAr)V(pAqAr)即为其析取范式。(3)(pVq)Ar即为其合取范式。(pVq)Aro(pAr)V(qAr)为其析取范式。pT(qTr)opVqVr即为其析取范式和合取范式。3.解pA(pVq)o(pV(qAq)A(pVq)o(pvq)a(pvq)a(pvq)o口(0,1,2)即为其主合取范式。其主析取范式为Z3opAqo(pTq)v(paq)o(pVq)V(pVq)o1o故其主析取范式为E(0,1,2,3)=(paq)v(pAq)v(pAq)v(pAq)o3(pVq)Tr)Tpo(pVq)Vr)Vpo(pVq)Ar)Vpo(pVq)A(pVr)o（pvq）v（rar）a（

13、pvr）v（qaq）o（pvqvr）a（pvqvr）a（pvqvr）a（pvqvr）on（0,1,3）即为其主合取范式。其主析取范式为丫（2,4,5,6,7）o（pAqAr）v（pAqAr）v（pAqAr）v（pAqAr）v（pAqAr）。（4）（pTq）T（rTs）o（pvq）v（rvs）o（paq）v（rvs）o（pvrvs）a（qvrvs）o（pvqvrvs）a（pvqvrvs）a（pvqvrvs）a（pvqvrvs）on（2,6,14）即为其主合取范式。其主析取范式为工（0,1,3,4,5,7,8,9,10,11,12,13,15）。4.解真值表如表2-21所示，所以其极小项是pAq，

14、极大项为pvq,pvq,pvq。表2-21真值表如表2-222所示，所以其极小项是pAq,pAq,pAq,极大项为pvq。表2-22pqpvqpTq（pTq）（pTq）v（pvq）000100011101101011111101其主析取范式是：（pAq）v（pAq）v（pAq）,主合取范式为：pvq。真值表如表2-23所示，所以其极小项是pAqAr,pAqAr,pAqAr,pAqAr,pAqAr,表2-23pqrppaqarpv（paqar）000100001100010100011111100001101001110001111001极大项为pvqvr,pvqvr,pvqvr。其主析取范式是

15、：(pq人r)v(pq人一r)v(pAq人r)v(pAqAr)v(pAqAr)，主合取范式为：(pvqvr)A(pvqvr)A(pvqvr)。真值表如表2-24所示，所以其极小项为pAqAr,pAqAr,pAqAr,pAqAr,pAqAr,而极大项分为pvqvr，pvqvr，pvqvr.主合取范式为(pvqvr)a(pvqvr)a(pvqvr),主析取范式为(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)。表2-24pqrpTq(pTq)Tr00010001110101001111100011010111010111115.解(pvq)a(paq)o(pvq)A(

16、pvq)Oqo(pAq)v(pAq),故为可满足式。(pTq)a(qTr)T(pTr)o(pvq)A(qvr)v(pvr)o(pAq)v(qAr)v(pvr)o(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)v(pAqAr)oY(0,123,4,5,6,7)故2为重言式。(pv(qAr)o(pvq)A(pvr)o(pv(qAr)o(pv(qAr)o(pv(qAr)v(pv(qAr)A(pv(qAr)v(pv(qAr)o(pv(qAr)A(pv(qAr)o(pv(qAr)

17、ApA(qAr)o(pAqAr)A(qvr)o0。故3为矛盾式。(pTq)v(rTs)T(pvr)T(qvs)o（pvq）a（rvs）v（par）vqvso（paq）a（ras）v（par）vqvso（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqaras）v（paqarvs）v（paqaras）v（paqaras）v（paqaras）v(paqaras)v(paqaras)v

18、(paqaras)oY(0,1,3,4,5,6,7,9,10,11,12,13,14,15)故仅为可满足式。6.证明右边已经是主合取范式。而左边主合取范式已是pAq,因此，(pvq)opaq，证毕。右边(pvq)A(pvq)已经是主合取范式。popv(qAq)o(pvq)A(pvq)。因此,po(paq)v(paq)。左边pT(qTr)opv(qvr)opvqvr,而右边(paq)Tro(pAq)vropvqvr，因此，PT(qTr)O(paq)Tr。习题2.61.解设p:这里有演出；前提：pTq,rTq,r结论:pq：这里通行是困难的；r：他们按照指定时间到达。证明rrTqqpTqp2.(1

19、)证明PPT假言推理PT拒取式ssTppPPT假言推理pTqqPT假言推理证明rP附加前提引入rTqPqT假言推理pT-qPpT拒取式pTSPST假言推理rTsTCP证明PP否定结论引入pTqPqT假言推理qTrPrT假言推理irsPrT化简厂人一,rT合取证明pP附加前提引入pvqPq析取三段论rTqPr拒取式pTrCP证明PP附加前提引入pT(qTr)PqTrT假言推理qP附加前提引入rT假言推理(rTtPrvsvtT蕴涵等价式S7tT析取三段论一h(SA一t)PsvtThT假言易位11.hT假言推理12.qThT11.CP13.pT(qTh)T12.CP3.解推理不正确。在到化简时，只能

20、对整个公式进行而不是子公式。4解正确。(1)P，P附加前提引入；T析取三段论；P；T假言推理；P;（7）T假言推理;TCP。5解设p：张三努力工作，q：李四高兴，r：王五高兴，s：刘六高兴结论：pTs证明：pP附加前提引入pT(qvr)PqvrT假言推理qTpPqT拒取式rT析取三段论sTirPsT拒取式pTiSTCP6解设：p:天下雪；q：马路结冰；r：汽车开得快;前提：pTq，qTr，rTs，s结论：p证明pTqPqTrPpTr推理三rTsPpTS推理三段sPp拒取式前提：pT（qvr），qTp，ST-rs：马路塞车。复习题2解设p：3是偶数，q：中国人的母语是汉语。命题符号化PTqo设p

21、：你抽烟，q：你很容易得病。命题符号化PTq。设p：今天是星期一，q：明天才是星期二。命题符号化qTP。设p：李春这个学期离散数学考了100分。q：李春这个学期数据结构考了100分。命题符号化p人q。设p：下雪路滑，q：他迟到了。命题符号化qTP。设p：经一事，q：长一智。命题符号化pTq。设p：一朝被蛇咬，q：十年怕井绳。命题符号化PTq。设p：以物喜，q：以己悲。命题符号化卩q。解命题中的“或”是不可兼或，因此，可以直接用“pvq”符号化；根据联结词的性质及其之间的转换关系，可知命题“李春生于1979年或生于1980年”的本意是“李春生于1979年（但不能生于1980年）或生于1980年（

22、但不能生于1979年）”，因此，也可以转化为“（p人q）v（p人q）”对其进行符号化。解设p：李刚会拳击，q：李春会唱歌。命题符号化（pvq）人（pTq）。而（pvq）aI（p_q）pvq）ai（pvq）pvq）apaqp人q因此，李刚会拳击并且李春不会唱歌。4.解(1)A的极小项对应于其真值表中的成真赋值0001,0110,1000,1001,1010,1100,1101,1111。成真赋值对应二进制数转化为十进制数就是A的极小项的下标。由此可得，A的极小项为：m二paiq人一iras；m二paqaras；m二paiq八r人一is；168m二paqaras；m二paqaras；m二paqar

23、as；91012m二paqaras；m二paqaras1315相应的,A的极大项对应于其真值表中的成假赋值,成假赋值对应二进制数转化为十进制数就是A的极大项的下标。由此可得,A的极大项为：M二pvqvrvs；M二pvqvrvs；M二pvqvrvs；023M二pvqvrvs；M二pvqvrvs；M二pvqvrvs；457M二pvqvrvs；M二pvqvrvs1114由问题得到了A的极小项和极大项，于是与A等值的主析取范式和主合取范式可以直接得到，分别为：工(16,8,9,10,12,13,15)；n(0,2,3,4,5,7,11,14)。从A的主析取范式出发,进行等值演算化简,可得析取范式的最简

24、形式：(paqaras)v(paqaras)v(paqaras)v(paqaras)v(paqaras)v(paqaras)v(paqaras)v(paqaras)(pAqArAs)v(qArAs)v(pAqAr)v(pAqArAs)v(pAqAr)(pAr)v(pAqArAs)v(qArAs)v(pAqArAs)(pAr)v(qArAs)v(qArAs)v(pAqArAs)(pAr)v(qArAs)v(qArAs)v(pAqAs)5.证明(1)(ptq)A(rtq)O(pvq)a(rvq)o(par)vqo(pvr)vqo(pvr)tqpt(qtr)Opv(qvr)oqv(pvr)oqt(p

25、tr)(pvq)a(paq)O(pvq)v(paq)O(paq)v(paq)o(pOq)(paqarts)a(rtpvqvs)o(pAqAr)vs)A(rv(pvqvs)o(pvqvr)a(rvpvq)vso(rv(pvq)a(pvq)vso(ra(pvq)a(pvq)vso(ra(paq)v(paq)vso(ra(p吕q)Ts6解公式的真值表如表2-27所示：表2-27pq-PqpTqiq-Tip(pTq)A(qTp)0011111011011110011001100010从真值表可见，公式所在列的填入值有1也有0，故仅为可满足式。(pT-(q)A(-,qT-(p)o(-ipv-,q)A(q

26、v-(p)oH(2,3)为其王合取范式，可见公式仅为可满足式。公式真值表如表2-28所示：表2-28从真值表可见，公式所在的列的填入值均为1，等值演算，以及求出的王析取范式均说明公式是重言式。(3)A=(pTq)A(qTr)T(pTr)真值表见习题2.2第4(4)题。(pTq)A(qTr)T(pTr)o(pvq)A(qvr)v(pvr)o(pAq)v(qAr)vpvro1.从真值表可见，公式所在的列的填入值均为1，由等值演算，以及求出的王析取范式均说明公式是重言式。7.(1)证明pP附加前提引入pT(qTr)qTrqqT(rTs)rTsqTspT(qTs)PT假言推理P附加前提引入PT假言推理T假言三段论TCP证明wUTWusvusrvsr(pvq)Tr(pvq)p人q)证明PPT拒取式PT析取三段论PT析取三段论PT拒取式T德摩根律ppTqvrqvrqTpqrstrspTs8.解P附加前提引入PT假言推理PT拒取式T析取三段论PT拒取式TCPpArppTqq(qvs)qAsqqAq由得到矛盾，可见pTq，(qvs)，PT化简PT假言推理PT德摩根律T化简T合取pAr不能同时成