离散数学作业-(2).doc

离散数学作业布置第1次作业（P15）1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p(qr)=0(01)=0 （2）（pr）(qs)=（01）(11)=01 =0 （3）（pqr）(pqr)=（111） (000)=0(4)（ rs）(p q)=（01）(10)=00=11.17 判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则 也是无理数。另外只有6能被2整除，6才能被4整除。”解： p: 是无理数 1 q: 3是无理数 0 r: 是无理数 1 s:6能被2整除 1t: 6能被4整除 0 命题符号化为： p(qr)(ts)的真值为1，所以这一段的论述为真。1.19 用真值表判断下列公式的类型：（4）(pq) (qp)（5）(pr) (p q)（6）(pq) (qr) (pr)解： （4） p q pq q p q p (pq)( q p) 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）公式类型为永真式（方法如上例，最后一列全为1）。第2次作业（P38）2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)解：(1) (pqq) (pq) q) (pq) qp(q q) p0 0所以公式类型为矛盾式(2)（p(pq)）(pr) (p(pq)( pr) ppqr1 所以公式类型为永真式(3) (pq) (pr) (pq) (pr) (pq) (pr) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111P q r pq pr (pq) (pr)0 0 0 1 0 10 0 1 1 0 10 1 0 0 0 00 1 1 0 0 01 0 0 0 0 01 0 1 0 1 11 1 0 0 0 01 1 1 0 1 1 所以公式类型为可满足式2.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)第3次作业（P38）2.5 求下列公式的主析取范式, 并求成真赋值:(1)( pq) (qp)(2) (pq) qr(3)(p (qr) (pqr)(4) (pq) qr解：(1)(pq) (qp)(pq) (qp)pq q pq p (吸收律) (pp)q p(qq)pqpq pq pqm0m2m2m3 m0m2m3成真赋值为 00, 10, 11.(2) (pq) qr (pq) qr (pqr) qr (pqr) (p p) qrpqrp qrpqrm3m7成真赋值为011，111.(3) (p(qr) (pqr)(p(qr) (pqr)p(qr) (pqr)p(qr)(pqr)pqprpqrpq(rr)p(qq)rp(qq) (rr) (pp) q(rr)(pp) (qq) rm0m1m2m3m4m5m6m7, 为重言式.(4) (pq) qr(pq) qr (pq) qr p(q q)r0主析取范式为0, 无成真赋值, 为矛盾式.第4次作业（P38）2.6 求下列公式的主合取范式, 并求成假赋值:(1) (qp) p(2)(pq) (pr)(3)(p(pq) r解：(1) (qp) p(qp) pqp pq00M0M1M2M3这是矛盾式. 成假赋值为 00, 01, 10, 11.(2)(pq) (pr)(pq) pr(pp)(p q)r (p q)r p qrM4, 成假赋值为100.(3)(p(pq) r(p(pq) r(pp)q r1主合取范式为1, 为重言式.第5次作业（P41）2.32 用消解原理证明下述公式是矛盾式:(1) (pq) (pr) (qr) (pr) r(2) (pq) pq)解：(1) (pq) (pr) (qr) (pr) r第一次循环 S0=, S1=pq,pr,qr,pr,r, S2=由pr, pr消解得到输出“no”，计算结束(2) (pq) pq)(pq) p) q)(pq) p) q (pq) p q第一次循环 S0=, S1=pq,p, q, S2=由pq,p消解得到q,由q, q消解得到,输出“no”，计算结束2.33 用消解法判断下述公式是否可满足的:(1) p (pq) q(2) (pq) (pq) (p r)解：(1) p (pq) q第一次循环 S0=, S1=p, pq, q, S2=由p, pq消解得到q,由q, q消解得到,输出“no”，计算结束(2) (pq) (pq) (p r)第一次循环 S0=, S1=pq, pq, p r, S2=由pq, pq消解得到p,由pq, p r消解得到q r,由pq, p r消解得到q r,由p, p r消解得到r,S2=p, q r, q r, r第二次循环 S0=pq, pq, p r, S1=p, q r, q r, r, S2=由pq, q r消解得到pr,由pq, q r消解得到pr,由pq, q r消解得到pr,由p r, p 消解得到r,S2=pr第三次循环 S0=p, q r, q r, r, S1=pr, S2=S2=输出“yes”，计算结束第6次作业（P52）3.6 判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给出)和判断过程(至少给出两种判断方法):(1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三.(2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一.(3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一.(4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二.(5)若今天是星期一, 则明天是星期二或星期三. 今天是星期一. 所以明天是星期二.(6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三.设p: 今天是星期一, q: 明天是星期二, r: 明天是星期三.(1)推理的形式结构为(pr) pr此形式结构为重言式, 即(pr) pr所以推理正确.(2)推理的形式结构为(pq) qp此形式结构不是重言式, 故推理不正确.(3)推理形式结构为(pr) rp此形式结构为重言式, 即(pr) rp故推理正确.(4)推理形式结构为(pq) pq此形式结构不是重言式, 故推理不正确.(5)推理形式结构为(p(qr) )p q它不是重言式, 故推理不正确.(6)推理形式结构为(pr) pr此形式结构为重言式, 即(pr) pr故推理正确.推理是否正确, 可用多种方法证明. 证明的方法有真值表法, 等值演算法. 证明推理正确还可用构造证明法.下面用等值演算法和构造证明法证明(6)推理正确.1. 等值演算法(pr) pr(pr) (rp)pr(pr) (rp)p) r (pr) (rp) p r(pr)(rp)p r (rp)p r吸收律 (rp)（p r）德摩根律1即(pr) pr故推理正确2.构造证明法前提: (pr), p结论: r证明: pr 前提引入 (pr) (rp) 置换 rp 化简律p 前提引入r 拒取式所以, 推理正确.第7次作业（P53-54）3.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 前提引入(pr) (qs) (pq) 合取引入规则rs 构造性二难(rs) (rs) 合取引入规则为矛盾式, 所以推理正确.第8次作业（P65-66）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) $x$y(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)个体域为实数集合R.(b)特定元素 =0.(c)特定函数(x,y)=x-y, x,yR.(d)谓词(x,y): x=y,(x,y): xy, x,yR.给出下列公式在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(x-y=0) (xy), 真值为0.(3) xy(xy) (x-y0), 真值为1.(4) xy(x-y0) (x=y), 真值为0.第9次作业（P79-80）5.5 给定解释I如下: (a) 个体域D=3,4； (b) (x)：(3)=4, (4)=3；(c)(x,y)：(3,3)=(4,4)=0,(3,4)=(4,3)=1. 试求下列公式在I下的真值: (1) xyF(x,y) (2) xyF(x,y) (3) xy(F(x,y)F(f(x),f(y) 解：(1) xyF(x,y) (F(3,3)F(3,4)(F(4,3)F(4,4) (01)(10) 1 (2) xyF(x,y) (F(3,3)F(3,4)(F(4,3)F(4,4) (01)(10) 0 (3) xy(F(x,y)F(f(x),f(y) (F(3,3)F(f(3),f(3) (F(4,3)F(f(4),f(3) (F(3,4)F(f(3),f(4) (F(4,4)F(f(4),f(4) (00)(11)(11)(00) 15.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(t, y) xy(F(x)G(t, y).(3) xF(x, y) xG(x, y) (xF(x, y)xG(x, y)(xG(x, y)xF(x, y) (xF(x, y)uG(u, y)(xG(x, y)vF(v, y)xu(F(x, y)G(u, y)xv(G(x, y)F(v, y)xu(F(x, y)G(u, y)wv(G(w, y)F(v, y)xuwv (F(x, y)G(u, y)(G(w, y)F(v, y)(5)x1F(x1, x2)(F(x1)x2G(x1, x2)x1F(x1, x2)(F(x1)x2G(x1, x2)x1F(x1, x2)x2(F(x1)G(x1, x2)x1F(x1, x3)x2(F(x4)G(x4, x2)x1(F(x1, x3)x2(F(x4)G(x4, x2)x1x2 (F(x1, x3)(F(x4)G(x4, x2)第10次作业（P79-80）5.15 在自然推理系统FL中,构造下面推理的证明:(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)(1)证明: xF(x) y(F(y)G(y)R(y) 前提引入 xF(x) 前提引入 y(F(y)G(y)R(y) 假言推理 (F(c)G(c)R(c) 全称量词消去规则 F(c) 存在量词消去规则 F(c) G(c) 附加 R(c) 假言推理 xR(x) 存在量词引入规则(2) 证明: xF(x) 前提引入 F(c) 存在量词消去规则 x(F(x)(G(a)R(x) 前提引入 F(c)(G(a)R(c) 全称量词消去规则 G(a)R(c) 假言推理 R(c) 化简 F(c)R(c) 合取引入 x(F(x)R(x) 存在量词引入规则(3) 证明: xG(x) 前提引入 xG(x) 置换 G(c) 全称量词消去规则 x(F(x)G(x) 前提引入 F(c)G(c) 全称量词消去规则 F(c) 析取三段论 xF(x) 存在量词引入规则(4) 证明: x(F(x)G(x) 前提引入 F(y)G(y) 全称量词消去规则x(G(x)R(x) 前提引入 G(y) R(y) 全称量词消去规则 xR(x) 前提引入 R(y) 全称量词消去规则 G(y) 析取三段论 F(y) 析取三段论 xF(x) 存在量词引入规则第11次作业（P96）6.4. 设 F 表示一年级大学生的集合, S 表示二年级大学生的集合, M表示数学专业学生的集合, R 表示计算机专业学生的集合, T表示听离散数学课学生的集合, G 表示星期一晚上参加音乐会的学生的集合, H 表示星期一晚上很迟才睡觉的学生的集合. 问下列各句子所对应的集合表达式分别是什么? 请从备选的答案中挑出来.(1)所有计算机专业二年级的学生在学离散数学课.(2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉.(3)听离散数学课的学生都没参加星期一晚上的音乐会.(4)这个音乐会只有大学一, 二年级的学生参加.(5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会.备选答案:TGH GHT SRTHGT TG FSGGFS S-(RM) G GS-(RM)解:(1) SRT(2) H=GT(3) TG=(4) GFS(5) S-(RM) G6.5. 确定下列命题是否为真:(1) (2) (3) (4) (5)a, ba, b, c, a, b, c(6)a, ba, b, c, a, b (7)a, ba, b, a, b(8)a, ba, b, a, b解:(1) 真(2)假(3) 真(4) 真(5) 真(6) 真(7) 真(8) 假第12次作业（P130-131）7.1. 已知 A=,求AP(A).解:AP(A)= ,=, 7.7. 列出集合 A=2, 3, 4上的恒等关系IA, 全域关系EA, 小于或等于关系LA, 整除关系DA.解:IA=,EA=AA=,LA=,DA=,7.12.设A=0, 1, 2, 3, R 是A 上的关系, 且R=0, 0, 0, 3, 2, 0, 2, 1, 2, 3, 3, 223010给出R的关系矩阵和关系图. 解:第13次作业（P131）7.13.设A = 1, 2, 2, 4, 3, 3B = 1, 3, 2, 4, 4, 2求AB, AB, domA, dom(AB), ranA, ranB, ran(AB), fld(AB).解:AB=1,2, 1,3, 2,4, 3,3, 4,2 AB=2,4domA=1,2,3dom(AB)=1,2,3,4ranA=2,3,4ranB=3,4,2ran(AB)=4fld(AB)=1,2,37.15.设A=,求A1,A2,A3,A,A,A,A,A.解:A1=,A2=,A3=,A=,A=, A=,A=,A=7.16.设A=a,b,c,d, R1,R2 为A上的关系, 其中R1=a,a,a,b,b,dR2=a,d,b,c,b,d,c,b求R1R2, R2R1,R12,R23.解:R1R2=a,a,a,c,a,d,R2R1=c,d,R12=a,a,a,b,a,d,R23=b,c,b,d,c,b7.17.设A=a,b,c, 试给出A 上两个不同的关系R1和R2,使得 R12=R1, R23=R2.解:R1=a,a,b,b,R2=b,c,c,b第14次作业（P131-133）7.21. 设A=1，2，,10,定义A上的关系 R=|x,yAx+y=10说明R具有哪些性质并说明理由。解:只有对称性。因为1+110,R,所以R不是自反的；又由于R,因此R不是反自反的；根据xRyx+y =10=yRx ,可知R是对称的；又由于,都是属于R,因此R不是反对称的；,都属于R,如果R是传递的,必有属于R.但这是不成立的,因此R也不是传递的.7.26. 设A=1，2，3，4，5，6，R为A上的关系，R的关系图如图3.13所示：123456解: (1)R=,，,R=, R3= ,. (2)r(R)=, s(R)=, T(R)=,第15次作业（P134-135）7.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)=, , , 7.43.对于下列集合与整除关系画出哈斯图:(1) 1,2,3,4,6,8,12,24(2) 1,2,3,4,5,6,7,8,9,10,11,12解:哈斯图如下图所示: 7.46.分别画出下列各偏序集的哈斯图,并找出A的极大元极小元最大元和最小元.(1)A=a,b,c,d,eR=,IA.(2)A=a,b,c,d,e, R=IA.解: （1）极大元e；极小元a；最大e；最小元a。（2）极大元a,b,d,e；极小元a,b,c,e；没有最大与最小元。第16次作业（P161-135）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 解:(1)不是满射，不是单射(2)不是满射，不是单射(3)不是满射，不是单射(4)是满射，不是单射(5)不是满射，是单射(6)不是满射，不是单射37. 根据自然数的集合定义计算：(1) 36, 25 ;(2)43,31(3)4 , 1 (4)14 ，2解:(1) 36 = 6, 25 = 2;(2)43 =3,31 = 1,2(3)4 = 3, 1 = 0(4)14 = ,2= ,，其中: =, = ,38. 计算下列集合的基数：解:(1)3, (2), (3), (4), (5), (6),第17次作业（P178-180）4判断下列集合对所给的二元运算是否封闭：（1）整数集合Z和普通的减法运算。（2）非零整数集合Z*和普通的除法运算。（3）全体nn实矩阵集合Mn（R）和矩阵加法及乘法运算，其中n2。（4）全体实可逆矩阵集合关于矩阵加法及乘法运算，其中n错误！未找到引用源。2。（5）正实数集合错误！未找到引用源。和错误！未找到引用源。运算，其中错误！未找到引用源。运算定义为：错误！未找到引用源。（6）错误！未找到引用源。关于普通的加法和乘法运算。（7）A = 错误！未找到引用源。n错误！未找到引用源。运算定义如下：错误！未找到引用源。 （8）S = 错误！未找到引用源。关于普通的加法和乘法运算。（9）S = 0,1,S是关于普通的加法和乘法运算。（10）S = 错误！未找到引用源。 ,S关于普通的加法和乘法运算。5对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。解:（1）封闭,不满足交换律和结合律，无零元和单位元（2）不封闭（3）封闭 均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；（4）不封闭（5）不封闭 因为 （6）封闭，均满足交换律，结合律，乘法对加法满足分配律加法单位元是0，无零元；乘法无单位元（），零元是0；单位元是1（7）封闭 不满足交换律，满足结合律，（8）封闭 均满足交换律，结合律，乘法对加法满足分配律（9）加法不封闭，乘法封闭；乘法满足交换律，结合律（10）加法不封闭，乘法封闭，乘法满足交换律，结合律10令S=a，b，S上有四个运算：*，错误！未找到引用源。分别有表10.8确定。 (a) (b) (c) (d)(1)这4个运算中哪些运算满足交换律，结合律，幂等律？(2)求每个运算的单位元，零元以及每一个可逆元素的逆元。解