离散数学复习题

对离散数学复习很有帮助哦!

1 将下列命题符号化

(1) 2 或 4 是素数.

(2) 2 或 3 是素数.

(3) 4 或 6 是素数.

(4) 小元元只能拿一个苹果或一个梨.

(5) 王小红生于 1975 年或 1976 年.

解

(1) 令p:2是素数, q:4是素数, p q

(2) 令p:2是素数, q:3是素数, p q

(3) 令p:4是素数, q:6是素数, p q

(4) 令p:小元元拿一个苹果, q:小元元拿一个梨

(p q) ( p q)

(5) p:王小红生于 1975 年, q:王小红生于1976 年,

(p q) ( p q) 或 p q

(1)—(3) 为相容或

(4)—(5) 为排斥或, 符号化时(5)可有两种形式，而(4)则不能

2 设 p：天冷，q：小王穿羽绒服，将下列命题符号化

(1) 只要天冷，小王就穿羽绒服. p q

(2) 因为天冷，所以小王穿羽绒服. p q

(3) 若小王不穿羽绒服，则天不冷. p q

(4) 只有天冷，小王才穿羽绒服. q p

(5) 除非天冷，小王才穿羽绒服. q p

(6) 除非小王穿羽绒服，否则天不冷. p q

(7) 如果天不冷，则小王不穿羽绒服. q p

(8) 小王穿羽绒服仅当天冷的时候. q p

3. 将下列命题符号化

(1) 豆沙包是由面粉和红小豆做成的.

(2) 苹果树和梨树都是落叶乔木.

(3) 王小红或李大明是物理组成员.

(4) 王小红或李大明中的一人是物理组成员.

(5) 由于交通阻塞，他迟到了.

(6) 如果交通不阻塞，他就不会迟到.

(7) 他没迟到，所以交通没阻塞.

(8) 除非交通阻塞，否则他不会迟到.

(9) 他迟到当且仅当交通阻塞.

答案: (1) 是简单命题 (2) 是合取式

(3) 是析取式（相容或）(4) 是析取式（排斥或）

设 p: 交通阻塞，q: 他迟到

(5) p q, (6) p q或q p

(7) q p 或p q, (8) q p或 p q

(9) p q 或 p q

可见(5)与(7)，(6)与(8) 相同（等值）

4 某单位要从A,B,C三人中选派若干人出国考察, 需满足下

述条件:

对离散数学复习很有帮助哦!

(1) 若A去, 则C必须去;

(2) 若B去, 则C不能去;

(3) A和B必须去一人且只能去一人.

问有几种可能的选派方案?

解 记 p:派A去, q:派B去, r:派C去

(1) p r, (2) q r, (3) (p q) ( p q)

求下式的成真赋值

A=(p r) (q r) ((p q) ( p q))

求A的主析取范式

A=(p r) (q r) ((p q) ( p q))

( p r) ( q r) ((p q) ( p q))

(( p q) ( p r) (r q) (r r))

((p q) ( p q))

(( p q) (p q)) (( p r) (p q))

((r q) (p q)) (( p q) ( p q))

(( p r) ( p q)) ((r q) ( p q))

(p q r) ( p q r)

成真赋值:101,010

结论: 方案1 派A与C去, 方案2 派B去

5．将A = (p q) r改写成下述各联结词集中的公式:

(1) { , , }

(2) { , }

(3) { , }

(4) { , }

(5) { }

(6) { }

解

(1) (p q) r ( p q) r

(2) (p q) r (p q) r

(3) (p q) r ( p q) r

( ( p q) r)

(4) (p q) r ( (p q) r)

((p q) r)

(5) (p q) r (p q) r

(p q) r

((p q) r)

((p q) r) ((p q) r)

(6) (p q) r ( p q) r

( ( p q) r)

( p q) r

((p p) (q q) (r r)

6. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选

派一些人出国学习. 选派必须满足以下条件：

(1) 若赵去，钱也去.

对离散数学复习很有帮助哦!

(2) 李、周两人中至少有一人去

(3) 钱、孙两人中去且仅去一人.

(4) 孙、李两人同去或同不去.

(5) 若周去，则赵、钱也去.

用等值演算法分析该公司如何选派他们出国？

解

1. 设简单命题并符号化

设 p: 派赵去，q: 派钱去，r: 派孙去，s: 派李去，u: 派周去

2. 写出复合命题

(1) 若赵去，钱也去 p q

(2) 李、周两人中至少有一人去 s u

(3) 钱、孙两人中去且仅去一人 (q r) ( q r)

(4) 孙、李两人同去或同不去 (r s) ( r s)

(5) 若周去，则赵、钱也去 u (p q)

3. 设(1)—(5)构成的合取式为A

A = (p q) (s u) ((q r) ( q r))

((r s) ( r s)) (u (p q))

4. 化成析取式

A ( p q r s u) (p q r s u)

结论：由上述析取式可知，A的成真赋值为00110与11001，

派孙、李去（赵、钱、周不去）

派赵、钱、周去（孙、李不去）

7. 构造公式A=(p q) ( q r) ( p q) r的否证, 从而证明

它是矛盾式.

解 消解序列:

① p q A的简单析取式

② p q A的简单析取式

③ q ①,②消解

④ q r A的简单析取式

⑤ r A的简单析取式

⑥ q ④,⑤消解

⑦ ③,⑥消解

这是A的一个否证, 从而证明A是矛盾式.

8. 在系统P中构造下面推理的证明：

如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和

园游人太多，就不去颐和园. 今天是周六，并且颐和园游

人太多. 所以, 我们去圆明园或动物园玩.

证明：

(1) 设 p：今天是周六，q：到颐和园玩，

r：到圆明园玩，s：颐和园游人太多

t：到动物园玩

(2) 前提：p (q r), s q, p, s

结论：r t

(3) 证明：

对离散数学复习很有帮助哦!

① p (q r) 前提引入

② p 前提引入

③ q r ①②假言推理

④ s q 前提引入

⑤ s 前提引入

⑥ q ④⑤假言推理

⑦ r ③⑥析取三段论

⑧ r t ⑦附加

9 证明下面公式既不是永真式，也不是矛盾式:

(1) x(F(x) G(x))

解释1: D1=N, F(x):x是偶数, G(x): x是素数, 真

解释2: D2=N, F(x):x是偶数, G(x): x是奇数, 假

(2) x y(F(x) G(y) H(x,y))

解释1: D1=Z, F(x):x是正数, G(x): x是负数, H(x,y):x>y 真

解释2: D2=Z, F(x):x是偶数, G(x): x是奇数, H(x,y):x>y 假

10 个体域D={a,b,c}, 消去下述公式中的量词:

(1) x y(F(x) G(y))

解 x y(F(x) G(y))

( y(F(a) G(y))) ( y(F(b) G(y))) ( y(F(c) G(y)))

((F(a) G(a)) (F(a) G(b)) (F(a) G(c)))

((F(b) G(a)) (F(b) G(b)) (F(b) G(c)))

((F(c) G(a)) (F(c) G(b)) (F(c) G(c)))…… 此处隐藏：4054字，全部文档内容请下载后查看。喜欢就下载吧 ……