离散数学第2版刘爱民习题解答11

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) pq；5.2) pØq; 5.3) pq；5.4) pØq；6) 6.1) pq 6.2)

2、Ø(p « q) 6.3) p¬q 6.4) ¬ (pr)6.5) (pq) ®r6.6) ¬ (r ® (pq) 7) p:蓝色和黄色可以调配成绿色； 8) Ø(p«q), p:李兰现在在宿舍, q:李兰在图书馆里； 9) ¬p®¬ q, p:一个人经一事，q:一个人长一智；10) (p¬q) ® Ø(r« s), p:晚上小王做完了做业, q: 晚上小王没有其他事情，r: 晚上小王看电视, s: 晚上小王看电影。11) Ø

3、(r« s), r:小飞在睡觉, s:小飞在游泳；12) ¬p¬qr, p:这个星期天我看电视，q: 这个星期天我外出，r:这个星期天我在睡觉。13) p®q , p:卫星上天了，q:国家强大了；14) p®q, p:今天没有课，q:我呆在图书馆里；15) p®q,p:我去图书城，q:我有时间；16) ¬p®¬q , p:人们辛劳，p: 人们收获1.3 1) 小李家住北大西门外, 他现在坐在公共汽车里看书，没有考虑问题； 2) 小李在思考问题, 他没有乘坐公共汽车，也没有看书； 3) 小李只要乘坐公共汽车

4、，他就看书或考虑问题； 4) 小李乘坐公共汽车，要么看书不考虑问题，要么考虑问题不看书， 5) 同4); 6) 如果小李家住北大西门外,则他现在没有乘坐公共汽车，没有看书，也没有考虑问题。1.4 1) 是2) 不是，因为联结词后没有字母3) 是4) 是5) 不是，因为pq之间缺联结词6) 不是，因为 不能构成公式7) 是*1.5 1) q是0层公式，Øq是1层公式，(p Øq)是2层公式，原公式是3层公式; 2) p是0层公式，Øp是1层公式，(Øp®q) 是2层公式，(q®r) 是1层公式，(Øp®q) (q&#

5、174;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.6 p ð q ® r s，q ð p ® q1) (q ® r s) Ø( p

6、74;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.7 AB, A的成真赋值或B的成真赋值，故为000,011,100,110,111, 101;

7、 ØAB, A®B: ØA的成真赋值或B的成真赋值，001,010,101, 000,110; AB: 同时是A和B的成真赋值，000,110；ØAØB: 同时是ØA和ØB的成真赋值，001, 010；A«B: 同时是A和B的成真赋值或成假赋值，000,110, 001, 010；1.8 1) ( p q ) ® q 2) (p ® q) « ppqp q( p q ) ® qpqp ® q(p ® q) « p00010010010101101

8、001100011111111这是重言式。这是可满足式。 3) (p®Øp) ® Øp 4) p ® (p q)pqØpp®Øp(p®Øp) ® Øppqp qp ® (p q)001110001011110111100011011110011111这是重言式。这是重言式。 5) Ø(p®q) q 6) (Øq®Øp) « (p ® q)pqØ(p®q) qpq(Øq

9、®Øp)«(p ® q)000100011111010100101111101001010010110101101011这是矛盾式这是重言式。 7) (p®r) ® (p®r) ®(pq)®r) 8) Ø(p®q) p rpqr(p®r)®(p®r)®(pq)®r)pqrØ(p®q)pr000111101000010000111110100101000101010100100100011111111011010010

10、00101101001010101111111101101111001011011001001111111111110100 这是可满足式 这是可满足式1.9 这里仅仅是无数个命题形式中的两个，读者可以另外给出F：矛盾式，用一个矛盾式与任何一个公式合取即可，即(pØp) AF1=(pØp) (qr), F2=p Ø qØr (qr)G：重言式，简单的可以是一个重言式与任何一个公式析取，(pØp) A如：G1=(pØp) (qr), G2= p (pq) Øp r，重言式拆分在不同的位置H：前四行可看成蕴涵式的否定，后四行与p

11、相同，两种情况相或。所以H1= p (Ø(q® r) ; p (Ør q)还是分成前后四行分析，如果以p作为蕴涵式的后件：A®p，后四行总成立，想法构成前件，使得前四行的第三行为0，其它行为1，正是蕴涵式q® r。所以可写成H2=q ® r ® pR：只有全0的才为0，所以最简单的是用析取式，R1=pqr这个公式再与其它的确保p,q,r三个为0时一定为0的公式相析取即可；R2= pqr (p q)， pqr (pr)S：类似H的分析，前四行和后四行情况相或，S1=p (qr)如果以p作为蕴涵式的后件：A®p，后四行

12、总成立，想法构成前件，使得前四行的第三行为0，其它行为1，正是蕴涵式q®Ø r。所以可写成S2=q ® Ør ® p习题二答案2.1 1) 不能。CÛ1时，两边总是等值； 2) 不能。CÛ0时，两边总是等值； 3) 能。由否定之否定可得。2.2 1) 证明下列等值式：(1) p®(q®r) Û Øp(Øqr) (2) Ø(p « q) ÛØ(p®q)(q®p)Û ØpØqrÛ

13、Ø (Øpq)(Øqp)Û Ø qØprÛ (pØq) (qØp) Û Øq(Øpr) Û (pq)(ØpØq)Û q ® (p ® r)Û (pq)Ø(pq)(3) p®(q®p) Û Øp (Øq p)(4) (p®r) (q ® r) Û (Øpr) (Øq r)Û p (Ø

14、;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 (qr) Û p ® q r 2) 判定命题形式类型：(1) (p«q)®Ø(pØp)

15、(Øpq) (2) Ø(qØ(Øp q) p) Û (p«q)® Ø(Øpq)Û Øq (Øp q) p) Û Ø (p®q) (q®p) Û Øq (q p) Û Ø (Øpq) (Øqp)Û 0 Ø(Øpq)这是矛盾式 Û (pØq) (qØp) Ø(Øpq)Û (pØq)

16、1Û 1这是重言式(3) (p®q)(Øq®p) «p (4) (q®p)(Øp®q) Û(Øpq)(qp) «pÛ (Øqp)(pq)Û(Øp p) q) «p Û (Øq q) p Û q « pÛ p 这是可满足式这是可满足式(5) Ø(Ø(p q) ® Øp) (6) (p ® q r) (Ør®(p 

17、4; 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) Ø (Øpq) Û (p q)(pØq) Û p( q &#

18、216;q) Û p对偶式是：Ø (ØpØq) Ø (Øpq) Û p2) q Ø(Øpq) p) Û q Ø(q p) Û q Øq Øp Û 1对偶式是：q Ø(Øpq) p) Û 03) (pq) (pØq) (ØpØq) Û (pq) (p Øp)Øq) Û (pq) Øq Û (pq) Øq Û p

19、 ØqÛ Ø(Øpq)对偶式是：(pq) (pØq) (ØpØq) Û Ø(Øpq)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, Ø, , )对偶式定义是重言式，其任何的替换实例仍

20、然是重言式，以Ø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)。

21、显然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，Ø可用®

22、;表示，是冗余联结词，所以Ø, ®不是极小全功能集。*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) Û &#

23、172;p p ¬,(重言式) Û ¬(p ¬p) ¬, 4) p(Øq r®p) Û pq ¬r ¬, Û ¬( ¬p¬q r) ¬, 5) (p ® q Øq) Øp qÛ ¬ (p¬q) ¬, Û ¬p q ¬ ¬,*2.7 1) Ø,®: (Øp ® q)®r 2) Ø,

24、: Ø(Ø (Øp Øq) ¬r) 3) Ø,: ¬(p q) r 4) ­；(p­p) ­ (q­q)­ (r­r) 5) ¯: (p¯q) ¯r) ¯ (p¯q) ¯r)2.8 1) (pq) (Øpq) r) 2) (pqr) (q(Øpr) *3) (pq) ¯ (Øpqr) *4) (p ­ q) (Øp¯Øq)2.9

25、 1) Øp r ® q 2) ØrØp ® (p«Øq) Û Ø (Øp r) q ÛØ (ØrØp ) (pØq) (Øpq)Û Øp Ør qÛ (p Ør) (pØq) (Øpq)Û M5 Û(pqØr) (pØqØr) (pØq r)主合取范式，仅含有一个极大项， (Øpq r) (

26、16;pqØr)所以是可满足式 Ûm6m4m5m3m2 含有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 Û m7m0 主析取范式，含有两个极小项主析取范式不含有任何极大项， 所以是可满足式是

27、矛盾式。2.10 1) (a) (pq)(Øpqr) (b) (p(qr)(q(Øpr) Û (pqr)(pqØr)(Øpqr) Û(p q)(qr)(Øpqr)Û m7m6m3Û(p q r)(p qØr)(pqr) Û M5M4M2M1M0 (pqØr)(Øpqr) Ûm7m6m3 Û M5M4M2M1M0主范式都相同，两者等值。 2) (a) p®(q®r) (b) q®(p®r) Û

28、16; p (Øqr) ÛØ p (Øqr) Û M6Û M6 Û m0m1m2m3m4m5m7Û m0m1m2m3m4m5m7主范式都相同，两者等值。 3) (a) p (ØpØq) (b) Ø(Øpq) Û p Øq Û p Øq Û m2Û m2 Û M0M1M3Û M0M1M3主范式都相同，两者等值。 4) (a) (p®q)® p q (b) (Øp

29、4;p) (r®p) Û Ø (Øpq) p q Û (p p) (Ørp) Û (pØq) p q Û pÛ (pØq r) (pØqØr) Û (pØq r) (pØqØr) (p q r) (p qØr)(p q r) (p qØr) Û m5m4m7m6Û m5m4m7m6 Û M0M1M2M3Û M0M1M2M3 主范式都相同，两者等值。2.11 指派需要同

30、时满足1), 2), 3)条件，以及只派两个人的条件。条件1)： A®Ø(C«D) Û ØA Ø(CD) (ØCØD) Û ØA (ØCØD) (CD) Û (ØA ØCØD) (ØACD) Û (ØABØCØD) (ØAØBØCØD) (ØABCD) (ØAØBCD) Û M11M15M8M12条件2)：

31、Ø(BC) Û ØBØC Û (AØBØCD) (AØBØCØD) (ØAØBØCD) (ØAØBØCØD) Û M6M7M14M15条件3)： C®ØD Û ØCØD Û (ABØCØD) (AØBØCØD) (ØABØCØD) (ØAØBØC&#

32、216;D) Û M3M7M11M15这三个条件同时满足，是合取关系。即为M11M15M8M12M6M7M14M3而指派的情况是各种可能的情况，是析取关系，为此得到析取范式，为m0m1m2m4m5m9m10m13这就是可能的情况，其中下标的二进制数对应位置为1的就是要指派的人。如1：0001，只指派D条件只指派两人，就是5：0101，9：1001，10：1010；即可以指派的情况有三种：B和D，A和D，或A和C2.12 解：按照题意，三个推测只有一个是对的。推测1：Ø(b «c)；推测2：ØaØb；推测3：Ø(b «d)推测

33、正确为肯定，推测错误为否定。推测1正确：Ø(b «c) Ø(ØaØb) (b «d)ÛaØbcd 推测2正确：(b «c) (ØaØb) (b «d) Û ØaØbØcØd推测3正确：(b «c) Ø (ØaØb) Ø (b «d) Û (abc) (ØabØc)( acd)可以看到，只有推测3正确时(ØabØc)中含

34、有一个肯定的b。所以该生没有说谎，他是从b地直接返校的。*111110BC001110AØAÙCAÙØC2.14 提示：设开关向上为肯定，向下为否定，四种情况分别是：1) 搬键C向上, A、B同向下时：Ø pØq r 2) 搬键A向上, B、C同向下时：pØq Ør3) 搬键B、C向上, A同向下时：Øpq r4) 搬键A、B向上, C同向下时：pq Ør各种情况都可以成立，所以是析取关系，可采用卡诺图化简，得到Ø pØq r pØq Ør Øp

35、q r pq Ør ÛØ p r pØr即只要A或C中的一个但又不同时控制电灯即可。*2.15 按照题意：只要A有信号，FA就有信号，此时不管B，C是否有信号设A，B，C有信号分别表示为p，q，r。 只要A有信号的情况就是：100，101，110，111 即：FAÛm4m5m6m7Û p Û (p¯p) ¯ (p¯p)类似A无信号，但是B有信号，C不管有无信号，FB输出信号。此时情况是：010，011FBÛm2m3ÛØpq Û p ¯ Ø

36、;qÛp ¯ (q¯q)FC输出信号必须是只有C有信号，只有001一种情况，所以FCÛm1Û ØpØq r Û Ø(pq) r Û Ø ( (pq) Ør) Û (pq) ¯ Ør Û Ø (p¯q) ¯ Ør Û (p¯q) ¯ (p¯q) ¯ (r¯r)习题三答案3.1判断前提是否一致，即判断他们的的合取是否不为矛盾式：下面用主范式判

37、断： 1) (p q) (s Ør) Ø(s Ør) Û(p q s) (p qØr) (Øs r) Û(p q r s) (p qØrØs)这是可满足式，所以前提一致。2) p1 (Øp1 p2) (Øp1 Øp2 p3) (Øp1 Øp2 Øpn-1 pn) Û p1 p2 (Øp2 p3) (Øp2 Øpn-1 pn) Û p1 p2 p3 (Øp3 Øpn-1 pn)

38、Û Û p1 p2 p3 pnn个命题变项的合取，这是可满足式，前提一致。3) (p q) (Øp Øq) (p ® q) Û (p q) (Øp Øq) (Øp q) Û (p q) Øp Û 0 诸前提矛盾，不一致；3.2构造下列推理的证明：1) 前提q ® p, q « s, s « t, t r; 结论p q s r。证明 s « t 前提引入P (t®s) (s®t)置换TE t®s 化简TI t

39、 r 前提引入P t 化简TI s 假言推理TI q « s 前提引入P (q®s) (s®q)置换TE s®q 化简TI q 假言推理TI q ® p 前提引入P p 假言推理TI p q s r 合取TI2)前提p®(q®s),Ørp,q;结论r®s。证明 p ® (q ® s) 前提引入P q ® (p ® s) 置换TE q 前提引入P p ® s 假言推理TI Ør p 前提引入P r ® p 置换TE r ® s

40、假言三段论TI3)前提Ø( pØq),Øqr, Ør; 结论Øp。证明 Øq r 前提引入P Ør 前提引入P Øq 析取三段论TI Ø( p Øq) 前提引入P Øp q 置换TE Øp 析取三段论TI3.3 用相应证明方法证明：1) 归谬法： 前提p ® Øq, q Ør, r Øs； 结论Øp。证明 p 否定结论作为前提P p ® Øq 前提引入P Øq 假言推理TI q Ør 前

41、提引入P Ør 析取三段论TI r Øs 前提引入P Ør r Øs 合取TI 0 置换TI推出矛盾，所以原结论正确。2) 附加前提法：前提(p q) ® (r s), (s t) ® u; 结论p ® u。证明 p 附加前提引入P p q 附加TI (p q) ® (r s)前提引入P r s 假言推理TI s 化简TI s t 附加TI (s t) ® u 前提引入P u 假言推理TI p ® uCP规则CP3) 反证法： 前提Øp Øq, 结论Ø (p q)证

42、明 p q 否定结论作为前提引入P p 化简TI p q 附加TI Ø(Øp Øq) 置换TE得到否定的前提，原推理正确。3.4 反证法。否定结论推出否定的前提。否定结论，即如果2不能整除a，即a=2m+1；则a2=(2m+1)2=4m2+2m+1所以2不能整除a2。这正是否定的前提。原推理正确。*3.5 甲在最后，丙在最前，甲先推测自己戴的帽子。设甲乙丙戴红帽子分别为p，q，r甲看到乙和丙戴的帽子推测自己带的，乙根据看到丙所戴及甲所判断的来确定自己所戴帽子，根据可能的情况是：(1) 乙和丙戴黑帽子，甲确定自己戴红帽子，即pØqØr。三个前提成

43、立，丙能确定自己为Ør，即戴黑帽子；(2) 乙和丙中并非都戴黑帽子，甲不能确定自己戴什么帽子，可能的情况是(2.1) 乙和丙都戴红帽子：qr，(2.2) 乙和丙一个戴红帽子：(Øqr) (qØr)综合即为(qr)(Øqr) (qØr)Û r (qØr) 一种情况就是：r，则q，Øq可能都成立，乙无法判断自己所戴帽子，而丙一旦听到乙无法判断自己所戴帽子，即可确定自己带红帽子； 另一种情况是：(qØr)，乙看到丙带黑帽子，确定自己带红帽子；丙一旦听到乙说自己带红帽子，可确定自己带黑帽子；总结就是：甲确定自己戴

44、红帽子，丙可确定自己戴黑帽子； 甲不能确定所戴帽子：乙可确定自己戴红帽子，丙能确定自己戴黑帽子； 乙不能确定自己所带帽子，丙能确定自己戴红帽子；所以丙总能判断出自己所戴帽子。*3.6 针对其中一个人，是哥哥(p)是弟弟(Øp)，是说真话 (q)还是说谎(Øq)，都必居其一。 可能的情况是：pq，pØq，Øpq，ØpØq， 询问只能就这几种情况询问，并根据答复情况确定结果。而答复可能是说真话的答复，或者说假话的答复。两种答复都要能判断。 如果只询问一种情况，如pq，则肯定答复结果是(pq) q) (Ø(pq) Øq)

45、ÛpqØqÛ pØq，无法得到确定的结果；不必再讨论否定答复结果。 如果只询问两种的情况，有共同点时，如pq，pØq，则肯定答复结果是(pq ØpØq) q Ø(pq ØpØq) Øq Û pq ØpØq，无法确定结果，不必再讨论否定答复结果。 无共同点时，如pq，ØpØq，则肯定答复结果是(pq ØpØq) q Ø(pq ØpØq) Øq Û p，能确定被询问的人是

46、哥哥；否定答复结果是Ø(pq ØpØq) q (pq ØpØq) Øq Û Øp；能确定被询问的人是弟弟。问话为： “你是哥哥且你说了真话，或你是弟弟且你说了假话”对吗？。肯定者是哥哥，否定者是弟弟。如果另外一对无共同点的情况，如Øpq，pØq，则肯定答复结果是(ØpqpØq) q Ø(ØpqpØq) Øq Û Øp，能确定被询问的人是弟弟；否定答复结果是Ø(ØpqpØq) q (

47、16;pqpØq) Øq Û p；能确定被询问的人是哥哥。问话也可为： “你是哥哥且你说了假话，或你是弟弟且你说了真话”对吗？。肯定者为弟弟，否定者是哥哥。3.7证明下列各推理是否正确.提示：也可以直接利用等值演算方法，获得原蕴涵式是可满足式，则推理不正确。1) p：我是一年级学生；q：我要学习高等数学，r：我要学习集合论；s：我是二年级学生；t：我要学习数学逻辑，u：我要学习图论；前提：p ®( qr)，s®(tu)，ØqØs结论：ØqØrØtØu证明 ØqØs

48、前提引入P Øq 化简TI Øs化简TI p ®( qr) 前提引入P到此无法继续往下推理，所以无法证明，即原推理是错误的。2) p：我复习完功课；q：我打篮球，r：我打乒乓球；前提：q ® p，q®Ør，Øp结论：ØqØr证明 q ® p 前提引入P Øp 前提引入P Øq 拒取式TI q®Ør 前提引入P到此无法继续往下推理，所以无法证明，即原推理是错误的。3) p：我的程序通过了；q：我高兴，r：我生活愉快；前提：p ® q，r®

49、q，p结论：r证明 p ® q 前提引入P p 前提引入P q 假言推理TI r®q 前提引入P到此无法继续往下推理，所以无法证明得到r，即原推理是错误的。3.8 解：符号化：p：甲获胜；q：乙获胜；r：丙获胜；s：丁获胜；前提：p®Øq，r®q，Øp®s，结论：r®s r®q 前提引入P p®Øq 前提引入P q®Øp 置换TE r®Øp假言三段论TI Øp®s前提引入P r®s 假言推理TI3.9 解：符号化：p

50、：今天天晴；q：今天下雨；r：我去看电影；s：我看书；前提：p q，p®r， r®Øs，结论：s®q p®r 前提引入P r®Øs 前提引入P p®Øs假言三段论TI p q®Øs q前后件附加TI p q 前提引入P Øs q假言推理TI s®q 置换TIE提示：3.8、3.9可用CP规则。*3.10 机器证明是：归谬法，并利用转换成合取范式，以便得到各简单析取式，各简单析取式之间消解。1) 前提q ® p, q « s, s « t

51、, t r; 结论p q s r。证明 Ø(p q s r) 否定结论引入得合取范式Øp Øq Øs Ør，也是简单析取式 q ® p前提引入得合取范式Øq p，也是简单析取式 q « s 前提引入得合取范式(Øq s) (q Øs)，再得Øq s q Øs 得到的第二个简单析取式 s « t 前提引入得合取范式(Øt s) (t Øs)，再得Øt s t Øs得到的第二个简单析取式 t r 前提引入为合取范式，得到t r得到

52、的第二个简单析取式 Øq Øs Ør 消解TI Øp Øq Ør消解TI Øp Øs Ør 消解TI Øp Øq Øt Ør消解TI Øp Øq Øs 消解TI p Øs 消解TI Øq t 消解TI q Øt消解TI s消解TI q消解TI Øp Øq消解TI Øq消解TI(21) 空消解TI得空，所以原推理正确。注：机器证明中有许多过程是机器的，得到的结果在后续可能并没用，

53、如上面得到，。2)前提p®(q®s),Ørp,q; 结论r®s。证明 Ø(r®s) 否定结论得合取范式rØs，得简单析取式r和 Ø s 得到第二个简单析取式 p®(q®s)前提引入得合取范式Øp Øq s Ør p 前提引入P q 前提引入P p 消解TI Øp Øq 消解TI Øp消解TI 空消解TI得空，所以原推理正确。3)前提Ø( pØq),Øqr, Ør; 结论Øp。证明 p 否

54、定结论引入P Ø( p Øq) 前提引入得Øp qP，E Øqr 前提引入P Ør 前提引入P q 消解TI Øpr 消解TI Øq 消解TI 空消解TI得空，所以原推理正确。习题四答案4.1 将下列命题用0元谓词符号化： 1) P(x): x是素数, Q(x): x是偶数；a:2; P(a) Q(a) 2) P(x,y): x大于y, a:2, b:3, c:4；P(a,b) ®P(a,c); 3) P(x,y): x比y高, a:张明, b: 李民, c: 赵亮; P(a,b) P(b,c) ®P(a

55、,c)； 4) P(x): x是素数, a:3; ØP(a)； 5) P(x): x是素数, a:2,b:3; P(a) P(b)； 6) P(x,y): x能被y整除,a:16,b:4,c:8；P(a,b) P(a,c) 7) P(x,y): x能整除y, a:7,b:100,c:3, P(a,b) ®P(c,b); 8) P(x,y): x能整除y , Q(x): x是偶数,b:2; P(2,a) « Q(a)。4.2 解：个体域全部为全总个体域： 1) P(x): x是火车，Q(x):x是轮船，R(x,y):x比y快； "x(P(x) ®

56、"y(Q(y) ® R(x,y) 2) P(x): x是汽车，Q(x):x是火车，R(x,y):x比y慢； $x(P(x) "y(Q(y) ® R(x,y) 3) P(x): x是实数，Q(x，y):x大于y； Ø$x(P(x) "y(P(y) ® Q(x,y) 4) P(x,y): x和y是对顶角，Q(x，y):x等于y； "x"y(P(x,y) ® Q(x,y) 5) P(x): x是人, Q(x): x会犯错误； Ø$(P(x) ØQ(x) = "x(P(x)

57、® Q(x) 6) P(x): x是北京人, Q(x): x是在北京工作的人； Ø"x(Q(x)®P(x) = $x(Q(x) ØP(x) 7) P(x): x是偶数, Q(x,y): x能被y整除, a:2； "x(P(x)®Q(x,a) 8) 所有能飞的动物都是鸟； P(x): x是动物, Q(x): x是鸟，R(x): x能飞； "x(P(x) R(x)®Q(x)4.3 解：1) 对于任意的x，存在y，使得x × y=0；(a)、(b)情况下为1，(c)、(d)情况下为0。2) 存在x，对

58、于所有y，均有x × y=0；(a)、(b)情况下为1，(c)、(d)情况下为0。3) 对于任意的x，存在y，使得x × y=1；(a)、(b)、(c)情况下为0，(d)情况下为1。4) 存在x，对于所有y，均有x × y=1；任何情况下为0。5) 对于任意的x，存在y，使得x × y=x；任何情况下为1。6) 存在x，对于所有y，均有x × y=x；(a)、(b)情况下为1，(c)、(d)情况下为0。7) 对于任意的x，y，存在z，使得x - y=z；(a)、(b)情况下为1，(c)、(d)情况下为0。4.4 解1) P(x): x2-1 =

59、 (x+1)(x-1) (a) 个体域为自然数集合: "xP(x), 真 (b) 个体域为实数集合: "xP(x), 真 (c) 个体域为一切事物: "x(Q(x)®P(x), Q(x): x是数，真2) P(x): x + 5 = 2 (a) 个体域为自然数集合: "xP(x), 假 (b) 个体域为实数集合: "xP(x), 真 (c) 个体域为一切事物: "x(Q(x) P(x), Q(x): x是数， 真4.5 解1) x<0: L(x, 0) Ø$x L(x, 0)真2) x + 0 = x: F(x, 0, x) "xF(x, 0, x)真3) x · y = y: G(