离散数学习题集

离散数学课外习题集

编者：金鹏

时间：2008-5-6

目录：

第一章

一、选择题

1. 由n个命题变元组成不等值的命题公式的个数为（）

A.2n B.2n C.n2 D.2n2

2. 设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（）

A.PQ B.QP C.P Q D.QP

3. 下列各组公式中，哪组是互为对偶的？（）

A.P,P B.P, P C.A,(A*)* D.A,A

（其中P为单独的命题变元，A为含有联结词的命题变元）

4. 设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑步”符号化为（）

A. pQ B. PQ C. (PQ) D.PQ

5. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）

A. 2是偶数或-3不是负数 C. 2是奇数或-3不是负数

C．2不是偶数且-3不是负数 D. 2是奇数且-3不是负数

6. 设P：张三可以作这件事，Q：李四可以作这件事。命题“张三或李四可以做这件事”符号化为（）

A.PQ B.PQ C.PQ D. (PQ)

7. 下列语句中哪个是真命题？（）

A.我正在说谎。 B.严禁吸烟。

C.如果1+2=3，那么雪是黑的。 D.如果1+2=5，那么雪是黑的。

8. 下面哪个联结词运算不可交换？（）

A. B. C. D.

9. 命题公式(P (PQ)) Q是（）。

A.矛盾式 B.蕴含式 C.重言式 D.等值式

10. 下面哪个命题公式是重言式？（）

A.(PQ)(Q P) B.(PQ)P

C.(PQ)(PQ) D.(PQ)

11. 下列哪一组命题公式是等值的？（）

A. PQ,PQ B.A(BA),A(AB)

C.Q(PQ),Q (PQ) D.A (AB),B

12. PQ的逆反式是（）

A.QP B. P  Q C. QP D. QP

13. PQ的逆反式是（）

A.QP B. P  Q C. QP D.P  Q

14. 下列命题联结词集合中，哪一个是最小联结词组？（）

A.{,} B.{,,} C.{} D.{,}

15. 下列联结词集合中，哪一个不是最小联结词组？（）

A.{,} B.{,} C.{,,} D.{}

16. 已知A是B的充分条件，B是C的必要条件，D是B的必要条件，则A是D的（）

A.充分条件 B.必要条件 C.充要条件 D.A、B、C都不对

17. P  Q的反换式是（）

A.QP B.PQ C.QP D.PQ

18. 下面哪一个命题公式是重言式？（）

A.P(QR) B.(PR)(PQ) C.(PQ)  (QR) D.(P(QR)) ((PQ) (PR))

19. 下列哪个命题公式不是重言式？（）

A.Q(PQ) B.(PQ)P

C.(PQ) (PQ) D.(PQ)(PQ)

20. 重言式的否定式是（）

A.重言式 B.矛盾式 C.可满足式 D.蕴含式

21. 下面哪一个命题是假命题？（）

A.如果2是偶数，那么一个公式的析取范式惟一

B.如果2是偶数，那么一个公式的析取范式不惟一

C.如果2是奇数，那么一个公式的析取范式惟一

D.如果2是奇数，那么一个公式的析取范式不惟一

22. 下面哪一组命题公式不是等值的？（）

A.(AB),AB B.(AB),(AB)(AB)

C.A(BC),A(BC) D. A(BC),(AB)C

23. 命题公式PQR的对偶式为（）

A.P(QR) B. P (QR)

C.P (QR) D.P (QR)

24. 命题公式P(QR)是（）

A.重言式 B.可满足式 C.矛盾式 D.等值式

25. PQ（）

A.P (PQ) B.(PQ) (QP)

C.(PQ)(QP) D.(PQ)(QP)

26. 命题公式(PQ)R的主析取范式中含极小项的个数为（）

A.8 B.3 C.5 D.0

27. 命题公式(PQ)R的主析取范式中含极大项的个数为（）

A.0 B.3 C.5 D.8

28. 命题公式(PQ)R的成真赋值为（）

A.000,001,110 B.001,011,101,110,111

C.全体赋值 D.无

29. 如果AB成立，则以下各种蕴含关系哪一个成立？（）

A.BA B.AB C.BA D.AB

二、填空题

1. 下列句子中，是命题的有

(1).我是教师。

(2).禁止吸烟！

(3).蚊子是鸟类动物。

(4).上课去！

(5).月亮比地球大。

2. 设P：我生病，Q：我去学校

(1).命题“我虽然生病但我仍去学校”符号化为 。

(2).命题“只有在生病的时候，我才不去学校”符号化为 。

(3).命题“如果我生病，那么我不去学校”符号化为 。

3. 设P：我有钱，Q：我去看电影。

(1).命题“如果我有钱，那么我就去看电影”符号化为 。

(2).命题“虽然我有钱，但我不去看电影”符号化为 。

(3).命题“当且仅当我有钱时，我才去看电影”符号化为 。

4. 对于下列各式，是永真式的有 。

(1).(P(PQ))Q

(2).P(PQ)

(3).Q(PQ)

(4).(P(PQ))Q (5).(PQ) Q

5. (P(PQ)) R 。

6. P(PQ) 。

7. 对于下列各式

(1).(PQ)(PQ)可化简为 。

(2).Q(P(PQ)) 可化简为 。

(3).(PQ)(QP)P可化简为 。

8. 命题公式P(QR)的成真赋值为 ，成假赋值为 。

9. 若 且 则称X是公式A的子公式。

10. 写出表中各列所定义的命题联结词。

P Q P ① Q P ②

Q

1 1 1

0

1 0 0

1

0 1 0 1

0 0 0

1

11. 由n个命题变元可组成 个不等值的命题公式。

12. 用两种形式写出PQ的对偶式 ①

， ②

。

13. 两个重言式的析取是 ① ，一个重言式与一个矛盾式的析取是

② 。

14. A、B为两个命题公式，AB当且仅当 ① ，AB当且仅当

② 。

15. 设P、Q为两个命题公式，德●摩根律可表示为 ① ，吸收率可表示为

② 。

16. 设命题公式A中仅含有联结词，，，若 得到公式A*，则A*称为A的对偶式。

17. 公式(PQ)

R的只含联结词，，的等值式为 ① ，它的对偶式为

②

。

18. 命题公式A(PQR)0，则其对偶式A*

。

19. 在命题演算中，一个蕴含式与它的 ①

式是等值的，它的 ② 式与它的

③ 是不等值的。

20. 公式PQ的反换式为 ①

，逆反式为 ②

。

21. 任意两个不同极小项的合取为 ① 式，全体极小项的析取式必为

② 。

22.

命题公式(PQ)的主析取范式为 ① ，主合取范式的编码表示为

②

。

23. 已知公式A(P,Q,R)的主合取范式为M0M3M5，它的主析取范式为（写成编码形式）

。

24. 命题公式(PQ)的主析取范式为 ①

，其编码表示为 ② ，主合取范式的编码表示为 ③

。

25. 对于前提：SQ，SR，R, PQ，其有效结论为

。

26. 对于前提：(PQ) R，RS, S，其有效结论为 。

三、判断题

1. “王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。（）

2. 凡陈述句都是命题。（）

3. 语句3x+5y=0是一个命题。（）

4. 命题“两个角相等当且仅当它们是对顶角“的值为1。（）

5. 语句“x+y=4”是个命题。（）

6. 命题“十减四等于五”是一个原子命题。（）

7. 命题“如果1+2=3，那么雪是黑的”是真命题。（）

8. (P(QR))是一个命题演算的命题公式，其中P、Q、R是命题变元。（）

9. (P(QRQ))是一个命题公式，其中P、Q、R是命题变元。（）

10. 若A：张明和李红都是三好学生，则A：张明和李红都不是三好学生。（）