离散数学知识点模板.doc

第一章
1. 将下列命题符号化： 解：令p：天下雨，q：我骑自行车上班，则
（1）只要不下雨，我就骑自行车上班 ¬p是q充足条件，所以符号化为：¬p→q
（2）只有不下雨，我才骑自行车上班 ¬p是q 必需条件，所以符号化为：q→¬ p
（3）除非下雨，不然我就骑自行车上班 ¬p仍然是q充足条件，所以符号化为：¬p→q
（4）假如下雨，我就不骑自行车上班 p是¬q充足条件，所以符号化为：p→¬q
: 判定结果惟一陈说句（注意: 感叹句、祈使句、疑问句全部不是命题
陈说句中悖论和判定结果不惟一确定也不是命题）
3. p®q为假当且仅当 p 为真 q 为假
4. p®q （q 为 p 必需条件）
“假如 p，则 q ” 不一样表述法很多：
若 p，就 q
只要 p，就 q
p 仅当 q
只有 q 才 p
除非 q, 才 p 或 除非 q, 不然非 p
因为….所以
5. p«q为真当且仅当p和q同真或同假
6. p 0层
Øp 1层
Øp®q 2层
Ø(p®q)«r 3层
((ØpÙq) ®r)«(ØrÚs) 4层
ØØAÛA
等幂律： AÚAÛA, AÙAÛA
交换律: AÚBÛBÚA, AÙBÛBÙA
结合律: (AÚB)ÚCÛAÚ(BÚC) (AÙB)ÙCÛAÙ(BÙC)
分配律: AÚ(BÙC)Û(AÚB)Ù(AÚC) AÙ(BÚC)Û (AÙB)Ú(AÙC)
德·摩根律: Ø(AÚB)ØÛAØÙB Ø(AÙB)ØÛAØÚB
吸收律: AÚ(AÙB)ÛA, AÙ(AÚB)ÛA
零律: AÚ1Û1, AÙ0Û0
同一律: AÚ0ÛA, AÙ1ÛA
排中律: AØÚAÛ1
矛盾律: AØÙAÛ0
蕴涵等值式: A®BØÛAÚB
等价等值式: A«BÛ(A®B)Ù(B®A)
假言易位: A®BØÛBØ®A
等价否定等值式: A«BØÛAØ«B
归谬论: (A®B)Ù(AØ®B) ØÛA
设A，B为两个命题公式，若A Û B，则A* Û B*.
：
(1) 消去A中®, «（若存在） (2) 否定联结词Ø内移或消去
(3) 使用分配律 Ù对Ú分配（析取范式） Ú对Ù分配（合取范式）
（公式范式存在，但不惟一）