离散数学答案屈婉玲版第二版 高等教育出版社课后答案
离散数学答案屈婉玲版
第二版高等教育出版社课后答案
第一章部分课后习题参考答案
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
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，所以这一段的论述为真。
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
所以公式类型为永真式
（5）公式类型为可满足式（方法如上例）
（6）公式类型为永真式（方法如上例）
第二章部分课后习题参考答案
3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
(1) ?(p∧q→q)
(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 q r p∨q p∧r （p∨q）→(p∧r)
0 0 0 0 0 1
0 0 1 0 0 1
0 1 0 1 0 0
0 1 1 1 0 0
1 0 0 1 0 0
1 0 1 1 1 1
1 1 0 1 0 0
1 1 1 1 1 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)∧(?q∨?p) ∧(?q∨q)
?1∧(p∨q)∧?(p∧q)∧1
?(p∨q)∧?(p∧q)
5.求下列公式的主析取范式与主合取范式，并求成真赋值
(1)(?p→q)→(?q∨p)
(2)?(p→q)∧q∧r
(3)(p∨(q∧r))→(p∨q∨r)
解：
（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)
?∑(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) ? M
1
?∏(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中构造下面推理的证明：
(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)条件时命题的真值:
(1) 对于任意x,均有x2?2=(x+√2)(x?√2).
(2) 存在x,使得x+5=9.
其中(a)个体域为自然数集合.
(b)个体域为实数集合.
解：
F(x): x2?2=(x+√2)(x?√2).
G(x): x+5=9.
(1)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化:
(1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解:
(1)F(x): x 能表示成分数 H(x): x 是有理数
命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人
命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快.
(3) 不存在比所有火车都快的汽车. 解:
(1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快 命题符号化为: )),())()(((y x H y G x F y x →∧??
(2) (1)F(x): x 是火车; G(x): x 是汽车; H(x,y): x 比y 快 命题符号化为: ))),()(()((y x H x F x y G y →?∧?? 9.给定解释I 如下:
(a) 个体域D 为实数集合R. (b) D 中特定元素a ?=0.
(c) 特定函数f (x,y)=x ?y,x,y D ∈.
(d) 特定谓词F
?(x,y):x=y,G ?(x,y):x 答:(1) 对于任意两个实数x,y,如果x (2) 对于任意两个实数x,y,如果x-y=0, 那么x （a ） 个体域D=N(N 为自然数集合). （b） D中特定元素a?=2. （c） D上函数f(x,y)=x+y,g?(x,y)=xy. （d） D上谓词F?(x,y):x=y. 说明下列各式在I下的含义，并讨论其真值. (1)?xF(g(x,a),x) (2)?x?y(F(f(x,a),y)→F(f(y,a),x) 答:(1) 对于任意自然数x, 都有2x=x, 真值0. (2) 对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x. 真值0. 11. 判断下列各式的类型: (1) F(x,y)→(G(x,y)→F(x,y)). (3) ?x?yF(x,y)→?x?yF(x,y). 解:(1)因为1 →p → ? p p为永真式； q p q ) ? ) (? ( ∨ ? ∨ 所以F(x,y)→(G(x,y)→F(x,y)).为永真式； (3)取解释I个体域为全体实数 F(x,y)：x+y=5 所以,前件为任意实数x存在实数y使x+y=5，前件真； 后件为存在实数x对任意实数y都有x+y=5，后件假，] 此时为假命题 再取解释I个体域为自然数N， F(x,y)：:x+y=5 所以,前件为任意自然数x存在自然数y使x+y=5，前件假。此时为假命题。 此公式为非永真式的可满足式。 13. 给定下列各公式一个成真的解释，一个成假的解释。 (1) ?x(F(x)∨G(x)) (2) ?x(F(x)∧G(x)∧H(x)) 解:(1)个体域:本班同学 F(x)：x会吃饭, G(x)：x会睡觉.成真解释 F(x)：x是泰安人,G(x)：x是济南人.（2）成假解释 (2)个体域:泰山学院的学生 F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释. F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸. 成真解释. 第五章部分课后习题参考答案 5.给定解释Ｉ如下: (a)个体域D={3,4}; (b))(x f f 为 3)4(,4)3(==f f (c)1)3,4()4,3(,0)4,4()3,3(),(====F F F F y x F 为. 试求下列公式在Ｉ下的真值. (1)),(y x yF x ?? (3))))(),((),((y f x f F y x F y x →?? 解:(1) ))4,()3,((),(x F x F x y x yF x ∨???? (2) )))(),((),((y f x f F y x F y x →?? 12.求下列各式的前束范式。 (1)),()(y x yG x xF ?→? (5))),()((),(2121211x x G x x H x x F x ??→→? (本题课本上有错误) 解:(1) ),()(y x yG x xF ?→?),()(y t yG x xF ?→??)),()((y t G x F y x →??? (5) )),()((),(2121211x x G x x H x x F x ??→→? 15.在自然数推理系统F 中,构造下面推理的证明: (1) 前提: ))())()((()(y R y G y F y x xF →∨?→?,)(x xF ? 结论: ?xR(x) (2) 前提: ?x(F(x)→(G(a)∧R(x))), ?xF(x) 结论:?x(F(x)∧R(x)) 证明(1) ①)(x xF ? 前提引入 ②F(c) ①EI ③))())()((()(y R y G y F y x xF →∨?→? 前提引入 ④))())()(((y R y G y F y →∨? ①③假言推理 ⑤(F(c)∨G(c))→R(c)) ④UI ⑥F(c)∨G(c) ②附加 ⑦R(c) ⑤⑥假言推理 ⑧?xR(x) ⑦EG (2) ①?xF(x) 前提引入 ②F(c) ①EI ③?x(F(x)→(G(a)∧R(x))) 前提引入 ④F(c)→(G(a)∧R(c)) ③UI ⑤G(a)∧R(c) ②④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ②⑥合取引入 ⑧?x(F(x)∧R(x)) ⑦EG 第六章部分课后习题参考答案 5.确定下列命题是否为真： （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 ｝｝｝ 假 6．设a,b,c 各不相同，判断下述等式中哪个等式为真: （1）｛｛a,b ｝，c,?｝ =｛｛a,b ｝,c ｝ 假 （2）｛a ,b,a ｝=｛a,b ｝ 真 （3）｛｛a ｝，{b}｝=｛｛a,b ｝｝ 假 （4）｛?，｛?｝，a,b ｝=｛｛?,｛?｝｝,a,b ｝ 假 8．求下列集合的幂集： （1）｛a,b,c ｝ P(A)={ ?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} （2）｛1，｛2，3｝｝ P(A)={ ?, {1}, {{2,3}}, {1，{2，3}} } （3）｛?｝ P(A)={ ?, ｛?｝ } （4）｛?，｛?｝｝ P(A)={ ?, {1}, {{2,3}}, {1，{2，3}} } 14．化简下列集合表达式： （1）（A Y B）I B ）-（A Y B） （2）（（A Y B Y C）-（B Y C））Y A 解: (1)（A Y B）I B ）-（A Y B）=（A Y B）I B ）I～（A Y B） =（A Y B）I～（A Y B）)I B=?I B=? （2）（（A Y B Y C）-（B Y C））Y A=（（A Y B Y C）I～（B Y C））Y A =（A I～（B Y C））Y（（B Y C ）I～（B Y C））Y A =（A I～（B Y C））Y?Y A=（A I～（B Y C））Y A=A 18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。 解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打网球的人} |A|=14, |B|=12, |A I B|=6,|A I C|=5,| A I B I C|=2, |C|=6,C?A Y B 如图所示。 25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5人 21.设集合A＝{{1，2}，{2，3}，{1，3},{?}},计算下列表达式： （1）Y A （2）I A （3）I Y A （4）YI A 解: （1）Y A={1，2}Y{2，3}Y{1，3}Y{?}={1，2，3,?} （2）I A={1，2}I{2，3}I{1，3}I{?}=? （3）I Y A=1I2I3I?=? （4）YI A=? 27、设A,B,C是任意集合，证明 (1)(A-B)-C=A- B?C (2)(A-B)-C=(A-C)-(B-C) 证明 (1) (A-B)-C=(A I ～B) I ～C= A I ( ～B I ～C)= A I ～(B ?C) =A- B ?C (2) (A-C)-(B-C)=(A I ～C) I ～(B I ～C)= (A I ～C) I (～B Y C) =(A I ～C I ～B) Y (A I ～C I C)= (A I ～C I ～B) Y ? = A I ～(B ?C ) =A- B ?C 由（1）得证。 第七章部分课后习题参考答案 7.列出集合A={2,3,4}上的恒等关系I A ,全域关系E A ,小于或等于关系L A ,整除关系D A . 解：I A ={<2，2>,<3,3>,<4,4>} E A ={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>} L A ={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} D A ={<2,4>} 13.设A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>} 求A ?B,A ?B, domA, domB, dom(A ?B), ranA, ranB, ran(A ?B ), fld(A-B). 解：A ?B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A ?B={<2,4>} domA={1,2,3} domB={1,2,4} dom(A ∨B)={1,2,3,4} ranA={2,3,4} ranB={2,3,4} ran(A ?B)={4} A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求R οR, R -1, R ↑{0,1,}, R[{1,2}] 解：R οR={<0,2>,<0,3>,<1,3>} R -1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R ↑{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3} 16．设A={a,b,c,d}，1R ，2R 为A 上的关系，其中 1 R ={ },,,,,a a a b b d 求23 122112,,,R R R R R R o o 。 解: R 1οR 2={ R 12=R 1οR 1={ 36．设A={1，2，3，4}，在A ?A 上定义二元关系R ， ? ∴ ? 任意的 ∴R 是对称的 任意的 ∴R 是A ×A 上的等价关系 (2) ∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>}, {<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} } 41.设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)证明：? a+b=a+b ∴ 任意的 任意的 ∴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>}} 43. 对于下列集合与整除关系画出哈斯图: (1) {1,2,3,4,6,8,12,24} (2) {1,2,3,4,5,6,7,8,9,10,11,12} 解: (1) (2) 45.下图是两个偏序集 (a) (b) 解: (a)A={a,b,c,d,e,f,g} R p ={ R p ={ 46.分别画出下列各偏序集 (1)A={a,b,c,d,e} R p ={ 解: (1) (2) 项目 (1) (2) 极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无 第八章部分课后习题参考答案 1．设f :N →N,且 f (x)=12x x x ?? ??? ，若为奇数若为偶数， 求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,…})，f ({4,6,8}), f -1({3,5,7}). 解：f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1}, f ({0,2,4,6,…})=N ，f ({4,6,8})={2,3,4}, f -1 ({3,5,7})={6,10,14}. 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)=x 2-2x-15 不是满射，不是单射 5. 设X={a,b,c,d},Y={1,2,3},f={ (1)f 是从X 到Y 的二元关系,但不是从X 到Y 的函数; 对 (2)f 是从X 到Y 的函数,但不是满射,也不是单射的; 错 (3)f 是从X 到Y 的满射,但不是单射; 错 (4)f 是从X 到Y 的双射. 错 第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。 封闭,不满足交换律和结合律，无零元和单位元 （2） 非零整数集合Z ?和普通的除法运算。不封闭 （3） 全体n n ?实矩阵集合M n （R ）和矩阵加法及乘法运算，其中n ≥2。 封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）全体n n ?实可逆矩阵集合关于矩阵加法及乘法运算，其中n ≥2。不封闭 （5）正实数集合R +和 ° 运算，其中 ° 运算定义为： ? a ，b ∈R +，a ° b = ab ?a ?b 不封闭 因为 +?-=--?=R 1111111ο （6）n ∈Z +,nZ ={nz | z ∈ Z }.nZ 关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（1>n ），零元是0；1=n 单位元是1 （7）A = {},,,21n a a a Λ n ≥2.° 运算定义如下： ? a ，b ∈ A ，a ° b = b 封闭 不满足交换律，满足结合律， （8）S = {2x ?1|x ∈Z +}关于普通的加法和乘法运算。 封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S 是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = {x | x =2n ,n ∈Z +} ,S 关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律 5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题 7．设 * 为+Z 上的二元运算+∈?Z y x ,， X * Y = min ( x ，y ),即x 和y 之中较小的数. (1)求4 * 6，7 * 3。 4, 3 (2)* 在+ Z 上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律 (3)求*运算的单位元，零元及+Z 中所有可逆元素的逆元。 单位元无，零元1, 所有元素无逆元 8．Q Q S ?= Q 为有理数集，*为S 上的二元运算，? < a ，b >* （1）*运算在S 上是否可交换，可结合？是否为幂等的？ 不可交换： 可结合：( （2）*运算是否有单位元，零元？ 如果有请指出，并求S 中所有可逆元素的逆元。 设 ? 所以当x ≠0时，x y x y x -= ><-,1,1 10．令S={a ，b}，S 上有四个运算：*，°，?和□?分别有表10.8确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 (c)满足交换律,不满足幂等律,不满足结合律 没有单位元, 没有零元 (d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元 (2)求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上 16．设V=〈 N ，+ ，? 〉，其中+ ，?分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V 的子代数，为什么？ （1）S 1={2n | n ∈Z } 是 （2）S 2={2n +1 | n ∈Z } 不是 加法不封闭 （3）S 3 = {-1，0，1} 不是，加法不封闭 第十一章部分课后习题参考答案 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)=(1 x)=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 〉构成群 11.设G=? ?? ??????? ??--???? ??-???? ??-???? ??1001,1001, 1001,1001，证明G 关于矩阵乘法构成一个群． 解：(1) ?x,y ∈G, 易知xy ∈G,乘法是Z 上的代数运算。 (2) 矩阵乘法满足结合律 (3)设???? ??1001是单位元， (4)每个矩阵的逆元都是自己。 所以G 关于矩阵乘法构成一个群． 14.设G 为群，且存在a∈G,使得 G={a k ∣k∈Z} 证明：G 是交换群。 证明:?x,y ∈G ，设l k a y a x ==,，则 所以，G 是交换群 17.设G 为群，证明e 为G 中唯一的幂等元。 证明:设G e ∈0也是幂等元，则020 e e =，即e e e 02 0=，由消去律知e e =0 18.设G 为群，a,b,c∈G,证明 ∣abc∣=∣bca∣=∣cab∣ 证明：先证设e bca e abc k k =?=)()( 设,)(e abc k =则e abc abc abc abc =)())()((Λ， 即 e a bca bca bca bca a =-1)())()((Λ 左边同乘1-a ，右边同乘a 得 反过来，设,)(e bac k =则.)(e abc k = 由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣ 19.证明：偶数阶群G 必含2阶元。 证明：设群G 不含2阶元，G a ∈?，当e a =时，a 是一阶元，当e a ≠时，a 至少是3阶元,因为群G 时有限阶的，所以a 是有限阶的，设a 是k 阶的,则1-a 也是k 阶的，所以高于3阶的元成对出现的，G 不含2阶元，G 含唯一的1阶元e ,这与群G 是偶数阶的矛盾。所以，偶数阶群G 必含2阶元 20.设G 为非Abel 群，证明G 中存在非单位元a 和b,a≠b,且ab=ba. 证明：先证明G 含至少含3阶元。 若G 只含1阶元,则G={e},G 为Abel 群矛盾； 若G 除了1阶元e 外,其余元a 均为2阶元，则e a =2，a a =-1 ba ba b a ab ab ab b b a a G b a ======∈?------111111)(,)(,,,,所以， 与G 为Abel 群矛盾； 所以，G 含至少含一个3阶元，设为a ，则≠a 2a ，且22aa a a =。 令2a b =的证。 21.设G 是M n (R)上的加法群，n≥2，判断下述子集是否构成子群。 （1）全体对称矩阵 是子群 （2）全体对角矩阵 是子群 （3）全体行列式大于等于0的矩阵. 不是子群 （4）全体上（下）三角矩阵。 是子群 22.设G 为群，a 是G 中给定元素，a 的正规化子N （a ）表示G 中与a 可交换的元素构成的集合，即 N （a ）={x ∣x ∈G ∧xa=ax} 证明N （a ）构成G 的子群。 证明：ea=ae,φ≠∈)(a N e 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 的子群 31.设?1是群G 1到G 2的同态，?2是G 2到G 3的同态，证明?1?ο2是G 1到G 3的同态。 证明：有已知?1是G 1到G 2的函数，?2是G 2到G 3的函数，则?1·?2是G 1到G 3的函数。 所以:?1·?2是G 1到G 3的同态。 33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 证明：设G 是循环群,令G=,G y x ∈?,,令l k a y a x ==,,那么 yx a a a a a a xy k l k l l k l k =====++,G 是阿贝尔群 克莱因四元群,},,,{c b a e G = 是交换群,但不是循环群,因为e 是一阶元，a,b,c 是二阶元。 36.设τσ,是5元置换，且 ???? ??=3541254321σ，??? ? ??=2154354321τ (1)计算τσσσττσστ111,,,,---； (2)将τσσττσ11,,--表成不交的轮换之积。 (3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。 解：(1) ???? ??=1235454321τσ ???? ??=5213454321στ ??? ? ??=-32154543211τ (2) )1425(=τσ )14253(1=-τ )25)(143(1=-τσσ (3) )15)(12)(14(=τσ 奇置换， )13)(15)(12)(14(1=-τ 偶置换 )25)(13)(14(1=-τσσ 奇置换 第十四章部分课后习题参考答案 5、设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、)()(G G δ、?。 解：由握手定理图G 的度数之和为：20102=? 3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。 其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2, 所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2,2)(,4)(==?G G δ. 7、设有向图D 的度数列为2，3，2，3，出度列为1，2，1，1，求D 的入度列，并求)(),(D D δ?， )(),(D D ++?δ,)(),(D D --?δ. 解：D 的度数列为2，3，2，3，出度列为1，2，1，1，D 的入度列为1,1,1,2. 2)(,3)(==?D D δ,1)(,2)(==?++D D δ,1)(,2)(==?--D D δ 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？ 离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论 离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素； 7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}} 习题参考解答 习题 1、（3）P：银行利率降低 Q：股价没有上升 P∧Q （5）P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 Q P? （7）P：不识庐山真面目 Q：身在此山中 Q→P，或～P→～Q （9）P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 P→Q∧R ，Q→T 2、（1）T （2）F （3）F （4）T （5）F （6）T （7）F （8）悖论 习题 1（3） ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ → （4） ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不， 不， 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解：根据给定的条件有下述命题公式： （A →（CD ））∧～（B ∧C ）∧～（C ∧D ） （～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） （（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ） 离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 ) 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 、 解：原式()(()())p q r r p 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 q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 。 解：公式的真值表如下： 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ [ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 } ⑦ s ⑤⑥假言推理 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论： p u → 证明：用附加前提证明法。 ① p 附加前提引入 习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1. （2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表： 第一章部分课后习题参考答案 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 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，所以这一段的论述为真。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）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (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 q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 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)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p) 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（pr）∧(﹁q∨s) ?（01）∧(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 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，所以这一段的论述为真。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 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (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 q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 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)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). G(x): x+5=9. (1)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快 命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 离散数学第四版课后答案 第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9）， （10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p 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 q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： 4.1 （1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如 果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。 （2）设有序对 1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列, 并给出各命题的: (1)2+2＝4 当且仅 当3+3＝6. (2)2+2＝4 的充要 条件是3+3 6. (3)2+2 4 与3+3 ＝6 互为充要条件. (4)若2+24, 则 3+36, 反之亦然. (1)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. (2)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (3) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (4) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. 1.13．将下列命题符号化, 并给出各命题的真值:(1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p q 1. (2) q p 1. (3) p q 1. (4) p r 当p 0 时为真; p 1 时为假. 1.14．将下 列 . (1) 刘 晓月跑得快, 跳得高. (2) 老王是山东 人或河北人. (3)因为天气冷, 所以我穿了羽 绒服. (4)王欢与李乐组成一个 小组. (5)李辛与李末是兄弟. (6)王强与刘威都学 过法语. (7)他一面 吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他 迟到了. (12)2 与4 都是素数, 这是不对的. (13)“2或4 是素数, 这是不对的”是不对的. ４.１ (1）设Ｓ={１,２｝,R 是S 上的二元关系，且ｘR ｙ。如果Ｒ=Is ，则(A)； 如果R 是数的小于等于关系,则（Ｂ),如果Ｒ=Es ，则（C)。 （2）设有序对<ｘ+2，４>与有序对<５,2x+y>相等，则 ｘ=(D),y=(E). 供选择的答案 Ａ、B 、C ：① x ，y 可任意选择１或2;② ｘ＝1,ｙ=1；③ x=１,y=1 或 ２；x=y=2; ④ ｘ＝2,y=2;⑤ x=y=１或 x ＝y=２;⑥ x=1,ｙ＝2；⑦x=2,y ＝１。 D 、E:⑧ 3；⑨ 2;⑩－2。 答案: Ａ: ⑤ B: ③ Ｃ： ① D: ⑧ Ｅ: ⑩ 4.2设S ＝<1,2，３，４>,R 为S 上的关系，其关系矩阵是 ????? ???????0001100000011001 则（1）R 的关系表达式是（A ）。 (2)dom Ｒ＝(Ｂ),ranR=(C). (3）R ?Ｒ中有(Ｄ)个有序对。 (4）R ˉ1的关系图中有(E)个环。 供选择的答案 A ：①{<1,1>,<1,２>，<1，4>，<4，１>,＜4，3>}; ②{<１,１＞,<1,４＞,<2,1>,<４,1>,＜３,４>}; Ｂ、C ：③{１，2，3,4}；④{１,2，４};⑤{1,４}⑥{1，３,４}。 Ｄ、E ⑦1;⑧３；⑨6；⑩7。 答案： A ：② B:③ Ｃ：⑤ Ｄ:⑩ E:⑦ 4.3设R 是由方程ｘ+３ｙ=１2定义的正整数集Z+上的关系,即 { 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： 证明 设A 上定义的二元关系R 为： ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ① 对任意＜x,y ＞∈A ，因为x y =x y ，所以 ＜＜x,y ＞, ＜x,y ＞＞∈R 即R 是自反的。 ② 设＜x,y ＞∈A ，＜u,v ＞∈A ，若 ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ?u v =x y ?＜＜u,v ＞,＜x,y ＞＞∈R 即R 是对称的。 ③ 设任意＜x,y ＞∈A ，＜u,v ＞∈A ，＜w,s ＞∈A ，对 ＜＜x,y ＞, ＜u,v ＞＞∈R ∧＜＜u,v ＞, ＜w,s ＞＞∈R ?（x y =u v ）∧（u v =w s ）?x y =w s ?＜＜x,y ＞, ＜w,s ＞＞∈R 故R 是传递的，于是R 是A 上的等价关系。 3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使 ………………………………………………最新资料推 荐……………………………………… 1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列命题符号化,并给出各命题的真值: (1)2+2＝4当且仅当3+3＝6.(2)2+2＝ 4的充要条件是3+3≠6.(3)2+2≠4与 3+3＝6互为充要条件.(4)若2+2≠4, 则 3+3≠6,反之亦然. (1)p?q,其中,p: 2+2＝4,q: 3+3＝6, 真值为 1.(2)p??q,其中,p:2+2＝4,q:3+3＝6,真值为0. (3)?p?q,其中,p:2+2＝4,q:3+3＝6,真值为 0.(4)?p??q,其中,p:2+2＝4,q:3+3＝6,真值为1. 1.13．将下列命题符号化, 并给出各命题的真值:(1) 若今天是星期一,则明天是星期二.(2)只有今天 是星期一,明天才是星期二.(3)今天是星期一当 且仅当明天是星期二. (4)若今天是星期一,则明 天是星期三. 令p: 今天是星期一;q:明天是星期二;r:明天是星期三.(1) p→q ? 1. (2) q→p ? 1. (3) p?q? 1. (4)p→r当p ? 0时为真; p ? 1时为假. 1.14．将下列命题符号化. (1) 刘晓月跑得快,跳得高.(2) 老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小 组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃 饭, 一面听音乐. (8)如果天下大雨,他就乘 班车上班.(9)只有天下大雨,他才乘班车上 班.(10)除非天下大雨,他才乘班车上班.(11) 下雪路滑, 他迟到了. (12)2与4都是素数,这是不对的. (13)“2或4是素数,这是不对的”是不对的. 习题3.7 1. 列出关系}6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z 中所有有序4元组。 解 }6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z ,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><= ><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3,1,1,3,2,1,2,3,1,1,3,2,1 2. 列出二维表 3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。 表3.18 航班信息 航空公司 航班 登机口 目的地 起飞时间 Nadir 112 34 底特律 08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛 09:10 Nadir 322 34 底特律 09:44 解 略 3. 当施用投影运算5,3,2π到有序5元组>离散数学第三版课后习题答案
离散数学课后习题答案
离散数学习题答案(耿素云屈婉玲)
离散数学习题解答
屈婉玲版离散数学课后习题答案【1】
离散数学答案屈婉玲版第二版 高等教育出版社课后答案
屈婉玲版离散数学课后习题答案【2】
离散数学课后习题答案(左孝凌版)
离散数学课后答案
离散数学第四版课后标准答案
最新离散数学习题答案
离散数学(屈婉玲版)第四章部分答案
离散数学最全课后答案(屈婉玲版)
离散数学(屈婉玲版)第四章部分标准答案
离散数学习题详细答案
离散数学课后习题答案_(左孝
离散数学最全课后答案(屈婉玲版)
离散数学课后习题答案二
- 离散数学课后答案
- 离散数学课后习题答案(左孝凌版)
- 最新 离散数学(第二版)最全课后习题答案详解
- 离散数学课后习题答案_(左孝凌版)
- 离散数学最全课后答案(屈婉玲版)_0
- 离散数学课后习题答案
- 离散数学 第二版 课后习题答案详解
- 离散数学课后习题答案二
- 最新离散数学课后习题答案_(左孝凌版)
- 离散数学第2版课后答案
- 离散数学课后习题答案(第一章)
- 离散数学课后习题答案-(左孝凌版)
- 离散数学习题详细答案
- 离散数学(第二版)最全课后习题答案详解
- 离散数学最全答案 屈婉玲
- 离散数学课后习题答案
- 离散数学课后习题答案左孝凌版(20200602075307)
- 离散数学(第二版)最全课后习题答案详解
- 离散数学最全最新答案 屈婉玲
- 离散数学课后习题答案第一章