离散数学课后习题答案-(邱学绍)

1第一章命题逻辑习题1.11．解⑴不是陈述句，所以不是命题。⑵x取值不确定，所以不是命题。⑶问句，不是陈述句，所以不是命题。⑷惊叹句，不是陈述句，所以不是命题。⑸是命题，真值由具体情况确定。⑹是命题，真值由具体情况确定。⑺是真命题。⑻是悖论，所以不是命题。⑼是假命题。2．解⑴是复合命题。设p：他们明天去百货公司；q：他们后天去百货公司。命题符号化为qp。⑵是疑问句，所以不是命题。⑶是悖论，所以不是命题。⑷是原子命题。⑸是复合命题。设p：王海在学习；q：李春在学习。命题符号化为pq。⑹是复合命题。设p：你努力学习；q：你一定能取得优异成绩。pq。⑺不是命题。⑻不是命题⑼。是复合命题。设p：王海是女孩子。命题符号化为：p。3．解⑴如果李春迟到了，那么他错过考试。⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。⑶李春错过考试当且仅当他迟到了。⑷如果李春迟到了并且错过了考试，那么他没有通过考试。4．解⑴p(qr)。⑵pq。⑶qp。⑷qp。习题1.21．解⑴是1层公式。⑵不是公式。⑶一层：pq，p二层：pq所以，)()(qpqp是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-1pqqpA0000011110101111⑵pqpqA)(是3层公式。真值表如表2-2所示：2表2-2pqqp)(qpqA00101011101000111111⑶)()(qprqpA是3层公式。真值表如表2-3所示：表2-3pqrqprqpqpA00000010010001010001101100111000011101001111010111111111⑷)()()(rqrpqpA是4层公式。真值表如表2-4所示：3．解⑴pqpA)(真值表如表2-5所示：表2-5pqpqqpA001111011000100101110001所以其成真赋值为：00，10，11；其成假赋值为01。⑵)(qprA真值表如表2-6所示：表2-6pqrqpA00001001000100101100100011010011011111113所以其成真赋值为：000，010，100，110，111；其成假赋值为001，011，101。⑶)()(qpqpA真值表如表2-7所示，所以其成真赋值为：00，11；成假赋值为：01，10，。4．解⑴设)(qppA，其真值表如表2-8所示：表2-8pqqp)(qpA00011010111001111101故)(qppA为重言式。⑵设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-10pqpqpqpA001010011111100100110010故A=(pq)(pq)为可满足式。⑷设)())()((rprqqpA，其真值表如表2-11所示：表2-11pqrqprq)()(rqqprpA00011111001111110101001101111111100010011010101111010001411111111故)())()((rprqqpA为重言式。习题1.31．解⑴真值表如表2-12所示：表2-12pqpqqpqp)(qp0011101011001010010101100010由真值表可以看出)(qp和qp所在的列相应填入值相同，故等值。⑵真值表如表2-13所示：表2-13pqqqpqp)()(qpqp001000010000101011110101由真值表可以看出p和)()(qpqp所在的列相应填入值相同，故等值。⑶真值表如表2-14所示：表2-14pqpqqpqp)()(qpqp0011111011011110010101100100由真值表可以看出p和(pq)(pq)所在的列相应填入值相同，故等值。⑷真值表如表2-15所示：pqrqrp(qr)pq(pq)r00011010011101010010101111011001101101110111000105表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)。⑸)()(rqprqprqp)(rqp)(rqp)(⑹)()()()(qrqpqrqpqrp)(qrp)(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第4（4）相同。⑵真值表如表2-16所示：表2-16pqpqpqqpA0011111011011110010011100111所以公式是重言式。⑶真值表如表2-17所示，所以公式是矛盾式。表2-17pqpqqpqpA001110001101001001010111111161100100⑷真值表如表2-18所示，所以公式是重言式。表2-18pqrqprqpA000001001001010001011001100001101001110101111111⑸真值表如表2-19所示，所以公式仅为可满足式。表2-19pqpqp)(qpA001011011101100100110100⑹真值表如表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：他将上北京大学。则命题符号化)(rqp7其否定))((rqp))((rqprqp所以语句的否定：他努力学习，但是没有上清华大学，也没有上北京大学。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为真。习题1.41．解⑴设p：明天下雨；q：后天下雨。命题符号化qp。⑵设p：明天我将去北京；q：明天我将去上海。命题符号化qp。2．解⑴pqp)())(())((pqppqp))(())((pqppqp)(pqppqp⑵)(pqp))((pqp))()((pqpqp))((pqp)(qpqp⑶rqp)())((rqp))((rqprqp3．证明因为，{,,,,}是功能完备联结词集，所以，含有{,,,,}外的其他联结词的公式均可以转换为仅含{,,,,}中的联结词的公式。又因为qpqp)()()()(pqqppqqpqp8即含有,的公式均可以转换为仅含{,,}中的联结词的公式。因此，含{,,}外其他联结词的公式均可以转换为仅含{,,}中的联结词的公式。故{,,}是功能完备联结词集。4．证明},{是极小功能完备集，因而只需证明},{中的每个联结词都可以用表示，就说明}{是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，p(pp)pp，pq(pq)(pq)(pq)(pq)。对于证明}{是极小功能完备集，可类似证明。习题1.51．解⑴)()(qpqp；⑵prprqp))()(((2．解⑴)()(srqp)()(srqpsrqp)(即为其析取范式。)()(srqpsrqp)()()(srqsrp即为其合取范式。⑵)(rqp)()(qrrqp即为其合取范式。p(qr)p((qr)(qr))(pqr)(pqr)即为其析取范式。⑶rqp)(即为其合取范式。rqp)()()(rqrp为其析取范式。⑷)(rqprqp即为其析取范式和合取范式。3．解⑴)(qpp)())((qpqqp)2,1,0()()()(qpqpqp即为其主合取范式。其主析取范式为3pq。⑵)()(qpqp1)()(qpqp。故其主析取范式为(0,1,2,3)=(pq)(pq)(pq)(pq)。⑶prqp))((prqp))((prqp))(()()(rpqp9))()(())()((qqrprrqp)()()()(rqprqprqprqp)3,1,0(即为其主合取范式。其主析取范式为(2,4,5,6,7)(pqr)(pqr)(pqr)(pqr)(pqr)。⑷)()(srqp)()(srqp)()()()(srqsrpsrqp)()()()(srqpsrqpsrqpsrqp)14,6,2(即为其主合取范式。其主析取范式为)15,13,12,11,10,9,8,7,5,4,3,1,0(。4．解⑴真值表如表2-21所示,所以其极小项是pq，极大项为pq，pq，pq。表2-21pqqp)(qp0010011