离散数学知识点.doc

离散数学知识点.doc说 明 ：
定义 ：红色表示 。
定理性质： 橙色表示。
公式： 蓝色表示 。
算法 : 绿色表示
页码 ：灰色 表示
数理逻辑：
1. 命题公式： 命题， 联络词 ( ， ， ， ， )“p 当且仅当 q”称为p 等价 q ，记以 p
q 。p
q 是
真的当且仅当
p ， q 或许都是真的，或许都是假的。
【定义 】
合式公式 :
命题常元和变元符号是合式公式；
若 A 是合式公式，则 ( A) 是合式公式，称为 A 的否认式；
(3) 若 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
幂等律
A A
A, A
A A
互换律
A B
BA,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
, 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
A2
A n (n
1)
的公式称为析取范式，其中
Ai(i=1,,n) 是由文字组成的合
取范式。
合取范式： 形为 A
1
A
2
A
(n
1)
的公式称为合取范式，其中
A
1
, ,A都是由文字组成的析
n
n
取式。【定义
】
极小项： 文字的合取式称为极小项，其中公式中每个命题符号的文字