下载文档原格式
离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科，它研究离散对象及其关系、结构和运算方法。
离散数学的应用非常广泛，包括计算机科学、信息科学、密码学、人工智能等领域。
而离散数学第2版是一本经典的教材，它系统地介绍了离散数学的基本概念、原理和方法。
本文将为读者提供离散数学第2版课后习题的答案，帮助读者更好地理解和掌握离散数学的知识。
第一章：基本概念和原理1.1 命题逻辑习题1：命题逻辑的基本符号有哪些？它们的含义是什么？答：命题逻辑的基本符号包括命题变量、命题联结词和括号。
命题变量用字母表示，代表一个命题。
命题联结词包括否定、合取、析取、条件和双条件等，分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。
括号用于改变命题联结词的优先级。
习题2：列举命题逻辑的基本定律。
答：命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。
1.2 集合论习题1：什么是集合？集合的基本运算有哪些？答：集合是由一些确定的对象组成的整体，这些对象称为集合的元素。
集合的基本运算包括并、交、差和补等。
习题2：列举集合的基本定律。
答：集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。
第二章：数理逻辑2.1 命题逻辑的推理习题1：什么是命题逻辑的推理规则？列举几个常用的推理规则。
答：命题逻辑的推理规则是用来推导命题的逻辑规则。
常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。
习题2：使用推理规则证明以下命题：如果A成立，则B成立；B不成立，则A不成立。
答：假言推理规则可以用来证明该命题。
根据假言推理规则，如果A成立，则B成立。
又根据假言推理规则，如果B不成立，则A不成立。
2.2 谓词逻辑习题1：什么是谓词逻辑？它与命题逻辑有何区别？答：谓词逻辑是一种扩展了命题逻辑的逻辑系统，它引入了谓词和量词。
与命题逻辑不同，谓词逻辑可以对个体进行量化和描述。
离散数学答案屈婉玲版第二版高等教育出版社课后答案离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16设p、q的真值为0；r、s的真值为1,求下列各命题公式的真值。
(1) p V (q A r)二0 V (0 A 1) =0(2) ( p?r)A (「q V s)二(0?1)A (1 V 1) = 0A 1= 0.(3) ( — p A 一q A r) ?(p A q A「r)二(1 A 1 A 1) ? (0 A 0A 0)=0(4) (一「A s)—(p A _q) = (0A 1)—(1 A 0) =0—0=117.判断下面一段论述是否为真：“二是无理数。
并且，如果3是无理数，则也是无理数。
另外6能被2整除，6才能被4整除。
”答：p:二是无理数1q: 3 是无理数0r: ' 2是无理数1s: 6能被2整除1t: 6 能被4整除0命题符号化为：p A (q —r) A (t —s)的真值为1,所以这一段的论述为真。
19.用真值表判断下列公式的类型：(4) (p —q) —( 一q—一p)(5) (p A r) ' ( 一p A 一q)(6) ((p —q) A (q —r)) —(p —r)答：(4)p q p —q _q _p —q—一p (p —q) — (一q—一p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 1 0 0 1 1所以公式类型为永真式(5) 公式类型为可满足式(方法如上例)(6) 公式类型为永真式(方法如上例)第二章部分课后习题参考答案3. 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值?⑴飞A q-q)(2) (p -(p V q)) V (p -r)(3) (p V q) -(p A r)答：(2) (p—(p V q) )V (p —r)=(—p V (p V q)) V (_p V r) u - p V p V q V r= 1 所以公式类型为永真式⑶P q r p V q p A r (p V q)—(p A r)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可满足式4. 用等值演算法证明下面等值式：(2) (p —q) A (p —r)二(p —(q A r))⑷(p A - q) V (-p A q)=(p V q) A 一(p A q)证明(2) (p —q) A (p —r)(一p V q) A ( 一p V r):二_ p V (q A r))二p—(q A r)(4) (p A - q) V ( 一p A q)u (p V (一p A q)) A(_ q V (一p A q)-(p V _ p) A (p V q) A ( 一q V 一p) A ( 一q V q)=1 A (p V q) A 一(p A q) A 1二(p V q) A _ (p A q)5. 求下列公式的主析取范式与主合取范式，并求成真赋值(1) ( _p—q) —(一q V p)(2) _(P —q) A q A r(3) (p V (q A r)) -(p V q V r)解：(1) 主析取范式(- p-q) —( 一q p)二_(p q) ( 一q p)=(- p -q) ( 一q p)=(一p _q) (一q p) (一q _p) (p q) (p _q)u ( - 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 i=n (i)(2) 主合取范式为：_(p —q) q r=—(一p q) q ru (p _q) q 产0所以该式为矛盾式?主合取范式为n (0,123,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 i二 1所以该式为永真式永真式的主合取范式为1主析取范式为刀（0,123,4,5,6,7）第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理的证明:(2) 前提：p—. q, —(q r),r(4)前提：q— p,q『s,s『t,t r结论：p q证明：（2）①—(q r) 前提引入②—q —r ①置换③q，一「②蕴含等值式④r 前提引入⑤一q ③④拒取式⑥p- q 前提引入⑦」p (3)⑤⑥拒取式证明（4）：①t r 前提引入②t ①化简律③qi s 前提引入④s—?t 前提引入⑤q r t ③④等价三段论( q > t)(t r q)?⑤置换炉(q >t)⑥化简⑧q ②⑥假言推理⑨ q—；p 前提引入⑩p ⑧⑨假言推理(11)p q ⑧⑩合取15在自然推理系统P中用附加前提法证1 F面各推理:结论：_ p(1)前提：pr (qr r),s r p,q结论：s —? r ①s 附加前提引入②Sr 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.在一阶逻辑中将下面将下面命题符号化，并分别讨论个体域限制为的真值：(1)对于任意 x,均有 2=(x+ )(x ).证明(a),(b) 条件时命题(2)存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合.解:F(x): 2=(x+ 一)(x 一).G(x): x+5=9.(1) 在两个个体域中都解释为-xF(x)，在(a)中为假命题，在(b)中为真命题。
习题一1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明.答：此命题是简单命题，其真值为 1.（2）5 是无理数.答：此命题是简单命题，其真值为 1.（3）3 是素数或 4 是素数.答：是命题，但不是简单命题，其真值为1.（4）2x+ <3 5 答：不是命题.（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年”既可以化答:列出两种符号化的真值表：p q0 0 0 00 1 1 11 0 1 11 1 0 1合命题可以发现,p 与q 不可能同时为真,故上述命题有两种符号化方式.8.将下列命题符号化,并指出真值., 就有；（1）只要, 则；（2）如果, 才有；（3）只有, 才有；（4）除非, 否则；（5）除非（6）仅当.答:设p: , 则: ; 设q: , 则: .符号化真值1（1）（2）（3）（4）（5）1（6）（1）；（2）；；（3）；（4）；（5）；（6）；（7）.答:根据题意,p 为假命题,q 为真命题.自然语言真值（1）只要俄罗斯位于南半球,亚洲人口就最多 1 （2）只要亚洲人口最多,俄罗斯就位于南半球0 （3）只要俄罗斯不位于南半球,亚洲人口就最多 1 （4）只要俄罗斯位于南半球，亚洲人口就不是最多 1 （5）只要亚洲人口不是最多，俄罗斯就位于南半球 1 （6）只要俄罗斯不位于南半球，亚洲人口就不是最多0 （7）只要亚洲人口不是最多，俄罗斯就不位于南半球 1（1）；（2）；（3）；（4）.答:根据题意,p 为真命题,q 为假命题.自然语言真值（1）9 是 3 的倍数当且仅当英语与土耳其相邻0 （2）9 是 3 的倍数当且仅当英语与土耳其不相邻 1 （3）9 不是3 的倍数当且仅当英语与土耳其相邻 1（4） 9 不是 3 的倍数当且仅当英语与土耳其不相邻11. （1） 若 2+2=4,则地球是静止不动的； （2） 若 2+2=4,则地球是运动不止的； （3） 若地球上没有树木,则人类不能生存；（4） 若地球上没有水,则 是无理数.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,反之亦然.答:设 p:2+2=4,q:3+3=6.符号化真值 (1)1(2)(3)(4)1（1） 若今天是星期一,则明天是星期二； （2） 只有今天是星期一,明天才是星期二；命题 1命题 2 符号化 真值 （1） p:2+2=4 q:地球是静止不动的（2） p:2+2=4 q:地球是静止不动的1 （3） p:地球上有树木 q:人类能生存1（4）p:地球上有树木q:人类能生存1（3）今天是星期一当且仅当明天是星期二；（4）若今天是星期一,则明天是星期三.答:设p:今天是星期一,q:明天是星期二,r:明天是星期三.（1）刘晓月跑得快,跳得高；（2）老王是山东人或者河北人；（3）因为天气冷,所以我穿了羽绒服；（4）王欢与李乐组成一个小组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他一面吃饭,一面听音乐；（8）如果天下大雨,他就乘班车上班；（9）只有天下大雨,他才乘班车上班；（10）除非天下大雨,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2 与4 都是素数,这是不对的；（13）“2 或 4 是素数,这是不对的”是不对的.答:(6) p:王强学过法语q:刘威学过法语-(7) p:他吃饭q:他听音乐-(8) p:天下大雨q:他乘车上班-(9) p:天下大雨q:他乘车上班-(10) p:天下大雨q:他乘车上班-(11) p:下雪q:路滑r:他迟到了(12) p:2 是素数q:4 是素数-(13) p:2 是素数q:4 是素数-q：大熊猫产在中国.r:太阳从西方升起. 求下列符合命题的真值：（1）（2）（3）（4）解：p真值为1，q 真值为1，r 真值为0.（1）0，（2）0，（3）0，（4）116.当p,q 的真值为0,r,s 的真值为1 时,求下列各命题公式的真值：（1）（2）（3）（4）解：（1）0，（2）0，（3）0，（4）117.判断下面一段论述是否为真：“ 是无理数.并且,如果3 是无理数,则也是无理数.另外,只有6 能被2 整除,6 才能被4 整除.”解：p: 是无理数q: 3 是无理数r:是无理数s: 6 能被2 整除t：6 能被 4 整除符号化为: ，该式为重言式，所以论述为真。
离散数学第二版答案(6-7章)LT第六章 代数系统6.1第129页1． 证明：任取,x y I ∈，(,)*(,)g y x y x y x yx x y xy g x y ==+-=+-=，因此，二元运算*是可交换的； 任取,,x y z I ∈，(,(,))*(*)*()()g x g y z x y z x y z yz x y z yz x y z yz x y z xy xz yz xyz==+-=++--+-=++---+((,),)(*)*()*()(,(,))g g x y z x y z x y xy zx y xy z x y xy z x y z xy xz yz xyz g x g y z ==+-=+-+-+-=++---+=因此，运算*是可结合的。
该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。
2．证明：任取,,x y N x y ∈≠，由*,*x y x y x y x ==≠知，**y x x y ≠，*运算不是可交换的。
任取,,x y z N ∈，由(*)**x y z x z x ==，*(*)*x y z x y x ==知，(*)**(*)x y z x y z =，*运算是可结合的。
任取x N ∈，*x x x =，可知N 中的所有元素都是等幂的。
*运算有右么元，任取,x y N ∈，*x y x =，知N 中的所有元素都是右么元。
*运算没有左么元。
证明：采用反证法。
假定e 为*运算的左么元，取,b N b e ∈≠，由*的运算公式知*e b e =，由么元的性质知，*e b b =，得e b =，这与b e ≠相矛盾，因此，*运算没有左么元。
3．解： ① 任取y x I y x ≠∈,,的最小公倍数和y x y x =*的最小公倍数和的最小公倍数和y x x y x y ==*因此对于任意的y x I y x ≠∈,,都有x y y x **=，即二元运算*是可交换的。
习题一1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明.答：此命题是简单命题，其真值为 1.（2）5 是无理数.答：此命题是简单命题，其真值为 1.（3）3 是素数或 4 是素数.答：是命题，但不是简单命题，其真值为1.（4）2x+ <3 5 答：不是命题.（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年”既可以化答:列出两种符号化的真值表：p q0 0 0 00 1 1 11 0 1 11 1 0 1根据真值表,可以判断出,只有当p 与q 同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p 与q 不可能同时为真,故上述命题有两种符号化方式.8.将下列命题符号化,并指出真值., 就有；（1）只要, 则；（2）如果, 才有；（3）只有, 才有；（4）除非, 否则；（5）除非（6）仅当.答:设p: , 则: ; 设q: , 则: .符号化真值（1） 1（2） 1（3）0（4）0（5）0（6） 1 ：俄罗斯位于南半球,q：亚洲人口最多,将下面命题用自然语言表述（1）；（2）；；（3）；（4）；（5）；（6）；（7）.答:根据题意,p 为假命题,q 为真命题.自然语言真值（1）只要俄罗斯位于南半球,亚洲人口就最多 1 （2）只要亚洲人口最多,俄罗斯就位于南半球0 （3）只要俄罗斯不位于南半球,亚洲人口就最多 1 （4）只要俄罗斯位于南半球，亚洲人口就不是最多 1 （5）只要亚洲人口不是最多，俄罗斯就位于南半球 1 （6）只要俄罗斯不位于南半球，亚洲人口就不是最多0 （7）只要亚洲人口不是最多，俄罗斯就不位于南半球 1（1）；（2）；（3）；（4）.答:根据题意,p 为真命题,q 为假命题.自然语言真值（1）9 是 3 的倍数当且仅当英语与土耳其相邻0 （2）9 是 3 的倍数当且仅当英语与土耳其不相邻 1 （3）9 不是3 的倍数当且仅当英语与土耳其相邻 1（4） 9 不是 3 的倍数当且仅当英语与土耳其不相邻11. 将下列命题符号化,并给出各命题的真值： （1） 若 2+2=4,则地球是静止不动的； （2） 若 2+2=4,则地球是运动不止的； （3） 若地球上没有树木,则人类不能生存；（4） 若地球上没有水,则 是无理数.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,反之亦然.答:设 p:2+2=4,q:3+3=6.符号化真值 (1)1(2)(3)(4)113. 将下列命题符号化,并讨论各命题的真值： （1） 若今天是星期一,则明天是星期二； （2） 只有今天是星期一,明天才是星期二；命题 1命题 2 符号化 真值 （1） p:2+2=4 q:地球是静止不动的（2） p:2+2=4 q:地球是静止不动的1 （3） p:地球上有树木 q:人类能生存1（4）p:地球上有树木q:人类能生存1（3）今天是星期一当且仅当明天是星期二；（4）若今天是星期一,则明天是星期三.答:设p:今天是星期一,q:明天是星期二,r:明天是星期三.将下列命题符号化：（1）刘晓月跑得快,跳得高；（2）老王是山东人或者河北人；（3）因为天气冷,所以我穿了羽绒服；（4）王欢与李乐组成一个小组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他一面吃饭,一面听音乐；（8）如果天下大雨,他就乘班车上班；（9）只有天下大雨,他才乘班车上班；（10）除非天下大雨,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2 与4 都是素数,这是不对的；（13）“2 或 4 是素数,这是不对的”是不对的.答:(6) p:王强学过法语q:刘威学过法语-(7) p:他吃饭q:他听音乐-(8) p:天下大雨q:他乘车上班-(9) p:天下大雨q:他乘车上班-(10) p:天下大雨q:他乘车上班-(11) p:下雪q:路滑r:他迟到了(12) p:2 是素数q:4 是素数-(13) p:2 是素数q:4 是素数-15.设p：2+3=5.q：大熊猫产在中国.r:太阳从西方升起. 求下列符合命题的真值：（1）（2）（3）（4）解：p真值为1，q 真值为1，r 真值为0.（1）0，（2）0，（3）0，（4）116.当p,q 的真值为0,r,s 的真值为1 时,求下列各命题公式的真值：（1）（2）（3）（4）解：（1）0，（2）0，（3）0，（4）117.判断下面一段论述是否为真：“ 是无理数.并且,如果3 是无理数,则也是无理数.另外,只有6 能被2 整除,6 才能被4 整除.”解：p: 是无理数q: 3 是无理数r:是无理数s: 6 能被2 整除t：6 能被 4 整除符号化为: ，该式为重言式，所以论述为真。
习题1：1. 解 （1）{2，3，5，7，11，13，17，19}（2）{x|x=20*k,k 是自然数}（3）{2，-1}2. 解 （1）{2，4}（2）{1，2，3，4，5}（3）{1，3}（4）{1，3，5}3. 解 （1）{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}（2）φ（3）全体自然数（4）{0，2，4，6，8，10，12，14，16，18，20}（5）1，3，5，7，9，11，13，15，17，19}4. 解 （1）正确（2）正确（3）错误（4）正确5. 解 （1）A={1}，B={{1}}，C={{1}}（2）A={1}，B={{1}}，C={{{1}}}6. 解 （1）正确。
由子集的定义。
（2） 不一定。
如：A={1}，B={{1}}，C={{1}}。
（3）不一定。
如：A={1}，B={1，2}，C={{1，2}}（4）不一定。
如：A={1}，B={1，2}，C={{1，2}}。
7. 解 A={1，2}，B={1}，C={2}，有B A ≠，但是C B C A =成立。
A={1，2}，B={1}，C={1}，有B A ≠，但是C B C A =成立。
8. 解 （1）φ（2）{φ}（3）{{φ}}（4）{φ，{φ}}9. 解 （1）{1,2,3,4,5,6,7,8,9}（2）{0,1,2,3,4,5,6,7,8,9,10}（3）{0,3,6,7,8,9}10. 解 33311. 解 2512. 解（1）454（2）124（3）22013. 解 （1）{φ}（2）{φ，{a}}（3）{φ，{φ}，{a}，{φ,a}}（4）{φ，{φ}，{{φ}}，{{φ},φ}}（5）{φ，{{φ}}，{φ}，{a}，{{φ},φ}，{{φ},a}，{φ,a}，{{φ},φ,a}}14. 证明：假设B ≠C ，则至少存在一元素x ∈B 且x ∉C 。
第二版高等教育出版社课后答案第一章部分课后习题参考答案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 117．判断下面一段论述是否为真：“ 是无理数。
并且，如果 3 是无理数，则 2 也是无理数。
另外6 能被2 整除，6 才能被4 整除。
答：p: 是无理数1q: 3 是无理数0r:2是无理数1s: 6 能被 2 整除1t: 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 p0 0 1 1 10 1 1 0 11 0 0 1 01 1 1 0 0所以公式类型为永真式( 5)公式类型为可满足式(方法如上例) q→ p111(p→q)→( q→ p)1111( 6)公式类型为永真式(方法如上例)第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1)](pAq-q)(2)(p^(pVq))V (p^r)⑶(pVq) 一(pAr)答：(2) (p一(pVq)) V(p-r)= (一pV(pVq))V(「pVr)=「pVpVqVru 1 所以公式类型为永真式⑶p q r PV q p A r (pV q) f (p/\「)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可涉足式4,用等值演算法证明下面等值式：⑵(p 一q)A(p—r) u (p 一(qAij)⑷(p A「q) V「pAq)u (p Vq) A」(p A q)证明(2) (p -q) A (p->r)u (」pVq) A(「pVr)u「P V (q A ij)u p一(q A r)(4) (pA「q) V(「pAq)u (p V(^pAq)) A(「qV(「pAq). (p V「p) A (p Vq) A (「qV「p) A(「qVq)u 1 A (p V q) A - (p A q) A 1u (p V q) A (p A q)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(「p-q)-(「qVp)(2)](p - q) AqAr(3)(p V(q Ar)) 一(p VqVr)解：( 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)m0 m2 m3∑ (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) M1∏ (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))11所以该式为永真式.永真式的主合取范式为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 前提引入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 是矛盾式 , 所以推理正确 .⑩p (11)p q ⑧⑨假言推第四章部分课后习题参考答案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)在两个个体域中都解释为xF(x)，在( a)中为假命题，在(b) 中为真命题。
离散数学第二版答案(6-7章)第六章 代数系统6.1第129页1． 证明：任取,x y I ∈，(,)*(,)g y x y x y x yx x y xy g x y ==+-=+-=，因此，二元运算*是可交换的； 任取,,x y z I ∈，(,(,))*(*)*()()g x g y z x y z x y z yz x y z yz x y z yz x y z xy xz yz xyz==+-=++--+-=++---+((,),)(*)*()*()(,(,))g g x y z x y z x y xy zx y xy z x y xy z x y z xy xz yz xyz g x g y z ==+-=+-+-+-=++---+=因此，运算*是可结合的。
该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。
2．(*,x,)*的最小公倍数=*=y)y（zz的最小公倍数x和yxz因此对于任意的z，x，都有)*，yzy）（=，即二x（x*y**z元运算*是可结合的。
③设幺元为e==的最小公倍数和**，则1=e，即幺元为1.x=exxxee④对于所有的元素I*，所以所有元x∈，都有xx=x素都是等幂的。
4．解：设nX=①设f是X上的二元运算，则f是一个从X2的X→映射。
求X上有多少个二元运算即相当于求这样的映射的个数。
由于22nX=，映射f的个数为2n n，即X上有2n n个二元运算。
②可交换即>yxff,,<>=y<x设集合}4,3,2,1{=X，要求X上可交换的二元运算的个数，即相当于求映射f的个数，X:，其中：f→A><><>><><><<=A><<><><4,41,1,2,23,3}4,34,2,2,1{>3,14,13,2具体如下图所示：A><><><><><><><><><><><><><><><><4,43,32,21,13,4,4,32,4,4,22,3,3,21,4,4,12,3,3,11,2,2,1 X4321此时映射f 的个数44642444++==C N推广到X 有n 个元素时，映射f 的个数nC n n n N +=2③ 单位元素即幺元，若存在必唯一。
第6-7章一．选择/填空1、设图G 的邻接矩阵为0101010010000011100000100，则G 的边数为( D )． A ．5 B ．6 C ．3 D ．42、设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( A )．A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的3、给定无向图G 如下图所示，下面给出的结点集子集中，不是点割集的为（ B ）．A ．{b , d }B ．{d }C ．{a , c }D ．{b , e }4、图G 如下图所示，以下说法正确的是 ( D ) ．A ．{(a , c )}是割边B ．{(a , c )}是边割集C ．{(b , c )}是边割集D ．{(a, c ) ,(b, c )}是边割集5、无向图G 存在欧拉通路，当且仅当(D )．A ．G 中所有结点的度数全为偶数B ．G 中至多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数D ．G 连通且至多有两个奇数度结点6、设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树．A ．1m n −+B ．m n −C ．1m n ++D ．1n m −+7、已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（B ）．A ．8B ．5C ．4D ．38、已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 9、连通无向图G 有6个顶点9条边，从G 中删去 4 条边才有可能得到G 的一棵生成树T ．10、如右图 相对于完全图K 5的补图为（A ）。
11、给定无向图，如下图所示，下面哪个边集不是其边割集（ B ）。
A 、；B 、{<v1,v4>,<v4,v6>};C 、；D 、。
12、设D 是有n 个结点的有向完全图,则图D 的边数为( A ) (A))1(−n n (B))1(+n n (C)2/)1(+n n (D)2/)1(−n n 13、无向图G 是欧拉图,当且仅当( C )(A) G 的所有结点的度数都是偶数 (B)G 的所有结点的度数都是奇数(C)G 连通且所有结点的度数都是偶数 (D) G 连通且G 的所有结点度数都是奇数。
离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案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）（⌝(4)（176能被2q:3r:2s:619（4）(p（5）(p（6）((p答：（pqp→q⌝0011111011011110010011110011所以公式类型为永真式（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 qrp∨qp∧r（p∨q）→(p∧r)0000010010014.(2)(p→(4)(p∧证明（2（45.(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⇔1∧(p⇔(p∨⇔∏(2)⌝(p→q)⇔(p∧(3)⇔⌝⇔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②t③q④s⑤q⑥（⑦（⑧q⑨q⑩p15在自然推理系统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③﹁④￢⑤￢⑥r⑦r⑧r3.:(1)均有2=(x+)(x).(2)其中(a)(b)解：F(x):2=(x+)(x).G(x):x+5=9.(1)在两个个体域中都解释为)(x∀，在（a）中为假命题，在(b)中为真命题。
