离散数学第2版答案

《离散数学第2版答案》由会员分享，可在线阅读，更多相关《离散数学第2版答案（13页珍藏版）》请在装配图网上搜索。

1、离散数学第 2 版答案【篇一：离散数学课后习题答案_屈婉玲 (高等教育出版社)】txt16 设 p、q 的真值为 0；r 、 s 的真值为 1，求下列各命题公式的真值。（ 1） p (q r)? 0 (01) ?0（ 2）（ p?r ） ( qs) ? （0?1 ） (1 1) ?0 1?0.（ 3）（ ?p ?q r ）?(p q r) ? （ 1 1 1） ? (0 00)?0(4) （?r s）(p ?q) ? （ 01）(1 0) ?0 0?117 判断下面一段论述是否为真： “?是无理数。并且，如果 3 是无理数，则 2 也是无理数。另外 6 能被 2 整除， 6 才能被 4 整除。

2、 ” 答： p: ? 是无理数 1q: 3 是无理数 0r: 2 是无理数 1s: 6能被2整除 1t: 6能被4整除 0命题符号化为： p (q r)(t s)的真值为 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 (pq) (?q ?p) 0 01111 1 0 11 01111 00 10011 11 001 1所以公式类型为永真式（ 5）公式类型为可满足式（方法如上例）（ 6）公式类型为永真式（方法如上例）第二章部分课

3、后习题参考答案3. 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值 .(2)(p (p q) (p r)(3)(p q) (p r)答： (2) （p (p q) ） (p r)?(?p (p q) (?p r)?p p q r?1 所以公式类型为永真式(3) p qr p q p r （p q） (p r)0 0000 10 0100 10 1010 00 1110 010 010 010 111 111 010 011 111 1所以公式类型为可满足式4. 用等值演算法证明下面等值式：(2)(p q) (p r)?(p (q r)(4)(p ?q) (?p

4、 q)?(p q) ?(p q) 证明（ 2）(p q) (p r)? (?p q) (?p r) ?p (q r)?p(q r)（ 4） (p ?q) (?p q)?(p (?p q) (?q (?p q)?(p ?p) (p q) (?q ?p) (?q q)?1 (p q) ?(p q) 1?(p q) ?(p q)5. 求下列公式的主析取范式与主合取范式，并求成真赋值(1)(?p q) (?qp)(2)?(p q)q r(3)(p (q r) (p qr)解：（1）主析取范式(?p q) (?q?p)?(p?q)?(?q?p)?(?p?q)?(?q?p)? (?p?q)?(?q?p)?

5、(?q?p)?(p?q)?(p?q)? (?p?q)?(p?q)?(p?q)?m0?m2?m3?(0,2,3)主合取范式：(?p q) (?q?p)?(p?q)?(?q?p)?(?p?q)?(?q?p)?(?p?(?q?p)?(?q?(?q?p)?1?(p?q)?(p?q) ? m1?(1)(2) 主合取范式为：?(p q)?q?r?(?p?q)?q?r?(p?q)?q?r?0所以该式为矛盾式.主合取范式为 (0,1,2,3,4,5,6,7)矛盾式的主析取范式为0(3) 主合取范式为：(p?(q?r)(p?q?r)?(p?(q?r)(p?q?r)?(?p?(?q?r)?(p?q?r)?(?p?

6、(p?q?r)?(?q?r)?(p?q?r)?1?1?1所以该式为永真式.永真式的主合取范式为1主析取范式为 (0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统 p 中构造下面推理的证明：(2) 前提： p?q,?(q?r),r结论： ?p(4) 前提： q?p,q?s,s?t,t?r结论： p?q证明：（ 2）?(q?r) 前提引入?q?r 置换q?r 蕴含等值式r 前提引入?q 拒取式p?q 前提引入 p （3） 拒取式证明（ 4）： t?r 前提引入t 化简律q?s 前提引入s?t 前提引入q?t 等价三段论（ q?t ）?(t?q) 置换（ q?t ）

7、化简 q 假言推理q?p 前提引入p假言推理(11)p?q 合取15 在自然推理系统 p 中用附加前提法证明下面各推理：(1)前提： p?(q?r),s?p,q结论： s?r证明s 附加前提引入s?p 前提引入 p 假言推理p?(q?r) 前提引入q?r 假言推理q 前提引入r 假言推理16 在自然推理系统 p 中用归谬法证明下面各推理：(1) 前提： p?q,?r?q,r?s结论： ?p 证明：p 结论的否定引入p? q 前提引入 q 假言推理 r?q 前提引入 r 化简律 r? s 前提引入r 化简律r? r 合取由于最后一步r? r 是矛盾式 ,所以推理正确 .第四章部分课后习题参考答案

8、3. 在一阶逻辑中将下面将下面命题符号化 ,并分别讨论个体域限制为 (a),(b) 条件时命题的真值 :(1)对于任意 x, 均有 2=(x+)(x).(2)存在 x, 使得 x+5=9.【篇二：华东师范大学离散数学章炯民课后习题第2 章答案】设 n1 是奇数，证明 n 整除 (1+?+)(n-1)!2n-1证明：11+?+)(n-1)!=(1?1)?(1?1)?(1?1)(n?1)! 2n-11n?12n?2 22nnn?)(n?1)! n?1n?1n?12(n?2)22111?(n?1)! n?1n?1n?1n?222 (1+ =( =n4 求方程 963x+657y=(963,657)的

9、所有整数解。解：（ 1）由辗转相除法可得到方程的一个解：x0 =-15 ，y0=22设(x?,y?) 也是一个解，则 963x?+657y?=(963,657)于是 963(x?-x0)+657(y?-y0)=0，从而 107(x?-x0)=-73(y?-y0)，所以 107?73(y?-y0) 。又因为 (107,73)=1, 所以 107?(y?-y0)设(y?-y0)=107k ，则 (x?-x0)=-73k ，从而 x?=x0-73k ，y?=y0+107k容易验证，对于任意整数 k， (x0+73k,y0+107k) 满足原方程。所以，原方程有无穷多个解： x=-15-73ky=22

10、+107k其中 k= ,-2,- 1,0,1,2,（2）963x+657y=(963,657) ? 963x-9=-657y?x,y?z ，963x-9=-657y ? ?x?z，963x9 (mod 657)5 设 a、b、 c、 d 是正整数，满足ab=cd 。证明： a4+b4+c4+d4不是素数。 证明：设和 q 是互素的正整数cbq n整除，其中aq=cp ? p?aq ? p?a（ p和q互素）于是，?u?n，使a=pu ? c=qu同理 ?v?n ，使 d=pv ? b=qv从而， a4+b4+c4+d4=(p4+q4)(u4+v4) ? a4+b4+c4+d47 团体操表演过程

11、中，要求队伍在变换成10 行、 15不是素数行、 18 行、 24行时均能成长方形，问需要多少人？解：由题意，所求之数为 10,15,18,24 的倍数， 10,15,18,24 360 ，故需 360k(k0) 人。10 证明：如果p,p+2,p+4都是素数，则p=3 。证明：用反证法，假设p3。p,p+1,p+2是 3 个连续的整数，其中有且仅有一个为p,p+2 是素数，且 p3 ? p+1 是 3 的倍数不妨设 p+1=3k(k?n)。于是， p+4=3(k+1) 必为合数，与条件矛盾。所以， p=311 计算 2400 mod 319。3 的倍数。解：14(2)解同余方程：56x88(

12、mod 96)。解：（ 1） (a,m)=(56,96)=8 ， 8|96 ，方程有解（ 2） a?=56/8=7 ， b?=88/8=11 ，m?=96/8=12（ 3）由辗转相除法可求得 p 和 q 满足 pa?+qm?=1 ， p=-5 ， q=3 特解 x0=p?b?=-5?11（4）解为 x?-5?11+t?12(mod 96) ，t=0,1,?,7 即 x 5,17,29,41,53,65,77,89(mod 96)16(1) 解同余方程组： ?x?3(mod5) x?7(mod9)?解：m1=5 ， m2=9 ， m=45 ， m1=9 ，m2=5?5x?7(mod 12)16(

13、2)解同余方程组 ? 7x?1(mod 10)?解：5x7(mod 12) ? 12?(5x-7) ? 4?(5x-7)且 3?(5x- 7) ? 5x7(mod 4)且 5x7(mod 3) 同余方程 5x7(mod 12) 与同余方程组?5x?7(mod 4) 同解?5x?7(mod 3)?x?3(mod 4) 后者可规约为 ? x?2(mod 3)?类似地，同余方程 7x1(mod 10) 可规约为同余方程组 ? ?x?1(mod 2) ?x?3(mod 5)?x?2(mod 3)?x?2(mod 3)?x?3(mod 4)x?3(mod 4)? 原同余方程组可规约为 ? ，它与同余方程

14、组 ?同解 ?x?3(mod 5)?x?1(mod 2) ?x?3(mod 5)?x?2(mod 3)?x?3(mod 4)求解同余方程组?： ?x?3(mod 5)?m1=3 ， m2=4 ，m3=5 ，m=60 ，m1=20 ，m2=15 ，m3=1220x1(mod 3),15x1(mod 4),12x1(mod 5)的特解：c1=2,c2=3,c3=3*17解同余方程组：x3(mod 8) ， x11(mod 20) ，x1(mod 15) 。解：?x?3(mod 8)?x?3(mod8)?x?11(mod 4)?x?1(mod 3) 原同余方程组与同余方程组 ?x?11(mod 5)

15、 同解，后者可规约为 ?x?1(mod 5)?x?1(mod 5)?x?1(mod 3)?x?3(mod8)?x?1(mod 3)： 求解同余方程组 ?x?1(mod 5)?m1=8 ， m2=3 ，m3=5 ，m=120 ，m1=15 ， m2=40 ， m3=2415x1(mod 8),40x1(mod 3),24x1(mod 5)的特解：c1=7,c2=1,c3=419 *设 m1 和 m2 是正整数， b1 和 b2 是整数。证明一次同余方程组xb1(mod m1) ， xb2(mod m2)有解的充分必要条件是(m1,m2)|(b1-b2)；并且，当此条件成立时，该同余方程组的解可表

16、示为xc(modm1,m2) ，其中0cm1,m2。证明：用反证法，假设p3。（1） ?有解 ? 可设 x 为一个解 ? m1?x-b1， m2?x-b2 ? ?k1,k2?z，使x-b1=k1m1, x-b2=k2m2 ? b2-b1=k1m1-k2m2(m1,m2)|m1, (m1,m2)|m 2 ? (m1,m2)| k1m1-k2m2=(b1-b2)（2） ?(m1,m2)|(b1-b2) ? ?k,s,t?n ，使 (b1-b2)=k(m1,m2)=k(sm1+tm2) 容易验证， x=b1-ksm1 是同余方程组的解 ? 有解（ 3）容易验证， ? 解 x ， ?k?z ，x+km

17、1,m2 也是解 ? 结论补充：1 编写一程序实现 miller-rabin 素性测试算法。2 已知 rsa 密码体制的公钥 (e,n)=(5,35) ，（1）请按本小节例题所示的方式将明文信息“rsa 加”密；（2）请破解出私钥。解：（ 1）明文信息由26 个小写字母构成，数字化编码为字母的序号：a?01 ，r?18 ，s?19 ，明文 “rsa ”?181901取段长为 2，明文 ” 181901 ”分为 3 段： m1=18 ，m2=19 ， m3=01 用公钥 (5,35) 加密得到 3 个密文：c1=m1e mod n =185 mod 35=23c2=m2e mod n =195

18、mod 35=24c3=m3e mod n =015 mod 35=01组合得到密文串：232401（ 2）由公钥： ku=(e,n)=(5,35)得到 n=35 的两个素因数p=5,q=7 ， ?(n)=(p-1)(q-1)=24，e=5 (5,24)=1 ，解同余方程5d 1(mod 24) ，得到唯一解d=5私钥： kr=(d,n)=(5,35)请编写一个高效的指数取模运算算法/*exp_mod.chandle the modexp calculation (ap)%m) using montgomery algorithm (o(logn) */#include stdio.hint

19、expmod(int a, int p, int m)int r;int k;if(p=0) return 1;r=a%m;k=1;while (p1)if (p1)!=0)k=(k*r)%m;r=(r*r)%m;p=1;return (r*k)%m;void main()int a,b,c,r;scanf (%d%d%d,a,b,c);r=expmod(a,b,c);printf (%d%d)%d=%dn,a,b,c,r);/getch();编写一程序实现miller-rabin素性测试算法#include stdio.h#include math.hint powmod(int i,int

20、 d,int n)/模 n 的大数幂乘快速算法int c = 1;/c为余数，保存每次模后的数while(d = 0)if(d % 2 = 0)d = d / 2;i = (i * i) % n;/d是偶数，就先求i 平方的模else d-;c = (c * i) % n;/d是奇数，就与上一次的模相乘后在求模【篇三：离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案】第二版 高等教育出版社课后答案第一章部分课后习题参考答案16 设 p、q 的真值为 0；r 、s 的真值为 1，求下列各命题公式的真值。（ 1） p (q r)? 0 (01) ?0（ 2）（ p?r ） ( qs) ? （

21、0?1 ） (1 1) ?0 1?0.（ 3）（ ?p ?q r ）?(p q r) ? （ 1 1 1） ? (0 00)?0(4) （?r s）(p ?q) ? （ 01）(1 0) ?0 0?117 判断下面一段论述是否为真： “?是无理数。并且，如果 3 是无理数，则 2 也是无理数。另外 6 能被 2 整除， 6 才能被 4 整除。 ” 答： p: ? 是无理数 1q: 3 是无理数 0r: 2 是无理数 1s: 6能被2整除 1t: 6能被4整除 0命题符号化为： p (q r)(t s)的真值为 1，所以这一段的论述为真。19 用真值表判断下列公式的类型：（4） (p q) (?

22、q ?p)（5） (p r) ?(?p ?q)（6）(p q) (q r) (p r)答：（4）p q pq ?q?p?q ?p (pq) (?q ?p) 0 01111 1 0 11 01111 00 10011 11 001 1所以公式类型为永真式（ 5）公式类型为可满足式（方法如上例）（ 6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值 .(1) ?(p qq)(2)(p (p q) (p r)(3)(p q) (p r)答： (2) （p(p q) ） (p r)?(?p (p q) (?p

23、 r)?p p q r?1 所以公式类型为永真式(3) p qr p q p r （p q） (p r)0 0000 10 0100 10 1010 00 1110 010 010 010 111 111 010 011 111 1所以公式类型为可满足式4. 用等值演算法证明下面等值式：(2)(p q) (p r)?(p (q r)(4)(p ?q) (?p q)?(p q) ?(p q)证明（ 2）(p q) (p r)? (?p q) (?p r) ?p (q r)?p(q r)（ 4） (p ?q) (?p q)?(p (?p q) (?q (?p q) ?(p ?p) (p q) (?

24、q ?p) (?q q)?1 (p q) ?(p q) 1?(p q) ?(p q)5. 求下列公式的主析取范式与主合取范式，并求成真赋值(1)(?p q) (?qp)(2)?(p q)q r(3)(p (q r) (p qr)解：（ 1）主析取范式(?p q) (?q?p) ?(p?q)?(?q?p) ?(?p?q)?(?q?p)? (?p?q)?(?q?p)?(?q?p)?(p?q)?(p?q)? (?p?q)?(p?q)?(p?q)?m0?m2?m3?(0,2,3)主合取范式：(?p q) (?q?p)?(p?q)?(?q?p)?(?p?q)?(?q?p)?(?p?(?q?p)?(?q?

25、(?q?p)?1?(p?q)?(p?q) ? m1?(1)(2) 主合取范式为：?(p q)?q?r?(?p?q)?q?r?(p?q)?q?r?0所以该式为矛盾式.主合取范式为 (0,1,2,3,4,5,6,7)矛盾式的主析取范式为0(3) 主合取范式为：(p?(q?r) (p?q?r) ?(p?(q?r) (p?q?r) ?(?p?(?q?r)?(p?q?r) ?(?p?(p?q?r)?(?q?r)?(p?q?r) ?1?1 ?1所以该式为永真式.永真式的主合取范式为1主析取范式为 (0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统 p 中构造下面推理的证明：

26、(2) 前提： p?q,?(q?r),r结论： ?p(4) 前提： q?p,q?s,s?t,t?r结论： p?q证明：（ 2）?(q?r) 前提引入?q?r 置换q?r 蕴含等值式r 前提引入?q 拒取式p?q 前提引入 p （3） 拒取式证明（ 4）： t?r 前提引入 t 化简律q?s 前提引入s?t 前提引入q?t 等价三段论（ q?t ）?(t?q) 置换（ q?t ） 化简 q 假言推理q?p 前提引入p假言推理(11)p?q 合取15 在自然推理系统 p 中用附加前提法证明下面各推理：(1) 前提： p?(q?r),s?p,q结论： s?r证明s 附加前提引入s?p 前提引入 p 假言推理p?(q?r) 前提引入q?r 假言推理 q 前提引入r 假言推理16 在自然推理系统 p 中用归谬法证明下面各推理：(1) 前提： p?q,?r?q,r?s结论： ?p 证明：p 结论的否定引入p? q 前提引入 q 假言推理 r?q 前提引入 r 化简律 r? s 前提引入r 化简律r? r 合取由于最后一步r? r 是矛盾式 ,所以推理正确 .第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化 ,并分别讨论个体域限制为 (a),(b) 条件时命