《离散数学》习题集

(b) 或非运算符（又叫皮尔斯（Peirce）箭头）用下述真值表定义，它与?（P?Q)逻辑等价。对下述每一式，找出仅用?表示的等价式。 （i）?P； （ii）P?Q； （iii）P?Q。

0 0 0 1 1 0 1 1 P Q P?Q 1 1 1 0 P Q 0 0 0 1 1 0 1 1 P?Q 1 0 0 0 17. (a) 用真值表证明?和?互相可分配；

(b) ?、?和?对自己可分配吗？ 18. 求出下列各式的代入实例：

(a) (((P?Q)?P)?P)：用P?Q代P，用((P?Q)?R)代Q； (b) ((P?Q)?(Q?P))；用Q代P，用P??P代Q。

1.3 范式

19. 对任一指派，i?j时，为什么mi和mj不能同时为真？为什么Mi和Mj不能同时为假？ 20. 求下列各式的主合取范式：

(a) P?Q?R??P?Q?R??P??Q??R； (b) P?Q??P?Q?P??Q； (c) P?Q??P?Q?R。

21. 求下列各式的主析取范式和主合取范式： (a) ； （?P??Q）?（P??Q）(b) P?(?P?(Q?(?Q?R)))； (c) （P?Q?R)?(?P?(?Q??R))； (d) P??Q?S??P?Q?R。

1.4 联结词的扩充与归约

第5页 共53页

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页