《离散数学课件thewholeexercisesfromchapter1tochapter4discretemathematics》由会员分享，可在线阅读，更多相关《离散数学课件thewholeexercisesfromchapter1tochapter4discretemathematics（16页珍藏版）》请在金锄头文库上搜索。
1、离散数学布置的课后作业习题解答作者：黄海平第一次布置的作业：P8 1-1,1-2习题(1) 指出下列语句哪些是命题，哪些不是命题，如果是命题，指出它的真值。a) 离散数学是计算机科学系的一门必修课。 命题，Tb) 计算机有空吗？ 不是命题c) 明天我去看电影。 命题，根据主体情况可能为T或者Fd) 请勿随地吐痰！ 不是命题e) 不存在最大质数。 命题，Tf) 如果我掌握了英语、法语，那么学习其它欧洲语言就容易得多。 命题，Tg) 9+512 命题，Fh) x=3 不是命题i) 我们要努力学习。 不是命题，是陈述句，但是没有真假值(3) 设P表示命题“天下雪”，Q表示命题“我将去镇上”，R表示命
2、题“我有时间”，以符号形式写出下列命题。a) 如果天不下雪和我有时间，那么我将去镇上。 b) 我将去镇上，仅当我有时间时。 c) 天不下雪。 d) 天下雪，那么我不去镇上。 (5) 将下列命题符号化。a) 小李一边看书，一边听音乐。 P: 小李看书。 Q: 小李听音乐。 d) 如果a和b是偶数，则a+b是偶数。 写法一： P: a和b是偶数。 Q: a+b是偶数。 写法二： P: a是偶数。 Q: b是偶数。 R: a+b是偶数。 f) 停机的原因在于语法错误或程序错误。 P: 停机。 Q: 语法错误。 R: 程序错误。 P12 1-3习题(5) 试把原子命题表示为P、Q、R等，然后用符号译出
3、下列各句子。a) 或者你没有给我写信，或者它在途中丢失了。 P: 你给我写信。 Q: 信在途中丢失了。 或者 d) 如果你来了，那末他唱不唱歌将看你是否伴奏而定。 P: 你来了。 Q: 他唱歌。 R: 你伴奏。 (7) 用符号形式写出下列命题。a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 P: 上午下雨。 Q: 我去看电影。 R: 我在家里读书。 S: 我在家里看报。第二次布置的作业：P19 1-4习题(7) 证明下列等价式。e) (8) 化简以下各式。a) 解：由于和是等价的，因此原式中的前半部分是永真式，原式就变为，化简完毕。(9) 如果，是否有？如果，是否有？如果是否有？
4、当然未必，C取T时，A和B随意真假，成立；或者 A取，B取P，C取Q，也可说明此问题。 当然未必，C取F时，A和B随意真假，成立；或者A取，B取P，C取Q，也可说明此问题。 是的，就说明了A和B必然同为真或者同为假，所以。P23 1-5习题(1) 试证下列各式为重言式。a) 解法一：可用真值表；(略)解法二：原式等价于只有当Q为假，为真，该式才可能为假，但是Q=F时，永为F，因此上式永真。c) 后件为假的情形是P=T且R=F，此时有两种情况： Q=T，为T，但是为F，前件只能为F； Q=F，为F，前件只能为F；因此根据定义，该式永真。(6) 检验下述论证的有效性。如果我学习，那么我数学不会不及
5、格。 P: 我学习。Q: 我数学不及格。 如果我不热衷于玩扑克，那么我将学习。 R: 我热衷于玩扑克。 但我数学不及格。 Q因此我热衷于玩扑克。 R即要证明 , , Q R前件为真的条件是Q=T，如此P=F(否则为假)，如此R=T(否则不可能为真)，因此后件为真，得证。第三次布置的作业：P39 1-7习题(2) 把下列各式化为析取范式。c) 原式(3) 把下列各式化为合取范式。e) 原式(4) 求下列各式的主析取范式及主合取范式，并指出下列各式哪些是重言式。e) f) 第四次布置的作业：P47 1-8习题(2) 仅用规则P和T，推证以下公式。c) ABCD，DEFAF（此题也可用CP规则来实现
6、，将A作为附加前提）(1) (AF) P(2) A (1)T,I(3) F (1)T,I(4) AB (2)T,I(5) (AB) CD P(6) CD (4)(5)T,I(7) C (6)T,I(8) D (6)T,I(9) DE (8)T,I(10) DEF Pe)(AB)(CD)，(BE)(DF)，(EF)，ACA（此题也可用反证法）(1) (AB) (CD) P(2) AB (1)T,I(3) (BE) (DF) P(4) BE (3)T,I(5) AE (2)(4)T,I(6) (EF) P(7) EF (6)T,E(8) EF (7)T,E(9) AF (5)(8)T,I(10)
7、CD (1)T,I(11) DF (3)T,I(12) CF (10)(11)T,I(13) AC P(14) AF (13)(12)T,I(15) FA (14)T,E(16) AA (9)(15)T,I(17) AA (16)T,E(18) A (17) T,E(5) c) 设P：我的程序通过。 Q：我很快乐。R：阳光很好。 S：天很暖和。（把晚上十一点理解为阳光不好）前提为：PQ，QR，RS (1) PQ P (2) QR P (3) PR (1)(2)T,I (4) RS P (5) R (4)T,I (6) P (3)(5)T,I结论为： P，我的程序没有通过P60 2-1 2-2习
8、题(2) i) 设W(x)：x是女同志。H(x)：x是家庭妇女。C(x)：x是国家选手。则有 ($x)(W(x) C(x) H(x)第五次布置的作业：P62 2-3习题(1) 令P(x)为“x是质数”；E(x)为“x是偶数”；O(x)为“x是奇数”；D(x, y)为“x除尽y”。把以下各式译成汉语：g) (x)(P(x) ($y)( E(y) D(x, y) 对所有的x，若x是质数，则存在y，y是偶数且x能除尽y (即所有质数能除尽某些偶数)h) (x)(O(x) (y)( P(y) D(x, y)对所有的x，若x是奇数，则对所有y，y是质数，则x不能除尽y (即任何奇数不能除尽任何质数)(3
9、) 利用谓词公式翻译下列命题c) 存在实数x，y和z，使得x与y之和大于x与z之积。R(x):x是实数。G(x,y):x大于y。 则 ($x)($y)($z)(R(x)R(y)R(z)G(x+y,xz) 注意：也可以用函数f(x, y)表示x+y，用函数g(x, y)表示xy，代入得G(f(x, y), g(x, z)P66 2-4习题(4) 对下列谓词公式中的约束变元进行换名。a) (x)($y) (P(x, z) Q(y)DS(x, y)(u)($v) (P(u, z) Q(v)DS(x, y)第六次布置的作业：P72 2-5习题(4) 求证：($x)(A(x)B(x) ($x) (A(x
10、)B(x) ($x)A(x) ($x) B(x) (x)A(x)($x) B(x) (x)A(x)($x) B(x)(5) 求证：(x)A(x)(x)B(x)( x)(A(x)B(x)证明：假设x变元的论域为a1时，上式变成A(a)B(a) A(a)B(a)成立假设x变元的论域为a1, a2, . ,ak时，上式变成(A(a1)A(a2).A(ak)(B(a1)B(a2).B(ak) (A(a1)B(a1)(A(a2)B(a2).(A(ak)B(ak) 成立当x变元的论域为a1, a2, . ,ak, ak+1时，(A(a1)A(a2).A(ak)A(ak+1)(B(a1)B(a2).B(ak)B(ak+1) (A(a1)B(a1)(A(a2)B(a2).(A(ak)B(ak)(A(ak+1)B(ak+1) 成立(说明：(A(a1)A(a2)(B(a1)B(a2) (A(a1)B(a1)(A(a1)B(a2)(A(a2)B(a1)(A(a2)B(a2) (A(a1)B(a1)(A(a2)B(a2) )(7) 求证：(x)( y)(P(x)Q(y) ( $x)P(x)(y)Q(y)证明：(x)( y)(P(x)Q(y) (x)( y)( P(x) Q(y) (x) P(x) ( y)Q(y)($x)P(x) ( y)Q(
