离散数学及其应用数理逻辑部分课后习题答案
作业答案：数理逻辑部分
P14：习题一
1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？
（3 答：简单命题，真命题。 （9）吸烟请到吸烟室去！ 答：不是命题。
（12）8是偶数的充分必要条件是8能被3整除。 答：复合命题，假命题。 14、讲下列命题符号化。 （6）王强与刘威都学过法语。 答：:p 王强学过法语；:q 刘威学过法语。
符号化为：
p q ∧
（10）除非天下大雨，他就乘班车上班。 答：:p 天下大雨；:q 他乘班车上班。
符号化为：
p q →
（13）“2或4是素数，这是不对的”是不对的。 答：:p 2是素数；:q 4是素数。
符号化为：(())p q ??∨
15、设:p 2+3=5.
:q 大熊猫产在中国。
:r 太阳从西方升起。
求下列复合命题的真值。 （2）(())r p q p →∧??
（4）()(())p q r p q r ∧∧???∨?→ 解答： p 真值为1；q 真值为1；r 真值为0.
（2）p q ∧真值为1；()r p q →∧真值为1；p ?真值为0；
所以(())r p q p →∧??真值为0.
（4）
p q r ∧∧?真值为1，p q ?∨?真值为0，()p q r ?∨?→真值为1；
所以()(())p q r p q r ∧∧???∨?→真值为1. 19、用真值表判断下列公式的类型。 （4）()()p q q p →→?→?
所以为重言式。 )s
所以为可满足式。
P36:习题二
3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。
（1）()p q q ?∧→ 解答：
所以为永假式。
（2）(())()p p q p r →∨∨→ 解答：
所以因为永真式。 （3）()()p q p r ∨→∧
解答：
为可满足式。 真值表为
4、用等值演算法证明下面的等值式。
（2）(()())(())p q p r p q r →∧→?→∧ 解答：
（4）()()()()p q p q p q p q ∧?∨?∧?∨∧?∨ 解答：
5、求下列公式的主析取范式，并求它们的成真赋值。 （1）()()p q q p ?→→?∨
解答：
所以成真赋值为00，10，11 （3）(())()p q r p q r ∨∧→∨∨ 解答：
所以为永真式，成真赋值为000，001，010，011，100，101，110，111 6、求下列公式的主合取范式，并求它们的成假赋值。 （1）()q p p ?→?∧? 解答:
为永假式，成假赋值为00，01，10，11 （3）(())p p q r →∨∨ 解答：
永真式，无成假赋值
7、求下列公式的主析取范式，再用主析取范式求主合取范式。 （1）()p q r ∧∨
解答：
13567024
()()
(())(()())
()()()()()()()()()()()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 m m m m m M M M ∧∨?∧∧?∨∨?∨∧?∨∧?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧?∨∨∨∨?∧∧已经是析取范式
8、求下列公式的主合取范式，再用主合取范式求主析取范式。 （2）()p q r ?→ 解答：
13、已知公式A 含3个命题变项,,p q r ，并且它的成假赋值为010，011，110，111，求A 的主
析取范式和主合取范式。
解答：成真赋值为000,001,100,101 所以主析取范式为0145m m m m ∨∨∨ 而主合取范式为2367M M M M ∧∧∧ 15、用主析取范式判断下列公式是否等值。 （2）()p q ?∧和()p q ?∨ 解答：
所以两式并不等值。
18、将下列公式化成与之等值且仅含有{,}?∧中联结词的公式 （3）(())p q r p →∧∨
解答：
29、在某班班委成员的选举中，已知王小红、李强、丁金生3位同学被选进了班委会。该班的的甲、乙、丙3位同学预言： 甲说：王小红为班长，李强为生活委员； 乙说：丁金生为班长，王小红为生活委员。
丙说：李强为班长，王小红为学习委员。
班委会分工名单公布后发现，甲乙丙三人都恰好猜对了一半。问王小红、李强、丁金生各任何职？（用等值演算求解） 解答：命题符号化：
:p 王小红为班长；:q 李强为生活委员；:r 丁金生为班长；:s 王小红为生活委员；
:u 李强为班长；:v 王小红为学习委员。
设1:A p q ∧?；2:A p q ?∧；1:B r s ∧?；2:B r s ?∧；1:C u v ∧?；2:C u v ?∧； 由题意可知：
0;0;0;0;0;0;0;0
p r p s p u p v q s q u r u s v ∧?∧?∧?∧?∧?∧?∧?∧?所以1112111222210;0;0;0;0;0;A B A B A C A C A B A C ∧?∧?∧?∧?∧?∧? 所以
所以选举结果为：李强为生活委员；丁金生为班长；王小红为学习委员。
30、某公司要从赵、钱、孙、李、周5名新毕业的大学生中选派一些人出国学习。选派必须满足条件：
（1）若赵去，钱也去；
（2）李、周两人中必有一人去； （3）钱、孙两人中去且仅去一人； （4）孙、李两人同去或同不去； （5）若周去，则赵、钱也同去。
用等值演算法分析该公司该如何选派他们出国。 解答：命题符号化：
:p 赵去；:q 钱去；:r 孙去；:s 李去；:t 周去。
所满足的条件即为 （1）若赵去，钱也去：
p q →；
（2）李、周两人中必有一人去：s t ∨；
（3）钱、孙两人中去且仅去一人：()()q r q r ∧?∨?∧； （4）孙、李两人同去或同不去：()()r s r s ∧∨?∧?； （5）若周去，则赵、钱也同去：()t p q →∧。 将所有条件进行合取，然后求其主析取范式 （过程省略）
所以最终方案有两套：
（1）赵钱周不去，孙李去；（2）赵钱周去，孙李不去。
P50:习题三
9、用3种方法（真值表、等值演算、主析取范式）证明下面推理是正确的。
若a 是奇数，则a 不能被2整除。若a 是偶数，则a 能被2整除。因此，如果a 是偶数，则a 不是奇数。
解答：命题符号化：:p a 为奇数；:q a 为偶数；:r a 能被2整除
推理的形式结构：
前提：
p r →?；q r →；q
结论：q ?
推理的形式结构的另外一种描述： 证明：（1）真值表法：
所以()()p r q r q p →?∧→∧→?为永真式；推理()()p r q r q p →?∧→∧??是正确的。
（2）等值演算： （3）主析取范式
12、填充下面推理证明中没有写出的推理规则。 前提：()p q r →→，()q r s →→ 结论：()p q s ∨→ 证明： ①p q ∨ 附加前提引入 ②
p
①化简 ③q
①化简 ④()p q r →→ 前提引入 ⑤q r → ②④假言推理 ⑥r
③⑤假言推理 ⑦()q r s →→ 前提引入
⑧r s → ③⑦假言推理 ⑨s
⑥⑧假言推理
14、在自然推理系统P 中构造下面推理的证明： （2）前提：,(),p q q r r →?∧
结论：p ? 证明： ①()q r ?∧ 前提引入 ②q r ?∨? ①置换 ③r 前提引入 ④q ?
②③析取三段论 ⑤
p q →
前提引入
⑥p ? ④⑤拒取式
（4）前提：,,,q p q s s t t r →??∧
结论：p q ∧
证明： ①t r ∧ 前提引入 ②t ①化简 ③r
①化简 ④s t ?
前提引入
⑤()()s t t s →∧→ ④置换
⑥t s →
⑤化简 ⑦q s ?
前提引入
⑧()()q s s q →∧→ ⑦置换 ⑨s q → ⑧化简 ⑩t
q →
⑥⑨假言三段论 ○11q
②⑩假言推理 ○12q p → 前提引入
○
13p
○11○12假言推理 ⑨
p q ∧
○
12○13合取 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 p r q s ∨→→
结论：r s ∨ 证明：
①()r s ?∨
结论否定引入
②r s ?∧? ①置换 ③s ? ②化简 ④r ?
②化简 ⑤
p r →
前提引入
⑥q s → 前提引入 ⑦p ? ④⑤拒取式 ⑧q ?
③⑥拒取式 ⑨p q ?∧? ⑦⑧合取 ⑩()p q ?∨
⑨置换
○
11p q ∨
前提引入
⑩○
11矛盾。 17：在自然推理系统P 中构造下面推理的证明：
只要A 曾到过受害者房间并且11点以前没有离开，A 就是谋杀嫌疑犯。A 曾到过受害者房间。如果A 在11点以前离开，看门人会看见过他。看门人没有看见他。所以，A 是谋杀嫌疑犯。 解答：
（1） 命题符号化：
:p A 曾到过受害者房间；:q A 在11点以前离开；
:r A 就是谋杀嫌疑犯；:s 看门人会看见过A ；
（2） 推理的形式结构：
前提：();;;p q r p q s s ∧?→→? 结论：r （3） 证明
①s ?
前提引入
②q s → 前提引入 ③q ? ①②拒取式 ④p
前提引入 ⑤
p q ∧?
③④合取 ⑥()p q r ∧?→ 前提引入 ⑦r
⑤⑥假言推理。
P63:习题四
5、在一阶逻辑中讲下列命题符号化。 （3）不存在比所有火车都快的汽车。 （4）凡是汽车就比火车慢是不对的。
解答：():()(,)F x x G y y H x y y x 为火车；：为汽车；：比快。
（3）((()()(,)))y x G y F x H x y ???∧→
（4）(()()(,))y x G y F x H y x ???∧→
6、将下列命题符号化，个体域为实数集合R ，并指出各命题的真值。 （1）对所有的x ，都存在y 使得0x y ?=。 （3）对所有的x ，都存在
y 使得1y x =+。
解答：(,):0;(,):1F x y x y G x y y x ?==+ （1）(,)x yF x y ??，真值为1； （3）(,)x yG x y ??，真值为1； 9、给定解释I 如下。 （a ）个体域为实数集合R 。 （b ）特定元素0a
=。
（c ）函数(,),,f x y x y x y R =-∈
（d ）谓词(,):,(,):,,F x y x y G x y x y x y R =<∈。 给出下列公式在I 下的解释，并指出它们的真值。 （1）((,)(,))x y G x y F x y ??→? （3）((,)((,),))x y G x y F f x y a ??→? 解答：（1）对任意的x 和y ，如果x y <,那么x y ≠。真值为1；
（3）对任意的x 和y ，如果x y <
,那么0x y -≠。真值为1；
11、判断下列各式的类型。
（2）(()())(()())x F x F x y G y G y ?→→?∧? （4）(,)(,)x yF x y y xF x y ??→??
解答：（2）(()())x F x F x ?→真值为1；(()())y G y G y ?∧?真值为0；
所以(()())(()())x F x F x y G y G y ?→→?∧?真值为0，所以为永假式。 （4）(,)x yF x y ??与(,)y xF x y ??真值相同，所以为永真式。 13、给出下列各公式的一个成真解释和一个成假解释。 （1）(()())x F x G x ?∨ （2）(()()())x F x G x H x ?∧∧ （3）(()(()(,))x F x y G y H x y ?∧?∧ 解答：
（1）成真解释：():():F x x G x x 为偶数；为奇数
成假解释：():():F x x G x x 为偶数；为素数
（2）成真解释：():2():3():5F x x G x x H x x 能被整除；能被整除；能被整除。
成假解释：():():():F x x G x x H x x 为偶数；为奇数，为素数
（3）成真解释：():():():F x x G x x H x y x y >为正数；负数；，。
成假解释：():():():F x x G x x H x y x y <为正数；负数；，。