下载文档原格式
《离散数学》布置的课后作业习题解答作者：黄海平第一次布置的作业：P8 1-1,1-2习题(1) 指出下列语句哪些是命题，哪些不是命题，如果是命题，指出它的真值。
a) 离散数学是计算机科学系的一门必修课。
命题，Tb) 计算机有空吗？ 不是命题c) 明天我去看电影。
命题，根据主体情况可能为T 或者F d) 请勿随地吐痰！ 不是命题e) 不存在最大质数。
命题，Tf) 如果我掌握了英语、法语，那么学习其它欧洲语言就容易得多。
命题，Tg) 9+5≤12 命题，Fh) x=3 不是命题i) 我们要努力学习。
不是命题，是陈述句，但是没有真假值(3) 设P 表示命题“天下雪”，Q 表示命题“我将去镇上”，R 表示命题“我有时间”，以符号形式写出下列命题。
a) 如果天不下雪和我有时间，那么我将去镇上。
()P R Q ⌝∧→b) 我将去镇上，仅当我有时间时。
Q R →c) 天不下雪。
P ⌝d) 天下雪，那么我不去镇上。
P Q →⌝(5) 将下列命题符号化。
a) 小李一边看书，一边听音乐。
P: 小李看书。
Q: 小李听音乐。
P Q ∧d) 如果a 和b 是偶数，则a+b 是偶数。
写法一： P: a 和b 是偶数。
Q: a+b 是偶数。
P Q →写法二： P: a 是偶数。
Q: b 是偶数。
R: a+b 是偶数。
P Q R ∧→f) 停机的原因在于语法错误或程序错误。
P: 停机。
Q: 语法错误。
R: 程序错误。
P Q R ∨P12 1-3习题(5) 试把原子命题表示为P 、Q 、R 等，然后用符号译出下列各句子。
a) 或者你没有给我写信，或者它在途中丢失了。
P: 你给我写信。
Q: 信在途中丢失了。
P Q ⌝∨ 或者 ()P R ⌝⌝d) 如果你来了，那末他唱不唱歌将看你是否伴奏而定。
P: 你来了。
Q: 他唱歌。
R: 你伴奏。
()P R Q →(7) 用符号形式写出下列命题。
a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。
P: 上午下雨。
Q: 我去看电影。
R: 我在家里读书。
S: 我在家里看报。
()()P Q P R S ⌝→∧→∨第二次布置的作业：P19 1-4习题(7) 证明下列等价式。
e)((())(()))((()))((())())((()))())((())())((()()))((()()))((()()))(()A B C D C A B D C A B D A B C D C A B D A B C D C A B D D C A B C A B D C A B A B D C A B A B D C A B A B D C A B ∧∧→∧→∨∨⇔∧→=⌝∧∧∨∧⌝∨∨∨⇔⌝∧∨⌝∨∧⌝∨∨∨⇔∨⌝∨⌝∧∧⌝∨∨⇔∨⌝∨⌝∧∧∨⇔∨⌝∧∧∨⌝∨⇔∨⌝∧∧∨⌝∧⌝⇔∨⌝∧⇔ 左边右边(8) 化简以下各式。
a) (()())A B B A C →⌝→⌝∧解：由于A B →和B A ⌝→⌝是等价的，因此原式中的前半部分()()A B B A →⌝→⌝ 是永真式，原式就变为T C C ∧⇔，化简完毕。
(9) ①如果A C B C ∨⇔∨，是否有A B ⇔？②如果A C B C ∧⇔∧，是否有A B ⇔？③如果A B ⌝⇔⌝是否有A B ⇔？① 当然未必，C 取T 时，A 和B 随意真假，A C B C ∨⇔∨成立；或者 A 取P Q ∨，B 取P ，C 取Q ，也可说明此问题。
② 当然未必，C 取F 时，A 和B 随意真假，A C B C ∨⇔∨成立；或者A 取P Q ∧，B 取P ，C 取Q ，也可说明此问题。
③ 是的，A B ⌝⇔⌝就说明了A 和B 必然同为真或者同为假，所以A B ⇔。
P23 1-5习题(1) 试证下列各式为重言式。
a) (())P P Q Q ∧→→解法一：可用真值表；(略)解法二：原式等价于(())(()())()P P Q Q P P P Q Q P Q Q ∧⌝∨→⇔∧⌝∨∧→⇔∧→只有当Q 为假，P Q ∧为真，该式才可能为假，但是Q=F 时，P Q ∧永为F ，因此上式永真。
c) (()())()P Q Q R P R →∧→→→后件为假的情形是P=T 且R=F ，此时有两种情况：① Q=T ，P Q →为T ，但是Q R →为F ，前件只能为F ；② Q=F ，P Q →为F ，前件只能为F ；因此根据定义，该式永真。
(6) 检验下述论证的有效性。
如果我学习，那么我数学不会不及格。
P: 我学习。
Q: 我数学不及格。
P Q →⌝ 如果我不热衷于玩扑克，那么我将学习。
R: 我热衷于玩扑克。
R P ⌝→但我数学不及格。
Q因此我热衷于玩扑克。
R即要证明 P Q →⌝, R P ⌝→, Q ⇒R前件为真的条件是Q=T ，如此P=F(否则P Q →⌝为假)，如此R=T(否则R P ⌝→不可能为真)，因此后件为真，得证。
第三次布置的作业：P39 1-7习题(2) 把下列各式化为析取范式。
c) ()()P Q S T ⌝∨⌝∧→原式()()()()P Q S T P Q S P Q T ⇔⌝∧∨⌝∨⇔⌝∧∧⌝∨⌝∧∧(3) 把下列各式化为合取范式。
e) ()()P Q P Q ⌝∧∨∧⌝原式(())(())(()())(()())()()P P Q Q P Q P P P Q Q P Q Q Q P P Q ⇔⌝∨∧⌝∧∨∧⌝⇔⌝∨∧⌝∨⌝∧∨∧∨⌝⇔∨∧⌝∨⌝(4) 求下列各式的主析取范式及主合取范式，并指出下列各式哪些是重言式。
e) (())P P Q P →∧→(())(())(()())(())(())()(())()()()()P P Q P P P Q P P P Q P P P P Q P P Q Q P Q P Q Q P Q P Q P Q P Q T→∧→⇔⌝∨∧⌝∨⇔⌝∨∧⌝∨∧⇔⌝∨∧⌝∨⇔⌝∧⌝∨∨∧⌝∨∧⌝∨⇔⌝∧⌝∨⌝∧∨∧⌝∨∧⇔从此步骤可以看出其为重言式主析取范式主合取范式f) ()()Q P P Q →∧⌝∧ ()()()()()()F =F()(())(())()()()()Q P P Q Q P P Q Q P Q P Q P Q P P Q Q Q P P Q P P Q P Q Q P →∧⌝∧⇔⌝∨∧⌝∧⇔⌝∧⌝∧∨⌝∧∧⇔⌝∨∧⌝∨⌝∧∧∨⌝∧⇔⌝∨∧⌝∨⌝∧⌝∨∧∨从而可以看出该式为矛盾式，真值为，主析取范式主合取范式第四次布置的作业：P47 1-8习题(2) 仅用规则P 和T ，推证以下公式。
c) A ∨B→C ∧D ，D ∨E→F ⇒A→F （此题也可用CP 规则来实现，将A 作为附加前提）(1) ┐(A→F) P(2) A (1)T,I(3) ┐F (1)T,I(4) A ∨B (2)T,I(5) (A ∨B) →C ∧D P(6) C ∧D (4)(5)T,I(7) C (6)T,I(8) D (6)T,I(9) D ∨E (8)T,I(10) D ∨E→F Pe)(A→B)∧(C→D)，(B→E)∧(D→F)，┐(E ∧F)，A→C ⇒┐A （此题也可用反证法）(1) (A→B) ∧(C→D) P(2) A→B (1)T,I(3) (B→E) ∧(D→F) P(4) B→E (3)T,I(5) A→E (2)(4)T,I(6) ┐(E ∧F) P(7) ┐E ∨┐F (6)T,E(8) E→┐F (7)T,E(9) A→┐F (5)(8)T,I(10) C→D (1)T,I(11) D→F (3)T,I(12) C→F (10)(11)T,I(13) A→C P(14) A→F(13)(12)T,I(15) ┐F→┐A(14)T,E(16) A→┐A(9)(15)T,I(17) ┐A∨┐A(16)T,E(18) ┐A(17) T,E(5) c) 设P：我的程序通过。
Q：我很快乐。
R：阳光很好。
S：天很暖和。
（把晚上十一点理解为阳光不好）前提为：P→Q，Q→R，┐R∧S(1) P→Q P(2) Q→R P(3) P→R(1)(2)T,I(4) ┐R∧S P(5) ┐R(4)T,I(6) ┐P(3)(5)T,I结论为：┐P，我的程序没有通过P60 2-1 2-2习题(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) 利用谓词公式翻译下列命题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,x·z) [注意：也可以用函数f(x, y)表示x+y，用函数g(x, y)表示x·y，代入得G(f(x, y), g(x, z))]P66 2-4习题(4) 对下列谓词公式中的约束变元进行换名。
a) (∀x)(∃y) (P(x, z) → Q(y)) S(x, y)(∀u)(∃v) (P(u, z) → Q(v)) S(x, y)第六次布置的作业：P72 2-5习题(4) 求证：(∃x)(A(x)→B(x))⇔ (∃x) (┐A(x)∨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, ... ,a k}时，上式变成(A(a1)∧A(a2)∧...∧A(a k))∨(B(a1)∧B(a2)∧...∧B(a k))⇒ (A(a1)∨B(a1))∧(A(a2)∨B(a2))∧...∧(A(a k)∨B(a k)) 成立当x变元的论域为{a1, a2, ... ,a k, a k+1}时，(A(a1)∧A(a2)∧...∧A(a k)∧A(a k+1))∨(B(a1)∧B(a2)∧...∧B(a k)∧B(a k+1)) ⇒(A(a1)∨B(a1))∧(A(a2)∨B(a2))∧...∧(A(a k)∨B(a k))∧(A(a k+1)∨B(a k+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(y)⇔ ( ∃x)P(x)→(∀y)Q(y)P75 2-6习题(1) 把以下各式化为前束范式。
