离散数学知识点整理.docx

离散数学
一、逻辑和证明
命题逻辑
命题：是一个可以判断真假的陈述句。
联接词：∧、∨、→、 ? 、?。记住“ p 仅当 q”意思是“如果 p，则 q”，即p→。记住“ q 除非 p”意思是“?p→q”。会考察条件语句翻译成汉语。
构造真值表
p
q
p∧q
p∨ q
p→ q
p? q
p⊙q
?p
T
T
T
T
T
T
F
F
T
F
F
T
F
F
T
F
F
T
F
T
T
F
T
T
F
F
F
F
T
T
F
T
语句翻译
系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若
pq 无论
取何值都无法让复合语句为真，则该系统规范说明是不一致的。
命题等价式
逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。
证逻辑等价是通过 p 推导出 q，证永真式是通过 p 推导出 T。
逻辑等价式
p∧T ? p
恒等律
p∨F ? p
p∧F ? F
支配律
p∨T ? T
p∧p ? p
幂等律
?(?P) ?
p
双否律
p∧q ?
q ∧ p
交换律
(p ∧q) ∧ r
?
p ∧(q ∧r)
结合律
p∨(q ∧r)
?
(p ∨q) ∧ (p ∨r)
分配律
p∧(q ∨r)
?
(p ∧q) ∨ (p ∧r)
?(p ∧ q)
?
?p∨?q
德摩根律
?(p ∨ q) ? ?p∧?q
p∨(p ∧q)
?
p
吸收律
P∧(p ∨q)
?
p
p∧?p ? F
否定律
p∨?p ? T
条件命题等价式
p→q ? ?p∨q
p→q ? ?q→?p
p∨q ? ?p→q
p∧q ? ?(p →?q)
?(p → q) ? p∧?q
(p →q) ∧ (p →r) ? p →(q ∧ r)
(p →r) ∧ (q →r)
?
( p∨ q) →r
(p →q) ∨ (p →r)
?
p →(q ∨ r)
(p →r) ∨ (q →r)
?
( p∧ q) →r
双条件命题等价式
p? q ? (p → q) ∧(q →p)
p? q ? ?p? ?q
p? q ? (p ∧ q) ∨(?p ∧?q)
?(p ? q) ? p ? ?q
量词
谓词 +量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如 ? x>0P(x) 。
当论域中的元素可以一一列举，那么 ? xP(x) 就等价于 P(x1) ∧P(x2)... ∧ P(xn) 。同理， ? xP(x) 就等价于 P(x1) ∨ P(x2)... ∨P(xn) 。
两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同