篇一：离散数学习题答案-2015
离散数学习题答案
习题一
1、利用逻辑联结词把下列命题翻译成符号逻辑形式
（1） 他既是本片的编剧，又是导演 --- P ∧ Q （2） 银行利率一降低，股价随之上扬--- P → Q （3） 尽管银行利率降低，股价却没有上扬 --- P ∧ Q （4） 占据空间的、有质量而且不断变化的对象称为物质--- M ??(S∧P∧T) （5） 他今天不是乘火车去北京，就是随旅行团去了九寨沟 --- P ▽ Q
（6） 小张身体单薄，但是极少生病，并且头脑好使--- P ∧ Q ∧ R （7） 不识庐山真面目，只缘身在此山中 --- P → Q
（解释：因为身在此山中，所以不识庐山真面目）
（8） 两个三角形相似，当且仅当他们的对应角相等或者对应边成比例
--- S ??(E∨T)
（9） 如果一个整数能被6整除，那么它就能被2和3整除。如果一个整数能被3整除，
那么它的各位数字之和也能被3整除
解：设 P – 一个整数能被6整除 Q – 一个整数能被2整除 R – 一个整数能被3整除 S – 一个整数各位数字之和能被3整除 翻译为：（P → （Q ∧ R））∧ （R → S）
2、判别下面各语句是否命题，如果是命题，说出它的真值
（1）BASIC语言是最完美的程序设计语言 --- Y，T/F （2）这件事大概是小王干的 --- N （3）x2 = 64--- N （4）可导的实函数都是连续函数 --- Y，T/F （5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利 --- N （6）客观规律是不以人们意志为转移的--- Y，T （7）到2020年，中国的国民生产总值将赶上和超过美国 --- Y，N/A （8）凡事都有例外 --- Y，F
3、构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式
（1）（P ∨（～P ∧ Q））→ Q 解：
4、利用真值表方法验证下列各式为永真式
（1）~（8）略
5、证明下列各等价式
（3）P→（Q∨ R）? （P → Q）∨（P → R） 证明：左式 ? ～P∨Q∨ R
? ～P∨Q∨～P∨ R
? （～P∨Q）∨（～P∨ R）
? （P → Q）∨（P → R）? 右式
（4）（P∧ Q）∨（R∧ Q）∨（R∧ P）? （P∨ Q）∧（R∨ Q）∧（R∨ P） 证明：左式 ? (（P∨R）∧ Q）∨（R∧ P）
? (（P∨R）∨R) ) ∧(（P∨R）∨P) ) ∧（Q∨R）∧（Q∨P） ? （P∨ Q）∧（R∨ Q）∧（R∨ P）? 右式
6、如果P∨ Q ? Q∨R,能否断定 P ? R ？ 如果P∧ Q ? Q∧R，能否断定 P ? R？如果～P ? ～R，能否断定 P ? R？
解： （1）如果P∨ Q ? Q∨R，不能判断P ? R，因为如果 Q = P∨ R, 那么P∨ Q? P∨P∨ R ? Q∨R，但P可以不等价于R.
（2）如果P∧ Q ? Q∧R，不能判断P ? R，因为如果 Q = P∧ R, 那么P∧ Q? P∧P∧ R ? Q∧R，但P可以不等价于R.
（3）如果～P ? ～R，那么有P ? R，因为～P ? ～R，则～P <-> ～R为永真式，及有P <-> R为永真式，所以P ? R.
8、把下列各式用↑等价表示出来
（1）(P∧Q) ∨～P
解：原式 ? ((P↑Q) ↑ (P↑Q)) ∨(P↑P)
? (((P↑Q) ↑ (P↑Q)) ↑((P↑Q) ↑ (P↑Q))) ↑((P↑P) ↑(P↑P))
9、证明：{ ～ →}是最小功能完备集合
证明: 因为{～, ∨}是最小功能完备集合,所以,如果{ ～ →}能表示出∨,则其是功能完备集合。由于 P ∨ Q ? (～P) →Q ,所以{ ～ →}是功能完备集合。因为～ →不能相互表示，所以{ ～ →}是最小功能完备集合；同理可证：{非，条件非}也能将或表示出来： P ∨ Q ? ～(～P ! → Q)
8、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:
(3) P→(R∧(Q→P)) 解：真值表法
主合取范式为 = (～P∨Q∨R) ∧(～P∨～Q∨R) = M4∧M6
主析取范式为 = (～P∧～Q∧～R)∨(～P∧～Q∧R)∨(～P∧Q∧～R)∨(～P∧Q∧R)∨(P∧～Q∧R)∨(P∧Q∧R) = m0∨m1∨m2∨m3∨m5∨m7 等价变换法（略）
(4) (P→(Q∧R)) ∧(～P→(～Q∧～R)) 解：真值表法
主合取范式为 = (P∨Q∨～R) ∧( P∨～Q∨R) ∧( P∨～Q∨～R) ∧(～P∨Q∨R) ∧(～ P∨Q∨～R) ∧(～ P∨～Q∨R) = M1∧M2∧M3∧M4∧M5∧M6 主析取范式为 = (～P∧～Q∧～R)∨(P∧Q∧R) = m0∨m7 等价变换法（略）
14、从A,B,C,D 4个人中派2人出差，要求满足下列条件：如果A去，则必须在C或D中选一人同去；B和C不能同时去；C和D不能同时去。用构造范式的方法决定选派方案。
解：由题设 A：A去，B：B去，C：C去，D：D去则满足条件的选派应满足如下范式： （A→（C?D））∧～（B∧C）∧～（C∧D）
构造和以上范式等价的主析取范式 （A→（C?D））∧～（B∧C）∧～（C∧D）
?（～A∧～B∧ ～C ∧D ）∨（～A∧～B∧～C∧～D）∨（～A∧～B∧C∧～D）∨（～A∧B∧～C∧～D）∨（A∧～B∧C∧～D）∨（A∧～B∧～C∧D）∨（～A∧B∧～C∧D）∨（A∧B∧～C∧D）
共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：（A∧～B∧C∧～D），（A∧～B∧～C∧D），（～A∧B∧～C∧D） 即有三种方案：A和C去或者A和D去或者B和D去。
15、证明下列蕴含试：
（1）P→Q=>P →(P∧Q)
证明：P→Q ? ～P ∨Q ? T∧(～P ∨Q) ? (～P∨P) ∧ (～P ∨Q) ? ～P ∨(P∧Q) ? P →(P∧Q)
所以，这是个等价式，因此也是个蕴含式 （2）(P→Q) →Q=> (P∨Q)
证明：(P→Q) →Q ? ～(～P∨Q) ∨Q ? (P∧～Q) ∨Q ? (P∨Q) ∧(Q∨～Q) ? (P∨Q) ∧ T ? (P∨Q)
所以，这是个等价式，因此也是个蕴含式 （3）P∧～P∧R=>S
证明：P∧～P∧R ? F => S (F可蕴含任何命题公式) （4）P=>Q∨R∨～R
证明：P=>T ? Q∨R∨～R （任何公式可蕴含永真式）
18、一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：
（1） 如果藏宝的房子靠近池塘，那么珍宝不会藏在东厢房。 （2） 如果房子的前院栽有大柏树，那么珍宝就藏在东厢房。 （3） 藏宝房子靠近池塘。
（4） 要么前院栽有大柏树，要么珍宝埋在花园正中地下。 （5） 如果后院栽有香樟树，珍宝藏在附近。 请利用蕴含关系找出藏宝处
解：根据给定的条件有下述命题： P：珍宝藏在东厢房 Q：藏宝的房子靠近池塘 R：房子的前院栽有大柏树 S：珍宝藏在花园正中地下 T：后院栽有香樟树 M：珍宝藏在附近 根据题意，得出：
（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M） ?？ （Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M） ?～P∧（R→P）∧（R∨S）∧（T→M） ?～R∧（R∨S）∧（T→M） ?S∧（T→M）
?S 即珍宝藏在花园正中地下
20、演绎证明下面各蕴含式：
（4）(R→Q) ∧(R→S),(Q→E) ∧(S→B), ～(E∧B),(P→R) ? ～P 证明：运用反证方法，将结论的非纳入前提，证明步骤如下 [1] P p(附加前提) [2] P→Rp
[3] R T [1,2] I [4] (R→Q) ∧(R→S) p
[5] Q∧ST [3,4] I [6] (Q→E) ∧(S→B) p
[7] E∧BT [5,6] I [8] ～(E∧B) p
[9] F(矛盾式) T [7,8] E
（5）P→(Q→R),Q→(R→S) ? P→(Q→S)
证明：运用cp法，将结论条件式的前件作为前提，证明步骤如下 [1] P p(附加前提) [2] P→(Q→R) p
[3] Q→RT [1,2] I [4] Q→(R→S) p
[5] R→(Q→S) T [4] E [6] Q→ST [3,5] I [7] P→(Q→S) CP [1,6]
21、把下列句子演绎成逻辑形式，并给出证明
（2）某公司发生了一起盗窃案，经仔细侦察，掌握了如下一些事实：
? 被盗现场没有留下任何痕迹
? 失盗时，小花或则小英正在卡拉ok厅
? 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去 ? 如果失盗时小花正在卡拉ok厅唱歌，那么金刚是最大的嫌疑者 ? 如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游 ? 如果失盗时小英正在卡拉ok厅唱歌，那么瘦子是最大的嫌疑者 根据以上事实，请通过演绎推理找出偷窃者
解：根据给定的条件有下述命题： P：现场无任何痕迹
Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者 M：瘦子是偷窃者
则根据案情有如下命题公式：
{P，Q∨R，S→ ～ P，Q→ T，～ S→ ～ R，R→ M}
① P P ②S→～PP
篇二：离散数学最全课后答案(屈婉玲版)
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是素数,这是不对的”是不对的.
(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是素数.
1.15． 设p:2+3=5.
q: 大熊猫产在中
国.r: 复旦大学在广州.
求下列复合命题的真值:
(1)(p?q)?r(2)(r??(
p?q))???p(3)?r??(
?p??q?r)
(4)(p?q??r)??((?p??q)?r)
(1)真值为0.
(2)真值为0.
(3)真值为0.
(4)真值为1.
注意:p, q是真命题,r是假命题.
1.16．
1.17．
1.18．
1.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)为可满足式.
1.20．
1.21．
1.22．
1.23．
1.24．
1.25．
1.26．
1.27．
1.28．
1.29．
1.30．
1.31． 略 略 略 略 略 略 略 略 略 略 略 将下列命题符号化,并给出各命题的真
值:(1)若3+＝4,则地球是静止不动的.
(2)若3+2＝4,则地球是运动不止的. (3)若地球
上没有树木,则人类不能生存.
(4)若地球上没有水,则3是无理数.
(1)p?q,其中, p: 2+2＝4,q:地球静止不动,真值为0.(2)p?q,
其中, p: 2+2＝4,q:地球运动不止,真值为1.
(3)?p??q,其中,p:地球上有树木,q:人类能生存,真值为
1.(4)?p?q,其中,p:地球上有水,q: 3 是无理数,真值为1.
2.1.设公式A=p?q,B=p??q,用真值表验证公式A和B适合德摩根律:
?(A?B)???A??B.
因为?(A?B)和?A??B的真值表相同,所以它们等值.
2.2. 略
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??0.矛盾式.(2)重言式.
(3) (p?q)??(p?r)???(p?q)??(p?r)???p??q??p?r易见,是可满足式,但不是重言式.成真赋值为:000,001, 101, 111
2.4.用等值演算法证明下面等值
式:(1)p??(p?q)??(p??q)
(3)??(p?q)??(p?q)???(p?q)
(4)(p??q)??(?p?q)??(p?q)???(p?q)
(1)
(p?q)??(p??q)??p??(q??q)??p??1??p.(3)??(p
?q)
???((p?q)??(q?p))
???((?p?q)??(?q?p))
??(p??q)??(q??p)
??(p?q)??(p??p)??(?q?q)??(?p??q)
??(p?q) ???(p?q)
(4)(p??q)??(?p?q)
??(p??p)??(p?q)??(?q??p)??(?q?q)
??(p?q) ???(p?q)
2.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(吸收律)??(p??p)??q??p?(q??q) ??p??q??p??q??p?q??p??q
??m10??m00??m11??m10
??m0??m2??m3
???(0, 2,3).
成真赋值为00,10, 11.
(2)主析取范式为0, 无成真赋值,为矛盾式.(3)m0?m1?m2?m3?m4?m5?m6?m7,为重言式.
2.6.求下列公式的主合取范式, 并求成假赋
值:(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)M4,成假赋值为100.
(3)主合取范式为1, 为重言式.
篇三：离散数学习题答案
离散数学习题答案
习题一及答案：（P14-15） 14、将下列命题符号化：
（5）李辛与李末是兄弟
解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语
解：设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，
p?q
(p?q??r)?(1?1??0)?1，
((?p??q)?r)?((?1??1)?0)?(0?0)?1 ?(p?q??r)?((?p??q)?r)?1?1?1
19、用真值表判断下列公式的类型： （2）(p??p)??q
解：列出公式的真值表，如下所示：
20、求下列公式的成真赋值：
（4）?(p?q)?q
解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：
??(p?q)?1?p?0
???
q?0q?0??
所以公式的成真赋值有：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)?m3?m7，此即公式的主析取范式， 所以成真赋值为011，111。
*6、求下列公式的主合取范式，并求成假赋值： （2）(p?q)?(?p?r)
解：原式?(p??p?r)?(?p?q?r)?(?p?q?r)?M4，此即公式的主合取范式， 所以成假赋值为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
?(?p?q?)?r(?p?q?)r?(?p)?r(?p
?q?)r?(?p
q?
)?r?(
?q?)r?(?p q?r?
?pq?r?
?m1?m3?m5?m6?m，此即主析取范式。 7
主析取范式中没出现的极小项为m0，m2，m4，所以主合取范式中含有三个极大项M0，M2，
M4，故原式的主合取范式?M0?M2?M4。
9、用真值表法求下面公式的主析取范式：
（1）(p?q)?(?p?r) 解：公式的真值表如下：
由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式?m1?m2?m3?m4?m5?m6?m7
习题三及答案：（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附加前提引入
② p?q ①附加 ③ (p?q)?(r?s) 前提引入 ④ r?s ②③假言推理 ⑤ s ④化简 ⑥ s?t ⑤附加 ⑦ (s?t)?u前提引入
⑧ u ⑥⑦假言推理 故推理正确。
16、在自然推理系统P中用归谬法证明下面推理： （1）前提：p??q，?r?q，r??s结论：?p
证明：用归谬法
① p结论的否定引入 ② p??q前提引入 ③ ?q ①②假言推理 ④ ?r?q 前提引入
⑤ ?r③④析取三段论 ⑥ r??s 前提引入 ⑦ r ⑥化简 ⑧r??r ⑤⑦合取
由于r??r?0，所以推理正确。
17、在自然推理系统P中构造下面推理的证明：
只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。 解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。
则前提：(p??q)?r，p，q?s，?s结论：r 证明：
① q?s 前提引入 ② ?s 前提引入 ③ ?q ①②拒取式 ④ p 前提引入
⑤ p??q ③④合取引入 ⑥ (p??q)?r 前提引入 ⑦ r⑤⑥假言推理
习题四及答案：（P65-67）
5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快。
解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：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(F(x)??y(G(y)??H(x,y)))
方法二：
设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：
??x(G(x)??y(F(y)?H(x,y)))或??x?y(G(x)?(F(y)?H(x,y)))
9、给定解释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?y,x,y?R。
?
给出以下公式在I下的解释，并指出它们的真值：
（2）?x?y(F(f(x,y),a)?G(x,y))
解：解释是：?x?y(x?
y?0?x?y)，含义是：对于任意的实数x，y，若x-y=0则x<y。
该公式在I解释下的真值为假。
14、证明下面公式既不是永真式也不是矛盾式： （1）?x(F(x)??y(G(y)?H(x,y)))
解：取解释I如下：个体域为全总个体域，
F(x)：x是兔子，G(y)：y是乌龟，H(x,y)：x比y跑得快，则该公式在解释I下真值是1；
取解释I如下：H(x,y)：x比y跑得慢，其它同上，则该公式在解释I下真值是0；
'
'
《离散数学习题答案》出自：百味书屋
链接地址：http://www.850500.com/news/143187.html
转载请保留,谢谢!