离散数学屈婉玲版课后题答案.pdf

1.14 将下列 命题符号化.(1)刘晓月跑得快,跳得高.(2)老王是山东人或河北人.(3)因为天气冷,所以我穿了羽绒服.(4)王欢与李乐组成一个小组.(5)李辛与李末是兄弟.(6)王强与刘威都学过法语.(7)他一面吃饭,一面听音乐.(8)如果天下大雨,他就乘班车上班.(9)只有天下大雨,他才乘班车上班.(10)除非天下大雨,他才乘班车上班.(11)下雪路滑,他迟到了.(12)2 与 4 都是素数,这是不对的.(13)“2或 4 是素数,这是不对的”是不对的.(1)pq,其中,p:刘晓月跑得快,q:刘晓月跳得高.(2)pq,其中,p:老王是山东人,q:老王是河北人.(3)pq,其中,p:天气冷,q:我穿了羽绒服.(4)p,其中,p:王欢与李乐组成一个小组,是简单命题.(5)p,其中,p:李辛与李末是兄弟.(6)pq,其中,p:王强学过法语,q:刘威学过法语.(7)pq,其中,p:他吃饭,q:他听音乐.(8)pq,其中,p:天下大雨,q:他乘班车上班.(9)pq,其中,p:他乘班车上班,q:天下大雨.(10)pq,其中,p:他乘班车上班,q:天下大雨.(11)pq,其中,p:下雪路滑,q:他迟到了.(12)(pq)或pq,其中,p:2 是素数,q:4是素数.(13)(pq)或 pq,其中,p:2是素数,q:4是素数.1.19 用真值表判断下列公式的类型:(1)p(pqr)(2)(pq)q(3)(qr)r(4)(pq)(qp)(5)(pr)(pq)(6)(pq)(qr)(pr)(7)(pq)(rs)(1),(4),(6)为重言式.(3)为矛盾式.(2),(5),(7)为可满足式.2.4.用等值演算法证明下面等值式:(1)p(pq)(pq)(3)(pq)(pq)(pq)(4)(pq)(pq)(pq)(pq)(1)(pq)(pq)p (qq)p 1 p.(3)(pq)(pq)(qp)(pq)(qp)(pq)(qp)(pq)(pp)(qq)(pq)(pq)(pq)离散数学习题解 4(4)(pq)(pq)(pp)(pq)(qp)(qq)(pq)(pq)2.7.求下列公式的主析取范式,再用主析取范式求合取范式:(1)(pq)r (2)(pq)(qr)(1)m1m3m5m6m7M0M2M4(2)m0m1m3m7M2M4M5M6 2.27.某电路中有一个灯泡和三个开关 A,B,C.已知在且仅在下述四种情况下灯亮:(1)C的扳键向上,A,B 的扳键向下.(2)A的扳键向上,B,C的扳键向下.(3)B,C的扳键向上,A的扳键向下.(4)A,B的扳键向上,C的扳键向下.设 F 为 1 表示灯亮,p,q,r分别表示 A,B,C的扳键向上.(a)求 F 的主析取范式.(b)在联结词完备集,上构造 F.(c)在联结词完备集,上构造 F.(a)由条件(1)-(4)可知,F 的主析取范式为 F(pqr)(pqr)(pqr)(pqr)m1m4m3m6 m1m3m4m6(b)先化简公式 F(pqr)(pqr)(pqr)(pqr)q(pr)(pr)q(pr)(pr)(qq)(pr)(pr)(pr)(pr)(pr)(pr)(已为,中公式)(c)F(pr)(pr)(pr)(pr)(pr)(pr)(pr)(pr)(rp)(pr)(已为,中公式)3.14.在自然推理系统 P 中构造下面推理的证明:(1)前提:p(qr),p,q 结论:rs(2)前提:pq,(qr),r 结论:p(3)前提:pq 结论:p(pq)(4)前提:qp,qs,st,tr 结论:pq(5)前提:pr,qs,pq 结论:rs(6)前提:pr,qs,pq 结论:t(rs)离散数学习题解 5(1)证明:(2)证明:(qr)前提引入 qr 置换 r 前提引入 q 析取三段论 pq 前提引入 p 拒取式 (3)证明:pq 前提引入 pq 置换 (pq)(pp)置换 p(pq)置换 p(pq)置换 也可以用附加前提证明法,更简单些.(4)证明:st 前提引入 (st)(ts)置换 ts 化简 tr 前提引入 t 化简 s 假言推理 qs 前提引入 (sq)(qs)置换 sq 化简 q 假言推理 p(qr)前提引入 p 前提引入 qr 假言推理 q 前提引入 r 假言推理 rs 附加律 11 q p 前提引入 12 p 11假言推理 13 pq 12合取 (5)证明:pr 前提引入 qs 前提引入 pq 前提引入 p 化简 q 化简 r 假言推理 s 假言推理 rs 合取 (6)证明:t 附加前提引入 pr 前提引入 pq 前提引入 p 化简 r 析取三段论 rs 附加 说明:证明中,附加提前 t,前提qs没用上.这仍是正确的推理.离散数学习题解 63.15.在自然推理系统 P 中用附加前提法证明下面各推理:(1)前提:p(qr),sp,q 结论:sr(2)前提:(pq)(rs),(st)u 结论:pu(1)证明:s 附加前提引入 sp 前提引入 p 假言推理 p(qr)前提引入 qr 假言推理 q 前提引入 r 假言推理 (2)证明:P 附加前提引入 pq 附加 (pq)(rs)前提引入 rs 假言推理 S 化简 st 附加 (st)u 前提引入 u 假言推理 3.16.在自然推理系统 P 中用归谬法证明下面推理:(1)前提:pq,rq,rs 结论:p(2)前提:pq,pr,qs 结论:rs(1)证明:P 结论否定引入 pq 前提引入 q 假言推理 rq 前提引入 r 析取三段论 rs 前提引入 r 化简 rr 合取 为矛盾式,由归谬法可知,推理正确.(2)证明:(rs)结论否定引入 pq 前提引入 pr 前提引入 qs 前提引入 rs 构造性二难 (rs)(rs)合取 为矛盾式,所以推理正确.3.17.P53 17.在自然推理系统 P 中构造下面推理的证明:只要 A 曾到过受害者房间并且 11 点以前没用离开,A 就犯了谋杀罪.A 曾到过受害者房间.如果 A 在11 点以前离开,看门人会看到他.看门人没有看到他.所以 A 犯了谋杀罪.离散数学习题解 7令 p:A 曾到过受害者房间;q:A 在 11 点以前离开了;r:A 就犯了谋杀罪;s:看门人看到 A.前提:pq r,p,q s,s;结论:r.证明:s 前提引入 q s 前提引入 q 拒取 p 前提引入 pq 合取 pq r 前提引入 r 假言推理 4.4.在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.(3)乌鸦都是黑色的.(4)有的人天天锻炼身体.没指定个体域,因而使用全总个体域.(1)x(F(x)G(x)或x(F(x)G(x),其中,F(x):x 为有理数,G(x):x 能表示成分数.(2)x(F(x)G(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)x(F(x)G(x),其中,F(x):x是人,G(x):x 天天锻炼身体.4.5.在一阶逻辑中将下列命题符号化:(1)火车都比轮船快.(2)有的火车比有的汽车快.(3)不存在比所有火车都快的汽车.(4)“凡是汽车就比火车慢”是不对的.因为没指明个体域,因而使用全总个体域 (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)H(x,y)或x(F(x)y(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)或xy(F(x)G(y)H(x,y),其中,F(x):x是汽车,G(y):y是火车,H(x,y):x 比 y 慢.4.9.给定解释 I 如下:(a)个体域 DI为实数集合?.(b)DI中特定元素a=0.(c)特定函数f(x,y)=xy,x,yDI.(d)特定谓词F(x,y):x=y,G(x,y):xy,x,yDI.说明下列公式在 I 下的含义,并指出各公式的真值:(1)xy(G(x,y)F(x,y)(2)xy(F(f(x,y),a)G(x,y)(3)xy(G(x,y)F(f(x,y),a)(4)xy(G(f(x,y),a)F(x,y)(1)xy(xyxy),真值为 1.(2)xy(xy=0)xy),真值为 0.(3)xy(xy)(xy0),真值为 1.(4)xy(xy0)(x=y),真值为 0.离散数学习题解 84.11.判断下列各式的类型:(1)F(x,y)(G(x,y)F(x,y).(3)xyF(x,y)xyF(x,y).(5)xy(F(x,y)F(y,x).(1)是命题重言式 p (q p)的代换实例,所以是永真式.(3)在某些解释下为假(举例),在某些解释下为真(举例),所以是非永真式的可满足式.(5)同(3).5.8.在一阶逻辑中将下列命题符号化,要求用两种不同的等值形式.(1)没有小于负数的正数.(2)相等的两个角未必都是对顶角.(1)令 F(x):x 小于负数,G(x):x 是正数.符合化为:x(F(x)G(x)x(G(x)G(x).(2)令 F(x):x 是角,H(x,y):x 和 y 是相等的,L(x,y):x 与 y 是对顶角.符合化为:xy(F(x)F(y)H(x,y)L(x,y)xy(F(x)F(y)H(x,y)L(x,y)x(F(x)(y(F(y)H(x,y)L(x,y).5.12.求下列各式的前束范式.(1)xF(x)yG(x,y);(3)xF(x,y)xG(x,y);(5)x1F(x1,x2)(F(x1)x2G(x1,x2).前束范式不是唯一的.(1)xF(x)yG(x,y)x(F(x)yG(x,y)xy(F(x)G(x,y).(3)xF(x,y)xG(x,y)(xF(x,y)xG(x,y)(xG(x,y)xF(x,y)(x1F(x1,y)x2G(x2,y)(x3G(x3,y)x4F(x4,y)x1x2(F(x1,y)G(x2,y)x3x4(G(x3,y)F(x4,y)x1x2x3x4(F(x1,y)G(x2,y)(G(x3,y)F(x4,y).5.15.在自然推理系统 F 中构造下面推理的证明:(1)前提:xF(x)y(F(y)G(y)R(y),xF(x)结论:xR(x).(2)前提:x(F(x)(G(a)R(x),xF(x)结论:x(F(x)R(x)(3)前提:x(F(x)G(x),xG(x)结论:xF(x)(4)前提:x(F(x)G(x),x(G(x)R(x),xR(x)结论:xF(x)5.24.在自然推理系统 F 中,构造下面推理的证明:每个喜欢步行的人都不喜欢骑自行车.每个人或者喜欢骑自行车或者喜欢乘汽车.有的人不喜欢乘汽车,所以有的人不喜欢步行.(个体域为人类集合)离散数学习题解 9令 F(x):x 喜欢步行,G(x):x 喜欢骑自行车,H(x):x 喜欢乘汽车.前提:x(F(x)G(x),x(G(x)H(y),xH(x).结论:xF(x).x(G(x)H(y)前提引入 G(c)H(c)UI xH(x)前提引入 H(c)UI G(c)析取三段 x(F(x)G(x)前提引入 F(c)G(c)UI F(c)拒取 xF(x)EG 8.5.设 X=a,b,c,d,Y=1,2,3,f=a,1,b,2,c,3,判断以下命题的真假(1)f 是从 X 到 Y 的二元关系,但不是从 X 到 Y 的函数;(2)f 是从 X 到 Y 的函数,但不是从满射,也不是单射(3)f 是从 X 到 Y 的满射,但不是从单射;(4)f 是从 X 到 Y 的双射.8.12.设 f:ST,证明(1)f(AB)f(A)f(B),其中 A,B S.(2)举出反例说明等式 f(AB)=f(A)f(B)不是永远为真的.(3)说明对于什么函数,上述等式为真.8.16.16.设 A=a,b,c.R 为 A 上的等价关系,且 R=a,b,b,aIA 求自然映射 g:AA/R.8.21.21.设 f:?,f(x)=x,x+1.(1)说明 f 是否为单射和满射,为什么(2)f 的反函数是否存在,如果存在,求出 f 的反函数;(3)求 ran f.(1)f 是单射的,x1,x2?,若 x1 x2,则 f(x1)=x1,x1+1 f(x2)=x2,x2+1.F不是满射的,因为若0,0 ran f,则x?,使得 f(x)=x,x+1=0,0,而这是不可能的.(2)因为 f=x,x,x+1|x?是单射,它的逆关系 f 1=x,x+1,x|x?是函数,是从 ran f 到 dom f=?的双射函数.但 f 1不是?的函数,因为 dom f 1=ran f?.(3)ran f=n,n+1n?.19用真值表判断下列公式的类型：（4）(pq)(qp)（5）(pr)(pq)（6）(pq)(qr)(pr)答：答：（4）pqpqqpqp(pq)(qp)0011111011011110010011110011所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）