离散数学作业
离散数学作业布置
第1次作业（P15）
设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∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0
(4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1
判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也
是无理数。另外只有6能被2整除，6才能被4整除。”
解：p: π是无理数 1
q: 3是无理数0
r: 2是无理数 1
s:6能被2整除 1
t: 6能被4整除0
命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。用真值表判断下列公式的类型：
（4）(p→q) →(﹁q→﹁p)
（5）(p∧r) ? (﹁p∧﹁q)
（6）((p→q) ∧(q→r)) →(p→r)
解：（4）
p q p→q q p q→p (p→q)→( q→p)
0 0 1 1 1 1 1
0 1 1 0 1 1 1
1 0 0 1 0 0 1
1 1 1 0 0 1 1
所以公式类型为永真式，最后一列全为1
（5）公式类型为可满足式（方法如上例），最后一列至少有一个1
（6）公式类型为永真式（方法如上例，最后一列全为1）。
第2次作业（P38）
用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
(1) ﹁(p∧q→q)
(2)(p→(p∨q))∨(p→r)
(3)(p∨q)→(p∧r)
解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0
所以公式类型为矛盾式
(2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1
所以公式类型为永真式
(3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r)
易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
P q r ￢p∧￢q p∧r (￢p∧￢q) ∨(p∧r)
0 0 0 1 0 1
0 0 1 1 0 1
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 0 0 0
1 0 1 0 1 1
1 1 0 0 0 0
1 1 1 0 1 1
所以公式类型为可满足式
用等值演算法证明下面等值式：
(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)∧(﹁q∨﹁p) ∧(﹁q∨q)
?1∧(p∨q)∧(﹁p∨﹁q)∧1
? (p∨q)∧﹁(p∧q)
第3次作业（P38）
求下列公式的主析取范式, 并求成真赋值:
(1)( ￢p→q) →(￢q∨p)
(2) (￢p→q) ∧q∧r
(3)(p∨(q∧r)) →(p∨q∨r)
(4) ￢(p→q) ∧q∧r
解：
(1)(￢p→q) →(￢q∨p)
?￢(p∨q) ∨(￢q∨p)
?￢p∧￢q ∨￢q ∨p
?￢q ∨p (吸收律)
? (￢p∨p)∧￢q ∨p∧(￢q∨q)
?￢p∧￢q∨p∧￢q ∨p∧￢q ∨p∧q
?m0∨m2∨m2∨m3
?m0∨m2∨m3
成真赋值为00, 10, 11.
(2) (￢p→q) ∧q∧r
? (p∨q) ∧q∧r
? (p∧q∧r) ∨q∧r
? (p∧q∧r) ∨(￢p ∨p) ∧q∧r
?p∧q∧r∨￢p ∧q∧r∨p∧q∧r
?m3∨m7
成真赋值为011，111.
(3) (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∨￢p∧￢r∨p∨q∨r
?￢p∧￢q∧(r∨￢r)∨￢p∧(q∨￢q)∧￢r∨p∧(q∨￢q) ∧(r∨￢r) ∨ (p∨￢p) ∧q∧(r∨￢r)∨(p∨￢p) ∧(q∨￢q) ∧r
?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7, 为重言式.
(4) ￢(p→q) ∧q∧r
?￢(￢p∨q) ∧q∧r
? (p∧￢q) ∧q∧r
? p∧(￢q ∧q)∧r
?0
主析取范式为0, 无成真赋值, 为矛盾式.
第4次作业（P38）
求下列公式的主合取范式, 并求成假赋值:
(1) ￢(q→￢p) ∧￢p
(2)(p∧q) ∨ (￢p∨r)
(3)(p→(p∨q)) ∨r
解：
(1) ￢(q→￢p) ∧￢p
?￢(￢q∨￢p) ∧￢p
?q∧p ∧￢p
?q∧0
?0
?M0∧M1∧M2∧M3
这是矛盾式. 成假赋值为00, 01, 10, 11.
(2)(p∧q) ∨ (￢p∨r)
?(p∧q) ∨￢p∨r
?(p∨￢p)∧(￢p ∨q)∨r
? (￢p ∨q)∨r
?￢p ∨q∨r
?M4, 成假赋值为100.
(3)(p→(p∨q)) ∨r
?(￢p∨(p∨q)) ∨r
?(￢p∨p)∨q ∨r
?1
主合取范式为1, 为重言式.
用消解原理证明下述公式是矛盾式:
(1) (￢p∨q) ∧ (￢p∨r) ∧ (￢q∨￢r) ∧ (p∨￢r) ∧r
(2) ￢((p∨q) ∧￢p→q)
解：
(1) (￢p∨q) ∧ (￢p∨r) ∧ (￢q∨￢r) ∧ (p∨￢r) ∧r
第一次循环S0=Φ, S1=｛￢p∨q,￢p∨r,￢q∨￢r,p∨￢r,r｝, S2=Φ
由￢p∨r, p∨￢r消解得到λ
输出“no”，计算结束
(2) ￢((p∨q) ∧￢p→q)
?￢(￢((p∨q) ∧￢p) ∨q)
?((p∨q) ∧￢p) ∧￢q
? (p∨q) ∧￢p ∧￢q
第一次循环S0=Φ, S1=｛p∨q,￢p, ￢q｝, S2=Φ
由p∨q,￢p消解得到q,
由q, ￢q消解得到λ,
输出“no”，计算结束
用消解法判断下述公式是否可满足的:
(1) p∧ (￢p∨￢q) ∧q
(2) (p∨q) ∧(p∨￢q) ∧(￢p∨ r)
解：
(1) p∧ (￢p∨￢q) ∧q
第一次循环S0=Φ, S1=｛p, ￢p∨￢q, q｝, S2=Φ
由p, ￢p∨￢q消解得到￢q,
由q, ￢q消解得到λ,
输出“no”，计算结束
(2) (p∨q) ∧(p∨￢q) ∧(￢p∨ r)
第一次循环S0=Φ, S1=｛p∨q, p∨￢q, ￢p∨ r｝, S2=Φ
由p∨q, p∨￢q消解得到p,
由p∨q, ￢p∨ r消解得到q ∨r,
由p∨￢q, ￢p∨ r消解得到￢q ∨r,
由p, ￢p∨ r消解得到r,
S2=｛p, q ∨r, ￢q ∨r, r｝
第二次循环S0=｛p∨q, p∨￢q, ￢p∨ r｝, S1=｛p, q ∨r, ￢q ∨r, r｝, S2=Φ由p∨q, ￢q ∨r消解得到p∨r,
由p∨￢q, q ∨r消解得到p∨r,
由p∨￢q, q ∨r消解得到p∨r,
由￢p∨ r, p 消解得到r,
S2=｛p∨r｝
第三次循环S0=｛p, q ∨r, ￢q ∨r, r｝, S1=｛p∨r｝, S2=Φ
S2=Φ
输出“yes”，计算结束
判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给
出)和判断过程(至少给出两种判断方法):
(1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三.
(2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一.
(3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一.
(4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二.
(5)若今天是星期一, 则明天是星期二或星期三. 今天是星期一. 所以明天是星期二.
(6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三.
设p: 今天是星期一, q: 明天是星期二, r: 明天是星期三.
(1)推理的形式结构为
(p→r) ∧p→r
此形式结构为重言式, 即
(p→r) ∧p?r
所以推理正确.
(2)推理的形式结构为
(p→q) ∧q→p
此形式结构不是重言式, 故推理不正确.
(3)推理形式结构为
(p→r) ∧￢r→￢p
此形式结构为重言式, 即
(p→r) ∧￢r?￢p
故推理正确.
(4)推理形式结构为
(p→q) ∧￢p→￢q
此形式结构不是重言式, 故推理不正确.
(5)推理形式结构为
(p→(q∨r) )∧p →q
它不是重言式, 故推理不正确.
(6)推理形式结构为
(p?r) ∧￢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) ∧￢p?￢r
故推理正确
2.构造证明法
前提: (p?r), ￢p
结论: ￢r
证明:
①p?r 前提引入
②(p→r) ∧(r→p) ①置换
③r→p ②化简律
④￢p 前提引入
⑤￢r ③④拒取式
所以, 推理正确.
第7次作业（P53-54）在自然推理系统P中用附加前提法证明下面各推理: (1)前提: p→(q→r), s→p, q
结论: s→r
(2)前提: (p∨q) →(r∧s), (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 ⑥⑦假言推理
在自然推理系统P中用归谬法证明下面推理:
(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）
在一阶逻辑中将下列命题符号化:
(1)火车都比轮船快.
(2)有的火车比有的汽车快.
(3)不存在比所有火车都快的汽车.
(4)“凡是汽车就比火车慢”是不对的.
解：因为没指明个体域, 因而使用全总个体域
(1) ?x?y(F(x) ∧G(y) →H(x,y))
其中, F(x): x 是火车, G(y): y 是轮船, H(x,y):x 比y 快.
(2) ?x?y(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) ￢?x?y(F(x) ∧G(y) →H(x,y))
或
?x?y(F(x) ∧G(y) ∧￢H(x,y) )
其中, F(x): x 是汽车, G(y): y 是火车, H(x,y):x 比y 慢. 给定解释I 如下:
(a)个体域为实数集合R.
(b)特定元素a=0.
(c)特定函数-f(x,y)=x-y, x,y∈R.
(d)谓词
-
F(x,y): x=y,
-
G(x,y): x 给出下列公式在I 下的解释, 并指出它们的真值: (1) ?x?y(G(x,y) →￢F(x,y)) (2) ?x?y(F(f(x,y),a) →G(x,y)) (3) ?x?y(G(x,y) →￢F(f(x,y),a)) (4) ?x?y(G(f(x,y),a) →F(x,y)) 解： (1) ?x?y(x (2) ?x?y((x-y=0) →(x (3) ?x?y((x (4) ?x?y((x-y<0) → (x=y)), 真值为0. 第9次作业（P79-80）给定解释I如下: (a) 个体域D={3,4}； (b)- f(x)： - f(3)=4, - f(4)=3； (c) - F(x,y)： - F(3,3)= - F(4,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)→F(f(4),f(4))) ? (0→0)∧(1→1)∧(1→1)∧(0→0) ?1 求下列各式的前束范式. (1)?xF(x)→?yG(x, y) (3)?xF(x, y) ??xG(x, y) (5) ?x1F(x1, x2)→(F(x1)→￢?x2G(x1, x2)). 解： 前束范式不是唯一的. (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, 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)?x1F(x1, x2)→(F(x1)→￢?x2G(x1, x2)) ??x1F(x1, x2)→(F(x1)→?x2￢G(x1, x2)) ??x1F(x1, x2)→?x2(F(x1)→￢G(x1, x2)) ??x1F(x1, x3)→?x2(F(x4)→￢G(x4, x2)) ??x1(F(x1, x3)→?x2(F(x4)→￢G(x4, x2))) ??x1?x2 (F(x1, x3)→(F(x4)→￢G(x4, x2))) 第10次作业（P79-80） 在自然推理系统F L中,构造下面推理的证明: (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) 结论:?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(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) ⑧存在量词引入规则 第11次作业（P96） . 设F 表示一年级大学生的集合, S 表示二年级大学生的集合, M表示数学专业学生的集合, R 表示计算机专业学生的集合, T表示听离散数学课学生的集合, G 表示星期一晚上参加音乐会的学生的集合, H 表示星期一晚上很迟才睡觉的学生的集合. 问下列各句子所对应的集合表达式分别是什么? 请从备选的答案中挑出来. (1)所有计算机专业二年级的学生在学离散数学课. (2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉. (3)听离散数学课的学生都没参加星期一晚上的音乐会. (4)这个音乐会只有大学一, 二年级的学生参加. (5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会. 备选答案: ①T?G∪H ②G∪H?T ③S∩R?T ④H＝G∪T ⑤T∩G＝?⑥F∪S?G ⑦G?F∪S ⑧S-(R∪M) ?G ⑥G?S-(R∩M) 解: (1) ③S∩R?T (2) ④H=G∪T (3) ⑤T∩G=? (4) ⑦G?F∪S (5) ⑧S-(R∪M)?G . 确定下列命题是否为真: (1) ??? (2) ?∈? (3) ??{?} (4)?∈{?} (5){a, b}?{a, b, c, {a, b, c}} (6){a, b}∈{a, b, c, {a, b }} (7){a, b}?{a, b, {{a, b}}} (8){a, b}∈{a, b, {{a, b}}} 解: (1) 真(2)假(3) 真(4) 真(5) 真(6) 真(7) 真(8) 假 第12次作业（P130-131） . 已知A={?,{?}},求A×P(A). 解: A×P(A)= {?,{?}}×{?,{?},{{?}},{?,{?}}} ={,,,,<{?},?>,<{?},{?}>,<{?},{{?}}>, <{?},{?,{?}}>} . 列出集合A={2, 3, 4}上的恒等关系I A, 全域关系E A, 小于或等于关系L A, 整除关系D A.解: I A={<2,2>,<3,3>,<4,4>} E A=A×A={<2,2>,<2,3>,<2,4>,<3,2>,<3,3>,<3,4>,<4,2>,<4,3>,<4,4>} L A={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} D A={<2,2>,<2,4>,<3,3>,<4,4>} .设A={0, 1, 2, 3}, R 是A 上的关系, 且 R={?0, 0?, ?0, 3?, ?2, 0?, ?2, 1?, ?2, 3?, ?3, 2?} 给出R 的关系矩阵和关系图. 解: ??????? ??0010110100001001 第13次作业（P131） .设 A = {?1, 2?, ?2, 4?, ?3, 3?} B = {?1, 3?, ?2, 4?, ?4, 2?} 求A ∪B , A ∩B , dom A , dom(A ∪B ), ran A , ran B , ran(A ∩B ), fld(A ?B ). 解:A ∪B={?1,2?, ?1,3?, ?2,4?, ?3,3?, ?4,2?} A∩B={?2,4?} domA={1,2,3} dom(A ∪B)={1,2,3,4} ranA={2,3,4} ranB={3,4,2} ran(A∩B)={4} fld(A?B)={1,2,3} .设 A={??,{?,{?}}?,?{?},??} 求A ?1,A 2,A 3,A ?{?},A[?],A??,A ?{{?}},A[{{?}}]. 解: A ?1={?{?,{?}},??,??,{?}?}, A 2={?{?},{?,{?}}?}, A 3=?, A ?{?}={??,{?,{?}}?}, A[?]={?,{?}}, A ??=?, A ?{{?}}={?{?},??}, A[{{?}}]=? .设A={a,b,c,d}, R1,R2 为A 上的关系, 其中 R 1={?a,a?,?a,b?,?b,d?} R 2={?a,d?,?b,c?,?b,d?,?c,b?} 求R 1○R 2, R 2○R 1,R 12,R 23. 解: R 1○R 2={?a,a?,?a,c?,?a,d?}, R 2○R 1={?c,d?}, R 12={?a,a?,?a,b?,?a,d?}, R 23={?b,c?,?b,d?,?c,b?} 0 1 2 3 .设A={a,b,c}, 试给出A 上两个不同的关系R 1和R 2,使得 R 12=R 1, R 23=R 2. 解: R 1={?a,a?,?b,b?}, R 2={?b,c?,?c,b?} 第14次作业（P131-133） . 设A={1，2，…,10},定义A 上的关系 R={ 说明R 具有哪些性质并说明理由。 解:只有对称性。因为1+1≠10,<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 是传递的,必有<1,1>属于R.但这是不成立的,因此R 也不是传递的. . 设A={1，2，3，4，5，6}，R 为A 上的关系，R 的关系图如图所示： 解: (1)R={<1,5>,<2,5>,<3,1>，<3,3>,<4,5>} R ={<3,3>,<3,1>,<3,5>}, R 3= {<3,3>,<3,1>,<3,5>}. (2)r(R)={<1,1>,<1,5>,<2,2>,<2,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） .设A={1，2，3，4}，R 为A ?A 上的二元关系, ?〈a ，b 〉，〈c ，d 〉∈ A ?A , 〈a ，b 〉R 〈c ，d 〉?a + b = c + d (1) 证明R 为等价关系. (2) 求R 导出的划分. 1 2 3 4 5 6 (1)证明：? a+b=a+b ∴ ∴R是自反的 任意的 设 ∴c+d=a+b ∴ ∴R是对称的 任意的 若 则a+b=c+d,c+d=x+y ∴a+b=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>,<4,3>}, {<4,4>}} .对于下列集合与整除关系画出哈斯图: (1) {1,2,3,4,6,8,12,24} (2) {1,2,3,4,5,6,7,8,9,10,11,12} 解:哈斯图如下图所示: .分别画出下列各偏序集 (1)A={a,b,c,d,e} R ={ (2)A={a,b,c,d,e}, R ={ 解: a b c d e a b c d e （1）极大元e ；极小元a ；最大e ；最小元a 。 （2）极大元a,b,d,e ；极小元a,b,c,e ；没有最大与最小元。 第16次作业（P161-135） 4. 判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的? (1) f:N →N, f(x)=x 2+2 (2) f:N →N,f(x)=(x)mod 3, x 除以3的余数 (3) f:N →N,f(x)=10x x ??? ，若为奇数，若为偶数 (4) f:N →{0,1},f(x)=01x x ???，若为奇数，若为偶数 (5) f:N-{0}→R,f(x)=lgx (6) f:R→R,f(x)=x2-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) 3∪6 = 6, 2∩5 = 2; (2)4–3 ={3},3⊕1 = {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）和矩阵加法及乘法运算，其中n≥2。 n?实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。（4）全体n （5）正实数集合和运算，其中运算定义为： （6）n 关于普通的加法和乘法运算。 （7）A = {},,,21n a a a n 运算定义如下： （8）S = 关于普通的加法和乘法运算。 （9）S = {0,1},S 是关于普通的加法和乘法运算。 （10）S = ,S 关于普通的加法和乘法运算。 5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 解: （1）封闭,不满足交换律和结合律，无零元和单位元 （2）不封闭 （3）封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）不封闭 （5）不封闭 因为 +?-=--?=R 1111111 （6）封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（1>n ），零元是0；1=n 单位元是1 （7）封闭 不满足交换律，满足结合律， （8）封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）加法不封闭，乘法封闭，乘法满足交换律，结合律 10．令S={a ，b}，S 上有四个运算：*， 分别有表确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (2)求每个运算的单位元，零元以及每一个可逆元素的逆元。 解: (a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 b b a a ==--11, (c)满足交换律,不满足幂等律,不满足结合律 a b a b b a b a a b b a ==== )(, )( b b a b b a )()(≠ 没有单位元, 没有零元 (d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元 16．设V=〈 N ，+ ，〉，其中+ ，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V 的子代数，为什么？ （1）S1= （2）S2= （3）S3 = {-1，0，1} 解: （1）是 （2）不是 加法不封闭 （3）不是，加法不封闭 第18次作业（P202-205） 8.设S={0，1，2，3}， 为模4乘法，即 ?x,y ∈S, x y=(xy)mod 4 问〈S ，〉是否构成群？为什么？ 解：(1) ?x,y ∈S, x y=(xy)mod 4S ∈,是S 上的代数运算。 (2) ?x,y,z ∈S,设xy=4k+r 30≤≤r (x y)z =((xy)mod 4)z=r z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x (y z) =(xyz)mod 4 所以，(x y)z = x (y z)，结合律成立。 (3) ?x ∈S, (x 1)=(1x)=x,，所以1是单位元。 (4),33,1111==-- 0和2没有逆元 所以，〈S ，〉不构成群 9.设Z 为整数集合，在Z 上定义二元运算。如下： ?x,y ∈Z,xoy= x+y-2 问Z 关于o 运算能否构成群？为什么？ 解：(1) ?x,y ∈Z, xoy= x+y-2Z ∈,o 是Z 上的代数运算。 (2) ?x,y,z ∈Z, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，结合律成立。 (3)设e 是单位元，?x ∈Z, xo e = e ox=x,即x+e -2= e +x-2=x, e=2 (4) ?x ∈Z , 设x 的逆元是y, xoy= yox=e , 即x+y-2=y+x-2=2, 所以， x y x -==-41 所以〈Z ，o 〉构成群 22.设G 为群，a 是G 中给定元素，a 的正规化子N （a ）表示G 中与a 可交换的元素构成的集合，即 N （a ）={x ∣x ∈G ∧xa=ax} 证明N （a ）构成G 的子群。 证明：ea=ae,φ≠∈)(a N e ya ay xa ax a N y x ==∈?,),(,则 a xy ya x ay x y xa y ax xy a )()()()()()(=====,所以)(a N xy ∈ 由xa ax =，得111111,------==eax ae x xax x axx x ，即11--=ax a x ，所以 )(1a N x ∈- 所以N （a ）构成G 的子群 36.设τσ,是5元置换，且 ???? ??=3541254321σ，???? ??=2154354321τ (1)计算 τσσσττσστ111,,,,---； (2)将τσσττσ11,,--表示成不交的轮换之积。 (3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。 解：(1) ???? ??=1235454321τσ ???? ??=5213454321στ ???? ??=-32154543211τ ???? ??=-43512543211σ ???? ??=-23145543211τσσ (2) )1425(=τσ )14253(1=-τ )25)(143(1=-τσσ (3) )15)(12)(14(=τσ 奇置换， )13)(15)(12)(14(1=-τ 偶置换 )25)(13)(14(1=-τσσ 奇置换 第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 - 四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 - 第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 - 离散数学形成性考核作业4作业与答案 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档． 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、公式翻译题 1．请将语句“小王去上课，小李也去上课．”翻译成命题公式． 设Ｐ：小王去上课 Ｑ:小李去上课 则：命题公式Ｐ∧Ｑ 2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设Ｐ：他去旅游 Ｑ：他有时间 则命题公式为Ｐ→Ｑ 3．请将语句“有人不去工作”翻译成谓词公式． 设Ａ（x）:x是人 Ｂ（x）：去工作 则谓词公式为?x（A(x)∧－B（x）) 4．请将语句“所有人都努力学习．”翻译成谓词公式． 设A（x）: x是人 B（x）:努力学习 则谓词公式为?x（A（x）∧B（x）） 二、计算题 1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A-B)；（2）(A∩B)；（3）A×B． 解： （1）（A-B）＝{{1}，{2}} （2）（A∩B）＝{1，2} （3）A×B＝ {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1, 2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>} 2．设A={1，2，3，4，5}，R={ 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作， 一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>} {<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G) 离散数学作业布置 第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∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 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 p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111 命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。 华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P (5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P 离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元. 解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。 3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素. 离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 《离散数学》课程作业（2）-------数理逻辑部分 一、 填空题 1. 将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、 、 、 和等值。 2、命题公式G=（P ∧Q ）→R ，则G 共有 个不同的解释；把G 在其所有解释下所 取真值列成一个表，称为G 的 ；解释（?P ，Q ，?R ）或（0，1，0）使G 的真值为 。 3、 已知命题公式R Q P G →∧?=)(，则G 的析取范式是 。 4、 求公式)()(R P Q P ∧?∨∧的主析取范式 。 5、 设命题公式)(R Q P G →?→=，则使公式G 为假的解释是 、 和 。 6、在谓次词逻辑中将下面命题符号化：在北京工作的人未必都是北京人（提示：设F （x ）：x 在北京工作。G （x ）：x 是北京人。） 。 7、将公式化成等价的前束范式，=→?→???)))()((),((x R z zQ y x yP x 。 8、设谓词的定义域为},,{c b a ，将表达式)()(x xS x xR ?∧?中的量词消除，写成与之等价的 命题公式是 。 二、 单项选择题 1、下列语句中，（ ）是命题。 A ．下午有会吗？ B ．这朵花多好看呀！ C ．2是常数。 D ．请把门关上。 2、一个公式在等价意义下，下面哪个写法是唯一的（ ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 3、设命题公式P Q P G →∧=)(，则G 是（ ）。 A. 恒假的 B. 恒真的 C. 可满足的 D. 析取范式 4、设命题公式)(), (P Q P H Q P G ?→→=→?=，则G 与H 的关系是（ ）。 以上都不是。.;.;.;.D H G C G H B H G A =?? 5、已知命题))((R Q P G ∧→?=，则所有使G 取真值1的解释是（ ）。 A （0，0，0），（0，0，1），（1，0，0） B （1，0，0），（1，0，1），（1，1，0） C （0，1，0），（1，0，1），（0，0，1） D （0，0，1），（1，0，1），（1，1，1） 6、设I 是如下一个解释，0 101),(),(),() ,(},,{b b P a b P b a P a a P b a D =， 则在解释I 下取真值为1的公式是（ ）。 ),(.);,(.);,(.);,(.y x yP x D x x xP C y x yP x B y x yP x A ??????? 7、下面给出的一阶逻辑等价式中，（ ）是错的。 )). (()(.)); (()(.); ()())()((.); ()())()((.x B A x x xB A D x A x x xA C x xB x xA x B x A x B x xB x xA x B x A x A →?=?→??=???∨?=∨??∨?=∨? 三、 计算题 1. 求命题公式?（P ∨Q ）?（P ∧Q ）的析取范式与合取范式。 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 离散数学作业 一、选择题 1、下列语句中哪个是真命题（C ）。 A ．我正在说谎。 B ．如果1+2=3，那么雪是黑色的。 C ．如果1+2=5，那么雪是白色的。 D ．严禁吸烟！ 2、设命题公式))((r q p p G →∧→=，则G 是（ C ）。 A. 恒假的 B. 恒真的 C. 可满足的 D. 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x （ C ）。 A ．是自由变元但不是约束变元 B ．既不是自由变元又不是约束变元 C ．既是自由变元又是约束变元 D ．是约束变元但不是自由变元 4、设A={1，2，3}，则下列关系R 不是等价关系的是（C ） A ．R={<1，1>，<2，2>，<3，3>} B ．R={<1，1>，<2，2>，<3，3>，<2，3>，<3，2>} C ．R={<1，1>，<2，2>，<3，3>，<1，4>} D ．R={<1，1>，<2，2>，<3，3>，<1，2>，<1，3>，<2，3>，<2，1>， <3，1>，<3，2>} 5、设R 为实数集，映射σ=R →R ，σ（x ）= -x 2+2x-1，则σ是（ D ）。 A ．单射而非满射 B ．满射而非单射 C ．双射 D ．既不是单射，也不是满射 6、下列二元运算在所给的集合上不封闭的是（ D ） A. S={2x-1|x ∈Z +}，S 关于普通的乘法运算 B. S={0，1}，S 关于普通的乘法运算 C. 整数集合Z 和普通的减法运算 D. S={x | x=2n ，n ∈Z +}，S 关于普通的加法运算 7、*运算如下表所示，哪个能使（{a,b}，*）成为含幺元半群（ D ） b a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b a a b a * A B C D 8、下列图中是欧拉图的是（ A ）。 2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）： 国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,3}， A B {1,2,3}} ，A B= {< 1,1>，<1,2>，<2，1>，<2，2>，<3，1>，<3， 2> } ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {< 2,2>，<2,3>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 『离散数学』课程 作业3： P64：3 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。 解：直接使用容斥原理。我们做如下设定： A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生； 根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|B∩C|=4，|A∩B∩C|=2 由容斥原理: |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|=14+12+6-6-5-4+2=19 —————————————————————————————————————— 但相当一部分同学没有直接使用容斥原理， 而是画了文氏图。 使用文氏图的方法，会发现此题存在问题： 表示只会打网球的同学是-1人， 此种情况与实际不符。 这可能是作者的疏忽，该教材第一版中， “已知6个会打网球的人中有4人会打排球。” 一句是写作 “已知6个会打网球的人都会打篮球或排球。” 则用容斥原理或文氏图，都可以得到5的结果。 A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生； 根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|A∩B∩C|=2 因为“会打网球的人都会打篮球或排球。” 所以C =（A∩C）∪（B∩C） 由容斥原理: |C|=|（A∩C）∪（B∩C）| = |（A∩C）|+|（B∩C）|-|（A∩C）∩（B∩C）| 可知|（B∩C）|= |C|-|（A∩C）|+|（A∩C）∩（B∩C）| = 6-5+2=3 |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C| =14+12+6-6-5-3+2=20 离散数学(第2版)_在线作业 _4 交卷时间：2017-01-12 14:00:56 一、单选题 1. (5分) ? A. q ∧┐q ? B. p →┐q ? C. p → (p ∨q) ? D. (p ∨┐p)→q 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 2. (5分) ? A. ? B. ? C. ? D. 下列命题公式为重言式的是( )。 设，下列式子正确的是( )。 纠错 得分： 5 知识点： 离散数学(第2版 ) 收起解析 答案 C 解析 3. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 4. (5分) ? A. ? B. ? C. 下列是两个命题变元的极小项的是( )。 设G 是有个顶点， 条边和个面的连通平面图，则 等于( )。 ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 5. (5分) ? A. 满射函数 ? B. 非单射非满射函数 ? C. 双射函数 ? D. 单射函数 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 6. (5分) 设R 是实数集合，函数，则是( )。 ? A. 11，3，4 ? B. 10，4，3 ? C. 11，3，5 ? D. 12，3，6 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 A 解析 7. (5分) ? A. x*y=gcd(x,y)，即x,y 的最大公约数 ? B. x*y=lcm(x,y)，即x,y 的最小公倍数 ? C. x*y=max{x,y} ? D. x*y=min{x,y} 纠错 得分： 5 知识点： 离散数学(第2版) 下列平面图的三个面的次数分别是( )。 设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A 是不封闭的？( )。 《离散数学》作业一、选择或填空 1．下列公式中哪些是永真式？( ) A.(┐P ∧Q)→(Q→?R) B.P→(Q→Q) C.(P ∧Q)→P D.P→(P ∨Q) 2．设全体域D 是正整数集合，确定下列命题的真值： A. ?x ?y (xy=y) ( ) B. ?x ?y(x+y=y) ( ) C. ?x ?y(x+y=x) ( ) D. ?x ?y(y=2x) ( ) 3．有n 个结点的树，其结点度数之和是( )。 4．举出集合A 上的既是等价关系又是偏序关系的一个例子。( ) 5．群 《离散数学》作业参考答案一、选择或填空： 1． B C D 2． A， F B，F C，F D，T 3． 2n-2 4． I A 5．单位元，1 6． A 7． A D 8． (1) P→?Q (2) P??Q 9．偶数 10．自反性、对称性和传递性 11． 1，单位元，0 12．所有边一次且恰好一次 13． B C D E F 14． B D 15． 5,10 16． D 17． B 18． D 19． A 20．（1）R R={ 〈1，1〉，〈1，3〉，〈2，2〉，〈2，4〉} （2）Ｒ-1＝｛〈1，2〉，〈2，1〉，〈3，2〉，〈4，3〉｝ 21． m=n-1 22． 9,3 23． A 24． D 25 (1) 26 (2) 27 (3) 28 (1) 29 (1) 30 (3) 31 (2) 32 (3) 33 (2) 34 (4) 35 (2) 36 (1) 二、求下列各公式的主析取范式和主合取范式 解：1． P∨?Q （主合取范式） ?（P∧(?Q∨Q)）∨（(?P∨P)∧?Q） ?(P∧?Q)∨（P∧Q）∨（?P∧?Q）∨（P∧?Q） ?(P∧?Q)∨（P∧Q）∨（?P∧?Q）（主析取范式） 2．Q→( P∨?R) ??Q∨P∨?R（主合取范式） ?（Q→( P∨?R)） ?（?P∨?Q∨?R）∧（?P∨?Q∨R）∧（?P∨Q∨?R）∧（?P∨Q∨R）∧（P∨?Q∨R）∧ （P∨Q∨?R）∧（P∨Q∨R）（原公式否定的主合取范式） Q→( P∨?R) ?（P∧Q∧R）∨（P∧Q∧?R）∨（P∧?Q∧R）∨（P∧?Q∧?R）∨（?P∧Q∧?R）∨（?P∧?Q∧R）∨（?P∧?Q∧?R）（主析取范式） 3． P→Q??P∨Q（主合取范式） ?(?P∧(Q∨?Q))∨((?P∨P)∧Q) ?(?P∧Q)∨(?P∧?Q)∨(?P∧Q)∨(P∧Q) ?(?P∧Q)∨(?P∧?Q)∨(P∧Q)（主析取范式） 4．?(P→Q)∨(R∧P)??(?P∨Q)∨(R∧P) ?(P∧?Q)∨(R∧P)（析取范式） ?(P∧?Q∧(R∨?R))∨(P∧(?Q∨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)) ?(P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R) （原公式否定的主析取范式） ?(P→Q)∨(R∧P) ?(?P∨?Q∨R)∧(P∨?Q∨?R)∧(P∨Q∨?R)∧(P∨Q∨R)∧(P∨?Q∨R)（主合取范式）5．P∧Q（主析取范式） ?(P∨(Q∧?Q))∧((P∧?P)∨Q) ?(P∨?Q)∧(P∨Q)∧(P∨Q)∧(?P∨Q) ?(P∨?Q)∧(P∨Q)∧(?P∨Q)（主合取范式） 6 Q→(P∨?R) ??Q∨P∨?R（主合取范式） ?(Q→(P∨?R))离散数学作业
离散数学形成性考核作业4题目与答案
离散数学作业答案
离散数学(大作业)与答案
离散数学作业(2)
离散数学作业
华南理工离散数学作业题2017版
离散数学作业
离散数学作业答案完整版
离散数学课程作业(2)
离散数学作业答案
离散数学作业标准答案
离散数学 作业及答案
国开放大学离散数学本离散数学作业答案
离散数学 作业 3~4 答案
离散数学(第2版)_在线作业_4
《离散数学》作业
《离散数学》作业参考答案