作业题与解答。
第一章 19 (2)、(4) 、6) 21 (1)、(2) 、3)
解答： (p→┐p)→┐q 真值表如下：
所以公式(p→┐q)→┐q 为可满足式。
解答： (p→q)→(q→┐p) 真值表如下：
所以公式(p→q)→(q→┐p)为永真式。
19、(6)解答： (p→q)∧(q→r))→p→r) 真值表如下：
所以公式((p→q)∧(q→r))→p→r)为永真式。
21、(1)解答： ┐p∧q)∨┐r 真值表如下：
所以成假赋值为：011
解答： (q∨r)∧(p→q)真值表如下：
所以成假赋值为：010,100,101,110
21、(3)解答： (p→q)∧(p∧r)∨p)真值表如下：
所以成假赋值为：100,101
第二章 5、(1) (2) (3) 6、(1) (2) (3) 7、(1) (2) 8、(1) (2) (3)
5、求下列公式的主析取范式，并求成真赋值。
1) (p→q)→(q∨p)
(┐p→q) ∨q∨p)
(┐(p) ∨q) ∨q∨p)
┐p ∧ q) ∨q∨p)
┐p ∧ q) ∨p ∧ q)∨(p ∧q)
m0 ∨m 2∨m3，所以 00，10，11 为成真赋值。
2) (p→q)∧(q∧r)
┐┐p∨q)∧(q∧r)
p∨q)∧(q∧r)
p∧q∧r)∨(q∧r)
p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)
p∧q∧r)∨(p∧q∧r)
m3∨m 7，所以 011，111 为成真赋值。
3) (p∨(q∧r))→p∨q∨r)
(p∨(q∧r))∨p∨q∨r)
┐p∧ (q∨┐r))∨p∨q∨r)
┐p∧┐q)∨(p∧┐r)∨(p∨q∨r)
┐p∧┐q)∨(p∧┐r)∨(p∨q∨r))
┐p∧┐q)∨(p∨p∨q∨r)∧(r∨p∨q∨r) )
┐p∧┐q)∨(1∧1)
┐p∧┐q)∨1
m0∨m1∨m 2∨ m3∨m4∨m5∨m 6 ∨m 7，所以 000, 001, 010, 011, 100, 101, 110, 111 为成真赋值。
7、求下列公式的主析取范式，再用主析取范式求主合取范式。
1) (p∧q)∨r
p∧q∧r)∨(p∧q∧┐r)∨(p∧r)∨(p∧r)
p∧q∧r)∨(p∧q∧┐r)∨(p∧r∧q)∨(p∧r∧┐q)
(┐p∧r∧q)∨(p∧r∧┐q)
p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(p∧q∧r)
(┐p∧┐q∧r)
m1∨m3∨m5∨m6∨m7 由主析取范式和主合取范式之间的关系，所以公式的主合取范式为：
p∧q)∨r m0∧m2∧m4
2) (p→q)∧(q→r)
┐p∨q)∧(q∨r)
┐p∧(┐q∨r))∨q∧(┐q∨r))
┐p∧┐q)∨(p∧r)∨(q∧┐q)∨(q∧r)
┐p∧┐q)∨(p∧r)∨(q∧r)
┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q∧r)
(┐p∧┐q∧r)∨(p∧q∧r)∨(p∧q∧r)
┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q∧r)
(p∧q∧r)
m0∨m1∨m3∨m7
由主析取范式和主合取范式之间的关系，所以公式的。
主合取范式为：(p→q)∧(q→r) m2∧m4∧m5∧m6
8、求下列公式的主合取范式，再用主合取范式求主析取范式 (1) (p∧q)→q
(p∧q )∨q
┐p∨┐q )∨q
p∨(┐q∨q)
p∨11 该公式无主合取范式，所以公式的主析取范式为：(p∧q)→q m0∨m1∨m2∨m3 (2) (pq)→r
((┐p∨q)∧(p∨┐q))∨r
(p∧┐q)∨(p∧q))∨r
((p∨(┐p∧q)) q∨(┐p∧q)))r
(p∨┐p)∧(p∨q)∧(q∨┐p)∧(q∨q))∨r
(p∨q)∧(q∨┐p))∨r
p∨q∨r)∧(p∨┐q∨r)
m0∧m6 由主合取范式和主析取范式之间的关系，所以公式的主析取范式为：(pq)→r m1∨m2∨m3∨m4∨m5∨m7
3) ┐r→p)∧p∧q
(┐r∨p)∧p∧q
r∧┐p)∧p∧q
r∧(┐p∧p)∧q
r∧0∧q0
m0∧m1∧m2∧m3∧m4∧m5∧m6∧m7
该公式无主析取范式。
第三章 14 (2)、(4)、(5) 15 (1)、(2) 16 (1)
14、在自然推理系统 p 中构造下面推理的证明 (2) 前提：p→q, ┐q∧r), r
结论：┐p证明：①┐q∧r) 前提引入。
┐q∨┐r ①置换。
r 前提引入。
┐q ②③析取三段论。
p→q 前提引入。
┐p ④⑤拒取式。
4）前提：q→p, q s, s t, t∧r
结论：p∧q
证明：①s t 前提引入。
(s→t)∧(t→s) ①置换。
t→s ②化简。
t∧r 前提引入。
t ④化简。
s ③⑤假言推理。
q s 前提引入。
(s→q)∧(q→s) ⑦置换。
s→q ⑧化简。
q ⑥⑨假言推理。
q→p 前提引入。
p ⑩ 假言推理。
p∧q ⑩ 合取。
5）前提：p→r, q→s, p∧q
结论：r∧s
证明：p∧q 前提引入。
p ①化简。
q ①化简。
p→r 前提引入。
r ②④假言推理。
q→s 前提引入。
s ③⑥假言推理。
r∧s ⑤⑦合取。
15、在自然推理系统 p 中用附加前提法证明下面各推理： (1) 前提：p→(q→r), s→p, q
结论：s→r
证明：①s 附加前提引入。
s→p 前提引入。
p ①②假言推理。
p→(q→r) 前提引入。
q→r ③④假言推理。
q 前提引入。
r ⑤⑥假言推理 (2) 前提：(p∨q)→(r∧s), s∨t)→u
结论：p→u
证明：p 附加前提引入。
p∨q ①附加。
(p∨q)→(r∧s) 前提引入。
r∧s ②③假言推理。
s ④化简。
s∨t ⑤附加。
(s∨t)→u 前提引入。
u ⑥⑦假言推理。
16、在自然推理系统 p 中用归谬法证明下面推理： (1) 前提：p→┐q, ┐r∨q, r∧┐s
结论：┐p证明：
p 结论否定引入。
p→┐q 前提引入。
┐q ①②假言推理。
┐r∨q 前提引入。
┐r ③④析取三段论。
r∧┐s 前提引入。
r ⑥化简。
┐r∧r ⑤⑦合取(矛盾)
为矛盾式，由归谬法可知，推理正确。 第四章 5、(1) (2) (3) (4) 10、(2) (4) 11、(2) (6)
5、在一阶逻辑中将下列命题符号化： (1) 火车都比轮船快。
xy(f(x)∧g(y)→h(x,y))，其中，f(x)：x 是火车，g(y)：y 是轮船，h(x,y):x 比 y 快。 (2) 有的火车比有的汽车快。
xy(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 慢。
10、给定解释 i 如下：
a） 个体域 d=n（n 为自然数）。
b） d 中特定元素 =2。
c） d 上函数(x,y)=x＋y， (x,y)=x·y。 d 上谓词 (x,y)：x=y。
2) xy(f(f(x,a),y)→f(f(y,a),x))
xy((x+2=y)→(y+2=x))，真值为 0。 (4) xf(f(x,x),g(x,x))
x(x+x=x·x),真值为 1。
11、判断下列各式的类型。
2) x(f(x)→f(x)) y(g(y)∧┐g(y)))此谓词公式前件永为真，而后件永为假，即公式为(1→0)
此公式为矛盾式，所以原谓词公式为矛盾式。
6) ┐xf(x)→yg(y))∧yg(y) 此谓词公式是命题公式┐(p→q)∧q 的代换实例，而该命题公式是矛盾式，所以此谓词公式是矛盾式。
第五章 15 (1)(2)(3)(4) 20 (1) (2) 23 (1) (2)
15、在自然推理系统 f 中构造下面推理的证明：
1) 前提： xf(x)→y((f(y)∨g(y))→r(y)),xf(x) 结论：xr(x)
证明：① xf(x) →y((f(y)∨g(y)) r(y)) 前提引入)
xf(x) (前提引入)
离散数学作业答案
1 第7页第3题。1 解 逆命题 如果我去公园，则天不下雨 反命题 如果天下雨，则我不去公园 逆反命题 如果我不去公园，则天下雨了。2 解 此题注意 p仅当q翻译成 逆命题 如果你去，那么我逗留。反命题 如果我不逗留，那么你没去。逆反命题 如果你没去，那么我不逗留。3 解 逆命题 如果方程无整数解，...
离散数学作业34答案
离散数学 课程。作业3 p64 3 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。解 直接使用容斥原理。我们做如下设定 a 会打篮球的学生 b 会打排球的学生 c 会打网球的...
离散数学作业4答案
1.如图一所示，以下说法正确的是 d a.是割边 b.是边割集。c.是边割集 d.是边割集。2.设g是连通平面图，有v个结点，e条边，r个面，则r a a.e v 2 b.v e 2 c.e v 2 d.e v 2 3.若g是一个欧拉图，则g一定是 c a.平面图 b.汉密尔顿图 c.连通图 d.对...