《离散数学第一章部分课后习题参考答案.docx》由会员分享，可在线阅读，更多相关《离散数学第一章部分课后习题参考答案.docx（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章部分课后习题参考答案16 设p、q真值为0；r、s真值为1，求以下各命题公式真值。 1p(qr) 0(01) 0 2pr(qs) 01(11) 010. 3pqr(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
2、(pq) (qr) (pr)答： 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 所以公式类型为永真式5公式类型为可满意式方法如上例6公式类型为永真式方法如上例第二章部分课后习题参考答案3.用等值演算法推断以下公式类型，对不是重言式可满意式，再用真值表法求出成真赋值.(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)答：(2)p(pq)(pr)(p(pq)(pr)ppqr1 所以公式类型为永真式(3) P q r pq pr pq(pr)0 0 0 0 0 10 0
3、 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)qr(3)(p(qr)(pqr)解：1主析取范式(pq)(q
4、p) (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) 11 1 所以该式为永真式. 永真式主合取范式为 1 主析取范式为
5、(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理证明： (2)前提：pq,(qr),r结论：p (4)前提：qp,qs,st,tr结论：pq证明：2(qr) 前提引入qr 置换qr 蕴含等值式r 前提引入q 拒取式pq 前提引入p3 拒取式证明4：tr 前提引入t 化简律qs 前提引入st 前提引入qt 等价三段论qt(tq) 置换qt 化简q 假言推理qp 前提引入p 假言推理(11)pq 合取 15在自然推理系统P中用附加前提法证明下面各推理：(1) 前提：p(qr),sp,q结论：sr证明s 附加前提引入sp 前提引入p 假言推理p(qr
6、) 前提引入qr 假言推理q 前提引入r 假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：pq,rq,rs 结论：p证明：p 结论否认引入pq 前提引入q 假言推理rq 前提引入r 化简律rs 前提引入r 化简律rr 合取由于最终一步rr 是冲突式,所以推理正确.第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化,并分别探讨个体域限制为(a),(b)条件时命题真值:(1) 对于随意x,均有x2-2=(x+2)(x-2).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合. (b)个体域为实数集合.解：F(x): x2-2=(x+2)(x-2). G(
7、x): x+5=9.(1)在两个个体域中都说明为，在a中为假命题，在(b)中为真命题。(2)在两个个体域中都说明为，在a(b)中均为真命题。4. 在一阶逻辑中将以下命题符号化:(1) 没有不能表示成分数有理数.(2) 在北京卖菜人不全是外地人.解:(1)F(x): x能表示成分数 H(x): x是有理数命题符号化为: (2)F(x): x是北京卖菜人 H(x): x是外地人命题符号化为: 5. 在一阶逻辑将以下命题符号化: (1) 火车都比轮船快. (3) 不存在比全部火车都快汽车. 解:(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快命题符号化为: (2) (1
8、)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快命题符号化为: 9.给定说明I如下: (a) 个体域D为实数集合R. (b) D中特定元素a =0. (c) 特定函数f(x,y)=x-y,x,y. (d) 特定谓词F(x,y):x=y,G(x,y):xy,x,y. 说明以下公式在I下含义,并指出各公式真值:(1)(2)答:(1) 对于随意两个实数x,y,假如xy, 那么xy. 真值1.(2) 对于随意两个实数x,y,假如x-y=0, 那么xy. 真值0.10. 给定说明I如下： a 个体域D=N(N为自然数集合). b D中特定元素a=2. c D上函数fx,y =x
9、+y,g(x,y)=xy. d D上谓词F(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) Fx,yGx,yFx,y.(3) xyF(x,y)xyF(x,y).解:(1)因为 为永真式； 所以 Fx,yGx,yFx,y.为永真式；(3)取说明I个体域为全体实数F(x,y)：x+y=5所以,前件为随意实数x存在实数y使x+y=5，
10、前件真；后件为存在实数x对随意实数y都有x+y=5，后件假，此时为假命题再取说明I个体域为自然数N，F(x,y)：:x+y=5所以,前件为随意自然数x存在自然数y使x+y=5，前件假。此时为假命题。此公式为非永真式可满意式。13. 给定以下各公式一个成真说明，一个成假说明。(1) x(F(x)G(x)(2) x(F(x)G(x)H(x)解:(1)个体域:本班同学F(x)：x是泰安人,G(x)：x是济南人.2成假说明(2)个体域:泰山学院学生F(x)：x诞生在山东,G(x):x诞生在北京,H(x):x诞生在江苏,成假说明.F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸. 成真说明.第
11、五章部分课后习题参考答案5.给定说明如下:(a)个体域D=3,4;(b)f为(c). 试求以下公式在下真值.(1) (3)解:(1) (2) 12.求以下各式前束范式。(1) (5) (此题课本上有错误)解:(1) (5) 15.在自然数推理系统F中,构造下面推理证明:(1) 前提: ,结论: xR(x)(2) 前提: x(F(x)(G(a)R(x), xF(x)结论:x(F(x)R(x)证明(1) 前提引入 F(c) EI 前提引入 假言推理 (F(c)G(c)R(c) UI F(c)G(c) 附加 R(c) 假言推理 xR(x) EG(2)xF(x) 前提引入F(c) EIx(F(x)(G
12、(a)R(x) 前提引入F(c)(G(a)R(c) UIG(a)R(c) 假言推理R(c) 化简F(c)R(c) 合取引入x(F(x)R(x) EG 第六章部分课后习题参考答案5.确定以下命题是否为真：1 真 2 假3 真4 真5a,ba,b,c,a,b,c 真6a,ba,b,c,a,b 真7a,ba,b,a,b 真8a,ba,b,a,b 假6设a,b,c各不一样，推断下述等式中哪个等式为真:1a,b，c,=a,b,c 假2a ,b,a=a,b 真3a，b=a,b 假4，a,b=,a,b 假8求以下集合幂集：1a,b,c P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c21，2，3
13、 P(A)= , 1, 2,3, 1，2，3 3 P(A)= , 4， P(A)= , 1, 2,3, 1，2，3 14化简以下集合表达式：1ABB -AB2ABC-BCA解:(1)ABB -AB=ABB AB=ABAB)B=B=2ABC-BCA=ABCBCA=ABCBC BCA=ABCA=ABCA=A18某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。6个会打网球人都会打篮球或排球。求不会打球人数。解: 阿A=会打篮球人，B=会打排球人，C=会打网球人 |A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|
14、=2, |C|=6,CAB如下图。25-(5+4+2+3)-5-1=25-14-5-1=5不会打球人共5人21.设集合A1，2，2，3，1，3,计算以下表达式：1A2A3A4A解: 1A=1，22，31，3=1，2，3,2A=1，22，31，3=3A=123= 4A=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) (B C)= (AC) (BC)=(ACB) (ACC)= (ACB) = A(BC) =A-
15、BC 由1得证。第七章部分课后习题参考答案7.列出集合A=2,3,4上恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA.解：IA =, EA=,LA=,DA=13.设A=, B=,求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB ), fld(A-B).解：AB=, AB=domA=1,2,3 domB=1,2,4 dom(AB)=1,2,3,4ranA=2,3,4 ranB=2,3,4ran(AB)=4A-B=,，fld(A-B)=1,2,314.设R=,求RR, R-1, R0,1, R1,2解：RR=, R-1,=,R0,1=,
16、R1,2=ran(R|1,2)=2,316设A=a,b,c,d，为A上关系，其中=求。解: R1R2=, R2R1=R12=R1R1=,R22=R2R2=,R23=R2R22=,36设A=1，2，3，4，在AA上定义二元关系R， ,AA ，u,v R u + y = x + v.(1) 证明R 是AA上等价关系.(2)确定由R 引起对AA划分.1证明：R u+y=x-yRu-v=x-yAAu-v=u-vRR是自反随意,AA假如R ，那么u-v=x-yx-y=u-v R R是对称随意,AA假设R,R那么u-v=x-y,x-y=a-bu-v=a-b RR是传递R是AA上等价关系(2) =, , ,
17、 , , 41.设A=1，2，3，4，R为AA上二元关系, a，b，c，d AA , a，bRc，da + b = c + d(1) 证明R为等价关系.(2) 求R导出划分.(1)证明：a，b AA a+b=a+bR R是自反随意,AA设R，那么a+b=c+dc+d=a+b RR是对称随意,AA假设R,R那么a+b=c+d,c+d=x+ya+b=x+y RR是传递R是 AA上等价关系(2)=, , , , , , 43. 对于以下集合与整除关系画出哈斯图:(1) 1,2,3,4,6,8,12,24(2) 1,2,3,4,5,6,7,8,9,10,11,12解: (1) (2)45.以下图是两个
18、偏序集A,R集合表达式. (a) (b)解: (a)A=a,b,c,d,e,f,g R=, (b) A=a,b,c,d,e,f,gR=,46.分别画出以下各偏序集哈斯图,并找出A极大元微小元最大元和最小元.(1)A=a,b,c,d,eR=,IA.(2)A=a,b,c,d,e, R=IA.解: (1) (2)工程 (1) (2)极大元: e a,b,d,e 微小元: a a,b,c,e最大元: e 无最小元: a 无第八章部分课后习题参考答案1 设f :NN,且 f (x)=求f (0), f (0), f (1), f (1), f (0,2,4,6,)，f (4,6,8), f -1(3,5
19、,7).解：f (0)=0, f (0)=0, f (1)=1, f (1)=1, f (0,2,4,6,)=N，f (4,6,8)=2,3,4, f -1 (3,5,7)=6,10,14.4. 推断以下函数中哪些是满射哪些是单射哪些是双射 (1) f:NN, f(x)=x2+2 不是满射，不是单射 (2) f:NN,f(x)=(x)mod 3,x除以3余数 不是满射，不是单射 (3) f:NN,f(x)= 不是满射，不是单射 (4) f:N0,1,f(x)= 是满射，不是单射 (5) f:N-0R,f(x)=lgx 不是满射，是单射 (6) f:RR,f(x)=x2-2x-15 不是满射，不
20、是单射5. 设X=a,b,c,d,Y=1,2,3,f=,推断以下命题真假: (1)f是从X到Y二元关系,但不是从X到Y函数; 对 (2)f是从X到Y函数,但不是满射,也不是单射; 错 (3)f是从X到Y满射,但不是单射; 错 (4)f是从X到Y双射. 错第十章部分课后习题参考答案4推断以下集合对所给二元运算是否封闭：（1） 整数集合Z和一般减法运算。封闭,不满意交换律和结合律，无零元和单位元（2） 非零整数集合Z*和一般除法运算。不封闭（3） 全体实矩阵集合MnR和矩阵加法及乘法运算，其中n2。封闭 均满意交换律，结合律，乘法对加法满意安排律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，
21、零元是零矩阵；4全体实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。不封闭5正实数集合R+和 运算，其中 运算定义为： a，b R+，a b = ab-a-b 不封闭 因为 6 Z+, nZ=nz z Z .nZ关于一般加法和乘法运算。封闭，均满意交换律，结合律，乘法对加法满意安排律加法单位元是0，无零元；乘法无单位元，零元是0；单位元是17A = n2. 运算定义如下： a，b A，a b = b 封闭 不满意交换律，满意结合律，8S = 2x-1xZ+关于一般加法和乘法运算。封闭 均满意交换律，结合律，乘法对加法满意安排律9S = 0,1,S是关于一般加法和乘法运算。 加法不封闭，乘法封闭
22、；乘法满意交换律，结合律10S = x x=2n,nZ+ ,S关于一般加法和乘法运算。加法不封闭，乘法封闭，乘法满意交换律，结合律5对于上题中封闭二元运算推断是否合适交换律，结合律，安排律。 见上题7设 * 为上二元运算，X * Y = min ( x，y ),即x和y之中较小数.(1) 求4 * 6，7 * 3。 4, 3(2)* 在上是否合适交换律，结合律，和幂等律？满意交换律，结合律，和幂等律(3)求*运算单位元，零元及中全部可逆元素逆元。单位元无，零元1, 全部元素无逆元8 为有理数集，*为S上二元运算，, S有 * = 1*运算在S上是否可交换，可结合？是否为幂等？不行交换：*= *可结合：(*)*=*=*(*)=*=(*)*=*(*)不是幂等2*运算是否有单位元，零元？ 假如有请指出，并求S中全部可逆元素逆元。 设是单位元， S ，*= *= 那么=，解=，即为单位。设是零元， S ，*= *= 那么=，无解。即无零元。 S，设是它逆元*= *=