《离散数学最全最新答案屈婉玲.doc》由会员分享，可在线阅读，更多相关《离散数学最全最新答案屈婉玲.doc（18页珍藏版）》请在三一文库上搜索。
1、第一章 命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（1）pq,其中，p:2是素数，q:5是素数,真值为1；（2）pq,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）pq,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）pq,其中，p:3是素数，q:3是偶数,真值为0；（5）pq,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：（1）pq,其中，p:2是偶数，q:3是偶数,真值为1；（2）pq,其中，p:2是偶数，q:4是偶数,真值为1；（3）pq,其中，p:3是偶数，q:4是偶数,真值为0；（4）pq,其中，
2、p:3是偶数，q:4是偶数,真值为1；（5）pq,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(pq)(pq),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(pq)(pq),其中，p：刘晓月选学英语，q：刘晓月选学日语；.7.因为p与q不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）pq，真值为1（不会出现前件为真，后件为假的情况）；（2）qp，真值为1（也不会出现前件为真，后件为假的情况）；（3）pq，真值为1；（4）pr，若p为真，则pr真值为0，否则，pr真值为1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值
3、。 （1）p(qr) 0(01) 0 （2）（pr）(qs) （01）(11) 010. （3）（pqr）(pqr) （111） (000)0(4)（rs）(pq) （01）(10) 00117判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。”答：p: 是无理数 1 q: 3是无理数 0 r: 是无理数 1 s:6能被2整除 1t: 6能被4整除 0 命题符号化为： p(qr)(ts)的真值为1，所以这一段的论述为真。19用真值表判断下列公式的类型：（4）(pq) (qp)（5）(pr) (pq)（6）(pq) (qr) (pr)答：
4、 （4） p q pq q p qp (pq)(qp) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 /最后一列全为1（5）公式类型为可满足式（方法如上例）/最后一列至少有一个1（6）公式类型为永真式（方法如上例）/第二章 命题逻辑等值演算本章自测答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)答：(2)（p(pq)）(pr)(p(pq)(pr)ppqr1 所以公式类型为永真式(3) P q r pq
5、 pr （pq）(pr)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1 所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(pq)(pr)(p(qr)(4)(pq)(pq)(pq) (pq)证明（2）(pq)(pr) (pq)(pr)p(qr)p(qr)（4）(pq)(pq)(p(pq) (q(pq)(pp)(pq)(qp) (qq)1(pq)(pq)1(pq)(pq) 5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(pq)(qp)(2)(pq
6、)qr(3)(p(qr)(pqr)解：（1）主析取范式(pq)(qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq) (0,2,3) 主合取范式： (pq)(qp) (pq)(qp) (pq)(qp) (p(qp)(q(qp) 1(pq) (pq) M1 (1) (2) 主合取范式为： (pq)qr(pq)qr (pq)qr0 所以该式为矛盾式. 主合取范式为(0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为：(p(qr)(pqr) (p(qr)(pqr)(p(qr)(pqr)(p(pqr)(qr)(pqr)
7、 11 1 所以该式为永真式. 永真式的主合取范式为 1 主析取范式为(0,1,2,3,4,5,6,7)7.(1)：；(2)：；8.(1)：1,重言式；(2)：；(3)：0，矛盾式. 11.(1)：；(2)：1；(3)：0. 12.A.第三章 命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三
8、，推理的形式结构为(pq)pq(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(pq)pq q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(pq)pq(记作*2) 可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(pq)qp(pq) q pq ppq从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同
9、时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为 (pq)(rq)(rp) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(pq)(rq)(rp)(pq) (qr)(qr) (使用了交换律)(pq)(pr)qr(pq)(qr)p(qq)r110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(pq)p(qr)(pq) p(qr)p(qr) (使用了吸收律)p(qr)由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序
10、列可不惟一，下面对每一小题各给出一个证明 p(qr)前提引入 P前提引入 qr 假言推理 q前提引入 r 假言推理 rs 前提引入（2）证明： (pr) 前提引入 qr 置换 r前提引入 q 析取三段论 pq 前提引入 p拒取式（3）证明： pq 前提引入 qq 置换 (pq)(pp) 置换 p(qp 置换 p(pq) 置换15.(1)证明： S结论否定引入 SP 前提引入 P假言推理 P(qr)前提引入 qr 假言推论 q前提引入 r假言推理（2）证明： p附加前提引入 pq 附加 (pq)(rs)前提引入 rs 假言推理 s化简 st 附加 (st)u前提引入 u拒取式16.(1)证明：
11、p结论否定引入 p q前提引入 q 假言推理 rq 前提引入 r析取三段论 rs 前提引入 r化简 rr 合取（2）证明： (rs) 结论否定引入 rs 置换 r化简 s化简 pr 前提引入 p拒取式 qs 前提引入 q拒取式 pq 合取 (pq) 置换口 pq 前提引入口 (pq) (pq) 口合取16在自然推理系统P中用归谬法证明下面各推理：(1)前提：pq,rq,rs 结论：p证明：p 结论的否定引入pq 前提引入q 假言推理rq 前提引入r 化简律rs 前提引入r 化简律rr 合取由于最后一步rr 是矛盾式,所以推理正确.17设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋
12、杀罪，s：看门人看见过A。前提：(pq) r , p ,q s , s结论：r证明： qs 前提引入 s 前提引入 q 拒取式 p 前提引入 pq 合取（pq）r 前提引入 r 假言推理18（1）设 p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。前提：p(pr) , sq , p , s结论：r证明： sq 前提引入 s前提引入 q假言推理 p前提引入 p(qr)前提引入 qr 假言推理r 析取三段论（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。前提：pq ,rp ,q结论：r证明： pq 前提引入 q前提引入 p拒取式 rp 前提引入 r拒取式第四章 (一
13、阶)谓词逻辑基本概念本章自测答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意x,均有2=(x+)(x).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合. (b)个体域为实数集合.解：F(x): 2=(x+)(x). G(x): x+5=9.(1)在两个个体域中都解释为，在（a）中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为，在（a）(b)中均为真命题。4.(1)x(F(x) G(x)x( F (x) G (x) ),其中,F(x)：x是有理数,G(x) ：x能表示成分数；(2)x( F (x) G
14、(x) ) x(F(x) G(x),其中,F (x)：x在北京卖菜,G (x) ：x是外地人；(3)x( F (x) G (x) ),其中,F (x)：x是乌鸦,G (x) ：x是黑色的；(4)xF(x) G(x),其中,F (x)：x是人,G (x) ：x天天锻炼身体。因为本题中没有指明个体域,因而使用全总个体域。5.(1)xy (F(x) G( y ) H(x,y),其中,F(x)：x是火车,G(y) ：y是轮船,H(x,y)：x比y快；(2)xy (F(x) G( y ) H(x,y),其中,F(x)：x是火车,G(y) ：y是汽车,H(x,y)：x比y快；(3)x(F(x)y(G (y
15、) H (x,y)x(F(x) y(G(y) H(x,y),其中,F(x)：x是汽车,G (y) ：y是火车,H(x,y)：x比y快；(4)x(F(x)y(G(y) H(x,y)xy(F(x)G(y)H(x,y),其中,F(x)：x是汽车,G(y) ：y是火车,H(x,y)：x比y慢。6.各命题符号化形式如下：(1)xy (x y = 0)；(2)xy (x y = 0)；(3)xy (y =x+1)(4)xy(x y = yx)(5)xy(x y =x+ y)(6)xy (x + y 0 )9.(1)对任意数的实数x和y,若x y,则x y；(2)对任意数的实数x和y,若xy = 0,则xy
16、；(3)对任意数的实数x和y,若xy,则xy0；(4)对任意数的实数x和y,若xy 0,则x=y.其中,(1)(3)真值为1(2)与(4)真值为0.11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。这里仅对(3)、(4)、(5)给出证明。(3)取解释I 为：个体域为自然数集合N,F(x,y)：x y,在下,xy F(x,y)为真,而xy F(x,y)也为真(只需取x =0即可),于是(3)中公式为真,取解释 为：个体域仍为自然数集合N,而F(x,y)：x = y。此时,xyF(x,y)为真(取y为x即可),可是xyF(x,y)为假,于是(3)中公式在 下为假,这说
17、明(3)中公式为可满足式。(4)设I为任意一个解释,若在I下,蕴涵式前件xy F(x,y)为假,则xyF(x,y)yxF(x,y)为真,若前件xyF(x,y)为真,必存在I的个体域D1中的个体常项x0,使yF(x0,y)为真,并且对于任意y,F(x0,y)为真,由于有x0,F(x0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以 yxF(x,y )为真,由于I的任意性,所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。(5)取解释为：个体域为自然数集合,F(x,y)：x = y在下,(5)中公式为真,而将F(x,y)改为F(x,y)：x y,(5)中公式就
18、为假了,所以它为可满足式。10. 给定解释I如下： （a） 个体域D=N(N为自然数集合). （b） D中特定元素=2. （c） D上函数=x+y,(x,y)=xy. （d） D上谓词(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.(1) xF(g(x,a),x)(2) xy(F(f(x,a),y)F(f(y,a),x)答:(1) 对于任意自然数x, 都有2x=x, 真值0.(2) 对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x. 真值0.11. 判断下列各式的类型:(1) (3) yF(x,y).解:(1)因为 为永真式； 所以 为永真式；(3)取解释I个体域为全
19、体实数F(x,y)：x+y=5所以,前件为任意实数x存在实数y使x+y=5，前件真；后件为存在实数x对任意实数y都有x+y=5，后件假，此时为假命题再取解释I个体域为自然数N，F(x,y)：:x+y=5所以,前件为任意自然数x存在自然数y使x+y=5，前件假。此时为假命题。此公式为非永真式的可满足式。13（1）取解释为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在 下， x（F（x）G（x）为真命题。取解释为：个体域为整数集合Z，F（x）：x为正整数，G（x）：x为为负整数，在 下， x（F（x）G（x）为假命题。（2）与（3）可类似解答。14提示：对每个公式分别找个成真的
20、解释，一个成假的解释。第五章 谓词逻辑等值演算与推理本章自测答案2.(1) (F(a) F(b) F (c) (G (a )G (b)G (c)(2) (F(a) F(b) F (c) (G (a)G (b)G (c)(3) (F(a) F(b) F (c) (G (a)G (b)G (c)(4) (F(a ,y) F(b,y) F (c,y) (G (a)G (b)G (c)5.提示：先消去量词，后求真值，注意，本题3个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1 .(1) 的演算如下：xyF(x,y)x (F(x,3)F(x,4)(F(3,3)F(3,4)(F(4,
21、3)F(4 ,4)1116.乙说得对，甲错了。本题中，全称量词 的指导变元为x ，辖域为(F (x)G(x,y),其中F(x )与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。7.演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“ ”。演算的第二步，在原错的基础上又用错了等值式，即(F(x)(G(y) H(x,y) (F(x) G(y)H (x,y)12.公式的前束范式不唯一，下面每题各给出一个答案。(1) xy (F(x) G(z,y);(2) xt (x,y) G(x,t,z);(3) x4 (F(,y) G(,y)(G(,y) F(x4,y);(4) (F()G(
22、,) (H () L(,);(5) (F(,)(F() G (,).13.(1)xy(F(x) G(y) H(x ,y),其中，F(x):x是汽车，G(y)：y是火车，H(x，y)：x比y跑的快； (2)xy(F(x) G(y)H(x ,y),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快； (3)xy(F(x) G(y) H(x ,y),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快； (4)xy(F(x) G(y) H(x ,y),其中，F(x):x是飞机，G(y)：y是汽车，H(x，y)：x比y慢；14.(1)对F(x) xG(x)不能
23、使用EI规则，它不是前束范式，首先化成前束范式。F(x) xG(x) x(F(y)G(x)因为量词辖域(F(y)G(x)中，除x外还有自由出现的y，所以不能使用EI规则。 (2)对 x F(x) y G(y)也应先化成前束范式才能消去量词，其前束范式为 x y(F(x) G(y),要消去量词，既要使用UI规则，又要使用EI规则。 (3)在自然推理系统F中EG规则为A(c)/x(x)其中c为特定的个体常项，这里A(y) = F(y) G(y)不满足要求。 (4)这里，使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如，F(x):x为奇数，G(x):x为偶数，
24、显然F(3)G(4)为真，但不存在使F(x)G(x)为真的个体。 (5)这里c为个体常项，不能对F(c)G(c)引入全称量词。15.(1)证明：xF(x)前提引入xF(x) y(F(y)G(y) R(y) 前提引入y(F(y)G(y) R(y) 假言推理F(c) EI(F(c)G(c)R(c) UIF(c)G(c) 附加R(c) 假言推理xR(x) EG(2)证明xF(x) 前提引入x(F(x)G(a)R(x) 前提引入F(c) EIF(c)G(a)R(a) UIG(a)R(c) 假言推理R(c) 化简F(c)R(c) 合取x(F(x)R(x)EG(3)证明：xF(x) 前提引入xF(x)置换
25、F(c) UIx(F(x)G(x) 前提引入F(c)G(c) UIF(c) 析取三段论xF(x)EG(4)证明x(F(x)G(x)前提引入F(y)G(y) UIx(G(x)R(x) 前提引入G(y)R(y) UIx R(x) 前提引入R(y) UIG(y) 析取三段论F（y） 析取三段论xF(x) UG17本题不能用附加前提证明法.20.(1)与(2)均可用附加前提证明法。22.(1)设F(x)：x为偶数，G(x):x能被2整除。前提:x(F(x)G(x)，F(6)结论：G(6)(2)设F(x)：x是大学生，G(x):x是勤奋的，a：王晓山。前提:x(F(x)G(x)，G(a)结论：F(a)2
26、3.(1)设F(x)：x是有理数，G(x):x是实数，H(x)：x是整数。前提:x( F(x)G(x)， x(F(x)H(x)结论:x(G(x)H(x)证明提示：先消存在量词。(2)设F(x)：x是有理数，G(x):x是无理数，H(x)：x是实数，I(x)：x是虚数。前提:x(F(x)G(x) H(x)， x( I(x)H(x)结论:x(I(x)(F(x)G(x)证明x(I(x)(H(x)前提引入I(y)H(y) UIx(F(x)G(x)H(x) 前提引入(F(y)G(y)H(y)UIH(y)(F(y)G(y)置换I(y)(F(y)G(y)假言三段论x(I(x)(F(x)G(x)UG24.设F
27、(x)：x喜欢步行，G(x)：x喜欢骑自行车，H(x)：x喜欢乘汽车。前提:x(F(x)G(x)， x(G(x)H(x)， xH(x)结论:xF(x)证明xH(x) 前提引入H(c)UIx(G(x)H(x)前提引入G(c)H(c)UIG(c)析取三段论x(F(x) G(x) 前提引入F(c)G(c)UIF(c)拒取式xF(x) UG25.设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在事业中获得成功。前提:x(F(x)G(x)，x(G(x)H(x)I(x)，a：王大海，F(a)，H(a)结论：I(a)证明F(a)前提引入x(F(x)G(x) 前提引入F
28、(a)G(a)UIG(a)假言推理H(a)前提引入x(G(x)H(x)I(x)前提引入G(a)H(a)I(a) UIG(a)H(a)合取I(a)假言推理第六章 集合代数本章自测答案4.(1) (2) (3) (4) (5) 6.只有(2)为真，其余为假。6设a,b,c各不相同，判断下述等式中哪个等式为真:（1）a,b，c,=a,b,c 假（2）a ,b,a=a,b 真（3）a，b=a,b 假（4），a,b=,a,b 假8求下列集合的幂集：（1）a,b,c P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c（2）1，2，3 P(A)= , 1, 2,3, 1，2，3 （3） P(A)=
29、 , （4）， P(A)= , 1, 2,3, 1，2，3 14化简下列集合表达式：（1）（AB）B ）-（AB）（2）（ABC）-（BC）A解:(1)（AB）B ）-（AB）=（AB）B ）（AB）=（AB）（AB）)B=B=（2）（ABC）-（BC）A=（ABC）（BC）A=（A（BC）（BC ）（BC）A=（A（BC）A=（A（BC）A=A18某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。解: 阿A=会打篮球的人，B=会打排球的人，C=会打网球的人 |A|=14,
30、 |B|=12, |AB|=6,|AC|=5,| ABC|=2, |C|=6,CAB如图所示。25-(5+4+2+3)-5-1=25-14-5-1=5不会打球的人共5人21.设集合A1，2，2，3，1，3,计算下列表达式：（1）A（2）A（3）A（4）A解: （1）A=1，22，31，3=1，2，3,（2）A=1，22，31，3=（3）A=123= （4）A=27、设A,B,C是任意集合，证明(1)(A-B)-C=A- BC(2)(A-B)-C=(A-C)-(B-C)证明(1) (A-B)-C=(AB) C= A( BC)= A(BC) =A- BC(2) (A-C)-(B-C)=(AC) (
31、B C)= (AC) (BC)=(ACB) (ACC)= (ACB) = A(BC) =A- BC 由（1）得证。9.(1) 4；(2) 1,3,5,6；(3) 2,3,4,5,6；(4) , 1 ；(5) 4 ,1,4.11.(1)； (2) 1,4,5.22.(2)、(3)、(4)、(8)、(10)为真，其余为假。24.(1)为真，其余为假，因为(P-Q) = P (P-Q)Q = PQ = PQ(2)(3)(4)的反例：P =1 ，Q =226.(AB)(BA) = (AB)(BA)=(AB)(BB)(AA)(BA)=(AB)E(AB)=(AB)-(AB)27.(1)(A-B)-C =
32、ABC =A(BC) = A-(BC) (2)(A-C)-(B-C)AC(BC) =AC(BC) = (ACB)(ACC) =AC=(AB)- C (3)(AB-C=ABC =ACB=(AC)B28.(1)A(BA) = (AB)(AA) =(AB) =AB=BA (2)(AB)A) = (AB)A =(AB)A = A29.由第26题有(A-B)(B-A)=(AB)(AB)，故(A-B)(B-A)AB。假若xAB，那么xAB，因此x(AB)-(AB),与(A-B)(B-A) = (AB)-(AB) = AB矛盾.30.ABx(xAxB)x(xBxA) x(xBxA)BA AB AAAB EA
33、B而ABE，因此AB AB=E反之， AB = E A(AB)= A AB = A AB 综合上述，ABAB = E AB A-B = A-BB反之A-BB (A-B)BB ABB AB = B AB综合上述ABA-BB31.任取x ,xA x A=xP(A)=xP(B)=xB xB32.先证CACB CAB,任取x,xC xCxC xAxB xAB,从而得到CAB.再证CAB CACB，这可以由CABA,CABB得到。33.PQ P-Q= P-QP，反之，P-QP P(P-Q)PP P-Q= PQ34.令X=，则有Y =，即Y = .35.AB AABA EBA因为E为全集,BAE综合上述BA=E.36.由ACBC,A-CB-C，利用ACBD有： (AC)(A-C) (BC)(B-C) (AC)(AC)(BC)(BC) (A(CC)(B(CC) AEBE AB37.恒等变形法B=B(BA)=B(AB)=B(AC) =(BA)(BC)=(AC)(BC) =(AB)C=(AC)C=C39.任取x，有xP(A) x A x B xP(B)