离散数学作业(2)分解

1、实用文案离散数学作业布置第 1 次作业（ P15）1.16设 p、q 的真值为 0； r 、 s 的真值为 1，求下列各命题公式的真值。解：（1）p(q r)=0 (0 1)=0（2）（p? r ） ( q s)= （0? 1） (1 1)=0 1 =0（3）（ p qr ）? (p q r)= （1 11）?(0 0 0)=0(4) （ r s） (p q)= （01） (1 0)=0 0=11.17判断下面一段论述是否为真： “是无理数。 并且，如果 3 是无理数，则2也是无理数。另外只有6 能被 2 整除， 6 才能被 4 整除。”解：p:是无理数1q: 3是无理数0r:2 是无理数1s

2、: 6能被2整除 1t: 6 能被4整除 0命题符号化为： p (q r) (t s) 的真值为 1，所以这一段的论述为真。1.19用真值表判断下列公式的类型：（ 4） (p q) ( q p)（ 5） (p r) ? ( p q)（ 6） (p q)(q r) (p r)解：（ 4）p q pq q p q p (p q) ( q p)0011111011011110010011110011所以公式类型为永真式，最后一列全为 1（ 5）公式类型为可满足式（方法如上例） ，最后一列至少有一个 1（ 6）公式类型为永真式（方法如上例，最后一列全为1）。第 2 次作业（ P38）2.3 用等值演算

3、法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值 .(1)(p qq)(2)(p (p q) (p r)(3)(p q) (p r)解： (1)(p qq)( (p q) q)(p q) qp (q q)p 00所以公式类型为矛盾式(2) （p(p q) ） (p r) ( p (p q) ( p r) pp q r 1所以公式类型为永真式(3) (pq) (p r)(p q) (p r)( p q) (p r)标准实用文案易见 , 是可满足式 ,但不是重言式 .成真赋值为 : 000,001, 101, 111Pqrp qpr ( p q) (p r)000101001

4、101010000011000100000101011110000111011所以公式类型为可满足式2.4 用等值演算法证明下面等值式：(2) ( (pq) (p r) )(p (q r)(4)(p q) ( pq)(p q) (p q)证明（ 2）(p q) (p r)( pq) ( pr)p (q r)p (q r)（ 4） (p q) ( p q)(p ( pq)( q( pq) )(p p) (p q) ( q p) ( qq)1 (p q) ( p q) 1(p q) (p q)第 3 次作业（ P38）2.5 求下列公式的主析取范式 , 并求成真赋值 :(1)( pq) ( qp)

5、(2) ( pq) q r(3)(p(q r)(p qr)(4) (p q) q r解：(1)( pq) ( q p) (p q) ( qp) p q q pq p(吸收律 )( pp) q p( qq)p qp q p q pqm0m2m2 m3m0m2m3成真赋值为 00, 10, 11.(2) ( pq) q r (p q) qr (p qr) qr(p qr) ( p p) qr标准实用文案p q r p q r p qrm3m7成真赋值为 011， 111.(3) (p (q r)(p q r)(p (q r)(p qr)p (q r) (p q r) p ( q r) (p q r

6、) p q p r p qr p q(r r) p(q (p p) q(r r) (pm0m1m2 m3m4m5m6 m7,(4) (p q) q r ( pq) qr (p q) q r p ( q q) r q) r p(q q) (r r) p) (q q) r为重言式 .0主析取范式为0,无成真赋值 ,为矛盾式 .第 4 次作业（ P38）2.6求下列公式的主合取范式,并求成假赋值 :(1) (q p) p(2)(p q) ( pr)(3)(p (p q) r解：(1) (q p) p ( q p) p q p pq 0 0M0M1M2M3这是矛盾式 .成假赋值为 00, 01, 10

7、, 11.(2)(p q) ( pr)(p q) pr(p p) ( p q) r( p q) r p qrM4,成假赋值为 100.(3)(p (p q) r( p (p q)r( p p) q r1主合取范式为1,为重言式 .标准实用文案第 5 次作业（ P41）2.32用消解原理证明下述公式是矛盾式:(1) (pq) ( pr) ( q r) (p r)r(2)(p q) pq)解：(1) (pq) ( pr) ( q r) (p r)r第一次循环S 0=, S 1= p q, pr, q r,p r,r , S 2=由 pr, p r 消解得到输出“ no”，计算结束(2)(p q)

8、pq)( (p q) p) q)(p q) p) q(p q) p q第一次循环S 0=, S 1=pq, p,q, S 2=由 pq, p 消解得到 q,由 q,q 消解得到 ,输出“ no”，计算结束2.33用消解法判断下述公式是否可满足的:(1) p ( p q) q(2) (p q) (p q) ( p r)解：(1) p ( p q) q第一次循环 S 0=, S 1=p, p q, q , S 2=由 p, p q 消解得到 q, 由 q, q 消解得到 ,输出“ no”，计算结束(2) (p q) (p q) ( p r)第一次循环 S 0=, S 1=pq, p q, p r

9、, S 2=由 pq, p q 消解得到 p,由 pq, p r 消解得到 q r,由 p q, p r 消解得到 q r, 由 p, p r 消解得到 r,S2=p, qr,q r, r第二次循环S 0=pq, p q, p r , S 1= p, qr,q r, r,S2=由 pq, q r 消解得到 pr, 由 p q, q r 消解得到 pr, 由 p q, q r 消解得到 pr,由 p r, p消解得到 r,S2=p r 第三次循环S 0=p, q r, q r, r , S 1=pr , S 2=标准实用文案S2=输出“ yes”，计算结束第 6 次作业（ P52）3.6 判断下

10、面推理是否正确 . 先将简单命题符号化 , 再写出前提 , 结论 , 推理的形式结构 ( 以蕴涵式的形式给出 ) 和判断过程 ( 至少给出两种判断方法):(1) 若今天是星期一 , 则明天是星期三；今天是星期一. 所以明天是星期三 .(2) 若今天是星期一 , 则明天是星期二；明天是星期二. 所以今天是星期一 .(3) 若今天是星期一 , 则明天是星期三；明天不是星期三. 所以今天不是星期一 .(4) 若今天是星期一 , 则明天是星期二；今天不是星期一. 所以明天不是星期二 .(5) 若今天是星期一 , 则明天是星期二或星期三 . 今天是星期一 . 所以明天是星期二 .(6) 今天是星期一当且

11、仅当明天是星期三；今天不是星期一.所以明天不是星期三.设 p: 今天是星期一 , q: 明天是星期二 , r: 明天是星期三 .(1) 推理的形式结构为(p r) pr此形式结构为重言式 , 即(p r)pr所以推理正确 .(2) 推理的形式结构为(p q) qp此形式结构不是重言式 ,故推理不正确 .(3) 推理形式结构为(p r) r p此形式结构为重言式 , 即(p r) rp故推理正确 .(4) 推理形式结构为(p q) p q此形式结构不是重言式 , 故推理不正确 .(5) 推理形式结构为(p (q r) ) p q它不是重言式 ,故推理不正确 .(6) 推理形式结构为(p ? r)

12、 p r此形式结构为重言式 , 即 (p ? r) p r故推理正确 .推理是否正确 , 可用多种方法证明 . 证明的方法有真值表法 , 等值演算法 . 证明推理正确还可用构造证明法 .下面用等值演算法和构造证明法证明 (6) 推理正确 .1. 等值演算法(p ? r) p r(p r) (r p) p r( p r)( r p) p) r标准实用文案 ( p r) ( r p) p r (p r) (r p) p r(r p) p r吸收律(r p) （ p r ） 德摩根律1即 (p ?r) pr故推理正确2. 构造证明法前提 : (p ?r),p结论 : r证明 : p ? r前提引入

13、(pr) (rp)置换 r p化简律 p前提引入 r拒取式所以 ,推理正确 .第 7 次作业（ P53-54）3.15在自然推理系统 P 中用附加前提法证明下面各推理 :(1) 前提 : p(q r), sp, q结论 : s r(2) 前提 : (pq) (rs), (s t) u结论 : p u(1) 证明 : s附加前提引入 s p前提引入 p假言推理 p (q r)前提引入 q r假言推理 q前提引入 r假言推理(2) 证明 : P附加前提引入 p q附加 (p q) (r s)前提引入 r s假言推理S化简 s t附加 (s t) u前提引入 u假言推理3.16在自然推理系统P 中用

14、归谬法证明下面推理:(1) 前提 : p q, r q, r s标准实用文案结论 : p(2) 前提 : p q, p r, q s结论 : r s(1) 证明 : P结论否定引入 p q前提引入 q假言推理 r q前提引入 r析取三段论 r s前提引入 r化简规则 r r合取引入规则为矛盾式 , 由归谬法可知 ,推理正确 .(2) 证明 : (r s)结论否定引入 p q前提引入 p r前提引入 q s前提引入 (p r) (q s) (p q)合取引入规则 r s构造性二难 (r s) (r s)合取引入规则为矛盾式 ,所以推理正确 .第 8 次作业（ P65-66）4.5 在一阶逻辑中将

15、下列命题符号化 :(1) 火车都比轮船快 .(2) 有的火车比有的汽车快 .(3) 不存在比所有火车都快的汽车 .(4) “凡是汽车就比火车慢”是不对的 .解：因为没指明个体域 , 因而使用全总个体域(1)xy F xG y)H x,y)( () (H xyx 比y 快其中,F x):x 是火车,G y):y 是轮船):.(, ( ,(2) x y( F( x) G( y) H( x, y)其中,F x):x是火车,G y):y是汽车,H xy):x比y 快.( ,(3)?x( F( x) y( G( y)H( x, y)或?x( F( x)? y( G( y) H( x, y)H xyx 比

16、y快其中 ,F x):x 是汽车,G y):y 是火车,):.(4)?x?y( F( x) G( y)H( x, y)或? x? y( F( x) G( y) H( x, y) )H xyx 比 y慢其中 ,F x):x 是汽车,G y):y 是火车):.(, (,4.9给定解释 I如下 :(a) 个体域为实数集合 R.(b) 特定元素 a =0.标准实用文案(c)x,y)=xy,x,yR特定函数 f (.d谓词F ( x, y):x=y,G ( x, y):x<y,x, yR.( )给出下列公式在 I下的解释 ,并指出它们的真值 :(1)? ?x?yG x,y)F xy)(,(2)?

17、?x?y( F( f ( x, y), a)G( x, y)(3)? ?x?yG x,y)F f(x,y),a)(4)? ?x?yG f(x,y),aF x,y)()(解：x?y( x<y xy),(1)? ?真值为 1.(2)? ?x?y( x-y =0)x<y) ),真值为 0.(3)? ?x?y(xy)(xy0),真值为1.xyx<yxy真值为(4)? ?(<0)(0.= ),第 9 次作业（ P79-80）5.5给定解释 I如下 :(a)个体域 D=3,4 ；(b)f (x) ： f (3)=4,f(4)=3 ；(c)F (x,y)： F (3,3)=F (4,

18、4)=0,F (3,4)= F (4,3)=1.试求下列公式在I 下的真值 :(1) ? x? yF(x,y)(2) ? x? yF(x,y)(3) ? x? y(F(x,y) F(f(x),f(y)解：(1)? x? yF(x,y)(F(3,3)F(3,4)(F(4,3)F(4,4)(0 1) (1 0)1(2)? x? yF(x,y)(F(3,3)F(3,4)(F(4,3)F(4,4)(0 1) (1 0)0(3)? x? y(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

19、) F(f(4),f(4)(00) (1 1) (1 1) (0 0)15.12求下列各式的前束范式 .(1)?xF(x) ? yG(x, y)(3)?xF(x, y) ? ? xG(x, y)(5)? x1F(x 1, x 2) (F(x 1) ? x2G(x1 , x 2).标准实用文案解：前束范式不是唯一的 .(1) ? xF(x) ? yG(x, y)? x (F(x) ? yG(t, y)? x? y(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,

20、y)? uG(u, y)( ? xG(x, y)? vF(v, y)? x? u(F(x, y)G(u, y)? x? v(G(x, y)F(v, y)? x? u(F(x, y)G(u, y)? w? v(G(w, y)F(v, y)? x? u? w? v (F(x, y) G(u, y)(G(w, y) F(v, y)(5) ? x1 F(x 1, x 2) (F(x 1) ? x2 G(x1, x 2)? x1F(x 1, x 2) (F(x 1 ) ? x2 G(x1, x 2 )? x1F(x 1, x 2) ? x2(F(x 1) G(x1, x 2 )? x1F(x 1, x

21、3) ? x2(F(x 4) G(x4, x 2 )? x1(F(x 1, x 3) ? x2(F(x 4) G(x4, x 2)? x1? x2 (F(x 1, x 3) (F(x 4) G(x4, x 2)第 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)结论 :

22、? 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

23、(c)假言推理 R(c)化简 F(c)R(c)合取引入标准实用文案 ? x(F(x) R(x)(3) 证明 : ? xG(x) ? x G(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)存在量词引入规则前提引入置换全称量词消去规则前提引入全称量词消去规则析取三段论存在量词引入规则前提引入全称量词消去规则前提引入全称量词消去规则前提引入全称量词消去规则析取三段论析取三段论存在量词引

24、入规则第 11 次作业（ P96）6.4. 设 F 表示一年级大学生的集合 , S 表示二年级大学生的集合 , M 表示数学专业学生的集合 , R 表示计算机专业学生的集合 , T 表示听离散数学课学生的集合 , G 表示星期一晚上参加音乐会的学生的集合 , H 表示星期一晚上很迟才睡觉的学生的集合 . 问下列各句子所对应的集合表达式分别是什么 ? 请从备选的答案中挑出来 .(1) 所有计算机专业二年级的学生在学离散数学课 .(2) 这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉 .(3) 听离散数学课的学生都没参加星期一晚上的音乐会 .(4) 这个音乐会

25、只有大学一 , 二年级的学生参加 .(5) 除去数学专业和计算机专业以外的二年级学生都去参加了音乐会 . 备选答案 :T GH GH T SR THGT TG FS GG FS S-(R M)G G S-(RM)解 :(1) SR T(2) H=GT(3) TG=(4) G FS(5) S-(RM) G标准实用文案6.5.确定下列命题是否为真 :(1)(2) (3) (4) (5)a, ba, b, c, a, b, c(6)a, b a, b, c, a, b (7)a, ba, b, a, b(8)a, b a, b, a, b解 :(1)真(2) 假(3)真(4)真(5)真(6)真(7)

26、真(8)假第 12 次作业（ P130-131）7.1.已知 A=,求 A×P(A).解 :A×P(A)= ,×,=<,>,< ,>,<,>,<,>,<,>,<,>,<,>,<,>7.7.列出集合 A=2, 3, 4上的恒等关系AA小于或等于关系A整除关系I ,全域关系 E ,L ,DA.解 :I A2,2,3,3,4,4=EA A×A2,2,2,3,2,4,3,2,3,3,3,4,4,2,=4,3, 4,4LA2,2,2,3,2,4,3,3,3,4,4,4=

27、DA2,2,2,4,3,3,4,4=7.12.设 A=0, 1, 2, 3, R是A 上的关系 ,且R=? 0, 0?, ?0, 3? , ?2,0 ?, ?2,1?,?2,3?,?3,2?给出 R的关系矩阵和关系图 .解 :10010000011101001023第 13 次作业（ P131）7.13. 设A=?1, 2? ,? 2,4?,?3,3 ?B=?1, 3? ,? 2,4?,?4,2 ?求AB, A B, dom A, dom(A B), ranA, ranB, ran(AB), fld(A- B).解: A B=? 1,2? ,? 1,3? ,? 2,4?, ?3,3? ,? 4

28、,2? A B=? 2,4 ? domA=1,2,3dom(A B)=1,2,3,4ranA=2,3,4ranB=3,4,2ran(A B)=4fld(A -B)=1,2,3标准实用文案7.15.设A=?,?,?,?,?求A-1 ,A 2,A 3,A ? ? ,A ? ,A ? ? ,A ? ? ,A ? .解 :A-1=? ? , ? , ? ? ,? ? ,? ? ,A2=? ? ,? , ? ? ,A3=? ,A?=?,?,?,A? = ? , ? ,A?=?,A?=?,?,A ? = ?7.16. 设A=a,b,c,d, R1,R2为 A上的关系 ,其中R1= ? a,a ? , ?

29、a,b ? , ? b,d ? R2= ? a,d ? , ? b,c ? , ? b,d ? , ? c,b ? 2 3求R1 R2, R 2R1,R1 ,R 2 .解 :R1R2 = ? a,a ? , ? a,c ? , ? a,d ? ,R2R1 = ? c,d ? ,R12= ? a,a ? , ? a,b ? , ? a,d ? ,3R2 = ? b,c ? , ? b,d ? , ? c,b ? 7.17. 设A=a,b,c,试给出 A 上两个不同的关系R1和R2 , 使得 R1 2=R1, R 2 3 =R2.解 :R1= ? a,a ? , ? b,b ? ,R2= ? b,

30、c ? , ? c,b ? 第 14 次作业（ P131-133）7.21. 设 A=1， 2， ,10, 定义 A上的关系R=<x,y>|x,yAx+y=10说明 R具有哪些性质并说明理由。解 : 只有对称性。因为 1+110,<1,1> R, 所以 R不是自反的；又由于 <5,5> R, 因此 R不是反自反的；根据 xRy? x+y =10=>yRx , 可知 R是对称的；又由于<1,9>,<9,1> 都是属于 R,因此 R不是反对称的； <1,9>,<9,1> 都属于 R, 如果 R是传递的 , 必

31、有 <1,1> 属于 R. 但这是不成立的 , 因此 R也不是传递的 .7.26. 设 A=1， 2， 3， 4， 5， 6 ，R为A上的关系， R的关系图如图 3.13 所示：162354解 :(1)R=<1,5>,<2,5>,<3,1>， <3,3>,<4,5>R =<3,3>,<3,1>,<3,5>, R3= <3,3>,<3,1>,<3,5>.(2)r(R)=<1,1>,<1,5> ,<2,2>, <2

32、,5>, <3,3>, <3,1> ,<4,4>, <4,5> ,<5,5>,<6,6>标准实用文案s(R)=<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4> T(R)=<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>第 15 次作业（ P134-135）7.4

33、1. 设 A=1，2，3，4 ，R为 A A 上的二元关系 ,a，b，c，dAA ,a，bRc，da + b = c + d(1)证明 R 为等价关系 .(2)求 R 导出的划分 .(1) 证明：<a，bAAa+b=a+b <a,b>R<a,b> R是自反的任意的 <a,b>,<c,d> A× A设 <a,b>R<c,d> ，则 a+b=c+d c+d=a+b <c,d>R<a,b> R是对称的任意的 <a,b>,<c,d>,<x,y> A

34、5; A若 <a,b>R<c,d>,<c,d>R<x,y>则 a+b=c+d,c+d=x+y a+b=x+y <a,b>R<x,y> R是传递的 R是 A ×A上的等价关系(2)=<1,1>,<1,2>,<2,1>,<1,3>,<2,2>,<3,1>,<1,4>,<4,1>,<2,3>,<3,2> , <2,4>,<4,2>,<3,3>, <3,4>

35、;,<4,3>, <4,4>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,R>的哈斯图 , 并找出 A 的极大元 极小元 最大元和最小元 .(1)A=a,b,c,d,eR=<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>I A.(2)A=a,b,c,d,e,R=&l

36、t;c,d>IA.解 :edbcdeaabc（ 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)=1x，若 为偶数0x0，若 x为奇数(4) f:N0,1,f(x)=1，若 x为偶数(5) f:N-0R,f(x)=lgx标准实用文案(6) f:RR,f(x)=x 2

37、 -2x-15解 :(1) 不是满射，不是单射(2) 不是满射，不是单射(3) 不是满射，不是单射(4) 是满射，不是单射(5) 不是满射，是单射(6) 不是满射，不是单射37. 根据自然数的集合定义计算：(1)3 6,2 5;(2)4 3,3 1(3) 4 , 1(4)1 ×4 ，2解 :(1) 36=6,25=2;(2)43=3,31 = 1,2(3)4=3, 1=0(4)1×4= <0,0>,<0,1>,<0,2>,<0,3>,2= , , , ，其中:=<0,0>,<1,0> = <0,0>,<1,1>38. 计算下列集合的基数：解 :(1)3, (2), (3), (4), (5), (6),第 17 次作业（ P178-180）4判断下列集合对所给的二元运算是否封闭：（ 1）整数集合 Z 和普通的减法运算。（ 2）非零整数集合 Z*和普通的除法运算。（ 3）全体 n× n 实矩阵集合 Mn（R）和矩阵加法及乘法运算，其中 n2。（ 4）全体 nn 实可逆矩阵集合关于矩阵加法及乘法运算，其中n 错误！未找到引用源。 2。（ 5）正实数集合 错误！未找到引用源。 和错误！未找到引用源。 运算，其中 错