离散数学课后答案精编版

第一章命题演算基础1.1判断下列语句是否为命题，若是请翻译为符号公式；若不是说明由。（1）请给我一支笔！（2）火星上有生物。（3）8=+YX（4）只有努力工作，方能把事情做好。（5）如果嫦娥是虚构的，而圣诞老人也是虚构的，那么许多孩子受骗了。解（1）不为命题，因为它不是陈述句。（2）是命题，用命题变元表示该命题。P（3）不为命题，虽为陈述句，但不能判断其真假性。（4）是命题。设表示努力工作，表示把事情做好，则原句翻译为命题公式PQ。PQ→（5）是命题。设表示嫦娥是虚构的，表示圣诞老人也是虚构的，表示许多孩子PQR受骗了，则原句翻译为。RQP→∧)(1.2试判定下列公式的永真性和可满足性。（1）))(()(RQPQP¬→¬∧¬→↔解当时，TP=原式=))(()(RQTQT¬→¬∧¬→↔=))((RQFQ¬→¬∧→=FQ→=Q¬当=时，上式=；当时，上式=，因此公式存在成真解释QTFFQ=T，存在成假解释，故公式可满足，但非永真。),,(),,(×=FTRQP),,(),,(×=TTRQP（2）))(()(PRQQP¬∨¬↔∧→¬解当时TP=   2原式=))(()(TRQQT¬∨¬↔∧→¬=))((FRQQ∨¬↔∧¬=)(RQQ¬↔∧¬当=时QT上式=)(RTT¬↔∧¬=RF¬∧=F当=时QF上式=)(RFF¬↔∧¬=RT¬¬∧=R¬¬=R当时，上式=，因此公式存在成真解释，存在成假解释TR=T),,(),,(TFTRQP=，故公式可满足，但非永真。),,(),,(×=TTRQP（3）))(()(PRQQP↔¬→→∧¬¬解当时TP=原式=))(()(TRQQT↔¬→→∧¬¬=)()(RQQT¬→→∧=)(RQQ¬→→当时TQ=上式=)(RTT¬→→=R¬当时，上式=，当时，上式=，因此，公式存在成真解释TR=FFR=T，存在成假解释，故公式可满足，但非永真。),,(),,(FTTRQP=),,(),,(TTTRQP=（4）))(()(PRQQP¬↔∧→→¬¬解   3当时TP=原式=))(()(TRQQT¬↔∧→→¬¬=))(()(FRQQT↔∧→→=)(RQQ∧¬→=)(RQQ¬∨¬→当时TQ=上式=)(RTT¬∨¬→=RF¬∨=R¬当时，上式=，当时，上式=，因此，公式存在成真解释TR=FFR=T，存在成假解释，故公式可满足，但非永真。),,(),,(FTTRQP=),,(),,(TTTRQP=1.3试求下列公式的成真解释和成假解释（1）)())((RQRQP∨↔→→¬解当时TQ=原式=)())((RTRTP∨↔→→¬=TRT↔→¬)(=R¬当时，上式=，当时，上式=。TR=FFR=T当时FQ=原式=)())((RFRFP∨↔→→¬=RRP↔→¬¬)(当时TR=上式=TTP↔→¬¬)(=TT↔¬=F当时FR=上式=FFP↔→¬¬)(   4=FP↔¬=P当时，上式=，当时，上式=，TP=TFP=F因此，公式的成真解释为；成假解释为),,(),,,(),,(FTFFTRQP×=。),,(),,,(),,,(),,(TFTTFFFRQP××=（2）))(()(PRQQP∨↔∧→¬解当时TP=原式=))(()(TRQQT∨↔∧→¬=TQT∧→¬)(=TQ∧¬=Q¬当时，上式=；当时，上式=。TQ=FFQ=T当时FP=原式=))(()(FRQQF∨↔∧→¬=)(RQT↔∧¬=)(RQF↔∧=F因此，公式的成真解释为；成假解释为),,(),,(×=FTRQP。),,(),,,(),,(×××=FTTRQP（3）))(()(PRQQP¬↔→→∧¬¬解当时TP=原式=))(()(TRQQT¬↔→→∧¬¬=))((FRQQ↔→→=)(RQQ→¬→当时TQ=   5上式=)(RTT→¬→=)(RT→¬=R¬当时，上式=；当时，上式=。TR=FFR=T当时FQ=上式=)(RFF→¬→=T当时FP=原式=))(()(FRQQF¬↔→→∧¬¬=))(()(TRQQF↔→→∧=)(RQF→→=T因此，公式的成真解释为；成假解释为),,(),,,(),,,(),,(×××=FFTFTTRQP。),,(),,(TTTRQP=（4）))(()(PRQQP∧¬∨∧¬→¬¬解当时TP=原式=))(()(TRQQT∧¬∨∧¬→¬¬=)()(RQQT¬∨∧¬→=)(RQQ¬∨∧¬当时TQ=上式=)(RTT¬∨∧¬=TF∧=F当时FQ=上式=)(RFF¬∨∧¬=RT¬∧   6=R¬当时，上式=；当时，上式=。TR=FFR=T当时FP=原式=))(()(FRQQF∧¬∨∧¬→¬¬=)()(FQQF∨∧¬→=)(FQT∨∧=Q当时，上式=；当时，上式=。TQ=TFQ=F因此，公式的成真解释为；成假解释为),,(),,,(),,(×=TFFFTRQP。),,(),,,(),,,(),,(××=FFTFTTTRQP1.4试写出下列公式的对偶式和内否式（1）))(()(PRQQP∧¬∨→∧¬（2）))(()(PRQQP¬∧∨∧¬→（3）))(()(PRQQP¬∨¬↔∧→¬（4）))(()(PRQQP¬∨¬→∨→¬解（1）内否式为))(()(PRQQP¬∧∨¬→¬∧消去“”得式子→))(()(PRQQP∧¬∨∨∧¬¬对偶式=))(()(PRQQP∨¬∧∧∨¬¬（2）内否式为))(()(PRQQP∧¬∨¬∧→¬消去“”得式子→))(()(PRQQP¬∧∨∧¬∨¬对偶式为))(()(PRQQP¬∨∧∨¬∧¬（3）内否式为))(()(PRQQP∨↔¬∧¬→¬¬消去和得式子→↔)))()((()(PRQRQQP¬∨∨∧¬∨¬∧∨¬¬对偶式为)))()((()(PRQRQQP¬∧∧∨¬∧¬∨∧¬¬   7（4）内否式为))(()(PRQQP∨→¬∨¬→消去“”得式子→))(()(PRQQP¬∨¬∨¬∨∨对偶式为))(()(PRQQP¬∧¬∧¬∧∧1.5试证明联结词集合{}是完备的。→¬,证明因为，QPQP→¬=∨)(QPQP¬→¬=∧所以，联结词集合可以表示集合。{}→¬,{}∨∧¬,,又因为，联结词集合是完备的，即可以表示任何一个命题演算公式，{}∨∧¬,,{}∨∧¬,,所以可以表示任何一个命题演算公式，故联结词集合是完备的。{}→¬,{}→¬,1.6试证明联结词集合不是完备的。{}{}→∧,证明设集合是完备的，则由联结词集合的完备性定义知{}∧。当全取为真时，上式左边=，右边⋯⋯∧∧∧==¬RQPRQPfP),,,(⋯,,,RQPF=，矛盾。T因此不是完备的。{}∧设集合是完备的，则由联结词集合的完备性定义知，其中{}→),,,(⋯RQPfP=¬表示“”。当全取为真时，上式左边=，右边=，矛盾。f→⋯,,,RQPFT因此不是完备的。{}→1.7试求下列公式的析取范式和合取范式（1）)()(QPQP¬↔→∨¬解原式=))()(()(QPQPQP¬¬∧¬∨¬∧∨∨¬¬=)()()(QPQPQP∧¬∨¬∧∨¬∧=（析取范式）)()(QPQP∧¬∨¬∧   8=))(())((QQPPQP∨¬∧∧¬∨¬∧=)()()()(QQQPQPPP∨¬∧∨∧¬∨¬∧¬∨=（合取范式）)()(QPQP∨∧¬∨¬（2）))(())((PQRRQP→→→¬→→解原式=))(())((PQRRQP∨¬∨¬∨¬∨¬∨¬¬=)()(RQPRQP¬∨¬∨∨∧∧=)()()(RQPRRQPQRQPP¬∨¬∨∨∧¬∨¬∨∨∧¬∨¬∨∨=（合取范式和析取范式）RQP¬∨¬∨（3）))(()(PRQQP¬∨¬→∧→¬解原式=))(()(PRQQP¬∨¬∨¬∧∨¬¬=（合取范式）)(RQPQP¬∨¬∨¬∧¬∧=)()(RQPQP¬∨¬∨¬∧¬∧=))(())(())((RQPQQPPQP¬∧¬∧∨¬∧¬∧∨¬∧¬∧=（析取范式）)()(RQPQP¬∧¬∧∨¬∧（4）))(()(RQPQP¬→¬∧¬→↔解原式=))(()(RQPQP¬∨¬¬∧¬∨↔¬=)()(RQPQP∧∧¬∨↔¬=（析取范式）)()()(RQPQPQP∧∧¬∨¬∧∨∧¬=)())()((RQPQPQP∧∧¬∨¬∧∨∧¬=)()))(())((RQPQQPPQP∧∧¬∨¬∨∧¬∧∨∧¬=)())()()()((RQPQQQPQPPP∧∧¬∨¬∨∧¬∨¬∧∨∧∨¬ 9=)())()((RQPQPQP∧∧¬∨¬∨¬∧∨=))()(())()((RQPQPRQPQP∧∧¬∨¬∨¬∧∧∧¬∨∨=∧¬∨¬∨¬∧∨∨∧∨∨∧¬∨∨)()()()(PQPRQPQQPPQP)()(RQPQQP∨¬∨¬∧∨¬∨¬=)()()()()(RQPQPQPRQPQP∨¬∨¬∨¬∨¬∧¬∨¬∧∨∨∧∨（合取范式）1.8试求下列公式的主析取范式和主合取范式（1）))(()(RQPRP∧¬↔¬→→¬解原式=)))(())((()(RQPRQPRP∧¬¬∧∨∧¬∧¬∨∨¬¬¬=))(()()(RQPRQPRP¬∨∧∨∧¬∧¬∨¬∧¬=)()()()(RPQPRQPRP¬∧∨∧∨∧¬∧¬∨¬∧¬=))()(()())()((RRQPRQPQQRP¬∨∧∧∨∧¬∧¬∨¬∨∧¬∧¬))()((QQRP¬∨∧¬∧∨=)()()()(RQPRQPRQPRQP∧∧∨∧¬∧¬∨¬∧¬∧¬∨¬∧∧¬)()()(RQPRQPRQP¬∧¬∧∨¬∧∧∨¬∧∧∨=)()()()(RQPRQPRQPRQP∧∧∨∧¬∧¬∨¬∧¬∧¬∨¬∧∧¬)()(RQPRQP¬∧¬∧∨¬∧∧∨=∑)7,6,4,2,1,0(=∏)5,3(=)()(RQPRQP¬∨∨¬∧¬∨¬∨（2）))(()(PRQQP¬↔→→∧¬¬解原式=))(()(PRQQP¬↔∨¬∨∧¬¬¬   10=))(())(()(PRQPRQQP∧∨¬¬∨¬∧∨¬∨¬∨¬=)()()()(RQPRPQPQP¬∧∧∨∧¬∨¬∧¬∨¬∨¬=∨¬∨∧¬∨∧¬∨¬∨∧¬∨∧¬))()(())()((RRPPQRRQQP)())()(())()((RQPQQRPRRQP¬∧∧∨¬∨∧∧¬∨¬∨∧¬∧¬=)()()()(RQPRQPRQPRQP¬∧¬∧¬∨∧¬∧¬∨¬∧∧¬∨∧∧¬∨¬∧¬∧¬∨∧¬∧¬∨¬∧¬∧∨∧¬∧∨)()()()(RQPRQPRQPRQP∨∧¬∧¬∨∧∧¬∨¬∧¬∧¬∨∧¬∧¬)()()()(RQPRQPRQPRQP)(RQP¬∧∧=)()()()(RQPRQPRQPRQP¬∧¬∧¬∨∧¬∧¬∨¬∧∧¬∨∧∧¬)()()(RQPRQPRQP¬∧∧∨¬∧¬∧∨∧¬∧∨=∑)6,5,4,3,2,1,0(=∏)7(=RQP¬∨¬∨¬（3）RQP∨¬→)(解原式=RQP∨¬∨¬=∏)6(=∑)7,5,4,3,2,1,0(=)()()()(RQPRQPRQPRQP∨∨¬∨¬∨∨¬∨∨¬∧¬∨¬∧¬∧¬)()()(RQPRQPRQP∧∧∨∧¬∧∨¬∧¬∧∨（4）))((PQPP→∧→解原式=))((PQPP∨¬∧∨¬   11=)()(PQPPP∨¬∨¬∧∨¬=TT∨=T=∏Φ)(=∑)3,2,1,0(=)()()()(QPQPQPQP∧∨¬∧∨∧¬∨¬∧¬1.9用把公式化为主范式的方法判断下列各题中两式是否等价（1）)()(),()(PQQPQPQP→∧∧¬∧→→解（1）)()(QPQP∧→→=)()(QPQP∧∨∨¬¬=)()(QPQP∧∨¬∧=∑)3,2()()(PQQP→∧∧¬=)()(PQQP∨¬∧∧¬=)()(PQPQQP∧∧¬∨¬∧∧¬=FF∨=F=∑Φ)(由此可见两公式的主析取范式不相等，因此，两公式不等价。（2）RQPRQRP→∨→∧→)(),()(解)()(RQRP→∧→=)()(RQRP∨¬∧∨¬=))()(())()((PPRQQQRP¬∧∨∨¬∧¬∧∨∨¬=)()()()(RQPRQPRQPRQP∨¬∨¬∧∨¬∨∧∨¬∨¬∧∨∨¬  12=)()()(RQPRQPRQP∨¬∨¬∧∨∨¬∧∨¬∨=∏)6,4,2(RQP→∨)(=RQP∨∨¬)(=RQP∨¬∧¬)(=)()(RQRP∨¬∧∨¬=))()(())()((PPRQQ