离散数学(第2版-刘爱民)习题解答(1)(1)

附录2习题答案习题一答案1.1下列各语句中哪些是命题?1)不是；2)是；3)不是；4)不是；5)不是；6)是；7)是；8)不是9)不是；10)是；11)不是；12)是。1.2将下列命题符号化。1)p∧q,p:太阳明亮,q:湿度高；2)qp,p:明天你看到我，q:我要去深圳。3)pq,p:我出校，q:我去图书城；4)qp,p:你去,q:我去；5)5.1)p∧q；5.2)p∧q;5.3)p∧q；5.4)p∧q；6)6.1)p∨q6.2)(pq)6.3)p∧¬q6.4)¬(p∧r)6.5)(p∧q)r6.6)¬(r(p∧q))7)p:蓝色和黄色可以调配成绿色；8)(pq),p:李兰现在在宿舍,q:李兰在图书馆里；9)¬p¬q,p:一个人经一事，q:一个人长一智；10)(p∧¬q)(rs),p:晚上小王做完了做业,q:晚上小王没有其他事情，r:晚上小王看电视,s:晚上小王看电影。11)(rs),r:小飞在睡觉,s:小飞在游泳；12)¬p∧¬q∧r,p:这个星期天我看电视，q:这个星期天我外出，r:这个星期天我在睡觉。13)pq,p:卫星上天了，q:国家强大了；14)pq,p:今天没有课，q:我呆在图书馆里；15)pq,p:我去图书城，q:我有时间；16)¬p¬q,p:人们辛劳，p:人们收获1.31)小李家住北大西门外,他现在坐在公共汽车里看书，没有考虑问题；2)小李在思考问题,他没有乘坐公共汽车，也没有看书；3)小李只要乘坐公共汽车，他就看书或考虑问题；4)小李乘坐公共汽车，要么看书不考虑问题，要么考虑问题不看书，5)同4);6)如果小李家住北大西门外,则他现在没有乘坐公共汽车，没有看书，也没有考虑问题。1.41)是2)不是，因为∨联结词后没有字母3)是4)是5)不是，因为pq之间缺联结词6)不是，因为∨∧不能构成公式7)是*1.51)q是0层公式，q是1层公式，(p∨q)是2层公式，原公式是3层公式;2)p是0层公式，p是1层公式，(pq)是2层公式，(qr)是1层公式，((pq)∧(qr))是3层公式，(pr)是1层公式，原公式是4层公式；3)r，s是0层公式，r∧s是1层公式，(qr∧s)是2层公式，(p∨(qr∧s))是3层公式，(p∨(qr∧s))是4层公式，(pq)∧s是2层公式，原公式是5层公式。4)p，q是0层公式，(p∨q)是1层公式，(p∨q)r是2层公式，(rs)是1层公式，原公式是3层公式.1.6pqr∧s，qpq1)((qr∧s)∨(pq))r;2)(((qr∧s)(pq))∧((pq)r))((qr∧s)r)；3)((qr∧s)∨((pq)r∧s))((qr∧s)(pq))∧s；4)((qr∧s)∨(pq))r(rs).1.7A∨B,A的成真赋值或B的成真赋值，故为000,011,100,110,111,101;A∨B,AB:A的成真赋值或B的成真赋值，001,010,101,000,110;A∧B:同时是A和B的成真赋值，000,110；A∧B:同时是A和B的成真赋值，001,010；AB:同时是A和B的成真赋值或成假赋值，000,110,001,010；1.81)(p∧q)q2)(pq)ppqp∧q(p∧q)qpqpq(pq)p00010010010101101001100011111111这是重言式。这是可满足式。3)(pp)p4)p(p∨q)pqppp(pp)ppqp∨qp(p∨q)001110001011110111100011011110011111这是重言式。这是重言式。5)(pq)∧q6)(qp)(pq)pq(pq)∧qpq(qp)(pq)000100011111010100101111101001010010110101101011②①③①②①③①这是矛盾式这是重言式。7)(pr)((pr)((p∨q)r)))8)(pq)∧p∧rpqr(pr)((pr)((p∨q)r)))pqr(pq)∧p∧r00011110100001000011111010010100010101010010010001111111101101001000101101001010101111111101101111001011011001001111111111110100①④①③①②②①③④这是可满足式这是可满足式1.9这里仅仅是无数个命题形式中的两个，读者可以另外给出F：矛盾式，用一个矛盾式与任何一个公式合取即可，即(p∧p)∧AF1=(p∧p)∧(q∨r),F2=p∧q∧r∧(q∨r)G：重言式，简单的可以是一个重言式与任何一个公式析取，(p∨p)∨A如：G1=(p∨p)∨(q∨r),G2=p∨(p∧q)∨p∨r，重言式拆分在不同的位置H：前四行可看成蕴涵式的否定，后四行与p相同，两种情况相或。所以H1=p∨((qr));p∨(r∧q)还是分成前后四行分析，如果以p作为蕴涵式的后件：Ap，后四行总成立，想法构成前件，使得前四行的第三行为0，其它行为1，正是蕴涵式qr。所以可写成H2=qrpR：只有全0的才为0，所以最简单的是用析取式，R1=p∨q∨r这个公式再与其它的确保p,q,r三个为0时一定为0的公式相析取即可；R2=p∨q∨r∨(p∧q)，p∨q∨r∨(p∧r)S：类似H的分析，前四行和后四行情况相或，S1=p∨(q∧r)如果以p作为蕴涵式的后件：Ap，后四行总成立，想法构成前件，使得前四行的第三行为0，其它行为1，正是蕴涵式qr。所以可写成S2=qrp习题二答案2.11)不能。C1时，两边总是等值；2)不能。C0时，两边总是等值；3)能。由否定之否定可得。2.21)证明下列等值式：(1)p(qr)p∨(q∨r)(2)(pq)((pq)∧(qp))p∨q∨r((p∨q)∧(q∨p))q∨p∨r(p∧q)∨(q∧p)q∨(p∨r)(p∨q)∧(p∨q))q(pr)((p∨q)∧(p∧q))(3)p(qp)p∨(q∨p)(4)(pr)∧(qr)(p∨r)∧(q∨r)p∨(p∨q)(重言式)(p∧q)∨rp∨(pq)(p∨q)∨rp(pq)(p∨q)r(5)(pq)∧(pr)(p∨q)∧(p∨r)p∨(q∧r)pq∧r2)判定命题形式类型：(1)(pq)((p∧p)∨(p∧q))(2)(q∨((p∨q)∧p))(pq)(p∧q)q∧((p∨q)∧p)((pq)∧(qp))q∧(q∧p)((p∨q)∧(q∨p))0∨(p∧q)这是矛盾式((p∧q)∨(q∧p))∨(p∧q)(p∧q)∨11这是重言式(3)((pq)∧(qp))p(4)(qp)∧(pq)((p∨q)∧(q∨p))p(q∨p)∧(p∨q)((p∧p)∨q)p(q∧q)∨pqpp这是可满足式这是可满足式(5)((p∨q)p)(6)(pq∧r)∨(r(pq))((p∨q)∨p)(p∨q∧r)∨(r∨(p∨q))((p∨p)∨q)p∨(q∧r)∨r∨p∨q1p∨r∨q0这是可满足式这是矛盾式2.3提示：对偶式是将∧与∨互换、0与1互换。但要注意括号省略问题。1)(p∨q)∨(p∨q)(p∧q)∨(p∧q)p∧(q∨q)p对偶式是：(p∧q)∧(p∧q)p2)q∨((p∨q)∧p)q∨(q∧p)q∨q∨p1对偶式是：q∧((p∧q)∨p)03)(p∧q)∨(p∨q)∧(p∨q)(p∧q)∨((p∧p)∨q)(p∧q)∨q(p∧q)∨qp∨q(p∨q)对偶式是：(p∨q)∧((p∧q)∨(p∧q))(p∧q)2.4香农定理：A(p1,p2,…,pn,0,1,,∧,∨)A(p1,p2,…,pn,1,0,,∨,∧)对偶式的定义为：A*(p1,p2,…,pn,0,1,,∧,∨)A(p1,p2,…,pn,1,0,,∨,∧)对偶式定义是重言式，其任何的替换实例仍然是重言式，以pi替换pi，所以A*(p1,p2,…,pn,0,1,,∧,∨)A(p1,p2,…,pn,0,1,,∧,∨)从而A(p1,p2,…,pn,0,1,,∧,∨)A*(p1,p2,…,pn,0,1,,∧,∨)这就是香农定理的对偶式表示式，简写成A(p1,p2,…,pn)A*(p1,p2,…,pn)。显然1)若A是重言式，则A*是矛盾式；2)若A是矛盾式，则A*是重言式；都成立。*2.5已知{,∧,∨}是全功能集。pp；p∧q(p∨q)(pq)p∨qp∨q)pq即{,∧,∨}可有{,}表示，所以{,}是全功能集。实际上pp0，可用表示，是冗余联结词，所以{,}不是极小全功能集。*2.6找出下式的等值的尽可能简单的由{,∨}和{,∧}生成的公式:1)p∨(q∧(rp))p∨¬(q∨r){¬,∨}¬(¬p∧(¬q∧¬r)){¬,∧}2)p(qp)¬p∨p{¬,∨}(重言式)¬(p∧¬p){¬,∧}3)(p∨q)∧r(p∨r)¬p∨p{¬,∨}(重言式)¬(p∧¬p){¬,∧}4)p∨(q∧rp)p∨q∨¬r{¬,∨}¬(¬p∧¬q∧r){¬,∧}5)(pq∨q)∧p∧q¬(p∨¬q){¬,∨}¬p∧q¬{¬,∧}*2.71){,}:(pq)r2){,∧}:((p∧q)∧¬r)3){,∨}:¬(p∨q)∨r4){}；((pp)(qq))(rr)5){}:((pq)r)((pq)r)2.81)(p∨q)∧((p∨q)∧r)2)(p∧q∧r)∨(q∧(p∨r))*3)(p∨q)(p∨q∨r)*4)(pq)∨(pq)2.91)p∧rq2)r∨p(pq)(p∧r)∨q(r∨p)∨((p∧q)∨(p∧q))p∨r∨q(p∧r)∨(p∧q)∨(p∧q)M5(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)主合取范式，仅含有一个极大项，∨(p∧q∧r)∨(p∧q∧r)所以是可满足式m6∨m4∨m5∨m3∨m2含有5个极小项，是可满足式3)(pq∧r)∧(pq∧r)4)p∧q∧(p∨q)(p∨q∧r)∧(p∨q∧r)(p∧q∧p)∨(p∧q∧q)(p∧q∧r)∨(p∧q∧r)0m7∨m0主析取范式，含有两个极小项主析取范式不含有任何极大项，所以是可满足式是矛盾式。2.101)(a)(p∧q)∨(p∧q∧r)(b)(p∨(q∧r))∧(q∨(p∧r)(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)(p∧q)∨(q∧r))∨(p∧q∧r)m7∨m6∨m3(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)M5∧M4∧M2∧M1∧M0∨(p∧q∧r)∨(p∧q∧r)m7∨m6∨m3M5∧M4∧M2∧M1∧M0主范式都相同，两者等值。2)(a)p(qr)(b)q(pr)p∨(q∨r)p∨(q∨r)M6M6m0∨m1∨m2∨m3∨m4∨m5∨m7m0∨m1∨m2∨m3∨m4∨m5∨m7主范式都相同，两者等值。3)(a)p∧(p∨q)(b)(p∨q)p∧