离散数学习题答案
习题一
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 解： P 0 0 1 1 Q 0 1 0 1 ～P ∧ Q 0 1 0 0 P ∨（～P ∧ Q） （P ∨（～P ∧ Q））→ Q 可满足式 0 1 1 1 1 1 0 1 （2）~（4）表略：（2）可满足式、（3）永真式 、（4）可满足式 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 Q→P R∧(Q→P) P→(R∧(Q→P)) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 所以： 主合取范式为 = (～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 Q∧R ～Q∧～R P→(Q∧R) ～P→(～Q∧～R) 1 0 0 0 1 1 1 1 (P→(Q∧R)) ∧(～P→(～Q∧～R)) 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 所以： 主合取范式为 = (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）