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

第二章命题逻辑习题2.11解不是述句，所以不是命题。x取值不确定，所以不是命题。问句，不是述句，所以不是命题。惊叹句，不是述句，所以不是命题。是命题，真值由具体情况确定。是命题，真值由具体情况确定。是真命题。是悖论，所以不是命题。是假命题。2解是复合命题。设p：他们明天去百货公司；q：他们后天去百货公司。命题符号化为。是疑问句，所以不是命题。是悖论，所以不是命题。是原子命题。是复合命题。设p：王海在学习；q：春在学习。命题符号化为pÙq。是复合命题。设p：你努力学习；q：你一定能取得优异成绩。p®q。不是命题。不是命题。是复合命题。设p：王海是女孩子。命题符号化为：Øp。3解如果春迟到了，那么他错过考试。要么春迟到了，要么春错过了考试，要么春通过了考试。春错过考试当且仅当他迟到了。如果春迟到了并且错过了考试，那么他没有通过考试。4解Øp®(qÚr)。p®q。q®p。q ® p。习题2.21解是1层公式。不是公式。一层：pÚq，Øp二层：Øp«q所以，是3层公式。不是公式。(p®q)ÙØ(Øq«( q®Ør)是5层公式，这是因为 一层：p®q，Øq，Ør 二层：q®Ør 三层：Øq«( q®Ør) 四层：Ø(Øq«( q®Ør)2解A=(pÚq)Ùq是2层公式。真值表如表2-1所示：表2-1pq0000011110101111是3层公式。真值表如表2-2所示：表2-2pq00101011101000111111是3层公式。真值表如表2-3所示：表2-3pqr00000010010001010001101100111000011101001111010111111111是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所示：表2-8pq00011010111001111101故为重言式。设A=(pÙq)ÙØ(pÚq)，其真值表如表2-9所示：表2-9pqpÙqpÚqØ(pÚq)A000010010100100100111100故A=(pÙq)ÙØ(pÚq)为矛盾式。设A=(p®q)«(Øp«q)，其真值表如表2-10所示：表2-10pq001010011111100100110010故A=(p®q)«(Øp«q)为可满足式。设，其真值表如表2-11所示：表2-11pqr0001111100111111010100110111111110001001101010111101000111111111故为重言式。习题2.31解真值表如表2-12所示：表2-12pq0011101011001010010101100010由真值表可以看出和所在的列相应填入值一样，故等值。真值表如表2-13所示：表2-13pq001000010000101011110101由真值表可以看出和所在的列相应填入值一样，故等值。真值表如表2-14所示：表2-14pq0011111011011110010101100100由真值表可以看出Øp和(p®q)Ù(p®Øq)所在的列相应填入值一样，故等值。真值表如表2-15所示：pqrq®rp®(q®r)pÙq(pÙq)®r00011010011101010010101111011001101101110111000101111111表2-15 由真值表可以看出p®(q®r)和(pÙq)®r所在的列相应填入值一样，故等值。2证明(pÙq)ÚØ (ØpÚq)Û (pÙq)Ú( pÙØq)ÛpÙ (qÚØq)Û p。(p®q)Ù(q®p)Û(ØpÚq)Ù(ØqÚp)Û(ØpÙØq)Ú(ØpÙ p)Ú( qÙØq)Ú(qÙ p)Û( pÙq)Ú(ØpÙØq)。由可得，Ø(p«q)ÛØ( pÙq)Ú(ØpÙØq)Û(Ø pÚØq)Ù(pÚq)Û(q®Øp)Ù(Øp®q)ÛØp«q。p®(q®r)ÛØ pÚ(ØqÚ r)ÛØ qÚ(ØpÚ r)Û q®( p ®r)。3解Ø(p®Øq)ÛØ(ØpÚØq)ÛpÙqØ(Øp®Øq)ÛØ( pÚØq)ÛØpÙqØ(p«Øq)ÛØ(p®Øq)Ù(Øq®p)ÛØ(p®Øq)ÚØ(Øq®p)Û(pÙq)Ú(ØpÙØq)Û p«q。同理可证Ø(Øp«q)Û p«q。4解与习题2.2第44一样。真值表如表2-16所示：表2-16pqØpØqp®qØq ®ØpA0011111011011110010011100111所以公式是重言式。真值表如表2-17所示，所以公式是矛盾式。表2-170011100011010010010101100100真值表如表2-18所示，所以公式是重言式。表2-18000001001001010001011001100001101001110101111111真值表如表2-19所示，所以公式仅为可满足式。表2-19001011011101100100110100真值表如表2-20所示，所以公式是重言式。表2-20pqrp®qr®qpÙr(p®q)Ù(r®q)(pÙr)®qA0001101110011000110101101110111101111000100111010010011101101111111111115解设p：他努力学习；q：他会通过考试。如此命题符号化p®q。其否认Ø(p®q)Û pÙØq。 所以语句的否认：他学习很努力但没有通过考试。设p：水温暖；q：他游泳。如此命题符号化p«q。其否认Ø(p«q)Û p«Øq。 所以语句的否认：当且仅当水不温暖时他游泳。设p：天冷；q：他穿外套；r：他穿衬衫。如此命题符号化p®(qÙØr)其否认Ø( p®(qÙØr)ÛØ(ØpÚ(qÙØr)Û pÙØ( qÙØr)Û pÙ(ØqÚ r) 所以语句的否认：天冷并且他不穿外套或者穿衬衫。设p：他学习；q：他将上清华大学；r：他将上大学。如此命题符号化其否认所以语句的否认：他努力学习，但是没有上清华大学，也没有上大学。6解 设p：三说真话；q：四说真话；r：王五说真话。如此：p«Øq, q«Ør(ÛØq«r), r«(ØpÙØq)为真,因此p«(ØpÙØq)Û(pÙØpÙØq)Ú(ØpÙ(pÚq)ÛØpÙq为真。因此，p为假，q为真，所以r为假。故三说谎，四说真话，王五说谎。7解 设p：甲得冠军；q：乙得亚军；r：丙得亚军；s：丁得亚军。前提：p®(qÚr)，q®Øp，s®Ør，p结论：Øs证明p®(qÚr)为真，其前件p为真，所以qÚr为真，又q®Øp为真，其后件Øp为假，所以要求q为假，所以r为真。又s®Ør为真，其后件Ør为假，所以要求s为假，故Øs为真。习题2.41解设p：明天下雨；q：后天下雨。命题符号化。设p：明天我将去；q：明天我将去。命题符号化。2解3证明 因为，是功能完备联结词集，所以，含有外的其他联结词的公式均可以转换为仅含中的联结词的公式。又因为即含有的公式均可以转换为仅含中的联结词的公式。因此，含外其他联结词的公式均可以转换为仅含中的联结词的公式。 故是功能完备联结词集。4证明是极小功能完备集，因而只需证明中的每个联结词都可以用­表示，就说明是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，ØpÛØ(pÙp)Ûp­p，pÙqÛØØ(pÙq)ÛØ(p­q)Û(p­q)­(p­q)。对于证明是极小功能完备集，可类似证明。习题2.5 1解；2解即为其析取式。即为其合取式。即为其合取式。ØpÙ(q«r)ÛØpÙ(qÙr)Ú(ØqÙØr)Û(ØpÙqÙr)Ú(ØpÙØqÙØr) 即为其析取式。即为其合取式。为其析取式。即为其析取式和合取式。3解即为其主合取式。其主析取式为å3ÛpÙq。故其主析取式为å(0,1,2,3)=(ØpÙØq)Ú(ØpÙq)Ú(pÙØq)Ú(pÙq)。即为其主合取式。其主析取式为å(2,4,5,6,7)Û (ØpÙqÙØr)Ú(pÙØqÙØr)Ú(pÙØqÙr)Ú(pÙqÙØr)Ú(pÙqÙr)。即为其主合取式。其主析取式为。4解真值表如表2-21所示, 所以其极小项是pÙØq，极大项为pÚq，pÚØq，ØpÚØq。表2-21pq0010011010011110其主析取式是：pÙØq，主合取式为：(pÚq)Ù( pÚØq)Ù(ØpÚØq)。真值表如表2-222所示, 所以其极小项是ØpÙq, pÙØq, pÙq, 极大项为pÚq。表2-22pq000100011101101011111101其主析取式是：(ØpÙq)Ú(pÙØq)Ú(pÙq)，主合取式为：pÚq。真值表如表2-23所示，所以其极小项是ØpÙqÙr,pÙØqÙØr, pÙØqÙr, pÙqÙØr,pÙqÙr,表2-23pqr000100001100010100011111100001101001110001111001极大项为pÚqÚr，pÚqÚØr，pÚØqÚr。其主析取式是：(ØpÙqÙr)Ú(pÙØqÙØr)Ú(pÙØqÙr)Ú(pÙqÙØr)Ú(pÙqÙr)，主合取式为：(pÚqÚr)Ù(pÚqÚØr)Ù(pÚØqÚr) 。真值表如表2-24所示,所以其极小项为ØpÙØqÙr,ØpÙqÙr,pÙØqÙØr,pÙØqÙr,pÙqÙr,而极大项分为pÚqÚr，pÚØqÚr，ØpÚØqÚr.主合取式为(pÚqÚr)Ù(pÚØqÚr)Ù(ØpÚØqÚr),主析取式为(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙØr,)Ú(pÙØqÙr)Ú(pÙqÙr)。表2-24pqr00010001110101001111100011010111010111115解(ØpÚq)Ù(Ø(ØpÙØq)Û(ØpÚq)Ù(pÚq)Û qÛ (ØpÙq)Ú(pÙq)， 故为可满足式。 故为重言式。Ø(pÚ(qÙr)«(pÚq)Ù(pÚr)ÛØ(pÚ(qÙr)«(pÚ(qÙr)Û(pÚ(qÙr)Ú(pÚ(qÙr)ÙØ(pÚ(qÙr)ÚØ(pÚ(qÙr)Û(pÚ(qÙr)ÙØ(pÚ(qÙr)Û(pÚ(qÙr)ÙØpÙØ(qÙr)Û(ØpÙqÙr)Ù(ØqÚØr)Û0。 故为矛盾式。 故仅为可满足式。6证明右边已经是主合取式。而左边主合取式已是ØpÙØq，因此，Ø(pÚ q)ÛØpÙØq，证毕。右边(pÚ q)Ù(pÚØq)已经是主合取式。pÛpÚ(qÙØq)Û (pÚ q)Ù(pÚØq)。因此，。左边p®(q®r)ÛØpÚ(ØqÚr)ÛØpÚØqÚr，而右边ÛØ(pÙq)ÚrÛØpÚØqÚr，因此，。习题2.61解 设p：这里有演出；q：这里通行是困难的；r：他们按照指定时间到达。前提：p®q, r®Øq,r结论：Øp证明r Pr®Øq PØq T假言推理p®q P ØpT拒取式2证明s Ps®pPpT假言推理p®qPqT假言推理证明rP附加前提引入r®qPq T假言推理p®ØqPØp T拒取式Øp®sPs T假言推理r®s TCP证明pP否认结论引入p®qPqT假言推理q®rPrT假言推理ØrÙsPØrT化简rÙØrT合取证明pP附加前提引入ØpÚqPq析取三段论r®ØqPØr拒取式p®ØrCP证明pP附加前提引入p®(q®r)Pq®rT假言推理qP附加前提引入rT假言推理(rÙs)®tPØrÚØsÚtT蕴涵等价式ØsÚtT析取三段论Øh®(sÙØt)PØsÚt®hT假言易位hT假言推理q®hTCP13. p®(q®h)TCP3解 推理不正确。在到化简时，只能对整个公式进展而不是子公式。4解 正确。P，P附加前提引入；T析取三段论；P；T假言推理；P；T假言推理；TCP。5解 设p：三努力工作，q：四高兴，r：王五高兴，s：六高兴 前提：p®(qÚr)，q®Øp，s®Ør 结论：p®Øs 证明：pP附加前提引入p®(qÚr)PqÚrT假言推理q®ØpPØqT拒取式rT析取三段论s®ØrPØsT拒取式p®ØsTCP6解设：p：天下雪；q：马路结冰；r：汽车开得快；s：马路塞车。前提：p®q，q®Ør，Ør®s，Øs结论：Øp证明p®qPq®ØrPp®Ør推理三段论Ør®sPp®s推理三段论ØsPØp拒取式复习题21解设p：3是偶数，q：中国人的母语是汉语。命题符号化。设p：你抽烟，q：你很容易得病。命题符号化。 设p：今天是星期一，q：明天才是星期二。命题符号化。 设p：春这个学期离散数学考了100分。q：春这个学期数据结构考了100分。命题符号化。设p：下雪路滑，q：他迟到了。命题符号化。 设p：经一事，q：长一智。命题符号化。 设p：一朝被蛇咬，q：十年怕井绳。命题符号化。 设p：以物喜，q：以己悲。命题符号化。 2. 解 命题中的“或是不可兼或，因此，可以直接用“符号化；根据联结词的性质与其之间的转换关系，可知命题“春生于1979年或生于1980年的本意是“春生于1979年但不能生于1980年或生于1980年但不能生于1979年，因此，也可以转化为“对其进展符号化。3解 设p：刚会拳击，q：春会唱歌。命题符号化(ØpÚØq)ÙØ(p®q)。而(ØpÚØq)ÙØ(p®q)Û(ØpÚØq)ÙØ(ØpÚq)Û(ØpÚØq)ÙpÙØqÛpÙØq因此，刚会拳击并且春不会唱歌。 4解A的极小项对应于其真值表中的成真赋值0001，0110，1000，1001，1010，1100，1101，1111。成真赋值对应二进制数转化为十进制数就是A的极小项的下标。由此可得，A的极小项为：；。 相应的，A的极大项对应于其真值表中的成假赋值，成假赋值对应二进制数转化为十进制数就是A的极大项的下标。由此可得，A的极大项为：；。由问题得到了A的极小项和极大项，于是与A等值的主析取式和主合取式可以直接得到，分别为：；。从A的主析取式出发，进展等值演算化简，可得析取式的最简形式：(ØpÙØqÙØrÙs)Ú(ØpÙqÙrÙs)Ú(pÙØqÙØrÙØs)Ú(pÙØqÙØrÙs)Ú(pÙØqÙrÙØs)Ú(pÙqÙØrÙØs)Ú(pÙqÙØrÙs)Ú(pÙqÙrÙs)Û(ØpÙØqÙØrÙs)Ú(qÙrÙs)Ú(pÙØqÙØr)Ú(pÙØqÙrÙØs)Ú(pÙqÙØr)Û(pÙØr)Ú(ØpÙØqÙØrÙs)Ú(qÙrÙs)Ú(pÙØqÙrÙØs)Û(pÙØr)Ú(ØqÙØrÙs)Ú(qÙrÙs)Ú(pÙØqÙrÙØs)Û(pÙØr)Ú(ØqÙØrÙs)Ú(qÙrÙs)Ú(pÙØqÙØs) 5 证明 6解公式的真值表如表2-27所示：表2-27p0011111011011110011001100010 从真值表可见，公式所在列的填入值有1也有0，故仅为可满足式。(p®Øq)Ù(Øq®Øp)Û(ØpÚØq)Ù(qÚØp)ÛÕ(2,3)为其主合取式，可见公式仅为可满足式。公式真值表如表2-28所示：表2-28pqr0000100111010110111110011101111101111111p®(pÚqÚr)ÛØpÚpÚqÚrÛ1Ûå(0,1,2,3,4,5,6,7) 从真值表可见，公式所在的列的填入值均为1，等值演算，以与求出的主析取式均说明公式是重言式。A=(p®q)Ù(q®r)®(p®r)真值表见习题2.2第4(4)题。(p®q)Ù(q®r)®(p®r)ÛØ(ØpÚq)Ù(ØqÚr)Ú(ØpÚr)Û(pÙØq)Ú(qÙØr)ÚØpÚrÛ1. 从真值表可见，公式所在的列的填入值均为1，由等值演算，以与求出的主析取式均说明公式是重言式。7证明p P附加前提引入p®(q®r) Pq®rT假言推理q P附加前提引入q®(r®s) Pr®sT假言推理q®sT假言三段论p®(q®s)TCP证明ØwPu®wPØuT拒取式ØsÚuPØsT析取三段论ØrÚsPØrT析取三段论(pÚq)®rPØ(pÚq)T拒取式ØpÙØq) T德×摩根律证明p P附加前提引入p®qÚrPqÚrT假言推理q®ØpPØqT拒取式rT析取三段论s®ØrPØsT拒取式p®ØsTCP8解pÙrPpT化简p®qPqT假言推理Ø(qÚs) PØqÙØsT德×摩根律ØqT化简ØqÙqT合取由得到矛盾，可见p®q，Ø(qÚs)，pÙr不能同时成立。9解 设p：小王曾经到过受害人的房间，q：小王11点以前离开，r：小王犯了谋杀罪，s：看门人看到小王。符号化：(pÙØq)®r)ÙpÙ(q®s)ÙØs)Þr。形式构造推理证明前提：(pÙØq)®r，p，q®s，Øs结论：r证明ØsPq®sPØqT拒取式pPpÙØqT合取(pÙØq)®rPT假言推理真值表技术：真值表如表2-30所示，设A=(pÙØq)®r)ÙpÙ(q®s)ÙØs)。表2-29pqrsØqØspÙØq(pÙØq)®rq®sA0000110110000110011000101101110011100111010001010001010001100110010101011100011110001110101001101010101011111110111011111100010100110100011011100101011111000111由真值表可以看出：(pÙØq)®r)ÙpÙ(q®s)ÙØs)Ûr，所以，(pÙØq)®r)ÙpÙ(q®s)ÙØs)Þr成立。等值演算方法(pÙØq)®r)ÙpÙ(q®s)ÙØs)®rÛØ(Ø(pÙØq)Úr)ÙpÙ(ØqÚs)ÙØs)ÚrÛØ(Ø(pÙØq)Úr)ÙpÙ(ØqÙØs)ÚrÛ(Ø(Ø(pÙØq)Úr)ÚØpÚØ(ØqÙØs)ÚrÛ(pÙØqÙØr)ÚØ(pÙØqÙØs)ÚrÛ1。由此可以说明(pÙØq)®r)ÙpÙ(q®s)ÙØs)®r为重言式，即(pÙØq)®r)ÙpÙ(q®s)ÙØs)Þr成立。 10解 逻辑学家手指A门问旁边的一名强盗A说：“这扇门是生门，他指强盗B将回答是，他的回答对吗？设：强盗A回答“对；：强盗B回答“对；：这扇门A是生门。因为，两个强盗一个总说真话，而另一个强盗一个总说假话，因此该问题符号化为：(Øp«q)Ùr。(Øp«q)ÙrÛ(ØpÙq)Ú(pÙØq)ÙrÛ(ØpÙqÙr)Ú(pÙØqÙr)逻辑学家的提问可知，r和q都为真，由公式可以看出这时Øp为真，即p为假。所以，当被问强盗A回答“否，如此逻辑学家开启所指的门从容离去。当被问强盗A回答“对，如此逻辑学家开启另一扇门从容离去。