离散数学问题详解命题逻辑.doc

《离散数学问题详解命题逻辑.doc》由会员分享，可在线阅读，更多相关《离散数学问题详解命题逻辑.doc（18页珍藏版）》请在课桌文档上搜索。

1、第二章命题逻辑习题2.11解不是述句，所以不是命题。x取值不确定，所以不是命题。问句，不是述句，所以不是命题。惊叹句，不是述句，所以不是命题。是命题，真值由具体情况确定。是命题，真值由具体情况确定。是真命题。是悖论，所以不是命题。是假命题。2解是复合命题。设p：他们明天去百货公司；q：他们后天去百货公司。命题符号化为。是疑问句，所以不是命题。是悖论，所以不是命题。是原子命题。是复合命题。设p：王海在学习；q：春在学习。命题符号化为pq。是复合命题。设p：你努力学习；q：你一定能取得优异成绩。pq。不是命题。不是命题。是复合命题。设p：王海是女孩子。命题符号化为：p。3解如果春迟到了，那么他错过

2、考试。要么春迟到了，要么春错过了考试，要么春通过了考试。春错过考试当且仅当他迟到了。如果春迟到了并且错过了考试，那么他没有通过考试。4解p(qr)。pq。qp。q p。习题2.21解是1层公式。不是公式。一层：pq，p二层：pq所以，是3层公式。不是公式。(pq)(q( qr)是5层公式，这是因为 一层：pq，q，r 二层：qr 三层：q( qr) 四层：(q( qr)2解A=(pq)q是2层公式。真值表如表2-1所示：表2-1pq0000011110101111是3层公式。真值表如表2-2所示：表2-2pq00101011101000111111是3层公式。真值表如表2-3所示：表2-3pq

3、r00000010010001010001101100111000011101001111010111111111是4层公式。真值表如表2-4所示：3解真值表如表2-5所示：表2-5pq001111011000100101110001所以其成真赋值为：00，10，11；其成假赋值为01。真值表如表2-6所示：表2-6pqr0000100100010010110010001101001101111111所以其成真赋值为：000，100，110，111；其成假赋值为001，011，101。真值表如表2-7所示，所以其成真赋值为：00，11；成假赋值为：01，10，。4解设，其真值表如表2-8所示：

4、表2-8pq00011010111001111101故为重言式。设A=(pq)(pq)，其真值表如表2-9所示：表2-9pqpqpq(pq)A000010010100100100111100故A=(pq)(pq)为矛盾式。设A=(pq)(pq)，其真值表如表2-10所示：表2-10pq001010011111100100110010故A=(pq)(pq)为可满足式。设，其真值表如表2-11所示：表2-11pqr0001111100111111010100110111111110001001101010111101000111111111故为重言式。习题2.31解真值表如表2-12所示：表2-1

5、2pq0011101011001010010101100010由真值表可以看出和所在的列相应填入值一样，故等值。真值表如表2-13所示：表2-13pq001000010000101011110101由真值表可以看出和所在的列相应填入值一样，故等值。真值表如表2-14所示：表2-14pq0011111011011110010101100100由真值表可以看出p和(pq)(pq)所在的列相应填入值一样，故等值。真值表如表2-15所示：pqrqrp(qr)pq(pq)r00011010011101010010101111011001101101110111000101111111表2-15 由真值表

6、可以看出p(qr)和(pq)r所在的列相应填入值一样，故等值。2证明(pq) (pq) (pq)( pq)p (qq) p。(pq)(qp)(pq)(qp)(pq)(p p)( qq)(q p)( pq)(pq)。由可得，(pq)( pq)(pq)( pq)(pq)(qp)(pq)pq。p(qr) p(q r) q(p r) q( p r)。3解(pq)(pq)pq(pq)( pq)pq(pq)(pq)(qp)(pq)(qp)(pq)(pq) pq。同理可证(pq) pq。4解与习题2.2第44一样。真值表如表2-16所示：表2-16pqpqpqq pA00111110110111100100

7、11100111所以公式是重言式。真值表如表2-17所示，所以公式是矛盾式。表2-170011100011010010010101100100真值表如表2-18所示，所以公式是重言式。表2-18000001001001010001011001100001101001110101111111真值表如表2-19所示，所以公式仅为可满足式。表2-19001011011101100100110100真值表如表2-20所示，所以公式是重言式。表2-20pqrpqrqpr(pq)(rq)(pr)qA000110111001100011010110111011110111100010011101001001

8、1101101111111111115解设p：他努力学习；q：他会通过考试。如此命题符号化pq。其否认(pq) pq。 所以语句的否认：他学习很努力但没有通过考试。设p：水温暖；q：他游泳。如此命题符号化pq。其否认(pq) pq。 所以语句的否认：当且仅当水不温暖时他游泳。设p：天冷；q：他穿外套；r：他穿衬衫。如此命题符号化p(qr)其否认( p(qr)(p(qr) p( qr) p(q r) 所以语句的否认：天冷并且他不穿外套或者穿衬衫。设p：他学习；q：他将上清华大学；r：他将上大学。如此命题符号化其否认所以语句的否认：他努力学习，但是没有上清华大学，也没有上大学。6解 设p：三说真话

9、；q：四说真话；r：王五说真话。如此：pq, qr(qr), r(pq)为真,因此p(pq)(ppq)(p(pq)pq为真。因此，p为假，q为真，所以r为假。故三说谎，四说真话，王五说谎。7解 设p：甲得冠军；q：乙得亚军；r：丙得亚军；s：丁得亚军。前提：p(qr)，qp，sr，p结论：s证明p(qr)为真，其前件p为真，所以qr为真，又qp为真，其后件p为假，所以要求q为假，所以r为真。又sr为真，其后件r为假，所以要求s为假，故s为真。习题2.41解设p：明天下雨；q：后天下雨。命题符号化。设p：明天我将去；q：明天我将去。命题符号化。2解3证明 因为，是功能完备联结词集，所以，含有外的

10、其他联结词的公式均可以转换为仅含中的联结词的公式。又因为即含有的公式均可以转换为仅含中的联结词的公式。因此，含外其他联结词的公式均可以转换为仅含中的联结词的公式。 故是功能完备联结词集。4证明是极小功能完备集，因而只需证明中的每个联结词都可以用表示，就说明是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，p(pp)pp，pq(pq)(pq)(pq)(pq)。对于证明是极小功能完备集，可类似证明。习题2.5 1解；2解即为其析取式。即为其合取式。即为其合取式。p(qr)p(qr)(qr)(pqr)(pqr) 即为其析取式。即为其合取式。为其析取式。即为其析取式和合取式。3解即为其主合取

11、式。其主析取式为3pq。故其主析取式为(0,1,2,3)=(pq)(pq)(pq)(pq)。即为其主合取式。其主析取式为(2,4,5,6,7) (pqr)(pqr)(pqr)(pqr)(pqr)。即为其主合取式。其主析取式为。4解真值表如表2-21所示, 所以其极小项是pq，极大项为pq，pq，pq。表2-21pq0010011010011110其主析取式是：pq，主合取式为：(pq)( pq)(pq)。真值表如表2-222所示, 所以其极小项是pq, pq, pq, 极大项为pq。表2-22pq000100011101101011111101其主析取式是：(pq)(pq)(pq)，主合取式为

12、：pq。真值表如表2-23所示，所以其极小项是pqr,pqr, pqr, pqr,pqr,表2-23pqr000100001100010100011111100001101001110001111001极大项为pqr，pqr，pqr。其主析取式是：(pqr)(pqr)(pqr)(pqr)(pqr)，主合取式为：(pqr)(pqr)(pqr) 。真值表如表2-24所示,所以其极小项为pqr,pqr,pqr,pqr,pqr,而极大项分为pqr，pqr，pqr.主合取式为(pqr)(pqr)(pqr),主析取式为(pqr)(pqr)(pqr,)(pqr)(pqr)。表2-24pqr000100011

13、10101001111100011010111010111115解(pq)(pq)(pq)(pq) q (pq)(pq)， 故为可满足式。 故为重言式。(p(qr)(pq)(pr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)p(qr)(pqr)(qr)0。 故为矛盾式。 故仅为可满足式。6证明右边已经是主合取式。而左边主合取式已是pq，因此，(p q)pq，证毕。右边(p q)(pq)已经是主合取式。pp(qq) (p q)(pq)。因此，。左边p(qr)p(qr)pqr，而右边(pq)rpqr，因此，。习题2.61解 设p：这里

14、有演出；q：这里通行是困难的；r：他们按照指定时间到达。前提：pq, rq,r结论：p证明r Prq Pq T假言推理pq P pT拒取式2证明s PspPpT假言推理pqPqT假言推理证明rP附加前提引入rqPq T假言推理pqPp T拒取式psPs T假言推理rs TCP证明pP否认结论引入pqPqT假言推理qrPrT假言推理rsPrT化简rrT合取证明pP附加前提引入pqPq析取三段论rqPr拒取式prCP证明pP附加前提引入p(qr)PqrT假言推理qP附加前提引入rT假言推理(rs)tPrstT蕴涵等价式stT析取三段论h(st)PsthT假言易位hT假言推理qhTCP13. p(q

15、h)TCP3解 推理不正确。在到化简时，只能对整个公式进展而不是子公式。4解 正确。P，P附加前提引入；T析取三段论；P；T假言推理；P；T假言推理；TCP。5解 设p：三努力工作，q：四高兴，r：王五高兴，s：六高兴 前提：p(qr)，qp，sr 结论：ps 证明：pP附加前提引入p(qr)PqrT假言推理qpPqT拒取式rT析取三段论srPsT拒取式psTCP6解设：p：天下雪；q：马路结冰；r：汽车开得快；s：马路塞车。前提：pq，qr，rs，s结论：p证明pqPqrPpr推理三段论rsPps推理三段论sPp拒取式复习题21解设p：3是偶数，q：中国人的母语是汉语。命题符号化。设p：你抽

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

17、号化。3解 设p：刚会拳击，q：春会唱歌。命题符号化(pq)(pq)。而(pq)(pq)(pq)(pq)(pq)pqpq因此，刚会拳击并且春不会唱歌。 4解A的极小项对应于其真值表中的成真赋值0001，0110，1000，1001，1010，1100，1101，1111。成真赋值对应二进制数转化为十进制数就是A的极小项的下标。由此可得，A的极小项为：；。 相应的，A的极大项对应于其真值表中的成假赋值，成假赋值对应二进制数转化为十进制数就是A的极大项的下标。由此可得，A的极大项为：；。由问题得到了A的极小项和极大项，于是与A等值的主析取式和主合取式可以直接得到，分别为：；。从A的主析取式出发，进

18、展等值演算化简，可得析取式的最简形式：(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(qrs)(pqr)(pqrs)(pqr)(pr)(pqrs)(qrs)(pqrs)(pr)(qrs)(qrs)(pqrs)(pr)(qrs)(qrs)(pqs) 5 证明 6解公式的真值表如表2-27所示：表2-27p0011111011011110011001100010 从真值表可见，公式所在列的填入值有1也有0，故仅为可满足式。(pq)(qp)(pq)(qp)(2,3)为其主合取式，可见公式仅为可满足式。公式真值表如表2-28所示：表2-28

19、pqr0000100111010110111110011101111101111111p(pqr)ppqr1(0,1,2,3,4,5,6,7) 从真值表可见，公式所在的列的填入值均为1，等值演算，以与求出的主析取式均说明公式是重言式。A=(pq)(qr)(pr)真值表见习题2.2第4(4)题。(pq)(qr)(pr)(pq)(qr)(pr)(pq)(qr)pr1. 从真值表可见，公式所在的列的填入值均为1，由等值演算，以与求出的主析取式均说明公式是重言式。7证明p P附加前提引入p(qr) PqrT假言推理q P附加前提引入q(rs) PrsT假言推理qsT假言三段论p(qs)TCP证明wPu

20、wPuT拒取式suPsT析取三段论rsPrT析取三段论(pq)rP(pq)T拒取式pq) T德摩根律证明p P附加前提引入pqrPqrT假言推理qpPqT拒取式rT析取三段论srPsT拒取式psTCP8解prPpT化简pqPqT假言推理(qs) PqsT德摩根律qT化简qqT合取由得到矛盾，可见pq，(qs)，pr不能同时成立。9解 设p：小王曾经到过受害人的房间，q：小王11点以前离开，r：小王犯了谋杀罪，s：看门人看到小王。符号化：(pq)r)p(qs)s)r。形式构造推理证明前提：(pq)r，p，qs，s结论：r证明sPqsPqT拒取式pPpqT合取(pq)rPT假言推理真值表技术：真值

21、表如表2-30所示，设A=(pq)r)p(qs)s)。表2-29pqrsqspq(pq)rqsA0000110110000110011000101101110011100111010001010001010001100110010101011100011110001110101001101010101011111110111011111100010100110100011011100101011111000111由真值表可以看出：(pq)r)p(qs)s)r，所以，(pq)r)p(qs)s)r成立。等值演算方法(pq)r)p(qs)s)r(pq)r)p(qs)s)r(pq)r)p(qs)r(p

22、q)r)p(qs)r(pqr)(pqs)r1。由此可以说明(pq)r)p(qs)s)r为重言式，即(pq)r)p(qs)s)r成立。 10解 逻辑学家手指A门问旁边的一名强盗A说：“这扇门是生门，他指强盗B将回答是，他的回答对吗？设：强盗A回答“对；：强盗B回答“对；：这扇门A是生门。因为，两个强盗一个总说真话，而另一个强盗一个总说假话，因此该问题符号化为：(pq)r。(pq)r(pq)(pq)r(pqr)(pqr)逻辑学家的提问可知，r和q都为真，由公式可以看出这时p为真，即p为假。所以，当被问强盗A回答“否，如此逻辑学家开启所指的门从容离去。当被问强盗A回答“对，如此逻辑学家开启另一扇门从容离去。