(完整版)离散数学实验指导书及其答案

离散数学（第⼆版）课后习题答案详解（完整版）习题⼀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 与q 不可能同时为真,故上述命题有两种符号化⽅式.8.将下列命题符号化,并指出真值., 就有；（1）只要, 则；, 才有；（3）只有, 才有；（4）除⾮, 否则；（5）除⾮（6）仅当.答:设p: , 则: ; 设q: , 则: .（1）；（2）；；（3）；（4）；（5）；（6）；（7）.答:根据题意,p 为假命题,q 为真命题.（1）；（2）；（3）；（4）.答:根据题意,p 为真命题,q 为假命题.（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）若今天是星期⼀,则明天是星期⼆；（2）只有今天是星期⼀,明天才是星期⼆；（3）今天是星期⼀当且仅当明天是星期⼆；（4）若今天是星期⼀,则明天是星期三.答:设p:今天是星期⼀,q:明天是星期⼆,r:明天是星期三.（1）刘晓⽉跑得快,跳得⾼；（2）⽼王是⼭东⼈或者河北⼈；（3）因为天⽓冷,所以我穿了⽻绒服；（4）王欢与李乐组成⼀个⼩组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他⼀⾯吃饭,⼀⾯听⾳乐；（8）如果天下⼤⾬,他就乘班车上班；（9）只有天下⼤⾬,他才乘班车上班；（10）除⾮天下⼤⾬,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2 与4 都是素数,这是不对的；（13）“2 或 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 整除符号化为: ，该式为重⾔式，所以论述为真。

离散数学~习题1.11.下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。

⑴中国有四大发明。

⑵计算机有空吗?⑶不存在最大素数。

⑷21+3＜5。

⑸老王是山东人或河北人。

⑹2与3都是偶数。

⑺小李在宿舍里。

⑻这朵玫瑰花多美丽呀!⑼请勿随地吐痰!⑽圆的面积等于半径的平方乘以 。

⑾只有6是偶数，3才能是2的倍数。

⑿雪是黑色的当且仅当太阳从东方升起。

⒀如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。

2. 将下列复合命题分成若干原子命题。

⑴李辛与李末是兄弟。

⑵因为天气冷，所以我穿了羽绒服。

⑶天正在下雨或湿度很高。

⑷刘英与李进上山。

⑸王强与刘威都学过法语。

⑹如果你不看电影，那么我也不看电影。

⑺我既不看电视也不外出，我在睡觉。

⑻除非天下大雨，否则他不乘班车上班。

解：⑴本命题为原子命题；⑵p：天气冷；q：我穿羽绒服；⑶p：天在下雨；q：湿度很高；⑷p：刘英上山；q：李进上山；⑸p：王强学过法语；q：刘威学过法语；⑹p：你看电影；q：我看电影；⑺p：我看电视；q：我外出；r：我睡觉；⑻p：天下大雨；q：他乘班车上班。

3. 将下列命题符号化。

⑴他一面吃饭，一面听音乐。

⑵3是素数或2是素数。

⑶若地球上没有树木，则人类不能生存。

⑷8是偶数的充分必要条件是8能被3整除。

⑸停机的原因在于语法错误或程序错误。

⑹四边形ABCD是平行四边形当且仅当它的对边平行。

⑺如果a和b是偶数，则a+b是偶数。

解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q⑵p：3是素数；q：2是素数；原命题符号化为：p∨q⑶p：地球上有树木；q：人类能生存；原命题符号化为：⌝p→⌝q⑷p：8是偶数；q：8能被3整除；原命题符号化为：p↔q⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：p↔q。

第一章命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.7.因为p与q不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为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⇔117．判断下面一段论述是否为真：“π是无理数。

并且，如果3是无理数，则2也是无理数。

另外6能被2整除，6才能被4整除。

1-1，1-2（1） 解：a) 是命题，真值为T。

b) 不是命题。

c) 是命题，真值要根据具体情况确定。

d) 不是命题。

e) 是命题，真值为T。

f) 是命题，真值为T。

g) 是命题，真值为F。

h) 不是命题。

i) 不是命题。

（2） 解：原子命题：我爱北京天安门。

A（3） 解：a) (┓P ∧R)→Qb) Q→Rc) ┓Pd) 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∧Qb) 设P：小李看书。

Q：小李听音乐。

P∧Qc) 设P：气候很好。

Q：气候很热。

P∨Qd) 设P： a和b是偶数。

Q：a+b是偶数。

P→Qe) 设P：四边形ABCD是平行四边形。

Q ：四边形ABCD的对边平行。

PQf) 设P：语法错误。

Q：程序错误。

R：停机。

（P∨ Q）→ R(6) 解：a) P:天气炎热。

Q:正在下雨。

P∧Qb) P:天气炎热。

R:湿度较低。

P∧Rc) R:天正在下雨。

S:湿度很高。

R∨Sd) A:刘英上山。

B:李进上山。

A∧Be) M:老王是革新者。

N:小李是革新者。

M∨Nf) L:你看电影。

M:我看电影。

┓L→┓Mg) P:我不看电视。

Q:我不外出。

R:我在睡觉。

P∧Q∧Rh) P:控制台打字机作输入设备。

Q:控制台打字机作输出设备。

P∧Q1-3（1）解：a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b) 是合式公式c) 不是合式公式（括弧不配对）d) 不是合式公式（R和S之间缺少联结词）e) 是合式公式。

（2）解：a） A是合式公式，(A∨B)是合式公式，(A→(A∨B)) 是合式公式。

离散数学习题答案习题一及答案：（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 qp⌝q⌝()p p →⌝()p p q→⌝→⌝001111011010100101110001由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。

20、求下列公式的成真赋值：（4）()p q q⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒0p 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。

离散数学课后答案习题一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(3) ¬ (q→r) ∧r(4)(p→q) →(¬q→¬p)(5)(p∧r) ↔( ¬p∧¬q)(6)((p→q) ∧ (q→r)) → (p→r)(7)(p→q) ↔ (r↔s)答：(1), (4), (6)为重言式.(3)为矛盾式.(2), (5), (7)为可满足式习题二9.用真值表求下面公式的主析取范式.(1) (pνq)ν(¬pΛr)(2) (p→q) →(¬p↔q)答：(1)(2)p q (p → q) →(¬p ↔ q)0 0 1 0 0 10 1 1 1 1 01 0 0 1 1 11 1 1 0 0 0从真值表可见成真赋值为01, 10.于是(p → q) →(¬p ↔ q) ⇔ m1 ∨ m211.用真值表求下面公式的主析取范式和主合取范式；(1) (pνq)Λr(2) p→(pνqνr)(3) ¬(q→¬p)Λ¬p15.用主析取范式判断下列公式是否等值:(1) (p→q) →r与q→ (p→r)(2) ¬(pΛq)与(¬pνq)答：(1)(p→q) →r ⇔¬(¬p∨q) ∨ r ⇔¬(¬p∨q) ∨ r ⇔ 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 = m101 ∨ m100 ∨ m111 ∨m101 ∨ m011 ∨ m001 ⇔m1 ∨ m3 ∨ m4 ∨ m5 ∨ m7 = ∑(1, 3, 4, 5, 7).而 q→(p→r) ⇔¬q ∨(¬p∨r) ⇔¬q ∨¬p ∨r ⇔(¬p∨p)¬∧q∧(¬r∨r) ∨¬p∧(¬q∨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)∨(p∧q∧r) = m0 ∨ m1 ∨ m4 ∨ m5 ∨ m0 ∨ m1 ∨ m2 ∨ m3 ∨ m1 ∨ m3 ∨ m5 ∨m7 ⇔ m0 ∨ m1 ∨ m2 ∨ m3 ∨ m4 ∨ m5 ∨ m7 ⇔∑(0, 1, 2, 3, 4, 5, 7). 两个公式的主吸取范式不同, 所以(p→q) →rk q→ (p→r).16. 用主析取范式判断下列公式是否等值:(1)(p→q) →r与q→ (p→r)(2) ¬ (p∧q)与¬ (p∨q)答：(1)(p→q) →r) ⇔m1∨m3∨m4∨m5∨m7q→ (p→r) ⇔m0∨m1∨m2∨m3∨m4∨m5∨m7所以(p→q) →r) k q→ (p→r)(2)¬ (p∧q) ⇔m0∨m1∨m2¬ (p∨q) ⇔m0所以¬ (p∧q) k ¬ (p∨q)习题三15.在自然推理系统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∨t ⑤附加⑦ (s∨t) →u 前提引入⑧ u ⑥⑦假言推理16.在自然推理系统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 前提引入⑤ r∨s ②③④构造性二难⑥¬ (r∨s) ∧ (r∨s) ①⑤合取⑥为矛盾式, 所以推理正确.18.在自然推理系统P中构造下面推理的证明.(1)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多, 我们就不去颐和园玩. 今天是星期六. 颐和园游人太多. 所以我们去圆明园玩.(2)如果小王是理科学生, 他的数学成绩一定很好. 如果小王不是文科生, 他必是理科生. 小王的数学成绩不好. 所以小王是文科学生.(1)令 p: 今天是星期六;q: 我们要到颐和园玩;r: 我们要到圆明园玩;s:颐和园游人太多.前提: p→ (q∨r), s →¬q, p, s. 结论: r.证明① p 前提引入② p→q∨r前提引入③q∨r①②假言推理④s前提引入⑤ s →¬q前提引入⑥¬q ④⑤假言推理⑦ r ③⑥析取三段论r ¬q s →¬q sq∨r p→q∨r p(2)令p: 小王是理科生,q: 小王是文科生,r: 小王的数学成绩很好.前提: p→r, ¬q→p, ¬r 结论: q证明：① p→r 前提引入②¬r 前提引入③¬p ①②拒取式④¬q→p 前提引入⑤ q ③④拒取式习题四在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.(3)乌鸦都是黑色的.(4)有的人天天锻炼身体. 没指定个体域, 因而使用全总个体域.答：(1) ¬∃x(F(x) ∧¬G(x))或∀x(F(x) →G(x)), 其中, F(x): x为有理数, G(x): x能表示成分数.(2) ¬∀x(F(x) →G(x))或∃x(F(x) ∧¬G(x)), 其中, F(x): x在北京卖菜,G(x): x是外地人.(3) ∀x(F(x) →G(x)), 其中, F(x): x是乌鸦, G(x): x是黑色的.(4) ∃x(F(x) ∧G(x)), 其中, F(x): x是人, G(x): x天天锻炼身体.5. 在一阶逻辑中将下列命题符号化:(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慢.9.给定解释I如下:(a)个体域DI为实数集合\.(b)DI中特定元素⎯a =0.(c)特定函数⎯f (x,y)=x−y, x,y∈DI.(d)特定谓词⎯F(x,y): x=y,⎯G(x,y): x<y, x,y∈DI.说明下列公式在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<y→x≠y), 真值为1.(2) ∀x∀y((x−y=0) →x<y), 真值为0.(3) ∀x∀y((x<y) → (x−y≠0)), 真值为1.(4) ∀x∀y((x−y<0) → (x=y)), 真值为0.习题五5.给定解释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)⇔112.求下列各式的前束范式.(1) ∀xF(x) →∀yG(x, y);(3) ∀xF(x, y) ↔∃xG(x, y);答：前束范式不是唯一的.(1) ∀xF(x) →∀yG(x, y) ⇔∃x(F(x) →∀yG(x, y))⇔∃x∀y(F(x) → G(x, y)).(3) ∀xF(x, y) ↔∃xG(x, y) ⇔ (∀xF(x, y) →∃xG(x, y)) ∧ (∃xG(x, y) →∀xF(x, y)) ⇔ (∀x1F(x1, y) →∃x2G(x2, y)) ∧ (∃x3G(x3, y) →∀x4F(x4, y)) ⇔∃x1∃x2(F(x1, y) → G(x2, y)) ∧∀x3∀x4(G(x3, y) → F(x4, y)) ⇔∃x1∃x2∀x3∀x4((F(x1, y) → G(x2, y)) ∧ (G(x3, y) → F(x4, y))).13.将下列命题符号化, 要求符号化的公式全为前束范式:(1) 有的汽车比有的火车跑得快.(2) 有的火车比所有的汽车跑得快.(3) 说所有的火车比所有的汽车跑得快是不对的.(4) 说有的飞机比有的汽车慢是不对的.答：(1)令F(x):x是汽车,G(y):y是火车,H(x,y):x比y跑得快.∃x(F(x)∧∃y(G(y)∧H(x,y))⇔∃x∃y(F(x)∧G(y)∧H(x, y)).(2)令F(x):x是火车, G( y): y 是汽车,H(x,y):x比y跑得快.∃x(F(x)∧∀y(G(y)→ H(x,y)))⇔∃x∀y(F(x)∧(G y)→H(x,y))).;错误的答案:∃x∀y(F(x)∧G(y)→H(x,y)).(3)令F(x):x是火车,G(y):y是汽车,H(x,y):x比y跑得快.¬∀x(F(x)→∀y(G(y)→H(x,y)))⇔¬∀x∀y(F(x)→(G(y)→H(x,y)))⇔¬∀x∀y(F(x)∧G(y)→H(x,y))(不是前束范式)⇔∃x∃y(F(x)∧G(y)∧H(x,y)).(4)令F(x):x是飞机,G(y):y是汽车,H(x,y):x比y跑得慢.¬∃x(F(x)∧∃y(G(y)∧H(x,y)))⇔¬∃x∃y(F(x)∧G(y)∧H(x,y))(不是前束范式)⇔∀x∀y¬(F(x)∧G(y)∧H(x,y))⇔∀x∀y(F(x)∧G(y)→¬H(x,y)).21.24.在自然推理系统F中, 构造下面推理的证明:每个喜欢步行的人都不喜欢骑自行车. 每个人或者喜欢骑自行车或者喜欢乘汽车. 有的人不喜欢乘汽车, 所以有的人不喜欢步行. (个体域为人类集合) 答：令 F(x): x 喜欢步行, G( x): x喜欢骑自行车, H(x): x 喜欢乘汽车.前提:∀x(F(x)→¬G(x)), ∀x(G(x)∨H(y)),∃x¬H(x).结论:∃x¬F(x).② ∀x(G(x) ∨ H(y)) 前提引入② G(c) ∨ H(c) ①UI③∃x¬H(x) 前提引入④¬H(c) ③UI⑤ G(c) ②④析取三段⑥∀x(F(x) →¬G(x)) 前提引入⑦ F(c) →¬G(c) ⑥UI⑧¬F(c) ⑤⑦拒取⑨∃x¬F(x) ⑧EG习题七12.设A={0, 1, 2, 3}, R是A上的关系, 且R={〈0, 0〉, 〈0, 3〉, 〈2, 0〉, 〈2,1〉, 〈2, 3〉, 〈3, 2〉} 给出R的关系矩阵和关系图.16.设A={a,b,c,d}, R1,R2为A上的关系, 其中R1={〈a,a〉,〈a,b〉,〈b,d〉}R2={〈a,d〉,〈b,c〉,〈b,d〉,〈c,b〉} 求R1·R2, R2·R1,R1²,R2³. R1·R2={〈a,a〉,〈a,c〉,〈a,d〉},R2·R1={〈c,d〉}, R1²={〈a,a〉,〈a,b〉,〈a,d〉},R2³={〈b,c〉,〈b,d〉,〈c,b〉}20.设R1和R2为A上的关系,证明: (1)(R1∪R2) −1=R1−1∪R2−1(2)(R1∩R2) −1=R1−1∩R2−1答：(1)(R1∪R2)−1=R1−1∪R2−1任取〈x,y〉〈x,y〉(∈R1∪R2)−1⇔〈y,x〉(∈R1∪R2)⇔〈y,x〉∈R1∨ (y,x)∈R2)⇔〈x,y〉∈R1−1∨〈x,y〉∈R2−1⇔〈x,y〉∈R1−1∨R2−1所以(R1∪R2) −1=R1−1∪R2−1(2)(R1∩R2) −1=R1−1∩R2−1 任取〈x,y〉〈x,y〉(∈R1∩R2) −1⇔〈y,x〉(∈R1∩R2)⇔〈y,x〉∈R1∧ (y,x)∈R2)⇔〈x,y〉∈R1−1∧〈x,y〉∈R2−1⇔〈x,y〉∈R1−1∧R2−1所以(R1∪R2) −1=R1−1∩R2−126.33.43.16.47.。

离散数学课后习题答案1. 第一章习题答案1.1 习题一答案1.1.1 习题一.1 答案根据题意，设集合A和B如下：Set A and BSet A and B在此情况下，我们可以得出以下结论：•A的幂集为{ {}, {a}, {b}, {a, b} }；•B的幂集为{ {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }；•A和B的笛卡尔积为{ (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }。

因此，习题一.1的答案为：•A的幂集为{ {}, {a}, {b}, {a, b} }；•B的幂集为{ {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }；•A和B的笛卡尔积为{ (a, 1), (a, 2), (a, 3), (b, 1), (b,2), (b, 3) }。

1.1.2 习题一.2 答案根据题意，集合A和B如下所示：Set A and BSet A and B根据集合的定义，习题一.2要求我们判断以下命题的真假性：a)$A \\cap B = \\{ 2, 3 \\}$b)$\\emptyset \\in B$c)$A \\times B = \\{ (a, 2), (b, 1), (b, 3) \\}$d)$B \\subseteq A$接下来，我们来逐个判断这些命题的真假性。

a)首先计算集合A和B的交集：$A \\cap B = \\{ x\\,|\\, x \\in A \\, \\text{且} \\, x \\in B \\} = \\{ 2, 3 \\}$。

因此，命题a)为真。

b)大家都知道，空集合是任意集合的子集，因此空集合一定属于任意集合的幂集。

根据题意，$\\emptyset \\in B$，因此命题b)为真。

c)计算集合A和B的笛卡尔积：$A \\times B = \\{ (x, y) \\,|\\, x \\in A \\, \\text{且} \\, y \\in B \\} = \\{ (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) \\}$。

习题一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. 熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。

2. 熟练掌握常用的基本等价式及其应用。

3. 熟练掌握（主）析/合取范式的求法及其应用。

4. 熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。

5. 熟练掌握形式演绎的方法。

教学重点：1 .命题的概念及判断2 .联结词，命题的翻译3. 主析（合）取范式的求法4. 逻辑推理教学难点：1. 主析（合）取范式的求法2. 逻辑推理1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母 A , B,…，Z或带下标的大写字母或数字表示,如A i, [10], R等，例如A1：我是一名大学生。

A1：我是一名大学生.[10]:我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1否定联结词「P1.2.2合取联结词A1.2.3 析取联结词V1.2.4 条件联结词—125126 与非联结词T性质：(1)P T P=「( PAP)二「P；(2)(P T Q)T( P T Q) -「( P T Q) - PAQ；(3)( P T P)T( Q TQ) -「P T「Q= P V Q。

127 或非联结词J性质:(1) P J P=「( P V Q) =「P;(2)( P J Q )；( P J Q) =「( P J Q) = P V Q;(3)( P J P)J( Q J Q) =「P Q=P V-Q) = PAQ1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2 ）如果P是公式，则「P是公式；（3）如果P、Q是公式,则PAQ、PVQ、P > Q、P Q都是公式；（4）当且仅当能够有限次的应用（1）、（2）、（3）所得到的包括命题变元、联结词和括号的符号串是公式。

1-1，1-2（1） 解：a) 是命题，真值为T。

b) 不是命题。

c) 是命题，真值要根据具体情况确定。

d) 不是命题。

e) 是命题，真值为T。

f) 是命题，真值为T。

g) 是命题，真值为F。

h) 不是命题。

i) 不是命题。

（2） 解：原子命题：我爱北京天安门。

复合命题：如果不是练健美操，我就出外旅游拉。

（3） 解：a) (┓P ∧R)→Qb) Q→Rc) ┓Pd) 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∧Qb) 设P：小李看书。

Q：小李听音乐。

P∧Qc) 设P：气候很好。

Q：气候很热。

P∨Qd) 设P： a和b是偶数。

Q：a+b是偶数。

P→Qe) 设P：四边形ABCD是平行四边形。

Q ：四边形ABCD的对边平行。

PQf) 设P：语法错误。

Q：程序错误。

R：停机。

（P∨ Q）→ R(6) 解：a) P:天气炎热。

Q:正在下雨。

P∧Qb) P:天气炎热。

R:湿度较低。

P∧Rc) R:天正在下雨。

S:湿度很高。

R∨Sd) A:刘英上山。

B:李进上山。

A∧Be) M:老王是革新者。

N:小李是革新者。

M∨Nf) L:你看电影。

M:我看电影。

┓L→┓Mg) P:我不看电视。

Q:我不外出。

R:我在睡觉。

P∧Q∧Rh) P:控制台打字机作输入设备。

Q:控制台打字机作输出设备。

P∧Q1-3（1）解：a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b) 是合式公式c) 不是合式公式（括弧不配对）d) 不是合式公式（R和S之间缺少联结词）e) 是合式公式。

离散数学课后习题答案离散数学课后习题答案离散数学是计算机科学中的一门重要课程，它涵盖了诸多数学概念与技巧，为计算机科学的理论基础打下了坚实的基础。

在学习离散数学的过程中，课后习题是巩固知识、提高能力的重要途径。

然而，有时候我们会遇到一些难以解答的问题，需要参考一些答案来进行思考与学习。

本文将为大家提供一些离散数学课后习题的答案，希望能对大家的学习有所帮助。

一、集合论1. 设A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。

答案：A∪B={1,2,3,4}，A∩B={2,3}。

2. 证明：任意集合A和B，有(A-B)∪(B-A)=(A∪B)-(A∩B)。

答案：首先，对于任意元素x，如果x属于(A-B)∪(B-A)，那么x属于A-B或者x属于B-A。

如果x属于A-B，那么x属于A∪B，但x不属于A∩B；如果x属于B-A，同样有x属于A∪B，但x不属于A∩B。

所以(A-B)∪(B-A)属于(A∪B)-(A∩B)。

另一方面，对于任意元素x，如果x属于(A∪B)-(A∩B)，那么x属于A∪B，但x不属于A∩B。

所以x属于A或者x属于B。

如果x属于A，但x不属于B，那么x属于A-B；如果x属于B，但x不属于A，那么x属于B-A。

所以x属于(A-B)∪(B-A)。

所以(A∪B)-(A∩B)属于(A-B)∪(B-A)。

综上所述，(A-B)∪(B-A)=(A∪B)-(A∩B)。

证毕。

二、逻辑与证明1. 证明：如果p为真命题，那么¬p为假命题。

答案：根据命题的定义，命题要么为真，要么为假，不存在其他情况。

所以如果p为真命题，那么¬p为假命题。

2. 证明：对于任意整数n，如果n^2为偶数，则n为偶数。

答案：假设n为奇数，即n=2k+1（k为整数）。

那么n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1。

根据偶数的定义，2(2k^2+2k)为偶数，所以n^2为奇数。

实验六洒水车路线问题●实验所属系列：离散数学课程实验●实验对象：本科●相关课程及专业：离散数学，计算机科学与技术●实验类型：设计型实验●实验时数（学分）：4学时实验目的解决与图论中欧拉回路有关的实际问题，扩展对于书本知识的理解，提高程序设计能力和逻辑思维能力。

实验内容与要求一辆洒水车从所在的市政办公点出发，需要在所有负责的街道上洒水，并最后回到原点。

问洒水车如何设计路线才能使得走的路程最短。

实验的软硬件环境PC机一台，装有C/C++/JA V A语言集成开发环境。

实验过程和方法1）对给定问题进行理论分析；将这个问题抽象成图论的语言，就是给定一个连通图，每条边的权值就是街道的长度，本问题转化为在图中求一条回路，使得回路的总权值最小。

如果街道的连通图为欧拉图，则只要求出图中的一条欧拉回路即可。

否则，洒水车要完成任务就必须在某些街道上重复走若干次。

如果重复走一次，就加一条平行边，于是原来对应的图形就变成了多重图。

只是要求加进的平行边的总权值最小就行了。

于是，问题就转化为，在一个有奇度数结点的赋权连通图中，增加一些平行边，使得新图不含奇度数结点，并且增加的边的总权值最小。

因此，问题的关键在于如何增加这些平行边。

设V1为图中所有奇度数节点的集合，下面给出了算法：1．使用弗洛伊德算法计算图中任一两结点间的最短路径长度。

2．构成一个|V1|×|V1|的矩阵，这个矩阵给出了图中每两个奇度数结点间的最短路径长度，3．将矩阵中的结点进行两两组合，找出一个最佳的组合情况，这种组合使得他们的最短路径长度之和最小。

4．根据前面得到的最佳组合，求出各对组合的最短路径。

并将最短路径上的每条边都加一条平行边。

5．利用Fleury算法求欧拉回路。

下面举例说明这个算法：上图的奇度数结点为1，3，6，11奇度数结点构成的矩阵为136111-153876315-247663824-5211767652-结点的最佳组合为:136111-153876315-247663824-5211767652-由于是对称的矩阵，我们只关心上三角部分:136111-153876315-247663824-5211767652-现在我们得到1和3，6和11之间的最短路径(1;3) (6;9), (9;11)将最短路径上的边各添加一条平行边。

离散数学课后答案第一章离散数学基础题目1问题：证明集合A和集合B的笛卡尔积的基数等于集合A 和集合B的基数的乘积。

答案：设集合A的基数为|A|，集合B的基数为|B|。

我们要证明集合A和集合B的笛卡尔积的基数等于集合A和集合B的基数的乘积，即|(A x B)| = |A| * |B|。

首先，我们可以将集合A x B表示为{(a, b) | a∈A, b∈B}。

由于A和B是两个集合，集合A x B中的元素可以看作是将A 中每个元素与B中每个元素组成的有序对。

因此，集合A x B 中的元素个数等于A中元素的个数乘以B中元素的个数，即|(A x B)| = |A| * |B|。

题目2问题：对任意两个集合A和B，证明A∩(A∪B) = A。

答案：要证明A∩(A∪B) = A，首先我们需要理解集合的交和并的定义。

- 集合的交：集合A∩B表示同时属于集合A和集合B的元素组成的集合。

- 集合的并：集合A∪B表示属于集合A或集合B的元素组成的集合。

现在，我们开始证明。

首先，根据集合的并的定义，A∪B 表示属于集合A或集合B的元素组成的集合。

因此，任意属于集合A的元素也一定属于A∪B，即A⊆A∪B。

其次，根据集合的交的定义，A∩(A∪B)表示同时属于集合A和集合A∪B的元素组成的集合。

由于A⊆A∪B，所以A中的元素一定属于A∪B，因此A∩(A∪B) = A。

综上所述，对任意两个集合A和B，A∩(A∪B) = A成立。

第二章命题逻辑题目1问题：证明合取命题的真值表达式。

答案：合取命题的真值表达式表示命题P和命题Q同时为真时合取命题为真，否则为假。

假设命题P和命题Q的真值分别为真（T）或假（F），那么合取命题的真值可以通过以下真值表得出：P Q P∧QT T TT F FF T FF F F从上述真值表可以看出，只有P和Q都为真时，合取命题才为真。

如果其中一个或两个命题为假，则合取命题为假。

题目2问题：证明命题的等价关系。

第1章 命题逻辑P7 习题1. 给出下列命题的否定命题： （1）大连的每条街道都临海。

否命题：不是大连的每条街道都临海。

（2）每一个素数都是奇数。

否命题： 并非每一个素数都是奇数。

2. 对下述命题用中文写出语句： （1）()P R Q ⌝∧→如果非P 与R ，那么Q 。

（2）Q R ∧Q 并且R 。

3. 给出命题P Q →，我们把Q P →、P Q ⌝→⌝、Q P ⌝→⌝分别称为命题P Q →的逆命题、反命题、逆反命题。

（1）如果天不下雨，我将去公园。

解：逆命题：如果我去公园，则天不下雨； 反命题：如果天下雨，则我不去公园；逆反命题：如果我不去公园，则天下雨了。

（2）仅当你去我才逗留。

解：（此题注意：p 仅当q 翻译成p q →） 逆命题：如果你去，那么我逗留。

反命题：如果我不逗留，那么你没去。

逆反命题：如果你没去，那么我不逗留。

（3）如果n 是大于2的正整数，那么方程nn n xy z +=无整数解。

解：逆命题：如果方程nn n xy z +=无整数解，那么n 是大于2的正整数。

反命题：如果n 不是大于2的正整数，那么方程nn n x y z +=有整数解。

逆反命题：如果方程nn n xy z +=有整数解，那么n 不是大于2的正整数。

（4）如果我不获得更多的帮助，那么我不能完成这项任务。

解：逆命题：如果我不完成任务，那么我不获得更多的帮助。

反命题：如果我获得了更多的帮助，那么我能完成任务。

逆反命题：如果我能完成任务，那么我获得了更多的帮助。

4. 给P 和Q 指派真值T ，给R 和S 指派真值F ，求出下列命题的真值。

（1）(()(()()))P Q R Q P R S ⌝∧∨⌝∨↔⌝→∨⌝=(()(()()))T T F T T F F ⌝∧∨⌝∨↔⌝→∨⌝ =()T F T ⌝∨→ =T F ∨ =T（2）()Q P Q P ∧→→ =()T T T T ∧→→ =T T T ∧→ =T T →=T（3）((()))()P Q R P Q S ∨→∧⌝↔∨⌝=((()))()T T F T T F ∨→∧⌝↔∨⌝ =(())T T F T ∨→↔ =T T ↔ =T（4）()()P R Q S →∧⌝→ =()()T F T F →∧⌝→=()F F F ∧→=F5. 构成下来公式的真值表： （1）()Q P Q P ∧→→（2）()()()P Q R P Q P R ⌝∨∧↔∨∧∨（3）()P Q Q P P R ∨→∧→∧⌝（4）()P P Q R Q R ⌝→∧⌝→∧∨⌝6. 使用真值表证明：如果P Q ↔为T ，那么P Q →和Q P →都是T ，反之亦然。

实验一命题逻辑公式化简【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。

【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。

实验用例：用化简命题逻辑公式的方法设计一个5人表决开关电路，要求3人以上（含3人）同意则表决通过（表决开关亮）。

【实验原理和方法】（1）写出5人表决开关电路真值表，从真值表得出5人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。

（2）上面公式中的每一个联结词是一个开关元件，将它们定义成C语言中的函数。

（3）输入5人表决值（0或1），调用上面定义的函数，将5人表决开关电路真值表的等价公式写成一个函数表达式。

（4）输出函数表达式的结果，如果是1，则表明表决通过，否则表决不通过。

参考代码：#include<stdio.h>int vote(int a,int b,int c,int d,int e){//五人中任取三人的不同的取法有10种。

i f( a&&b&&c || a&&b&&d || a&&b&&e || a&&c&&d || a&&c&&e || a&&d&&e || b&&c&&d || b&&c&&e || b&&d&&e || c&&d&&e)return 1;e lsereturn 0;}void main(){i nt a,b,c,d,e;p rintf("请输入第五个人的表决值（0或1，空格分开）：");s canf("%d%d%d%d%d",&a,&b,&c,&d,&e);i f(vote(a,b,c,d,e))printf("很好，表决通过！\n");e lseprintf("遗憾，表决没有通过！\n");}//注：联结词不定义成函数，否则太繁实验二命题逻辑推理【实验目的】加深对命题逻辑推理方法的理解。

离散数学（第⼆版）最全课后习题答案详解习题⼀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:刘红与魏新是同学.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（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 q 0 0 1 10 1 0 10 1 1 00 1 1 1根据真值表,可以判断出,只有当 p 与 q 同时为真时两种符号化的表⽰才会有不同的真值,但结合命题可以发现,p 与 q 不可能同时为真,故上述命题有两种符号化⽅式.8.将下列命题符号化,并指出真值.,就有（1）只要（2）如果（3）只有（4）除⾮（5）除⾮（6）,则:;设 q:,则:答:设 p: .符号化真值（1）（2）（3）（4）（5）1 1 0 0 0（6） 19.设p：俄罗斯位于南半球,q：亚洲⼈⼝最多,将下⾯命题⽤⾃然语⾔表述,并指出其真值：（1）（2）；；；（3）（4）；；（5）（6）（7）；；.答:根据题意,p为假命题,q为真命题.⾃然语⾔真值（1）（2）（3）（4）（5）（6）（7）只要俄罗斯位于南半球,亚洲⼈⼝就最多只要亚洲⼈⼝最多,俄罗斯就位于南半球11111 只要俄罗斯不位于南半球,亚洲⼈⼝就最多只要俄罗斯位于南半球，亚洲⼈⼝就不是最多只要亚洲⼈⼝不是最多，俄罗斯就位于南半球只要俄罗斯不位于南半球，亚洲⼈⼝就不是最多只要亚洲⼈⼝不是最多，俄罗斯就不位于南半球10．设p：9是3的倍数,q：英国与⼟⽿其相邻,将下⾯命题⽤⾃然语⾔表述,并指出真值：.答:根据题意,p为真命题,q为假命题.⾃然语⾔真值（1）（2）（3）9是3的倍数当且仅当英语与⼟⽿其相邻9是3的倍数当且仅当英语与⼟⽿其不相邻9不是3的倍数当且仅当英语与⼟⽿其相邻11（4）9不是 3的倍数当且仅当英语与⼟⽿其不相邻 011．将下列命题符号化,并给出各命题的真值：（1）若 2+2=4,则地球是静⽌不动的；（2）若 2+2=4,则地球是运动不⽌的；（3）若地球上没有树⽊,则⼈类不能⽣存；（4）若地球上没有⽔,则是⽆理数. 答:命题 1命题 2符号化真值（1）（2）（3）（4）p:2+2=4 q:地球是静⽌不动的 q:地球是静⽌不动的 q:⼈类能⽣存0 p:2+2=4 1 1 1p:地球上有树⽊ p:地球上有树⽊q:⼈类能⽣存12.将下列命题符号化,并给出各命题的真值：（1）2+2=4当且仅当 3+3=6；（2）2+2=4的充要条件是 3+36；（3）2+2 4与 3+3=6互为充要条件；（4）若 2+2 4,则 3+3 6,反之亦然. 答:设p:2+2=4,q:3+3=6. 符号化真值 (1) (2) (3) (4)（3）今天是星期⼀当且仅当明天是星期⼆；（4）若今天是星期⼀,则明天是星期三.答:设p:今天是星期⼀,q:明天是星期⼆,r:明天是星期三.符号化真值讨论(1)(2)(3)(4)不会出现前句为真,后句为假的情况不会出现前句为真,后句为假的情况必然为1若p为真,则真值为0;若p为假,则真值为114.将下列命题符号化：（1）刘晓⽉跑得快,跳得⾼；（2）⽼王是⼭东⼈或者河北⼈；（3）因为天⽓冷,所以我穿了⽻绒服；（4）王欢与李乐组成⼀个⼩组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他⼀⾯吃饭,⼀⾯听⾳乐；（8）如果天下⼤⾬,他就乘班车上班；（9）只有天下⼤⾬,他才乘班车上班；（10）除⾮天下⼤⾬,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2与4都是素数,这是不对的；（13）“2或4是素数,这是不对的”是不对的.答: 命题1 命题2命题3符号化(1)(2)p:刘晓⽉跑得快q:刘晓⽉跳得⾼-p:⽼王是⼭东⼈p:天⽓冷q:⽼王是河北⼈----q:我穿⽻绒服p:王欢与李乐组成p:王欢与李乐组成⼀个--⼀个⼩组⼩组p:李⾟与李末是兄p:李⾟与李末是兄弟弟(6)(7) p:王强学过法语p:他吃饭q:刘威学过法语q:他听⾳乐q:他乘车上班q:他乘车上班q:他乘车上班q:路滑--(8) p:天下⼤⾬p:天下⼤⾬p:天下⼤⾬p:下雪-(9) -(10)(11)r:他迟到了p:2是素数p:2是素数q:4是素数--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整除18.在什么情况下,下⾯⼀段论述是真的:“说⼩王不会唱歌或⼩李不会跳舞是正确的,⽽说如果⼩王会唱歌,⼩李就会跳舞是不正确的.”解：p:⼩王会唱歌。