《离散数学》习题集(2)

22. 仅用?表达P?Q；再用?表达它。 23. 仅用?表达P?Q；仅用?表达P?Q。

24. 试证明等价式：?(P?Q)??P??Q和?(P?Q)??P??Q。 25. 写出一个仅含?且等价于P?(Q?R)的公式来。 26. 证明{?},{?},{?,?}都不是全功能联结词集合。 27. 证明{?,?}，{?,T}是全功能联结词集合。 28. 证明联结词?可交换，可结合，且?在?上可分配。 29. 证明联结词?可交换，可结合，且?在?上可分配。

1.5 推理规则和证明方法

30. 用真值表证明下列推理规则的重言式形式都是重言式： (a) 拒取式； (b) 析取三段论； (c)构造性二难定理； (d) 破坏性二难推理。 31. H1,H2,是前提，C是结论，用真值表判断下列结论是否有效：

(a) H1:P?Q，H2:?Q，C:P；

(b) H1:P?Q，H2:P?R，H3:Q?R，C:R； (c) H1:P?(Q?R)，H2:P?Q，C:R； (d) H1:?P，H2:P?Q，C:P?Q。 32. 给出一个指派，证明以下结论是非有效的：

(a) 前提是A?B,B?(C?D),C?(A?E),A?E，结论是A?E。 (b) 前提是A?(B?C),B?(?A??C),C?(A??B),B，结论是A?C。 33. 对下列每一个前提集合，列出能得到的恰当结论和应用于这一情况的推理规则。 (a) 如果我跑，我喘气。我没有喘气。

(b) 天气是晴朗或阴暗，天气晴朗使我愉快而天气阴暗使我烦恼。

(c) 如果考试及格了，那么我很高兴。如果我很高兴，那么我的饭量增加。我的饭量减少。

第6页 共53页

34. 对下述每一论证构造一个证明，给出所有必须增加的断言，指出用于每一步的推理规则。 (a) 从语句“今天下雨或明天后天都下雨”和“明天不下雨或后天不下雨而今天下雨”

可推出“今天下雨”。

(b) 如果李敏来通信工程学院，若王军不生病，则王军一定去看望李敏。如果李敏出差

到南京，那么李敏一定来通信工程学院。王军没有生病。所以，如果李敏出差到南京，王军一定去看望李敏。

35. 确定下列论证哪些是有效的论证，为有效论证构造证明，对非有效论证，表明为什么结

论不能从前提得出。

A?BA?BA?B

A?CA?CA?C(a) ； (b) ； (c) 。

?C?B?C?B?C?B

36. 仅用E4,E5,E8,E18,E21,I2证明?P?(P?Q)?Q。 37. 证明下列论证的有效性：

(a) (A?B)?(A?C)，?(B?C)，D?A推得D； (b) P?Q?R，?R?S，?S推得?P??Q； (c) (P?Q)?R，R?S，Q?T推得R。 38. 证明下列结论“

(a) ?P?Q，?Q?R，R?S ?P?S； (b) P?Q?R?P?Q?R； (c) P?Q?P?P?Q；

(d) P?Q?R，Q?(R?S)， ?P?(Q?S)。 39. 试说明“从假的前提出发，能证明任何命题”。 40. 证明下列各式的有效性：

(a) R??Q，R?S，S??Q，P?Q推得?P； (b) S??Q，S?R，?R，?R?Q推得?P；

(c) ?(P?Q)?(?R?S)，((Q?P)??R)，R推得P?Q。

1.6 谓词和量词

第7页 共53页

41. 下列表达式哪些是命题？ (a) ?x(P(x)?Q(x))?R； (b) ?x(P(x)?Q(x))?S(x)。

42. 设谓词S(x,y,z)表示“x?y?z”，谓词M(x,y,z)表示“xy?z”，论述域是整数，用以

上谓词表示下述断言：

(a) 对每一x和y，有一z，使x?y?z； (b) 对每一x和y，有一z，使x?z?y； (c) 从任何整数减去0，其结果是原整数； (d) 对所有x，对所有y，xy?y。

43. 论述域是整数，对下列每一个断言找出谓词P使蕴含式是假。 (a) ?x?!yP(x,y)??!y?xP(x,y)； (b) ?!y?xP(x,y)??x?!yP(x,y)。

44. 指定一个论述域使下列命题是真。要使指定得论述域是尽可能大的整数的一个子集。 (a) ?x(x?0)； (b) ?x(x＝5)； (c) ?y?x(x?y＝3)； (d) ?y?x(x?y?0)。

(,)45. 设论述域是自然数，P(x,y,z)表示“x＋y?z”，Lxy表示“x?y”，用逻辑符表示下

列断言：

(a) 对每一x和y，有一z，使x＋y?z； (b) (b) 没有x小于0；(c) 4加3得7。 46. 将苏格拉底论证符号化。

47. 设P(x,y,z)表示xy?z，E(x,y)表示x＝y，G(x,y)表示x?y，论述域是整数，将下列

断言译成逻辑符。（提示：要注意数学上习惯写法和逻辑符表示的差异，例如加法交换律在数学中写成：x＋y?y?x，翻译成逻辑符时，要按照实际意义翻译成：

?x?y(x?y?y?x)），即要自动加上全称量词，使整个式子成为命题。）

(a) 如果xy?0，那么x＝0，或y＝0； (b) 如果xy?0，那么x?0，并且y?0； (c) x?z是x?y并且y?z的必要条件；

第8页 共53页

(d) x＝y和x?y不能同时出现；

(e) 存在一x，对每一y和z，使xy?xz。

48. 将下列断言译为逻辑符号，选用的谓词应使逻辑符号中至少含有一个量词： (a) 有一个且仅有一个偶数是质数； (b) 没有一个奇数是偶数；

(c) 某些卡车慢于所有火车，但是至少有一辆火车，快于每一卡车； (d) 所有步行的，骑马的或乘车的人，凡是口渴的都喝泉水。

49. 设E(x)表示“x是偶数”，O(x)表示“x是奇数”，P(x)表示“x是质数”，N(x)表示“x是负数”，I(x)表示“x是整数”和一些中缀表示的谓词诸如y?x2?1等，将下列各句翻译成逻辑符。

(a) 一个整数是奇数，如果它的平方是奇数； (b) 有两个奇数它们的和是偶数； (c) 不存在一个整数x使x2?1是负数； (d) 任何两个质数之和是质数；

(e) 对任何整数，如果它的平方是负的，那么1＝1。 50. 如果论述域是{a,b,c}，试消去下列公式中的量词： (a) ?xR(x)??xS(x)； (b) ?x(P(x)?Q(x))。 51. 试说明下列公式是合式公式： (a) (?x(F(x)?Q(x))； (b) (F(x,y)?(?xG(x,y)))。

1.7 谓词演算的永真公式

52. 证明永真公式Q14,Q15,Q16,Q17,Q19。

53. 下列断言如果是真的证明它们，如果是假的，找出P和Q的解释以证明公式是假。 (a) ?x(P(x)?Q(x))?(?xP(x)??xQ(x))； (b) (?xP(x)??xQ(x))??x(P(x)?Q(x))； (c) (?x(P(x)??xQ(x))??x(P(x)?Q(x))； (d) ?x(P(x)?Q(x))?(?xP(x)??xQ(x))。

第9页 共53页

54. 设论述域是{a0,a1,a2,,an}，试证明下列关系式：

(a) ?xA(x)?P??x(A(x)?P)； (b) ?x(A(x)?B(x))??xA(x)??xB(x)。

55. 对一个仅含元素0和1的论述域，试证明：?x(P(x)?Q(x))?(?xP(x)??xQ(x))，并

证明蕴含式之逆不是有效的。

1.8 谓词演算的推理规则

56. 对下列每一前提集合，列出能得到的恰当结论和应用于这一情况的推理规则。 (a) 所有三角形函数都是周期函数，而所有周期函数都是连续函数； (b) 所有偶数都被2除尽。整数4是偶数，但3不是；

(c) 对汽车工业的好事就是对国家的好事，对国家的好事就是对你的好事。你去买一辆

高价卡车是对汽车工业的好事。

57. 下列推导步骤为什么是错误的？ (a) (i) ?xP(x)?Q(x) P (ii) P(x)?Q(x) T，1，US (b) (i) ?x（P(x)?Q(x)) P

(ii) ?P(a)?Q(b) T，1，US (c) (i) ?xP(x)??x(Q(x)?R(x)) P

(ii) P(a)??x(Q(x)?R(x) T，1，US ）58. 证明下列各断言：

(a) ?(?xP(x)?Q(a))推得?xP(x)??Q(a))； (b) ?x(P(x)?Q(x)),?x?P(x)，推得?xQ(x)。 59. 考虑蕴含式?x(P(x)?Q(x))??xP(x)??xQ(x) (a) 证明它不是有效的。

(b) 下面是一个论证，企图证明上式有效，试找出不正确的地方。

?x(P(x)?Q(x))???x?(P(x)?Q(x))???x(?P(x)??Q(x))??(?x?P(x)??x?Q(x))???x?P(x)???x?Q(x)??xP(x)??xQ(x)

60. 判断下列结论C能否有效的从给定的前提得出： (a) ?x(P(x)?Q(x)),?yP(y) C:?zQ(z)；

第10页 共53页

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