离散数学.ppt

离散数学
习题课
第一章数理逻辑
1、将下列命题符号化
豆沙包是由面粉和红小豆做成的.
苹果树和梨树都是落叶乔木.
王小红或李大明是物理组成员.
王小红或李大明中的一人是物理组成员.
由于交通阻塞,他迟到了.
如果交通不阻塞,他就不会迟到.
他没迟到,所以交通没阻塞.
除非交通阻塞,否则他不会迟到.
他迟到当且仅当交通阻塞

(1)(pq)(qp) (2)(pq)q (3)(pq)p
3、构造下面推理的证明:
如果今天是周六,我们就到颐和园或圆明园玩. 如果颐和园游人太多,就不去颐和园. 今天是周六,并且颐和园游人太多. 所以我们去圆明园或动物园玩.
答案
1、分清复合命题与简单命题
分清相容或与排斥或
分清必要与充分条件及必要充分条件
答案:(1)是简单命题(2)是合取式(3)是析取式(相容或) (4)是析取式(排斥或)
(5)—(8)的符号化形式,
设p: 交通阻塞,q: 他迟到
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)相同(等值)
2、(1)重言式,(2)矛盾式,(3)可满足式
解用等值演算法求解
(1) (pq)(qp)
(pq)(qp) (消去) ①
(pq)(qp) (内移) ②
(pq)(pq)(pq)(pq) ③
 m2  m1  m3  m0 ④
 m0  m1  m2  m3 ⑤
 1 ⑥
问由②如何得③?
⑤为主析取范式,⑥为主合取范式
结论:(1)为重言式
(2) (pq)q
(pq)q ①
 pqq ②
 0 ③
 M0  M1  M2  M3 ④
问:由②如何得③?
③为主析取范式,④为主合取范式。
结论:(2)为矛盾式.
(3) (pq)p
 m0  m1 ①
 M2  M3 ②
请自己等值演算得①与②
结论:(3)
:今天是周六,q:到颐和园玩, r:到圆明园玩,s:颐和园游人太多, t:到动物园玩
(2)前提:p(qr), sq, p, s
结论:rt
(3)证明:
① p(qr) 前提引入
② p 前提引入
③ qr ①②假言推理