离散数学知识点.doc

说 明 ：
定义 ：红色表示 。
定理性质： 橙色表示。
公式： 蓝色表示 。
算法 : 绿色表示
页码 ：灰色 表示
数理逻辑：
命题公式： 命题， 联结词 (有一个是真的。 【定义
】
蕴含词符号
：设 p ，q 是两个命题，命题
“如果p ，则 q”称为p 蕴含 q，记以 p q。p q 是假的当且仅当
p 是
真的而 q 是假的。【定义 】
等价词符号
：设 p， q 是两个命题，命题
“p 当且仅当 q”称为p 等价 q ，记以 p q。 p q 是真的当且仅当
p，
q 或者都是真的，或者都是假的。
【定义
】
合式公式 :
命题常元和变元符号是合式公式；
(2) 若 A 是合式公式，则 ( A) 是合式公式，称为 A 的否定式；
若 A， B 是合式公式，则 (A B) ， (A B) ， (A B) ， (A B)是合式公式；
所有合式公式都是有限次使用(1) ， (2) ， (3) 、 (4) 得到的符号串。
子公式 : 如果Ｘ是合式公式 A 的一部分， 且Ｘ本身也是一个合式公式， 则称Ｘ为公式 A 的子公式。【定义 】
赋值（ 指派，解释 ）： 设 是命题变元集合，则称函数 v： {1 ， 0} 是一个真值赋值。 【定义 】
真值表： 公式 A 在其所有可能的赋值下所取真值的表，称为 A 的真值表。【定义 】
重言式（ 永真式 ） :任意赋值 v， v A
矛盾式（ 永假式 ） :任意赋值 v， 有 v A【定义 】
等值式： 若等价式
A B
是重言式，则称
A
与
B
等值，记作
。【定义 】
A B
基本等值式
双重否定律
A A
幂等律
AAA,A
A A
交换律
ABBA,A BBA
结合律
(A B)
CA(B
C), (A
B) CA(B C)
分配律
A(B C) (A B) (A
C),
A(BC)(AB)(A C)
德摩根律
(A
B)
A
B
,(AB)
A
B
吸收律
A(A B) A,A
(A
B)
A
零律
A
, A
同一律
A
A, A
A
排中律
A
A
矛盾律
A
A
蕴涵等值式
A
B
A B
等价等值式
A
B (A
B)
(B
A)
假言易位
A
B
B
A
等价否定等值式
A B
A
B
归谬论
(A
B) (A
B)
A
置换规则：
设Ｘ是公式
A 的子公式 ,
Ｘ Y 。将 A 中的Ｘ（可以是全部或部分
X）用 Y 来置换，所得到的公式
B，则 A B。
文字: 设A
（命题变元集） ,
则 A 和
A 都称为命题符号
A 的文字， 其中前者称为正文字， 后者称为负文字。
【定义 】
析取范式： 形如 A 1
A 2
A n (n 1)
的公式称为析取范式，其中
Ai (i=1,
,n) 是由文字组成的合取范式。
合取范式： 形为 A 1
A 2
An (n
1)
的公式称为合取范式，其中
A1 , ,An 都是由文字组成的析取式。 【定
义 】