离散数学知识点.docx

24 / 24
说明：
定义：红色表示。
定理性质：橙色表示。
公式：蓝色表示。
算法: 绿色表示
页码：灰色表示
数理逻辑：
命题公式：命题， 联结词(Ø，Ù，Ú，®，«)，合式公式，子公式
公式的真值：赋任意赋值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)
假言易位 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的文字，其中前者称为正文字，后者称为负文字。【】
析取范式：形如A1 Ú A2 Ú …Ú An (n³1) 的公式称为析取范式，其中Ai(i=1,…,n)是由文字组成的合取范式。
合取范式：形为A1Ù A2 Ù …ÙAn (n³ 1) 的公式称为合取范式，其中A1,…,An都是由文字组成的析取式。【】
极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。
极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。【】
主析取范式：给定的命题公式的主析取范式是一个与之等价的公式，后者由极小项的析取组成。
主合取范式：给定的命题公式的主合取范式是一个与之等价的公式，后者由极大项的合取组成。
4 / 26
【】
公式的真值表中真值为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是一个重言式时，称P重言蕴含Q，记为PÞQ。
有效结论：设A、C是两个命题公式，若A Þ C，称C是A的有效结论。【】
推理定律——重言蕴涵式
1. A Þ (AÚB) 附加律
2. (AÙB) Þ A 化简律
3. (A®B)ÙA Þ B 假言推理
4. (A®B)ÙØB Þ ØA 拒取式
5. (AÚB)ÙØB Þ A 析取三段论
6. (A®B)Ù(B®C) Þ (A®C) 假言三段论
7. (A«B)Ù(B«C) Þ (A«C) 等价三段论
8. (A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 构造性二难
(A®B)Ù(ØA®B) Þ B 构造性二难(特殊形式)
9. (A®B)Ù(C®D)Ù( ØBÚØD) Þ (ØAÚØC) 破坏性二难
形式系统: 一个形式系统 I 由下面四个部分组成：
(1) 非空的字母表，记作 A(I).
(2) A(I) 中符号构造的合式公式集，记作 E(I).
(3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I