离散数学知识点.doc

-
. z.
. . . 的而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)是合式公式；
所有合式公式都是有限次使用(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
-
. z.
. . . .
. 资料. .. .
排中律 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中的Ｘ（可以是全部或部分*）用Y来置换，所得到的公式B，则 AÛB。
文字: 设AÎå（命题变元集）, 则A和Ø A都称为命题符号A的文字，其中前者称为正文字，后者称为负文字。【】
析取*式：形如A1 Ú A2Ú …Ú An(n³1) 的公式称为析取*式，其中Ai(i=1,…,n)是由文字组成的合取*式。
合取*式：形为A1Ù A2Ù …ÙAn(n³ 1) 的公式称为合取*式，其中A1,…,An都是由文字组成的析取式。【】
极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。
极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。【】
主析取*式：给定的命题公式的主析取*式是一个与之等价的公式，后者由极小项的析取组成。
主合取*式：给定的命题公式的主合取*式是一个与之等价的公式，后者由极大项的合取组成。
【】
公式的真值表中真值为F的指派所对应的极大项的合取，即为此公式的主合取*式。
真值函数：称F:{0,1}n® {0,1} 为n元真值函数.【】
联结词的完备集：设C是联结词的集合，若对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C中的联结词，则称C是联结词的完备集。【】
{Ø，Ù，Ú，®，«}，{Ø，Ù，Ú } , {Ø，Ù}， {Ø，Ú}，{^，®}是联结词的完备集。【】
c
异或PÅQ：ÛØ (P « Q)
条件否定P®Q：ÛØ (P ® Q)
与非P­Q：ÛØ (P Ù Q)
或非P¯Q：ÛØ (P Ú Q)【】
{­},{↓}都是联结词的完备集【】
重言蕴含式：当且仅当P®Q是一个重言式时，