离散数学习题答案-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 解： 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）

共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求： （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→R p

[3] R T [1,2] I [4] (R→Q) ∧(R→S) p

[5] Q∧S T [3,4] I [6] (Q→E) ∧(S→B) p

[7] E∧B T [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→R T [1,2] I [4] Q→(R→S) p

[5] R→(Q→S) T [4] E [6] Q→S T [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→～P P

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学习题答案-2015在线全文阅读。