离散数学知识点.doc

-
. z.
. .。
否认词符号Ø：设p是一个命题，Øp称为p的否认式。Øp是真的当且仅当p是假的。p是真的当且仅当Øp是假的。【】
合取词符号Ù：设p，q是两个命题，命题“p并且q〞称为p，q的合取，记以pÙq，读作p且q。pÙq是真的当且仅当p和q都是真的。【】
析取词符号Ú：设p，q是两个命题，命题“p或者q〞称为p，q的析取，记以pÚq，读作p或q。pÚq是真的当且仅当p，q中至少有一个是真的。【】
蕴含词符号®：设p，q是两个命题，命题“如果p，则q〞称为p蕴含q，记以p®q。p®q是假的当且仅当p是真的而q是假的。【】
等价词符号«：设p，q是两个命题，命题“p当且仅当q〞称为p等价q，记以p«q。p®q是真的当且仅当p，q或者都是真的，或者都是假的。【】
合式公式:
命题常元和变元符号是合式公式；
假设A是合式公式，则(ØA)是合式公式，称为A的否认式；
假设A，B是合式公式，则 (AÚB)， (AÙB)， (A®B)，(A«B)是合式公式；
-
. z.
. ..
z. .
所有合式公式都是有限次使用(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Û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ÚÛ, AÙ^Û^
^
同一律 AÚ^ÛA, AÙÛA
排中律 AÚØA Û
矛盾律 AÙØAÛ^
蕴涵等值式 A®BÛØAÚB
等价等值式 A«BÛ(A®B)Ù(B®A)
-
. z.
. ..
z. .
假言易位 A®BÛØB®ØA
等价否认等值式A«BÛØA«ØB
归谬论 (A®B)Ù(A®ØB) ÛØA
置换规则：设Ｘ是公式A的子公式, ＸÛ Y。将A中的Ｘ〔可以是全部或局部*〕用Y来置换，所得到的公式B，则 AÛB。
文字: 设AÎå〔命题变元集〕, 则A和Ø A都称为命题符号A的文字，其中前者称为正文字，后者称为负文字。【】
析取范式：形如A1 Ú A2Ú …Ú An(n³1) 的公式称为析取范式，其中Ai(i=1,…,n)是由文字组成的合取范式。
合取范式：形为A1Ù A2Ù …ÙAn(n³ 1) 的公式称为合取范式，其中A1,…,An都是由文字组成的析取式。【】
极小项：文字的合取式