离散数学答案命题逻辑.doc

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

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

3、 0 1 02 / 181 1 1 1 pqA)(是 3 层公式。真值表如表 2-2 所示：表 2-2p q q)(qpA0 0 1 0 10 1 1 1 01 0 0 0 11 1 1 1 1 )()(qprqpA是 3 层公式。真值表如表 2-3 所示：表 2-3p q r rqpqpA0 0 0 0 0 0 10 0 1 0 0 0 10 1 0 0 0 1 10 1 1 0 0 1 11 0 0 0 0 1 11 0 1 0 0 1 11 1 0 1 0 1 11 1 1 1 1 1 1 )()()(rqpqA是 4 层公式。真值表如表 2-4 所示：3解 p真值表如表 2-5 所示：

4、表 2-5p q qqpA0 0 1 1 1 10 1 1 0 0 01 0 0 1 0 11 1 0 0 0 1所以其成真赋值为：00，10，11；其成假赋值为 01。 )(qprA真值表如表 2-6 所示：表 2-6p q r qpA0 0 0 0 10 0 1 0 00 1 0 0 10 1 1 0 01 0 0 0 13 / 181 0 1 0 01 1 0 1 11 1 1 1 1所以其成真赋值为：000，010，100，110，111；其成假赋值为 001，011，101。 )()(qpA真值表如表 2-7 所示，所以其成真赋值为：00，11；成假赋值为：01，10， 。4解 设

5、)(，其真值表如表 2-8 所示：表 2-8p q qp)(qpA0 0 0 1 10 1 0 1 11 0 0 1 11 1 1 0 1故 )(qpA为重言式。设 A=(pq)(pq)，其真值表如表 2-9 所示：表 2-9p q pq pq (pq) A0 0 0 0 1 00 1 0 1 0 01 0 0 1 0 01 1 1 1 0 0故 A=(pq)(pq)为矛盾式。设 A=(pq)(pq)，其真值表如表 2-10 所示：表 2-10p q pqqpA0 0 1 0 1 00 1 1 1 1 11 0 0 1 0 01 1 0 0 1 0故 A=(pq)(pq)为可满足式。设 )()

6、(rpr，其真值表如表 2-11 所示：表 2-11p q r q)()(rqrpA0 0 0 1 1 1 1 10 0 1 1 1 1 1 10 1 0 1 0 0 1 10 1 1 1 1 1 1 14 / 181 0 0 0 1 0 0 11 0 1 0 1 0 1 11 1 0 1 0 0 0 11 1 1 1 1 1 1 1故 )()()( rprqpA为重言式。习题 2.31解 真值表如表 2-12 所示：表 2-12p q pqqp)(qp0 0 1 1 1 0 10 1 1 0 0 1 01 0 0 1 0 1 01 1 0 0 0 1 0由真值表可以看出 )(qp和 所在的列

7、相应填入值相同，故等值。真值表如表 2-13 所示：表 2-13p q qp)()(qp0 0 1 0 0 00 1 0 0 0 01 0 1 0 1 11 1 0 1 0 1由真值表可以看出 p和 )()(qp所在的列相应填入值相同，故等值。真值表如表 2-14 所示：表 2-14p q )()(qp0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 1 01 1 0 0 1 0 0由真值表可以看出p 和(pq)(pq)所在的列相应填入值相同，故等值。真值表如表 2-15 所示：p q r qr p(qr) pq (pq)r 0 0 0 1 1 0 10 0 1 1 1

8、0 10 1 0 0 1 0 10 1 1 1 1 0 15 / 18表 2-15由真值表可以看出 p(qr)和(pq) r 所在的列相应填入值相同，故等值。2证明 (p q) (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)。 r)( rq)(qp )()()()( rprqr3解 (pq) (pq)pq(pq)( pq)pq(pq)(p q)(qp)(pq)(qp)(p

9、q) (pq) pq。同理可证(pq) pq。4解 与习题 22 第 4（4）相同。真值表如表 2-16 所示：表 2-16p q p q pq q p A 0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 0 0 1 1 1所以公式是重言式。真值表如表 2-17 所示，所以公式是矛盾式。表 2-17pqpqpqA1 0 0 1 1 0 11 0 1 1 1 0 11 1 0 0 0 1 01 1 1 1 1 1 16 / 180 0 1 1 1 0 00 1 1 0 1 0 01 0 0 1 0 1 01 1 0 0 1 0 0真值表如表 2-18 所示，

10、所以公式是重言式。表 2-18pqrqprA0 0 0 0 0 10 0 1 0 0 10 1 0 0 0 10 1 1 0 0 11 0 0 0 0 11 0 1 0 0 11 1 0 1 0 11 1 1 1 1 1真值表如表 2-19 所示，所以公式仅为可满足式。表 2-19pqpq)(qpA0 0 1 0 1 10 1 1 1 0 11 0 0 1 0 01 1 0 1 0 0真值表如表 2-20 所示，所以公式是重言式。表 2-20p q r pq rq pr (pq)(rq) (pr)q A0 0 0 1 1 0 1 1 10 0 1 1 0 0 0 1 10 1 0 1 1 0

11、1 1 10 1 1 1 1 0 1 1 11 0 0 0 1 0 0 1 11 0 1 0 0 1 0 0 11 1 0 1 1 0 1 1 11 1 1 1 1 1 1 1 15解 设 p：他努力学习；q：他会通过考试。则命题符号化 pq。其否定(pq) p q。所以语句的否定：他学习很努力但没有通过考试。设 p：水温暖；q：他游泳。则命题符号化 pq。其否定(pq) p q。所以语句的否定：当且仅当水不温暖时他游泳。设 p：天冷；q：他穿外套；r：他穿衬衫。则命题符号化 p(qr) 其否定( p( qr) (p(qr) 7 / 18 p( qr) p(q r)所以语句的否定：天冷并且他不

12、穿外套或者穿衬衫。设 p：他学习；q：他将上清华大学；r：他将上北京大学。则命题符号化 )(rqp其否定 )()(rqprqp所以语句的否定：他努力学习，但是没有上清华大学，也没有上北京大学。6解 设 p：张三说真话；q：李四说真话；r：王五说真话。则：pq, qr(q r), r(pq)为真,因此 p(pq)(ppq)(p(pq)pq 为真。因此，p 为假，q 为真，所以 r 为假。故张三说谎，李四说真话，王五说谎。7解 设 p：甲得冠军；q：乙得亚军；r：丙得亚军；s：丁得亚军。前提：p( qr)，qp，s r， p结论：s证明 p( qr)为真，其前件 p 为真，所以 qr 为真，又 q

13、p 为真，其后件p 为假，所以要求 q 为假，所以 r 为真。又 sr 为真，其后件 r 为假，所以要求 s 为假，故s 为真。习题 2.41解 设 p：明天下雨；q：后天下雨。命题符号化 p。设 p：明天我将去北京；q：明天我将去上海。命题符号化 q。2解 p)()(q(qp)(p )(q)(qp)( rqp)()(rqpr3证明 因为， ,是功能完备联结词集，所以，含有 ,外的其他联8 / 18结词的公式均可以转换为仅含 ,中的联结词的公式。又因为 qp)()()()( pqpqp 即含有 ,的公式均可以转换为仅含 ,中的联结词的公式。因此，含 ,外其他联结词的公式均可以转换为仅含 ,中的

14、联结词的公式。故 ,是功能完备联结词集。4证明 ,是极小功能完备集，因而只需证明 ,中的每个联结词都可以用 表示，就说明 是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，p(pp)pp，pq(pq)(pq)(pq)(pq)。对于证明 是极小功能完备集，可类似证明。习题 2.5 1解 )()(qp； rrqp2解 )()(s)()(srr即为其析取范式。)()(sqpsrqp)(r即为其合取范式。 )()()(r即为其合取范式。p(qr)p(qr)(qr)(pqr)(pqr) 即为其析取范式。 即为其合取范式。r)( )()(rr为其析取范式。 qpqp即为其析取范式和合取范式。3解

15、 )()()(qp2,10)(即为其主合取范式。其主析取范式为3pq。 )()(qp)()(qp。9 / 18故其主析取范式为(0,1,2,3)=(pq)( pq)(pq)(pq)。 r( r()( qrprqp)() rp3,10(即为其主合取范式。其主析取范式为(2,4,5,6,7) (pqr)(pqr) (pqr)(pqr)(pqr)。 )(ss)()()( rrr)( srqpsqpsqpsqp )14,62即为其主合取范式。其主析取范式为 )15,32,0987,53,0( 。4解 真值表如表 2-21 所示, 所以其极小项是 pq，极大项为 pq，pq， pq。表 2-21p q

16、)(0 0 1 00 1 1 01 0 0 11 1 1 0其主析取范式是：pq，主合取范式为：(pq) ( pq)(pq)。真值表如表 2-222 所示, 所以其极小项是 pq, pq, pq, 极大项为 pq。表 2-22p q p)( )()(qp0 0 0 1 0 00 1 1 1 0 11 0 1 0 1 11 1 1 1 0 1其主析取范式是：(p q)(pq)(pq)，主合取范式为：pq。真值表如表 2-23 所示，所以其极小项是 pqr,pqr, pqr, pqr,pqr,表 2-23p q r )(0 0 0 1 0 010 / 180 0 1 1 0 00 1 0 1 0

17、00 1 1 1 1 11 0 0 0 0 11 0 1 0 0 11 1 0 0 0 11 1 1 0 0 1极大项为 pqr，p qr，pq r。其主析取范式是：( pqr)(pqr)(pqr)(pqr)(pqr)，主合取范式为：(pqr) (pqr)(pqr) 。真值表如表 2-24 所示,所以其极小项为 pqr,pqr,pqr,pqr,pqr,而极大项分为 pqr，p qr， pqr.主合取范式为(pqr)(pqr)(p qr),主析取范式为(pq r)(pqr)(pqr,)(pqr)(pqr)。表 2-24p q r r)(0 0 0 1 00 0 1 1 10 1 0 1 00 1 1 1 11 0 0 0 11 0 1 0 11 1 0 1 01 1 1 1 15解 (p q)(pq)(pq)(pq) q (pq)(pq)，故为可满足式。 )()()( rrpqp()()()rr()()qrpqr()()pqrpqrp()()rr(0,1234,567)故为重言式。(p(q r)(pq)(pr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)